Los analizadores SLR, LALR y LR se pueden implementar utilizando exactamente la misma maquinaria basada en tablas.
Fundamentalmente, el algoritmo de análisis recoge la siguiente entrada testigo T, y consulta el estado actual S (y asociado de búsqueda hacia delante, GOTO, y las tablas de reducción) para decidir qué hacer:
- SHIFT: Si la corriente la tabla dice que SHIFT en el token T, el par (S, T) se inserta en la pila de análisis, el estado cambia según lo que dice la tabla GOTO para el token actual (por ejemplo, GOTO (T)), otro token de entrada T 'es captado, y el proceso se repite
- REDUCIR: cada estado tiene 0, 1 o muchas reducciones posibles que puedan ocurrir en el estado. Si el analizador es LR o LALR, el token se compara con los conjuntos de anticipación para todas las reducciones válidas para el estado. Si el token coincide con un conjunto de anticipación para una reducción para la regla de gramática G = R1 R2 .. Rn, se produce una reducción de pila y un desplazamiento: se llama a la acción semántica para G, la pila aparece n (a partir de Rn) veces, el par (S, G) se coloca en la pila, el nuevo estado S 'se establece en GOTO (G), y el ciclo se repite con el mismo token T. Si el analizador es un analizador SLR, hay como máximo una regla de reducción para el estado y así la acción de reducción se puede hacer a ciegas sin buscar para ver qué reducción se aplica. Es útil para un analizador SLR saber si hay es una reducción o no; esto es fácil de decir si cada estado registra explícitamente el número de reducciones asociadas con él, y ese recuento es necesario para las versiones L (AL) R en la práctica de todos modos.
- ERROR: Si no es posible SHIFT ni REDUCE, se declara un error de sintaxis.
Entonces, si todos usan la misma maquinaria, ¿cuál es el punto?
El valor pretendido en SLR es su simplicidad en la implementación; no tiene que escanear las posibles reducciones comprobando los conjuntos de anticipación porque hay como máximo uno, y esta es la única acción viable si no hay salidas MAYO del estado. La reducción aplicable se puede unir específicamente al estado, por lo que la maquinaria de análisis SLR no tiene que buscarla. En la práctica, los analizadores L (AL) R manejan un conjunto útilmente más grande de lenguajes, y es tan poco el trabajo extra para implementar que nadie implementa SLR excepto como un ejercicio académico.
La diferencia entre LALR y LR tiene que ver con la tabla generador. Los generadores de analizadores de LR realizan un seguimiento de todas las posibles reducciones de estados específicos y su conjunto preciso de anticipación; terminas con estados en los que cada reducción está asociada con su conjunto exacto de anticipación desde su contexto izquierdo. Esto tiende a construir conjuntos bastante grandes de estados. Los generadores de analizadores LALR están dispuestos a combinar estados si las tablas GOTO y los conjuntos de cabeceras para las reducciones son compatibles y no entran en conflicto; esto produce un número considerablemente menor de estados, al precio de no ser capaz de distinguir ciertas secuencias de símbolos que LR puede distinguir. Entonces, los analizadores LR pueden analizar un conjunto de lenguajes más grande que los analizadores LALR, pero tienen tablas de analizador mucho más grandes. En la práctica, uno puede encontrar las gramáticas LALR que están lo suficientemente cerca de los lenguajes de destino que el tamaño de la máquina de estado vale la pena optimizar; los lugares donde el analizador LR sería mejor se manejan mediante una verificación ad hoc fuera del analizador sintáctico.
Entonces: Los tres usan la misma maquinaria. SLR es "fácil" en el sentido de que puedes ignorar un poco de la maquinaria pero no vale la pena. LR analiza un conjunto más amplio de lenguajes, pero las tablas de estado tienden a ser bastante grandes. Eso deja a LALR como la elección práctica.
Una vez dicho todo esto, vale la pena saber que GLR parsers puede analizar cualquier lenguaje libre de contexto, usando la maquinaria más complicada pero exactamente las mismas tablas (incluyendo la versión más pequeña utilizada por LALR). Esto significa que GLR es estrictamente más poderoso que LR, LALR y SLR; más o menos si puedes escribir una gramática BNF estándar, GLR analizará de acuerdo con ella. La diferencia en la maquinaria es que GLR está dispuesto a intentar múltiples análisis cuando hay conflictos entre la tabla GOTO y/o los conjuntos de búsqueda anticipada. (Cómo GLR hace esto de manera eficiente es puro genio [no mío], pero no encajará en esta publicación de SO).
Eso para mí es un hecho enormemente útil. Construyo analizadores de programa y los transformadores y analizadores de código son necesarios pero "poco interesantes"; el trabajo interesante es lo que haces con el resultado analizado y, por lo tanto, el foco está en hacer el trabajo posterior al análisis. Usar GLR significa que puedo construir gramáticas que funcionen con relativa facilidad, en comparación con piratear una gramática para obtener la forma utilizable de LALR. Esto es muy importante cuando se intenta tratar con lenguajes no académicos como C++ o Fortran, donde literalmente se necesitan miles de reglas para manejar bien todo el idioma, y no se quiere pasar la vida tratando de hackear las reglas de la gramática. cumplir con las limitaciones de LALR (o incluso LR).
Como una especie de ejemplo famoso, C++ se considera extremadamente difícil de analizar ... por los chicos que realizan el análisis LALR. C++ es fácil de analizar utilizando maquinaria GLR utilizando prácticamente las reglas proporcionadas en la parte posterior del manual de referencia de C++. (Tengo precisamente ese analizador, y maneja no solo C++ vainilla, sino también una variedad de dialectos de proveedores también. Esto solo es posible en la práctica porque estamos usando un analizador GLR, en mi humilde opinión).
[EDITAR Noviembre de 2011: ampliamos nuestro analizador para manejar todo C++ 11. GLR hizo eso mucho más fácil de hacer.]
Bueno, incluso estoy buscando una respuesta adecuada sobre esto, LALR (1) es solo una ligera modificación de LR (1), donde el tamaño de la tabla se reduce para que podamos minimizar el uso de la memoria ... – vikkyhacks