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

Question

Me he estado preguntando durante mucho tiempo por qué no parece haber ningún analizador para, por ejemplo, BNF, que se comporte como expresiones regulares en varias bibliotecas.

Claro, hay cosas como ANTLR, Yacc y muchos otros que generar código el cual, a su vez, puede analizar una CFG, pero no parece ser una biblioteca que puede hacerlo sin el paso intermedio.

Estoy interesado en escribir un Packrat parser, para arrancar todos los paréntesis anidados-caprichos asociados con expresiones regulares (y, tal vez más aún, por el deporte de hacerlo), pero de alguna manera tengo la sensación de que soy simplemente caminando hacia otro problema de detención, como una clase de pantanos.

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

Answer 1

Creo que es algo más 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 analizadores: combinadores de analizadores en Haskell, por ejemplo. Por otro lado, las expresiones regulares tienen un amplio uso en herramientas como grep, donde no es conveniente ejecutar el compilador de C cada vez que el usuario da una nueva expresión regular.

Answer 2

Porque las gramáticas completas sin contexto son lo suficientemente confusas como lo son, sin alguna sintaxis crípticamente densa e incomprensible para hacerlas aún más confusas.

Es difícil saber lo que está preguntando. ¿Estás tratando de crear algo así como una expresión regular, pero para gramáticas libres de contexto? Me gusta, usando $var =~ /expr = expr + expr/ (en Perl) y teniendo esa coincidencia "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 tres reglas hará que tu "expresión gramatical" sea aún más ilegible que cualquier expresión regular de hoy en día.

Answer 3

El efecto secundario es lo único que veo que te atrapará. La mayoría de los generadores de analizadores incluyen código incrustado para el procesamiento y necesitaría una evaluación para que funcione.

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

Answer 4

En teoría, puede 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 porque los CFG no son tan comúnmente utilizados como los regex. Nunca tuve 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 los regex, por lo que tiene sentido generar código estáticamente con una herramienta como YACC o ANTLR.

Answer 5

tcllib tiene algo así, si puede soportar Parse Expression Grammars y también TCL. Si Perl es lo tuyo, CPAN tiene Parse::Earley. Here es una variación pura de Perl que parece prometedora. PLY parece ser una solución plausible para Python

Answer 6

Boost.Spirit parece lo que está buscando.

Si está buscando hacer uno propio, he usado BNFC para mi último proyecto de compilación y proporciona the grammar used in its own implementation. Este podría ser un buen punto de partida ...

Answer 7

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 sé de al menos una biblioteca que proporciona este tipo de análisis "en línea" que usted busca.

SimpleParse es una biblioteca de Python que le permite simplemente pegar su peluda gramática EBNF en su programa y usarla para analizar las cosas de inmediato, no en pasos inmediatos. 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 formal de compilación.

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

bibliotecas combinator

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") 

el analizador para Haskell y Scala también permiten su expresar su la gramática para su analizador en el mismo trozo de código que lo utiliza. Sin embargo, no se puede, por ejemplo, dejar que el usuario escriba una gramática en tiempo de ejecución (lo que solo podría interesar a las personas que crean software para ayudar a las personas a comprender las gramáticas de todos modos).

Answer 8

Pyparsing (http://pyparsing.wikispaces.com) tiene soporte incorporado para el análisis de paquetes y es puro Python, por lo que puede ver la implementación real.