¿Cuál es la diferencia entre los analizadores sintácticos LR, SLR y LALR?

¿Cuál es la diferencia real entre los analizadores LR, SLR y LALR? Sé que SLR y LALR son tipos de analizadores LR, pero ¿cuál es la diferencia real en lo que respecta a sus tablas de análisis?

¿Y cómo mostrar si una gramática es LR, SLR o LALR? Para una gramática LL, solo tenemos que mostrar que ninguna celda de la tabla de análisis no debe contener múltiples reglas de producción. ¿Alguna regla similar para LALR, SLR y LR?

Por ejemplo, ¿cómo podemos demostrar que la gramática

S --> Aa | bAc | dc | bda
A --> d

es LALR (1) pero no SLR (1)?

EDITAR (ybungalobill) : No obtuve una respuesta satisfactoria sobre cuál es la diferencia entre LALR y LR. Entonces, las tablas de LALR son más pequeñas pero solo pueden reconocer un subconjunto de gramáticas LR. ¿Alguien puede dar más detalles sobre la diferencia entre LALR y LR, por favor? LALR (1) y LR (1) serán suficientes para una respuesta. ¡Ambos usan 1 token de anticipación y ambos están controlados por tablas! ¿En qué se diferencian?

Los analizadores sintácticos SLR, LALR y LR pueden implementarse utilizando exactamente la misma maquinaria impulsada por tablas.

Básicamente, el algoritmo de análisis recopila el siguiente token de entrada T y consulta el estado actual S (y las tablas de reducción, GOTO y de anticipación asociadas) para decidir qué hacer:

• SHIFT: si la tabla actual dice SHIFT en el token T, el par (S, T) se inserta en la pila de análisis, el estado cambia de acuerdo con lo que dice la tabla GOTO para el token actual (por ejemplo, GOTO (T) ), se obtiene otro token de entrada T 'y el proceso se repite
• REDUCIR: Cada estado tiene 0, 1 o muchas reducciones posibles que pueden ocurrir en el estado. Si el analizador es LR o LALR, el token se compara con conjuntos de anticipación para todas las reducciones válidas para el estado. Si el token coincide con un conjunto de búsqueda anticipada para una reducción para la regla gramatical G = R1 R2 .. Rn, se produce una reducción y un desplazamiento de la pila: se llama a la acción semántica para G, la pila se abre n (de Rn) veces, el par ( S, G) se inserta 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, por lo tanto, 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 esuna 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 examinar 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 SHIFT del estado. La reducción que se aplica se puede adjuntar específicamente al estado, por lo que la maquinaria de análisis de SLR no tiene que buscarla. En la práctica, los analizadores sintácticos L (AL) R manejan un conjunto de idiomas útilmente más grande y es tan poco trabajo extra de implementar que nadie implementa SLR excepto como un ejercicio académico.

La diferencia entre LALR y LR tiene que ver con el generador de tablas. Los generadores de analizadores sintácticos LR realizan un seguimiento de todas las posibles reducciones de estados específicos y su conjunto de anticipación preciso; termina con estados en los que cada reducción está asociada con su conjunto de anticipación exacto de su contexto izquierdo. Esto tiende a construir conjuntos de estados bastante grandes. Los generadores de analizadores sintácticos LALR están dispuestos a combinar estados si las tablas GOTO y los conjuntos de cabezales de búsqueda para reducciones son compatibles y no entran en conflicto; esto produce un número considerablemente menor de estados, al precio de no poder distinguir ciertas secuencias de símbolos que LR puede distinguir. Por lo tanto, los analizadores LR pueden analizar un conjunto de idiomas más grande que los analizadores LALR, pero tienen tablas de analizadores mucho más grandes. En la práctica, se pueden encontrar gramáticas LALR que están lo suficientemente cerca de los idiomas de destino como para que valga la pena optimizar el tamaño de la máquina de estado;

Entonces: los tres usan la misma maquinaria. SLR es "fácil" en el sentido de que puede ignorar una pequeña parte de la maquinaria, pero simplemente no vale la pena. LR analiza un conjunto más amplio de idiomas, pero las tablas de estado tienden a ser bastante grandes. Eso deja a LALR como la opción práctica.

