¿Por qué los analizadores en línea parecen detenerse en las expresiones regulares?

Question

Por mucho tiempo me he preguntado por qué no parece haber analizadores, por ejemplo, BNF , que se comportan como expresiones regulares en varias bibliotecas.

Claro, hay cosas como ANTLR , Yacc y muchos otros que generan código que, a su vez, pueden analizar un CFG , pero no parece haber una biblioteca que pueda hacerlo sin el paso intermedio.

Estoy interesado en escribir un Packrat parser , para arrancar todos los nidos -parenthesis-rarezas asociadas con expresiones regulares (y, tal vez más, por el deporte de la misma), pero de alguna manera tengo la sensación de que simplemente estoy entrando en otra clase de pantanos, como un problema de detención.

¿Existe una limitación técnica / teórica para estos analizadores o simplemente me estoy perdiendo algo?

Answer 1

Creo que es más una cosa cultural. El uso de gramáticas libres de contexto se limita principalmente a los compiladores, que generalmente tienen un código asociado con cada regla de producción. En algunos idiomas, es más fácil generar código que simular devoluciones de llamada. En otros, verá bibliotecas de analizador: combinadores de analizador en Haskell, por ejemplo. Por otro lado, las expresiones regulares se utilizan ampliamente en herramientas como grep, donde es un inconveniente ejecutar el compilador de C cada vez que el usuario da una nueva expresión regular.

Answer 2

Boost.Spirit se parece a lo que estás buscando.

Si desea crear el suyo propio, he usado BNFC para mi último proyecto de compilación y proporciona la gramática utilizada en su propia implementación . Este podría ser un buen punto de partida ...

Answer 3

No hay una limitación técnica / teórica al acecho en las sombras. No puedo decir por qué no son más populares, pero conozco al menos una biblioteca que proporciona este tipo de " en línea " análisis que buscas.

SimpleParse es una biblioteca de Python que le permite simplemente pegar su vellosa gramática EBNF en su programa y usarla Para analizar las cosas de inmediato, no hay pasos intermedios. Lo he usado para varios proyectos en los que quería un lenguaje de entrada personalizado pero realmente no quería comprometerme con ningún proceso de construcción formal.

Aquí hay un pequeño ejemplo de la parte superior de mi cabeza:

decl = r"""
    root := expr
    expr := term, ("|", term)*
    term := factor+
    factor := ("(" expr ")") / [a-z]
"""
parser = Parser(decl) 
success, trees, next = parser.parse("(a(b|def)|c)def")

Las bibliotecas del combinador de analizadores para Haskell y Scala también le permiten expresar la gramática de su analizador en el mismo fragmento de código que lo utiliza. Sin embargo, no puede, digamos, dejar que el usuario escriba una gramática en tiempo de ejecución (lo que podría ser de interés únicamente para las personas que crean software para ayudar a las personas a entender las gramáticas de todos modos).

Answer 4

Pyparsing ( http://pyparsing.wikispaces.com ) tiene soporte incorporado para el análisis de packrat y es Python puro, así que puedes ver la implementación real.

Answer 5

¿Porque las gramáticas libres de contexto son lo suficientemente confusas como lo son sin una sintaxis crípticamente densa e incomprensible para hacerlas aún más confusas?

Es difícil saber lo que estás preguntando. ¿Estás tratando de crear algo parecido a una expresión regular, pero para gramáticas libres de contexto? Me gusta, usar $ var = ~ / expr = expr + expr / (en Perl) y tener que coincidan con " 1 + 1 " o " 1 + 1 + 1 " o " 1 + 1 + 1 + 1 + 1 + ... " ? Creo que una de las limitaciones de esto será la sintaxis: tener más de unas tres reglas hará que tu " expresión gramatical " incluso más ilegible que cualquier expresión regular moderna.

Answer 6

Los efectos secundarios son lo único que veo que te atrapará. La mayoría de los generadores de analizadores incluyen código incrustado para el procesamiento y necesitarías una evaluación para que funcione.

Una forma de evitarlo sería nombrar acciones y luego hacer una " acción " función que toma el nombre de la acción a realizar y los argumentos para hacerlo con.

Answer 7

Teóricamente, puedes hacerlo con Boost Spirit en C ++, pero está hecho principalmente para gramáticas estáticas. Creo que la razón por la que esto no es común es que los CFG no se usan tan comúnmente como las expresiones regulares. Nunca he tenido que usar una gramática excepto para la construcción de compiladores, pero he usado expresiones regulares muchas veces. Los CFG son generalmente mucho más complejos que las expresiones regulares, por lo que tiene sentido generar código estáticamente con una herramienta como YACC o ANTLR.

Answer 8

tcllib tiene algo por el estilo, si puedes aguantar Gramáticas de expresión Parse y también TCL. Si Perl es lo tuyo, CPAN tiene Parse :: Earley . Aquí es una variación de Perl pura que parece prometedora. PLY parece ser una solución plausible para Python