Nuestro equipo redactor ha estado mucho tiempo investigando para darle respuesta a tus dudas, te dejamos la respuesta y nuestro objetivo es que sea de gran ayuda.
Solución:
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 “mejorada” de un analizador LR (0) que realiza un seguimiento de información más precisa para eliminar la ambigüedad de 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 sintácticos LALR (1) son un factor constante mayor que los analizadores sintácticos LR (0), y los analizadores sintácticos LR (1) suelen ser exponencialmente más grandes que los analizadores sintácticos 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 ascendente que funciona manteniendo una pila de terminales y no terminales. El analizador es controlado por un autómata finito que determina, basándose en el estado actual del analizador y los siguientes k tokens de entrada, si cambio una nueva ficha en la pila o reducir los símbolos superiores de la pila aplicando una producción a la inversa.
Con el fin de realizar un seguimiento de la información suficiente para tomar una determinación sobre si cambiar o reducir, los analizadores sintácticos LR (k) hacen que cada estado corresponda a un “conjunto de configuración”, un conjunto de producciones anotadas con la siguiente información:
- ¿Cuánta producción se ha visto hasta ahora y
- ¿Qué tokens esperar después de que se haya completado la producción (el mirar hacia el futuro)
La primera de estas piezas de información se utiliza para determinar si el analizador puede necesitar hacer una reducción; si no se ha completado ninguna de las producciones en el estado actual, no hay razón para hacer una reducción. El segundo de estos datos se utiliza cuando se realiza una reducción para determinar si se debe realizar la reducción. Al decidir si reducir, un analizador LR (k) mira los siguientes k tokens 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 debe hacer el analizador en un estado dado. Un tipo de conflicto, un cambiar / reducir el conflicto, aparece cuando el analizador se encuentra en un estado en el que 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 reducir / reducir el conflicto, donde el analizador sabe que tiene que hacer una reducción, pero son posibles dos o más reducciones y no sabe cuál hacer.
Intuitivamente, a medida que k aumenta cada vez más, el analizador tiene información cada vez más precisa disponible para determinar cuándo cambiar y cuándo reducir. Si una gramática no es LR (0), por ejemplo, el analizador puede tener un estado en el que, dado que no se le da ninguna anticipación, no puede determinar si cambiar o reducir. Sin embargo, esa gramática podría seguir siendo LR (1) porque si se le da una muestra adicional de anticipación, puede reconocer que definitivamente debería cambiar y no reducir o reducir definitivamente y no cambiar.
El problema con los analizadores sintácticos LR (k) es que a medida que k aumenta, el número de estados puede aumentar exponencialmente. La búsqueda anticipada en los analizadores LR (k) se maneja construyendo más y más estados en el analizador para que correspondan a diferentes combinaciones de producciones y anticipaciones, de modo que a medida que aumenta el número de posibles búsquedas anticipadas, también lo hace el número de estados. En consecuencia, los analizadores sintácticos LR (1) suelen ser demasiado grandes para ser prácticos, y LR (2) o más es casi inaudito en la práctica.
LALR (1) se inventó como un compromiso entre la eficiencia espacial de los analizadores sintácticos LR (0) y el poder expresivo de los analizadores sintácticos LR (1). Hay varias formas de pensar qué es un analizador LALR (1). Originalmente, los analizadores sintácticos LALR (1) se especificaron como una transformación que convierte los autómatas LR (1) en autómatas más pequeños. Aunque un analizador sintáctico LR (1) puede tener muchos más estados que un autómata LR (0), la única diferencia es que un analizador sintáctico LR (1) puede tener múltiples copias de cualquier estado particular en un autómata LR (0), cada una anotada con diferente información de anticipación. Se puede formar un analizador LALR (1) comenzando con un analizador LR (1), luego combinando todos los estados que tienen el mismo “núcleo” (el conjunto de producciones y sus posiciones), luego agregando toda la información anticipada. Esto da como resultado un analizador que tiene el mismo número de estados que un analizador LR (0) pero retiene cierta cantidad de información sobre búsquedas anticipadas para ayudar a evitar conflictos LR.
Otra vista de las gramáticas LALR (1) utiliza el método “LALR-by-SLR”. Los analizadores sintácticos LALR (1) se pueden construir comenzando con un analizador sintáctico LR (0) para una gramática, luego creando una nueva gramática para el lenguaje que anota no terminales con información sobre los estados en el analizador LR (0) a los que corresponden. La información sobre los conjuntos FOLLOW de los no terminales en esa gramática se puede usar para calcular las búsquedas anticipadas en el analizador LR (0).
El resultado neto es que
- Los analizadores sintácticos LR (0) son pequeños, pero no muy expresivos.
- Los analizadores sintácticos LALR (1) son un poco más grandes debido a la información anticipada, pero muy expresivos.
- Los analizadores sintácticos 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 los autómatas de análisis para el analizador LR (1) y el analizador LALR (1) y verificar para conflictos. Para construir el analizador LR (1), construya los conjuntos de configuración LR (1), luego verifique si alguno de esos conjuntos de configuración tiene un conflicto de cambio / reducción o un conflicto de reducción / reducción. Para construir un analizador LALR (1), puede construir el analizador LR (1) y luego condensar los conjuntos de configuración con el mismo núcleo o puede usar el método LALR-by-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!
valoraciones y comentarios
Si para ti ha sido provechoso este artículo, sería de mucha ayuda si lo compartes con más juniors de este modo nos ayudas a difundir este contenido.