Habiendo dicho todo esto, vale la pena saber que los analizadores GLR pueden analizar cualquier lenguaje sin contexto, utilizando maquinaria más complicada pero exactamente las mismas tablas (incluida la versión más pequeña utilizada por LALR). Esto significa que GLR es estrictamente más potente que LR, LALR y SLR; más o menos si puede escribir una gramática BNF estándar, GLR la analizará de acuerdo con ella. La diferencia en la maquinaria es que GLR está dispuesto a probar varios análisis cuando hay conflictos entre la tabla GOTO o los conjuntos de anticipación. (La forma en que GLR hace esto de manera eficiente es pura genialidad [no mía] pero no encajará en esta publicación de SO).

Eso para mí es un hecho enormemente útil. Construyo analizadores de programas y transformadores de código y los analizadores son necesarios pero "poco interesantes"; el trabajo interesante es lo que haces con el resultado analizado, por lo que la atención se centra en hacer el trabajo posterior al análisis. Usar GLR significa que puedo construir gramáticas funcionales con relativa facilidad, en comparación con piratear una gramática para entrar en la forma utilizable de LALR. Esto es muy importante cuando se trata de lidiar con idiomas no académicos como C ++ o Fortran, donde literalmente necesita miles de reglas para manejar bien todo el idioma y no quiere pasar su vida tratando de piratear las reglas gramaticales para cumplir con las limitaciones de LALR (o incluso LR).

Como una especie de ejemplo famoso, C ++ se considera extremadamente difícil de analizar ... por personas que realizan análisis LALR. C ++ es sencillo de analizar utilizando maquinaria GLR utilizando prácticamente las reglas proporcionadas en la parte posterior del manual de referencia de C ++. (Tengo precisamente un analizador de este tipo, y maneja no solo C ++ vainilla, sino también una variedad de dialectos de proveedores. Esto solo es posible en la práctica porque estamos usando un analizador GLR, en mi humilde opinión).

[EDITAR noviembre de 2011: hemos ampliado nuestro analizador para manejar todo C ++ 11. GLR lo hizo mucho más fácil de hacer. EDITAR agosto de 2014: ahora manejando todo C ++ 17. Nada se rompió ni empeoró, GLR sigue siendo el maullido del gato.]

Los analizadores LALR fusionan estados similares dentro de una gramática LR para producir tablas de estado del analizador que son exactamente del mismo tamaño que la gramática SLR equivalente, que generalmente son un orden de magnitud más pequeñas que las tablas de análisis LR puras. Sin embargo, para las gramáticas LR que son demasiado complejas para ser LALR, estos estados combinados dan como resultado conflictos de analizador o producen un analizador que no reconoce completamente la gramática LR original.

Por cierto, menciono algunas cosas sobre esto en mi algoritmo de tabla de análisis MLR (k) aquí .

Apéndice

La respuesta corta es que las tablas de análisis sintáctico LALR son más pequeñas, pero la maquinaria del analizador es la misma. Una gramática LALR dada producirá tablas de análisis mucho más grandes si se generan todos los estados LR, con muchos estados redundantes (casi idénticos).

Las tablas LALR son más pequeñas porque los estados similares (redundantes) se fusionan, lo que elimina la información de contexto / anticipación que codifican los estados separados. La ventaja es que obtiene tablas de análisis mucho más pequeñas para la misma gramática.

El inconveniente es que no todas las gramáticas LR se pueden codificar como tablas LALR porque las gramáticas más complejas tienen búsquedas anticipadas más complicadas, lo que da como resultado dos o más estados en lugar de un solo estado combinado.

La principal diferencia es que el algoritmo para producir tablas LR transporta más información entre las transiciones de un estado a otro, mientras que el algoritmo LALR no. Por lo tanto, el algoritmo LALR no puede decir si un estado combinado dado realmente debería dejarse como dos o más estados separados.

Otra respuesta más (YAA).

