¿El lenguaje de expresiones regulares necesita un autómata para analizarlo?

Quiero convertir una expresión regular ingresada por el usuario en un NFA para que luego pueda ejecutar el NFA en una cadena con fines coincidentes. ¿Cuál es la máquina mínima que se puede usar para analizar las expresiones regulares?

Supongo que debe ser un autómata push down porque la presencia de paréntesis significa la necesidad de contar y un DFA / NFA no puede realizar un conteo arbitrario. ¿Es correcta esta suposición? Por ejemplo, la expresión a (bc *) d requeriría un PDA para que la subexpresión entre paréntesis se maneje correctamente.

formal-languages parsers regular-expressions pushdown-automata Phil Wright
fuente

¿Qué quieres decir exactamente con "análisis"? ¿Te refieres a verificar si la entrada es realmente una expresión regular o tienes algo más complicado en mente, por ejemplo, una máquina que emite una descripción del NFA correspondiente? (si no está seguro de si la entrada es realmente una expresión regular y necesita verificarla, entonces debe poder verificar que los paréntesis sean correctos y eso normalmente significa usar una pila.)

Kaveh

Para una respuesta práctica, usted podría mirar en el Plan 9 Grep fuente de grep.y .

Bruce Ediger

Respuestas:

Estás en lo correcto. Es fácil mostrar que la sintaxis de las expresiones regulares no es regular utilizando técnicas estándar .

Una posibilidad es usar un homomorfismo (contra el cual está cerrado) para deshacerse de todos los símbolos excepto los paréntesis, lo que te deja con el lenguaje Dyck que es bien conocido por no ser regular. En caso de duda, use el lema de bombeo en . $\mathrm{REG}$ $(^p)^p$

Dicho esto, probablemente no desee codificar un PDA a mano. Considere usar un generador de analizador sintáctico como ANTLR o byacc . Si, por otro lado, desea investigar el análisis de idiomas mediante la programación de analizadores usted mismo, debe continuar con otros algoritmos de análisis básicos como CYK , Earley , descenso recursivo y LR .

Rafael
fuente

Gracias. escribir código para estas tareas crea una mejor comprensión y no pretende ser tan eficiente como los servicios públicos existentes, como lex yacc, bisontes, etc.

Phil Wright

@ PhilWright: Ya veo, ¡bien! Edité más punteros para este caso.

Raphael

Yo preferiría un analizador de descenso recursivo codificado a mano para este.

Dave Clarke

Si escribir un analizador a mano para esto, ya sea una opción de descenso recursivo (después de factorizar y masajear), el analizador LCC para C < sites.google.com/site/lccretargetablecompiler > tiene una opción interesante para manejar muchos operadores. Pero quizás lo más fácil para la construcción manual es el análisis de precedencia.

vonbrand

Le sugiero que lea la buena respuesta de Jukka a la pregunta " Emparejar expresiones regulares usando expresiones regulares " en teoría también. Un experto:

Por ejemplo, podemos modificar la notación estándar de la siguiente manera para obtener expresiones regulares "comprimidas" :

Se le permite eliminar cualquier prefijo que consista en una secuencia de ('s

Se le permite eliminar cualquier sufijo que consista en una secuencia de)

Es decir, ((a|b)*c)de(f|g)se puede expresar en la notación "comprimida" utilizando, por ejemplo, cualquiera de las siguientes formas: a|b)*c)de(f|go ((a|b)*c)de(f|go (a|b)*c)de(f|g).

[...]

La notación "comprimida" (de una expresión regular) es un lenguaje regular.

Esto es solo un enlace a una interesante "vista diferente" (según mi opinión) sobre el lenguaje de expresión regular; como se subraya en los comentarios a continuación, no es útil para construir un árbol de sintaxis. Si desea codificar manualmente su analizador, le sugeriré este sencillo artículo sobre el proyecto de código " Writing-own-regular-expression-parser ".

Vor
fuente

Jukka esencialmente elimina el requisito de que los paréntesis estén equilibrados. No conozco ninguna instancia en la que esto se haga realmente, pero vale la pena señalar que al cambiar la semántica, puede "simplificar" la sintaxis.

Raphael

Usted (y Jukka) no están analizando expresiones regulares, solo las reconocen. "Sí, esa es una expresión regular (comprimida)".

Gilles 'SO- deja de ser malvado'