parsing - paquetes - r repository
¿Cuál es la diferencia entre LALR y LR? (3)
Entiendo que tanto LR como LALR son algoritmos de análisis ascendentes, pero ¿cuál es la diferencia entre los dos?
¿Cuál es la diferencia entre el análisis de LR (0), LALR (1) y LR (1)? ¿Cómo puedo saber si una gramática es LR (0), LALR (1) o LR (1)?
El algoritmo de análisis para un analizador LALR (1) es exactamente el mismo que el algoritmo de análisis para un analizador LR (1) canónico. La diferencia está en el número de estados. Los analizadores Canonical LR (1) tienen una gran cantidad de estados, lo que simplifica el algoritmo de recuperación de errores.
La única ventaja de los analizadores LR (1) canónicos es que no hacen reducciones erróneas cuando se encuentra un error, lo cual no es una gran ventaja.
Los analizadores Canonical LR (1) NO son útiles para lenguajes de programación grandes, ya que requieren tablas de analizador extremadamente grandes.
Hay otro caso, LR mínimo (1), que utiliza el mismo algoritmo de análisis y algoritmo de recuperación de errores que LALR (1). Los analizadores LR (1) mínimos ofrecen la potencia de LR (1) y su tamaño es casi tan pequeño como LALR (1).
El generador de analizadores LRSTAR crea analizadores LR (1) mínimos para los programadores de C ++ y la versión educativa es gratuita.
En un nivel alto, la diferencia entre LR (0), LALR (1) y LR (1) es la siguiente:
Un analizador LALR (1) es una versión "actualizada" de un analizador LR (0) que realiza un seguimiento de la información más precisa para desambiguar la gramática. Un analizador LR (1) es un analizador significativamente más potente que realiza un seguimiento de información aún más precisa que un analizador LALR (1).
Los analizadores LALR (1) son un factor constante mayor que los analizadores LR (0), y los analizadores LR (1) suelen ser exponencialmente más grandes que los analizadores LALR (1).
Cualquier gramática que se pueda analizar con un analizador LR (0) se puede analizar con un analizador LALR (1) y cualquier gramática que se pueda analizar con un analizador LALR (1) se puede analizar con un analizador LR (1). Hay gramáticas que son LALR (1) pero no LR (0) y LR (1) pero no LALR (1).
Más formalmente, un analizador LR (k) es un analizador de abajo arriba que funciona manteniendo una pila de terminales y no terminales. El analizador sintáctico está controlado por un autómata finito que determina, en función del estado actual del analizador sintáctico y las próximas k fichas de entrada, si desplaza un token nuevo a la pila o reduce los símbolos superiores de la pila al aplicar una producción en sentido inverso .
Para realizar un seguimiento de la información suficiente para determinar si se cambia o se reduce, los analizadores LR (k) tienen cada estado correspondiente a un "conjunto de configuración", un conjunto de producciones anotadas con la siguiente información:
- ¿Cuánto de la producción se ha visto hasta ahora?
- Qué cosas esperar después de que la producción se haya completado (la anticipación )
La primera de estas piezas de información se usa para determinar si el analizador puede necesitar hacer una reducción; si ninguna de las producciones en un estado actual se ha completado, no hay razón para hacer una reducción. La segunda de estas piezas de información se usa al hacer una reducción para determinar si se debe realizar la reducción. Al decidir si se reduce, un analizador LR (k) examina las siguientes k fichas del flujo de entrada. Si coinciden con los tokens de anticipación, el analizador se reducirá y, de lo contrario, el analizador no hará nada.
Los problemas surgen en un analizador LR (k) cuando hay conflictos sobre lo que el analizador debería hacer en un estado determinado. Un tipo de conflicto, un conflicto de cambio / reducción , aparece cuando el analizador está en un estado donde se ha completado una producción, pero los símbolos de anticipación para ese conflicto de producción también son utilizados por otra producción incompleta en el estado. Esto significa que el analizador no puede decir si realizar la reducción o no. Un segundo tipo de conflicto es un conflicto de reducción / reducción , donde el analizador sabe que tiene que hacer una reducción, pero dos o más reducciones son posibles y no puede decir qué hacer.
Intuitivamente, a medida que k se hace cada vez más grande, el analizador tiene cada vez más información precisa disponible para determinar cuándo cambiar y cuándo reducir. Si una gramática no es LR (0), por ejemplo, el analizador sintáctico puede tener un estado en el que, dado que no se le da un vistazo anticipado, no puede determinar si se desplazará o se reducirá. Sin embargo, esa gramática aún podría ser LR (1) porque, dado un token extra de anticipación, puede ser capaz de reconocer que definitivamente debería cambiar y no reducirse o definitivamente reducirse y no desplazarse.
El problema con los analizadores LR (k) es que a medida que k se hace más grande, la cantidad de estados puede aumentar exponencialmente. El análisis anticipado en los analizadores LR (k) se maneja construyendo más y más estados en el analizador para corresponder a diferentes combinaciones de producciones y cabeceras, de modo que a medida que aumenta el número de cabeceras posibles, también aumenta el número de estados. En consecuencia, los analizadores LR (1) suelen ser demasiado grandes para ser prácticos, y LR (2) o mayor es casi inaudito en la práctica.
LALR (1) se inventó como un compromiso entre la eficiencia espacial de los analizadores LR (0) y el poder expresivo de los analizadores LR (1). Hay varias maneras de pensar qué es un analizador LALR (1). Originalmente, los analizadores LALR (1) se especificaban como una transformación que convierte los autómatas LR (1) en autómatas más pequeños. Aunque un analizador LR (1) puede tener muchos más estados que un autómata LR (0), la única diferencia es que un analizador LR (1) puede tener múltiples copias de cualquier estado particular en un autómata LR (0), cada uno anotado con diferente información de anticipación. Se puede formar un analizador LALR (1) comenzando con un analizador LR (1), luego combinando juntos todos los estados que tienen el mismo "núcleo" (el conjunto de producciones y sus posiciones), luego agregando toda la información de búsqueda anticipada. Esto da como resultado un analizador sintáctico que tiene el mismo número de estados que un analizador LR (0) pero retiene cierta cantidad de información acerca de las alertas para evitar conflictos de LR.
Otra vista de gramáticas LALR (1) utiliza el método "LALR por SLR". Los analizadores LALR (1) se pueden construir comenzando con un analizador LR (0) para una gramática, y luego creando una nueva gramática para el lenguaje que anota no terminales con información sobre qué estados en el analizador LR (0) a los que corresponden. La información sobre los conjuntos de SEGUIMIENTO de los no terminales en esa gramática se puede usar para calcular las cabezas de búsqueda en el analizador LR (0).
El resultado neto es que
- Los analizadores LR (0) son pequeños, pero no muy expresivos.
- Los analizadores LALR (1) son un poco más grandes debido a la información de anticipación, pero son muy expresivos.
- Los analizadores LR (1) son enormes, pero extremadamente expresivos.
En cuanto a su segunda pregunta, ¿cómo se determina si una gramática es LR (1) o LALR (1)? El enfoque estándar es intentar construir el autómata de análisis para el analizador LR (1) y el analizador y la verificación LALR (1) para conflictos Para construir el analizador LR (1), construye los conjuntos de configuración LR (1), luego verifica si alguno de esos conjuntos de configuración tiene un conflicto de desplazamiento / reducción o reduce / reduce el conflicto. Para construir un analizador LALR (1), puede compilar el analizador LR (1) y luego condensar los conjuntos de configuración con el mismo núcleo o puede usar el método LALR por SLR basado en el analizador LR (0) para el lenguaje. Más detalles sobre cómo construir estos conjuntos de configuración están disponibles en la mayoría de los libros de texto de compiladores. También puede consultar las notas de clase de un curso de compiladores que impartí en el verano de 2012 , que cubre todos los métodos de análisis anteriores y algunos otros.
¡Espero que esto ayude!
Los analizadores LR (0), SLR (1), LALR (1) tienen todos el mismo número de estados. Los analizadores mínimos de LR (1) tendrán algunos estados más si la gramática lo requiere, para evitar conflictos de reducción-reducción.
Los analizadores Canonical LR (1) tendrán muchos más estados, demasiados para lenguajes de computadora medianos o grandes.
Los generadores de analizadores SLR (1) construyen una máquina de estados LR (0) y determinan los k = 1 lookaheads mediante el examen de la gramática (que puede informar conflictos erróneos).
Los generadores de analizadores LALR (1) construyen una máquina de estados LR (0) y determinan las cabezas de búsqueda k = 1 examinando la máquina de estados LR (0) (que es muy complicada).
Los generadores de analizadores LR (1) Canonical construyen una máquina de estado LR (1).
Los generadores de analizadores LR (1) mínimos construyen una máquina de estados LR (1) y fusionan estados compatibles durante el proceso de compilación.