Los algoritmos de análisis sintáctico para SLR (1), LALR (1) y LR (1) son idénticos, como dijo Ira Baxter,
sin embargo, las tablas del analizador pueden ser diferentes debido al algoritmo de generación del analizador.

Un generador de analizador de SLR crea una máquina de estado LR (0) y calcula las previsiones a partir de la gramática (conjuntos FIRST y FOLLOW). Este es un enfoque simplificado y puede informar conflictos que realmente no existen en la máquina de estado LR (0).

Un generador de analizador sintáctico LALR crea una máquina de estado LR (0) y calcula las previsiones desde la máquina de estado LR (0) (a través de las transiciones de terminal). Este es un enfoque correcto, pero ocasionalmente informa de conflictos que no existirían en una máquina de estado LR (1).

Un generador de analizador sintáctico Canonical LR calcula una máquina de estado LR (1) y las búsquedas anticipadas ya forman parte de la máquina de estado LR (1). Estas tablas del analizador pueden ser muy grandes.

Un generador de analizador sintáctico LR mínimo calcula una máquina de estados LR (1), pero fusiona estados compatibles durante el proceso, y luego calcula las previsiones desde la máquina de estados LR (1) mínima. Estas tablas del analizador son del mismo tamaño o un poco más grandes que las tablas del analizador LALR, lo que proporciona la mejor solución.

LRSTAR 10.0 puede generar analizadores sintácticos LALR (1), LR (1), CLR (1) o LR (*) en C ++, lo que sea necesario para su gramática. Vea este diagrama que muestra la diferencia entre los analizadores LR.

[Divulgación completa: LRSTAR es mi producto]

Suponga que un analizador sin una búsqueda anticipada está felizmente analizando cadenas para su gramática.

Usando su ejemplo dado, se encuentra con una cadena dc, ¿qué hace? ¿Lo reduce a S, porque dces una cadena válida producida por esta gramática? ¿O quizás estábamos tratando de analizar bdcporque incluso esa es una cadena aceptable?

Como humanos, sabemos que la respuesta es simple, solo necesitamos recordar si acabamos de analizar bo no. Pero las computadoras son estúpidas :)

Dado que un analizador SLR (1) tenía el poder adicional sobre LR (0) para realizar una búsqueda anticipada, sabemos que cualquier cantidad de búsqueda anticipada no puede decirnos qué hacer en este caso; en su lugar, debemos mirar hacia atrás en nuestro pasado. Así llega el analizador LR canónico al rescate. Recuerda el contexto pasado.

La forma en que recuerda este contexto es que se disciplina, que siempre que se encuentre con un b, empezará a caminar por un camino hacia la lectura bdc, como una posibilidad. Entonces, cuando ve un d, sabe si ya está caminando por un sendero. Por lo tanto, un analizador CLR (1) puede hacer cosas que un analizador SLR (1) no puede hacer.

Pero ahora, dado que tuvimos que definir tantos caminos, ¡los estados de la máquina se vuelven muy grandes!

Así que fusionamos caminos con el mismo aspecto, pero como era de esperar, podría dar lugar a problemas de confusión. Sin embargo, estamos dispuestos a correr el riesgo a costa de reducir el tamaño.

Este es su analizador LALR (1).

Ahora, cómo hacerlo algorítmicamente.

Cuando dibuje los conjuntos de configuración para el idioma anterior, verá un conflicto de reducción de cambios en dos estados. Para eliminarlos, es posible que desee considerar una SLR (1), que toma decisiones en función de un seguimiento, pero observará que aún no podrá hacerlo. Por lo tanto, dibujaría los conjuntos de configuración nuevamente, pero esta vez con la restricción de que siempre que calcule el cierre, las producciones adicionales que se agregan deben tener un seguimiento estricto. Consulte cualquier libro de texto sobre cuáles deberían ser estos.

La diferencia básica entre las tablas del analizador generadas con SLR y LR es que las acciones de reducción se basan en el conjunto de seguimientos para las tablas SLR. Esto puede ser demasiado restrictivo y, en última instancia, provocar un conflicto de reducción de cambios.

