Как найти все возможные регулярные выражения в python?

Question

Я пытаюсь найти все возможные пары слов/тегов или другие вложенные комбинации с python и его регулярными выражениями.

sent = '(NP (NNP Hoi) (NN Hallo) (NN Hey) (NNP (NN Ciao) (NN Adios)))' 

def checkBinary(sentence): 
    n = re.findall("\([A-Za-z-0-9\s\)\(]*\)", sentence) 
    print(n) 

checkBinary(sent) 

Output: 
['(NP (NNP Hoi) (NN Hallo) (NN Hey) (NNP (NN Ciao) (NN Adios)))'] 

ищет:

['(NP (NNP Hoi) (NN Hallo) (NN Hey) (NNP (NN Ciao) (NN Adios)))', 
'(NNP Hoi)', 
'(NN Hallo)', 
'(NN Hey)', 
'(NNP (NN Ciao) (NN Adios))', 
'(NN Ciao)', 
'(NN Adios)'] 

Я думаю, что формула регулярного выражения может найти вложенную скобку пару слов/тег как хорошо, но он не возвращает их. Как мне это сделать?

Answer 1

на самом деле это не представляется возможным сделать это с помощью регулярных выражений, поскольку регулярные выражения выражают язык, определенный регулярной грамматики, которая может быть решена при помощи, не конечный детерминированным автомата, где согласование представлены государствами; то для соответствия вложенным скобкам вам нужно будет иметь возможность сопоставить бесконечное число скобок и затем иметь автомат с бесконечным числом состояний.

Чтобы быть в состоянии справиться с этим, мы используем то, что называется пуш-вниз автомат, который используется для определения контекстно-свободной грамматики.

Так что, если ваш регулярное выражение не совпадает с вложенной скобкой, это потому, что это выражающее следующий автомат и ничего не найдено на вашем входе:

Play with it

As ссылку, пожалуйста, ознакомьтесь с курсами MIT по теме:

• http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec04.pdf
• http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-005-elements-of-software-construction-fall-2011/lecture-notes/MIT6_005F11_lec05.pdf
• http://www.saylor.org/site/wp-content/uploads/2012/01/CS304-2.1-MIT.pdf

Так один из способов эффективного разбора вашей строки, чтобы построить грамматику для вложенной скобки (pip install pyparsing первой):

>>> import pyparsing 
>>> strings = pyparsing.Word(pyparsing.alphanums) 
>>> parens = pyparsing.nestedExpr('(', ')', content=strings) 
>>> parens.parseString('(NP (NNP Hoi) (NN Hallo) (NN Hey) (NNP (NN Ciao) (NN Adios)))').asList() 
[['NP', ['NNP', 'Hoi'], ['NN', 'Hallo'], ['NN', 'Hey'], ['NNP', ['NN', 'Ciao'], ['NN', 'Adios']]]] 

NB: существует несколько механизмов регулярных выражений, которые реализуют вложенные скобки с использованием push do шп. Питон по умолчанию re двигателя не один из них, но существует альтернативный двигатель, названный regex (pip install regex), что может сделать рекурсивное согласование (что делает контекст повторного двигателя бесплатно), ср this code snippet:

>>> import regex 
>>> res = regex.search(r'(?<rec>\((?:[^()]++|(?&rec))*\))', '(NP (NNP Hoi) (NN Hallo) (NN Hey) (NNP (NN Ciao) (NN Adios)))') 
>>> res.captures('rec') 
['(NNP Hoi)', '(NN Hallo)', '(NN Hey)', '(NN Ciao)', '(NN Adios)', '(NNP (NN Ciao) (NN Adios))', '(NP (NNP Hoi) (NN Hallo) (NN Hey) (NNP (NN Ciao) (NN Adios)))'] 

Answer 2

регулярных выражения, используемый в современных языках НЕ представляют собой обычные языки. zmo прав, говоря, что регулярные языки в языке Theroy представлены автоматами с конечным состоянием, но регулярные выражения, которые используют любые виды обратного отслеживания, подобные тем, у кого есть группы захвата, поисковые системы и т. д., которые используются на современных языках, НЕ МОГУТ быть представлены FSA, известными на языке Теория. Как вы можете представить шаблон типа (\ w +) \ 1 с DFA или даже с NFA?

Регулярное выражение, которое вы ищете может быть что-то вроде этого (только соответствует двум уровням):

(?=(\((?:[^\)\(]*\([^\)]*\)|[^\)\(])*?\))) 

Я испытал это на http://regexhero.net/tester/

Спички в захваченных групп:

1: (НП (ННП Хой) (Н.Н. Алло) (Н.Н. Эй) (ННП (Н.Н. Чао) (Н.Н. Прощайте))

1: (ННП Хой)

1: (Н.Н. Алло)

1: (НН Эй)

1: (ННП (Н.Н. Чао) (Н.Н. Прощайте))

1: (Н.Н. Чао)

1: (NN Adios)