Diferencia entre un analizador LL y Recursive Descent?

Question

Recientemente he intentado enseñarme a mí mismo cómo funcionan los analizadores sintácticos (para gramáticas libres de lenguajes y contextos), y la mayor parte parece tener sentido, excepto por una cosa. Estoy centrando mi atención en particular en LL (k) gramáticas, cuyos dos algoritmos principales parecen ser el LL parser (usando la tabla de pila/parseo) y el Recursive Descent parser (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).

Así que 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?

Answer 1

LL es generalmente una técnica de análisis más eficiente que el descenso recursivo. De hecho, un analizador sintáctico de descenso recursivo 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 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, unlimited lookahead), 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 Parser Expression Grammar(s). Específicamente, el operador disyuntivo (a | b) no es conmutativo, lo que significa que a | b no es igual 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 btuviera con la entrada. Esto permite que las ambigüedades clásicas de "coincidencia más larga" como el problema else se manejen simplemente ordenando las disyunciones correctamente.

Con todo lo dicho, es posible para implementar un analizador LL (k) mediante 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 colgando else ya no se pueden resolver con tanta facilidad.

En cuanto a por qué se elegiría LL en lugar de descenso recursivo, 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 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 parser combinators, que son una forma funcional de componer analizadores sintácticos de descendencia recursiva.