Descenso recursivo versus analizadores generados - Eficiencia

Question

¿Cómo se comparan los analizadores de descenso recursivos escritos a mano (que son inevitablemente LL (k)) con los analizadores LALR generados en términos de rendimiento?

Sé que los analizadores LALR son capaces de manejar muchas más gramáticas que LL (k); sin embargo, es mi intención escribir mi analizador a mano, y el descenso recursivo parece ser la opción más adecuada. ¿Es posible escribir cualquier otro tipo a mano (razonablemente legible) por interés?

N.B. Estoy usando un lenguaje funcional con la optimización de la cola de llamadas (F #), por lo que la recursión [bien adaptada] no será tan problemática como en otros idiomas.

Answer 1

Creo que mucho depende del idioma que está tratando de analizar. Otra parte del rendimiento que a veces se olvida es la parte de análisis léxico (escaneo): es importante para el rendimiento ya que trata con caracteres en lugar de símbolos. El descenso recursivo es una buena primera iteración al escribir un analizador, y hace que seguir la lógica del lenguaje analizado sea bastante natural. Creo que si el lenguaje analizado se ajusta (no hay recursividad a la izquierda) debe comenzar con un descenso recursivo. Elegir LALR para el rendimiento en esta etapa parece ser una optimización prematura. Puede escribir un chart parser a mano, pero dudo que esto sea lo que quiere decir. Escribir un analizador LALR a mano es posible pero tedioso.

Answer 2

Decidir entre LALR y LL para rendimiento razones en este punto suena como una optimización prematura. El tiempo de análisis raramente es el cuello de botella en un compilador. Si yo fuera tú, elegiría si te sientes más cómodo definiendo tu gramática de abajo hacia arriba o de arriba hacia abajo.

Personalmente, encuentro que las gramáticas LALR son fáciles de usar, y la integración fsyacc de F # (que es cómo aprendí el análisis) hace que sea muy fácil integrar yacc en su proyecto.