parsing - tipos - parser
¿Qué ventajas tienen los analizadores de LL sobre los analizadores de LR? (6)
¿Qué ventajas tienen los analizadores de LL sobre los analizadores de LR para garantizar su popularidad relativa en las herramientas del generador de analizadores de hoy ?
Según Wikipedia , el análisis de LR parece tener ventajas sobre LL:
El análisis de LR puede manejar una gama más amplia de idiomas que el análisis de LL, y también es mejor en el informe de errores, es decir, detecta errores sintácticos cuando la entrada no se ajusta a la gramática lo antes posible. Esto contrasta con un LL (k) (o peor, un analizador LL (*)) que puede diferir la detección de errores a una rama diferente de la gramática debido al retroceso, a menudo haciendo que los errores sean más difíciles de localizar a través de disyunciones con prefijos comunes largos. .
Nota: Esto no es tarea. Me sorprendió cuando descubrí que Antlr es un generador de analizadores LL (¡a pesar de tener "LR" en su nombre!).
Desde mi experiencia personal (utilicé ambos para diversas situaciones), la diferencia más práctica es que, con un LL (k), puedes definir la gramática de una manera más fácil (ya que es de arriba hacia abajo) sin preocuparte por muchas reducciones posibles. reducir o reducir-reducir los conflictos que a menudo ocurren con los analizadores LR. Lo único que tiene que importar es la recursión a la izquierda, que debe transformarse en la correcta.
Otra cosa es que el enfoque de arriba hacia abajo generalmente implica una mayor complejidad (con respecto al espacio o al tiempo), ya que tiene que almacenar todo el árbol durante el análisis y puede crecer mucho hasta que se resuelvan las ambigüedades.
GLR es genial si quieres un árbol / bosque de análisis y no te molestan las cajas negras. Te permite escribir cualquier CFG que desees a cambio de buscar ambigüedades en el tiempo de análisis mediante pruebas exhaustivas, en lugar de resolver los conflictos de LR / LALR de forma estática. Algunos dicen que es una buena compensación. La herramienta DMS de Ira Baxter o Elkhound, que tiene una gramática C ++ gratuita, son útiles para esta clase de problemas. ANTLR es útil para una gran clase de aplicaciones de lenguaje, pero utiliza un enfoque de arriba hacia abajo, generando analizadores de descenso recursivos llamados LL (*) que permiten predicados semánticos. Declararé aquí sin pruebas que los predicados le permiten analizar lenguajes sensibles al contexto más allá de los CFG. Los programadores les gusta insertar acciones en gramáticas, como un buen manejo de errores, y les gusta depurar en un solo paso. LL es bueno en los tres. LL es lo que hacemos a mano, así que es más fácil de entender. No creas que la tontería de Wikipedia es que LR es mejor para manejar errores . Dicho esto, si retrocede mucho con ANTLR, los errores son de hecho peores con LL (*) (los PEG tienen este problema).
Retrospección. GLR también especula (es decir, backtracks), al igual que PEG, ANTLR y cualquier otra estrategia no determinista. En cualquier estado LR no determinista, GLR "bifurca" a los sub-analizadores para probar cualquier camino viable. De todos modos, LL tiene un buen contexto para el manejo de errores. Donde LR sabe que está haciendo coincidir una expresión, LL sabe que es una expresión en una asignación o IF -condicional; LR sabe que podría estar en cualquiera de los dos, pero no está seguro, y esa incertidumbre es donde obtiene su poder.
GLR es O(n^3) peor caso. packrat / PEG es O(n) peor caso. Las ANTLR son O(n^2) debido a DFA de búsqueda cíclica pero O(n) en la práctica. No importa realmente GLR es lo suficientemente rápido.
ANTLR es otra herramienta para L ang R ecognition no anti-LR, pero me gusta también;)
Francamente, como muchos codificadores jóvenes en los 80, no entendía LALR y no me gustaban las cajas negras (ahora me gusta la belleza del motor GLR pero aún prefiero LL). Creé un compilador basado en LL (k) comercial y decidí construir una herramienta para generar lo que había construido a mano. ANTLR no es para todos y los casos extremos como C ++ pueden manejarse mejor con GLR, pero mucha gente encuentra que ANTLR se adapta a su zona de confort. Desde enero de 2008, se han producido 134,000 descargas del binario binario de ANTLR, dentro de ANTLRWorks, y el total de cremalleras de origen (según Google Analytics). Vea nuestro documento sobre LL (*) con muchos datos empíricos.
La única ventaja con la que me he familiarizado es que puedes codificar fácilmente analizadores de LL a mano. Los analizadores de LR son MUCHO más difíciles de codificar a mano (normalmente se usa un generador de analizador sintáctico).
La complejidad del peor caso de LL Parsings es O (n ^ 4), mientras que la peor complejidad de caso del análisis de LR es mejor, O (n ^ 3).
(Pero nadie escribiría O (n ^ 4) gramática.)
Si tiene que codificar a mano uno, el descenso recursivo (LL) es algo que puede hacer de forma realista; la gente no puede construir manualmente L (AL) R parsers prácticamente a mano.
Dado que los generadores de analizadores modernos manejarán toda la construcción del analizador para ti, y ese espacio no es un gran problema, prefiero los analizadores de LR porque no tienes que luchar con las gramáticas tanto para que sean válidas para tu generador de analizador en particular. (no hay tonterías de "eliminar todas las recursiones a la izquierda").
De hecho, prefiero los analizadores GLR , que prácticamente analizarán cualquier cosa con una gramática libre de contexto. Sin preocupaciones de recursividad a la izquierda. No cambiar / reducir las preocupaciones de conflicto. Sin límites de anticipación.
Si desea ver el rango de idiomas que puede manejar un motor de análisis GLR (incluido el famoso lenguaje difícil de analizar-LL / LALR, C ++), puede consultar here .
Una razón que me viene a la mente es que es mucho más fácil hacer un lenguaje que necesita un retroceso arbitrario ( tos C ++) en un paradigma LL.