parsing - sintácticos - principio de preanalisis
¿Diferencia entre un analizador LL y Recursive Descent? (1)
Recientemente he estado tratando de enseñarme a mí mismo cómo funcionan los analizadores sintácticos (para las gramáticas libres de contexto y los lenguajes), y la mayor parte parece tener sentido, excepto por una cosa. Estoy centrando mi atención, en particular, en las gramáticas LL (k) , para las cuales los dos algoritmos principales parecen ser el analizador LL (usando la tabla de pila / parseo) y el analizador de Descenso Recursivo (simplemente usando recursividad).
Por lo que puedo ver, el algoritmo de descenso recursivo funciona en todas las gramáticas LL (k) y posiblemente más, mientras que un analizador LL trabaja en todas las gramáticas LL (k). Sin embargo, un analizador de descenso recursivo es mucho más simple que un analizador de LL para implementarlo (al igual que un LL es más simple que un LR).
Entonces mi pregunta es, ¿cuáles son las ventajas / problemas que uno puede encontrar al usar cualquiera de los algoritmos? ¿Por qué alguna vez se puede elegir LL sobre el descenso recursivo, dado que funciona en el mismo conjunto de gramáticas y es más complicado de implementar?
LL es generalmente una técnica de análisis más eficiente que el descenso recursivo. De hecho, un analizador sintáctico de descendencia recursiva será en realidad O (k ^ n) (donde n es el tamaño de entrada) en el peor de los casos. Algunas técnicas, como la memoria (que produce un analizador de Packrat ) pueden mejorar esto y extender la clase de gramáticas aceptadas por el analizador, pero siempre hay una compensación de espacio. Los analizadores LL son (a mi entender) siempre el tiempo lineal.
Por otro lado, tiene razón en su intuición de que los analizadores de descenso recursivo pueden manejar una clase de gramáticas mayor que LL. El descenso recursivo puede manejar cualquier gramática que sea LL (*) (es decir, búsqueda anticipada ilimitada ), así como un pequeño conjunto de gramáticas ambiguas. Esto se debe a que el descenso recursivo es en realidad una implementación codificada directamente de PEG o gramática (s) de expresión del analizador . Específicamente, el operador disyuntivo ( a | b ) no es conmutativo, lo que significa que a | b a | b no es igual a b | a b | a . Un analizador de descenso recursivo probará cada alternativa en orden. De modo que si a coincide con la entrada, tendrá éxito incluso si b hubiera coincidido con la entrada. Esto permite que las ambigüedades clásicas de "coincidencia más larga", como el problema de los else , se manejen simplemente ordenando las disyunciones correctamente.
Con todo lo dicho, es posible implementar un analizador LL (k) usando recursivo-descenso para que se ejecute en tiempo lineal. Esto se hace esencialmente alineando los conjuntos de predicciones para que cada rutina de análisis determine la producción apropiada para una entrada dada en tiempo constante. Desafortunadamente, tal técnica elimina la manipulación de una clase completa de gramáticas. Una vez que entramos en el análisis predictivo, los problemas como el colgar en else ya no se pueden resolver con tanta facilidad.
En cuanto a por qué se elegiría LL en lugar de descendencia recursiva, se trata principalmente de una cuestión de eficiencia y facilidad de mantenimiento. Los analizadores de descenso recursivo son marcadamente más fáciles de implementar, pero por lo general son más difíciles de mantener dado que la gramática que representan no existe en ninguna forma declarativa. La mayoría de los casos de uso de analizadores no triviales emplean un generador de analizadores como ANTLR o Bison. Con tales herramientas, realmente no importa si el algoritmo es de descendencia recursiva codificada directamente o LL (k) controlada por tablas.
Como cuestión de interés, también vale la pena investigar el recursive-ascent , que es un algoritmo de análisis directamente codificado según la moda del descenso recursivo, pero capaz de manejar cualquier gramática LALR. También profundizaría en los combinadores de analizadores sintácticos , que son una forma funcional de componer analizadores sintácticos de descendencia recursiva.