algorithm - tipos - lr 1
¿Cuál es la diferencia entre los analizadores LR, SLR y LALR? (7)
La diferencia básica entre las tablas del analizador generadas con SLR frente a LR es que las acciones de reducción se basan en los seguimientos establecidos para las tablas SLR. Esto puede ser demasiado restrictivo y, en última instancia, causar un conflicto de cambio-reducción.
Un analizador LR, por otro lado, reduce las decisiones solo en el conjunto de terminales que pueden seguir al no terminal siendo reducidos. Este conjunto de terminales a menudo es un subconjunto apropiado del conjunto Follows de un terminal no terminal y, por lo tanto, tiene menos posibilidades de entrar en conflicto con las acciones del cambio.
Los analizadores LR son más potentes por esta razón. Las tablas de análisis de LR pueden ser extremadamente grandes, sin embargo.
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 una pequeña posibilidad de conflictos sería introducida para algunas gramáticas que una tabla LR hubiera evitado de otra manera.
Los analizadores LALR son ligeramente menos potentes que los analizadores LR, pero aún más potentes que los analizadores SLR. YACC y otros generadores de analizadores sintácticos similares tienden a usar LALR por este motivo.
PD Por brevedad, SLR, LALR y LR significan realmente SLR (1), LALR (1) y LR (1), por lo que se anticipa una anticipación de token.
¿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 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 recibí una respuesta satisfactoria sobre la diferencia entre LALR y LR. Entonces, las tablas de LALR son de menor tamaño pero solo pueden reconocer un subconjunto de gramáticas de LR. ¿Puede alguien 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 avance de token y ambos son manejados por la mesa! ¿Cómo son diferentes?
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 es un orden de magnitud más pequeño que las tablas de análisis puro de LR. Sin embargo, para las gramáticas LR que son demasiado complejas para ser LALR, estos estados fusionados resultan en conflictos de analizador, o producen un analizador sintáctico 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) here .
Apéndice
La respuesta corta es que las tablas de análisis LALR son más pequeñas, pero la maquinaria del analizador es la misma. Una gramática LALR determinada 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 entre sí, eliminando efectivamente la información de contexto / búsqueda anticipada que codifican los estados por separado. La ventaja es que obtienes 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 caras más complicadas, lo que da como resultado dos o más estados en lugar de un solo estado fusionado.
La principal diferencia es que el algoritmo para producir tablas LR contiene más información entre las transiciones de estado a estado, mientras que el algoritmo LALR no lo hace. Entonces, el algoritmo LALR no puede decir si un estado fusionado dado debería realmente dejarse como dos o más estados separados.
Los analizadores SLR reconocen un subconjunto apropiado de gramáticas reconocibles por los analizadores sintácticos LALR (1), que a su vez reconocen un subconjunto apropiado de gramáticas reconocibles por los analizadores LR (1).
Cada uno de estos se construye como una máquina de estado, donde cada estado representa un conjunto de reglas de producción de la gramática (y posición en cada una) mientras analiza la entrada.
El ejemplo de Dragon Book de una gramática LALR (1) que no es SLR es esta:
S → L = R | R
L → * R | id
R → L
Este es uno de los estados para esta gramática:
S → L•= R
R → L•
El • indica la posición del analizador en cada una de las posibles producciones. No sabe en cuál de las producciones está realmente hasta que llega al final y trata de reducir.
Aquí, el analizador sintáctico podría cambiar an = o reducir R → L
Un analizador SLR (también conocido como LR (0)) determinaría si podría reducirse comprobando 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 a R ). Dado que = también está en este conjunto, el analizador SLR encuentra un conflicto shift-reduce.
Sin embargo, un analizador 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 comentaron los comentaristas anteriores, los analizadores LALR (1) tienen la misma cantidad de estados que los analizadores SLR. Un algoritmo de propagación anticipada se utiliza para unir lookaheads a producciones de estado SLR a partir de los correspondientes estados LR (1). El analizador LALR (1) resultante puede introducir conflictos de reducción-reducción no presentes en el analizador LR (1), pero no puede introducir conflictos de desplazamiento-reducción.
En su ejemplo , el siguiente estado LALR (1) causa un conflicto shift-reduce 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 ser desplazado.
Los analizadores SLR, LALR y LR pueden implementarse utilizando exactamente la misma maquinaria basada en tablas.
Fundamentalmente, el algoritmo de análisis recopila el siguiente token de entrada T, y consulta el estado actual S (y la búsqueda anticipada asociada, GOTO y tablas de reducción) para decidir qué hacer:
- SHIFT: si la tabla actual dice que SHIFT en el token T, el par (S, T) se coloca 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 recupera 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 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 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 supuesto valor 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 el generador de tablas. 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.
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 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 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.]
Otra respuesta más (YAA).
Los algoritmos de análisis 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 analizadores SLR crea una máquina de estados LR (0) y calcula los look-aheads de la gramática (FIRST y FOLLOW sets). Este es un enfoque simplificado y puede informar conflictos que realmente no existen en la máquina de estado LR (0).
Un generador de analizadores LALR crea una máquina de estados LR (0) y calcula los look-aheads de la máquina de estados LR (0) (a través de las transiciones de los terminales). Este es un enfoque correcto, pero ocasionalmente informa conflictos que no existirían en una máquina de estados LR (1).
Un generador de analizador de LR de Canonical calcula una máquina de estado LR (1) y los miradores ya son parte de la máquina de estado LR (1). Estas tablas de analizador pueden ser muy grandes.
Un generador de analizador de LR mínimo calcula una máquina de estado LR (1), pero combina estados compatibles durante el proceso y luego calcula los look-aheads de la máquina de estado 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, por lo que ofrecen la mejor solución.
LRSTAR 8.0 puede generar analizadores LALR (1), LR mínimo (1) y LR (k) en C ++.
Supongamos que un analizador sintáctico sin un vistazo está felizmente analizando cadenas para su gramática.
Usando su ejemplo dado se encuentra con una cadena de dc , ¿qué hace? ¿Lo reduce a S , porque dc es una cadena válida producida por esta gramática? O tal vez estábamos tratando de analizar bdc porque incluso eso es una cadena aceptable?
Como humanos sabemos que la respuesta es simple, solo debemos recordar si hubiéramos analizado b o 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 anticipación no puede decirnos qué hacer en este caso; en cambio, tenemos que mirar hacia atrás en nuestro pasado. Así viene el analizador canónico de LR al rescate. Recuerda el contexto pasado.
La forma en que recuerda este contexto es que se autodisciplina, que siempre que encuentre un b , comenzará a caminar en un camino hacia la lectura de bdc , como una posibilidad. Entonces, cuando ve una d , sabe si ya está caminando por un camino. 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 tantas rutas, ¡los estados de la máquina son muy grandes!
Así que fusionamos caminos que parecen iguales, pero como se esperaba, 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 dibuja los conjuntos de configuración para el lenguaje anterior, verá un conflicto shift-reduce en dos estados. Para eliminarlos, es posible que desee considerar una SLR (1), que toma decisiones mirando a un follow, pero observará que todavía no podrá hacerlo. De este modo, dibujaría los conjuntos de configuración nuevamente, pero esta vez con la restricción de que cada vez que calcule el cierre, las producciones adicionales que se agreguen deben tener seguimiento (s) estricto (s). Consulte cualquier libro de texto sobre lo que debe seguir.
Una respuesta simple es que todas las gramáticas LR (0) son gramáticas LALR (1). Comparado con LR (1), LALR (1) tiene más números de estados en el DFA asociado (casi estados dobles). Y esa es la razón principal para que las gramáticas LALR (1) tomen más tiempo para mostrar errores que las gramáticas LR (1) . Y una cosa más importante de saber con respecto a estas dos gramáticas es que en LR (1) las gramáticas no podemos encontrar cambios / reducir o reducir / reducir conflictos. Pero en LALR (1) existe la posibilidad de reducir / reducir el conflicto.