Diferencia entre LL y Recursiva Descenso analizador?

LL es generalmente una técnica de análisis más eficiente que el descenso recursivo. De hecho, un analizador de descenso recursivo ingenuo será O(k^n) (donde n es el tamaño de entrada) en el peor de los casos. Algunas técnicas como la memoización (que produce un analizador Packrat) pueden mejorar esto, así como extender la clase de gramáticas aceptadas por el analizador, pero siempre hay un equilibrio de espacio. TODOS los analizadores son (que yo sepa) siempre tiempo lineal.

En la otra cara, tienes razón en tu intuición de que los analizadores de descenso recursivo pueden manejar una clase de gramáticas mayor que LL. Recursive-descent 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 PEGs, o Gramática(es) de Expresiones Parser. Específicamente, el operador disyuntivo (a | b) no es conmutativo, lo que significa que a | b no es igual b | a. Un analizador de descenso recursivo probará cada alternativa en orden. Así que si a coincide con la entrada, tendrá éxito incluso si b habría coincidido con la entrada. Esto permite que las ambigüedades clásicas de "coincidencia más larga" como el problema de colgando else se manejen simplemente ordenando las disyunciones correctamente.

Con todo eso dicho, es posible implementar un analizador de LL(k) usando recursive-descent para que se ejecute en tiempo lineal. Esto se hace esencialmente mediante la inserción de la predecir conjuntos para que cada rutina de análisis determine la producción apropiada para una entrada dada en tiempo constante. Desafortunadamente, tal técnica elimina una clase entera de gramáticas de ser manejada. Una vez que nos metemos en el análisis predictivo, problemas como colgando else ya no son solucionables con tanta facilidad.

En cuanto a por qué se elegiría LL sobre el descenso recursivo, es principalmente una cuestión de eficiencia y mantenibilidad. Los analizadores de descenso recursivo son notablemente más fáciles de implementar, pero generalmente son más difíciles de mantener ya 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 descenso recursivo codificado directamente o LL(k) basado en tablas.

Como cuestión de interés, también vale la pena mirar recursive-ascent, que es un algoritmo de análisis codificado directamente a la manera de recursivo-descendiente, pero capaz de manejar cualquier gramática LALR. También me gustaría profundizar en combinadores de analizadores, que son una forma funcional de componer analizadores de descenso recursivo juntos.