parsing - sintacticos - parser
¿Por qué analizadores sintácticos en lugar de solo analizadores configurables? (1)
El título lo resume. Es de suponer que cualquier cosa que se pueda hacer con los generadores de analizadores generadores de código fuente (que esencialmente codifican la gramática que se analizará en el programa) se puede hacer con un analizador configurable (que mantendría la gramática futura -parsed soft-codificado como una estructura de datos).
Supongo que el código codificado generado-analizador sintáctico tendrá una bonificación de rendimiento con un nivel menos de indirección, pero el desorden de tener que compilarlo y ejecutarlo (o ejecutarlo en los lenguajes dinámicos) y el clunkiness general del código la generación parece ser un gran inconveniente. ¿Hay algún otro beneficio de la generación de código de tus analizadores que no conozco?
La mayoría de los lugares que uso la generación de código es para solucionar las limitaciones en la capacidad de metaprogramación de los lenguajes (es decir, marcos web, AOP, interconexión con bases de datos), pero todo el asunto de la lex-parse parece bastante directo y estático, no necesita cualquiera de los dinamismos extra de metaprogramación que obtienes de la generación de código. ¿Lo que da? Es el beneficio de rendimiento tan bueno?
Si todo lo que quiere es un analizador que puede configurar al darle reglas gramaticales, eso se puede lograr. Un analizador de Earley analizará cualquier lenguaje libre de contexto dado solo un conjunto de reglas. El precio es un tiempo de ejecución significativo: O (N ^ 3), donde N es la longitud de la entrada. Si N es grande (como lo es para muchas entidades analizables), puede finalizar con un análisis muy lento.
Y esta es la razón de un generador de analizadores (PG). Si analiza muchos documentos, Slow Parsing es una mala noticia. Los compiladores son un programa donde la gente analiza muchos documentos, y ningún programador (o su administrador) quiere que el programador espere al compilador. Hay muchas otras cosas para analizar: consultas SQL, documentos JSON, ... todos los cuales tienen esta propiedad "Nadie está dispuesto a esperar".
Lo que hacen las PG es tomar muchas decisiones que tendrían que ocurrir en el tiempo de ejecución (por ejemplo, para un analizador de Earley), y calcular previamente esos resultados en el momento de generación del analizador. Entonces un LALR (1) PG (p. Ej., Bison) producirá analizadores sintácticos que se ejecutan en el tiempo O (N), y eso es obviamente mucho más rápido en circunstancias prácticas. (ANTLR hace algo similar para los analizadores LL (k)). Si desea un análisis sintáctico libre de contexto completo que generalmente sea lineal, puede usar una variante de análisis LR llamado análisis de GLR ; esto le compra la conveniencia de un analizador "configurable" (Earley), con un rendimiento típico mucho mejor.
Esta idea de precomputar de antemano se conoce generalmente como evaluación parcial , es decir, dada una función F (x, y), y el conocimiento de que x es siempre una cierta constante x_0, calcular una nueva función F ''(y) = F (x0 , y) en el que las decisiones y los cálculos que dependen exclusivamente del valor de x son precalculados. F ''generalmente se ejecuta mucho más rápido que F. En nuestro caso, F es algo así como el análisis genérico (por ejemplo, un analizador de Earley), x es un argumento de gramática con x0 como una gramática específica, y F'' es alguna infraestructura de analizador P y adicional código / tablas calculadas por la PG de manera que F ''= PG (x) + P.
En los comentarios a su pregunta, parece haber cierto interés en por qué uno no solo ejecuta el generador de analizadores en vigencia en el tiempo de ejecución. La respuesta simple es que paga una parte importante del costo general que desea eliminar en tiempo de ejecución.