Un analizador sintáctico LR, por otro lado, las bases reducen las decisiones solo en el conjunto de terminales que realmente pueden seguir al no terminal que se reduce. Este conjunto de terminales es a menudo un subconjunto adecuado del conjunto Sigue de un no terminal y, por lo tanto, tiene menos posibilidades de entrar en conflicto con las acciones de cambio.

Los analizadores LR son más potentes por este motivo. Sin embargo, las tablas de análisis de LR pueden ser extremadamente grandes.

Un analizador LALR comienza con la idea de construir una tabla de análisis LR, pero combina los estados generados de una manera que da como resultado un tamaño de tabla significativamente menor. La desventaja es que se introduciría una pequeña posibilidad de conflictos para algunas gramáticas que una tabla LR habría evitado de otro modo.

Los analizadores LALR son un poco menos potentes que los analizadores LR, pero aún más potentes que los analizadores SLR. YACC y otros generadores de analizadores sintácticos tienden a usar LALR por esta razón.

PD Para mayor brevedad, SLR, LALR y LR anteriores realmente significan SLR (1), LALR (1) y LR (1), por lo que se implica una búsqueda anticipada de token.

Los analizadores sintácticos SLR reconocen un subconjunto adecuado de gramáticas reconocibles por los analizadores sintácticos LALR (1), que a su vez reconocen un subconjunto adecuado de gramáticas reconocibles por los analizadores sintácticos LR (1).

Cada uno de estos se construye como una máquina de estado, y cada estado representa un conjunto de reglas de producción de la gramática (y la posición en cada uno) a medida que analiza la entrada.

El ejemplo de Dragon Book de una gramática LALR (1) que no es SLR es este:

S → L = R | R
L → * R | id
R → L

Este es uno de los estados de esta gramática:

S → L•= R
R → L•

El •indica la posición del analizador en cada uno de los posibles producciones. No sabe en cuál de las producciones se encuentra realmente hasta que llega al final e intenta reducir.

Aquí, el analizador puede cambiar =o reducir R → L.

Un analizador SLR (también conocido como LR (0)) determinaría si podría reducir verificando si el siguiente símbolo de entrada está en el siguiente conjunto de R(es decir, el conjunto de todos los terminales en la gramática que puede seguir R). Dado =que también está en este conjunto, el analizador SLR encuentra un conflicto de reducción de cambios.

Sin embargo, un analizador sintáctico LALR (1) usaría el conjunto de todos los terminales que pueden seguir esta producción particular de R, que es solo $(es decir, el final de la entrada). Por lo tanto, no hay conflicto.

Como han señalado los comentaristas anteriores, los analizadores LALR (1) tienen el mismo número de estados que los analizadores SLR. Se utiliza un algoritmo de propagación de anticipación para agregar anticipaciones a las producciones de estado de SLR de los estados de LR (1) correspondientes. El analizador sintáctico LALR (1) resultante puede introducir conflictos de reducción-reducción que no están presentes en el analizador LR (1), pero no puede introducir conflictos de reducción-desplazamiento.

En su ejemplo , el siguiente estado de LALR (1) provoca un conflicto de reducción de cambios en una implementación de SLR:

S → b d•a / $
A → d• / c

El símbolo después /es el siguiente conjunto para cada producción en el analizador LALR (1). En SLR, follow ( A) incluye a, que también podría cambiarse.

Además de las respuestas anteriores, este diagrama demuestra cómo se relacionan los diferentes analizadores:

Una respuesta simple es que todas las gramáticas LR (1) son gramáticas LALR (1). En comparación con LALR (1), LR (1) tiene más estados en la máquina de estados finitos asociada (más del doble de estados). Y esa es la razón principal por la que las gramáticas LALR (1) requieren más código para detectar errores de sintaxis que las gramáticas LR (1). Y una cosa más importante que debe saber con respecto a estas dos gramáticas es que en las gramáticas LR (1) es posible que tengamos menos conflictos de reducción / reducción. Pero en LALR (1) hay más posibilidad de reducir / reducir conflictos.