¿Cómo encontrar todas las posibles coincidencias de expresiones regulares en python?

Estoy tratando de encontrar todos los posibles pares de palabras / tags u otras combinaciones anidadas con python y sus expresiones regulares.

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)))'] 

buscando:

 ['(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)'] 

Creo que la fórmula de expresiones regulares podría encontrar también los pares de palabra / etiqueta entre paréntesis nesteds, pero no los devuelve. ¿Cómo debería hacer esto?

en realidad no es posible hacerlo usando expresiones regulares, porque las expresiones regulares expresan un lenguaje definido por una gramática regular que puede resolverse mediante un autómata determinista no finito, donde la coincidencia se representa por estados; luego, para hacer coincidir el paréntesis nested, deberías poder hacer coincidir un número infinito de paréntesis y luego tener un autómata con un número infinito de estados.

Para poder hacer frente a eso, usamos lo que se llama un autómata push-down, que se utiliza para definir la gramática libre de contexto.

Jerarquía de chomsky

Entonces, si su expresión regular no coincide con el paréntesis nested, es porque está expresando el siguiente autómata y no coincide con nada en su entrada:

Visualización de expresiones regulares

Juega con ello

Como referencia, eche un vistazo a los cursos del MIT sobre el tema:

Así que una de las maneras de analizar su cadena de manera eficiente, es construir una gramática para paréntesis nesteds ( pip install pyparsing primero):

 >>> 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: existen algunos motores de expresiones regulares que implementan el emparejamiento de paréntesis nesteds utilizando el push down. El motor predeterminado de python no es uno de ellos, pero existe un motor alternativo, llamado regex ( pip install regex ) que puede hacer una coincidencia recursiva (lo que hace que el nuevo motor esté libre de contexto), vea este fragmento de código :

 >>> import regex >>> res = regex.search(r'(?\((?:[^()]++|(?&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)))'] 

Las expresiones regulares utilizadas en los idiomas modernos NO representan los idiomas regulares. zmo tiene razón al decir que los lenguajes regulares en Language Theroy están representados por autómatas de estado finito, pero las expresiones regulares que usan cualquier tipo de backtrack como aquellas con grupos de captura, miradas y etc. que se usan en lenguajes modernos NO PUEDEN ser representados por las FSA conocidas en Language Teoría. ¿Cómo puede representar un patrón como (\ w +) \ 1 con un DFA o incluso un NFA?

La expresión regular que está buscando puede ser algo como esto (solo coincide con dos niveles):

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

He probado esto en http://regexhero.net/tester/

Los partidos están en los grupos capturados:

1: (NP (NNP Hoi) (NN Hallo) (NN Hey) (NNP (NN Ciao) (NN Adios))

1: (NNP Hoi)

1: (NN Hallo)

1: (NN Hey)

1: (NNP (NN Ciao) (NN Adios))

1: (NN Ciao)

1: (NN Adios)