¿Cuál es la diferencia entre LR (0) y el análisis de SLR?

Question

Estoy trabajando en mis conceptos de compiladores, sin embargo, estoy un poco confundido ... Google no me llevó a ninguna parte de una respuesta definitiva.

¿Es SLR y LR (0) analizadores uno y lo mismo? Si no, ¿cuál es la diferencia?

Answer 1

Los analizadores LR (0) y SLR (1) son avisadores de abajo hacia arriba, direccionales y predictivos. Esto significa que

• Los analizadores intentan aplicar producciones en reversa para reducir la oración de entrada al símbolo de inicio (de abajo hacia arriba)
• Los analizadores escanean la entrada de izquierda a derecha (direccional)
• Los analizadores intentan predecir qué reducciones se aplicarán sin necesariamente ver toda la entrada (profético)

Tanto LR (0) como SLR (1) son cambiar/reducir los analizadores, lo que significa que procesan los tokens de la secuencia de entrada colocándolos en una pila, y en cada punto ya sea cambiando un token empujándolo a la pila o reductora Alguna secuencia de terminales y no terminales sobre la pila de regreso a algún símbolo no terminal. Se puede demostrar que cualquier gramática se puede analizar de abajo hacia arriba utilizando un analizador de cambio/reducción, pero ese analizador podría no ser determinista. Es decir, el analizador puede tener que "adivinar" si aplicar un cambio o reducción, y puede terminar teniendo que retroceder para darse cuenta de que tomó la decisión equivocada. No importa cuán poderoso sea un analgésico determinista que construya, nunca podrá analizar todas las gramáticas.

Cuando se usa un analizador de desplazamiento/reducción determinista para analizar una gramática que no puede manejar, resulta en cambiar/reducir conflictos o Reducir/reducir los conflictos, donde el analizador puede ingresar a un estado en el que no puede decir qué medidas tomar. En un conflicto de cambio/reducción, no puede decir si debe agregar otro símbolo a la pila o realizar alguna reducción en los símbolos superiores de la pila. En un conflicto de reducción/reducción, el analizador sabe que necesita reemplazar los símbolos superiores de la pila con algunos no terminales, pero no puede decir qué reducción usar.

Pido disculpas si esta es una exposición larga, pero necesitamos esto para poder abordar la diferencia entre el análisis LR (0) y SLR (1). Un analizador LR (0) es un analizador de cambio/reducción que usa tokens cero de LookAhead para determinar qué acción tomar (de ahí el 0). Esto significa que en cualquier configuración del analizador, el analizador debe tener una acción inequívoca para elegir, ya sea cambia un símbolo específico o aplica una reducción específica. Si alguna vez hay dos o más opciones para tomar, el analizador falla y decimos que la gramática no es LR (0).

Recuerde que los dos posibles conflictos LR son cambiantes/reducen y reducen/reducen. En ambos casos, hay al menos dos acciones que el autómata LR (0) podría estar tomando, y no puede decir cuál de ellos usar. Dado que al menos una de las acciones conflictivas es una reducción, una línea de ataque razonable sería tratar de que el analizador tenga más cuidado cuando realiza una reducción particular. Más específicamente, supongamos que el analizador puede mirar el siguiente token de entrada para determinar si debe cambiar o reducir. Si solo permitimos que el analizador se reduzca cuando "tiene sentido" hacerlo (para alguna definición de "tiene sentido"), entonces podemos eliminar el conflicto haciendo que el autómata elija específicamente cambiar o reducir en un paso particular.

En SLR (1) ("LR simplificado (1)"), el analizador puede mirar una token de LookAhead al decidir si debe cambiar o reducir. En particular, cuando el analizador quiere intentar reducir algo de la forma A → W (para A y String W y String W), mira el siguiente token de entrada. Si esa token pudiera aparecer legalmente después de la A no terminal en alguna derivación, el analizador se reduce. De lo contrario, no lo hace. La intuición aquí es que, en algunos casos, no tiene sentido intentar una reducción, porque dados los tokens que hemos visto hasta ahora y la próxima ficha, no hay forma de que la reducción pueda ser correcta.

La única diferencia entre LR (0) y SLR (1) es esta capacidad adicional para ayudar a decidir qué acción tomar cuando hay conflictos. Debido a esto, cualquier gramática que pueda ser analizada por un analizador LR (0) puede ser analizado por un analizador SLR (1). Sin embargo, los analizadores SLR (1) pueden analizar un mayor número de gramáticas que LR (0).

Sin embargo, en la práctica, SLR (1) sigue siendo un método de análisis bastante débil. Más comúnmente, verá los analizadores Lalr (1) ("LookAhead LR (1)") que se utilizan. Ellos también trabajan tratando de resolver conflictos en un analizador LR (0), pero las reglas que usan para resolver conflictos son mucho más precisas que las utilizadas en SLR (1) y, en consecuencia, un número mucho mayor de gramáticas son LALR (1) que son SLR (1). Para ser un poco más específicos, los analizadores SLR (1) intentan resolver conflictos observando la estructura de la gramática para aprender más información sobre cuándo cambiar y cuándo reducir. Los analizadores LALR (1) miran tanto la gramática como el analizador LR (0) para obtener información aún más específica sobre cuándo cambiar y cuándo reducir. Debido a que Lalr (1) puede mirar la estructura del analizador LR (0), puede identificar con mayor precisión cuándo ciertos conflictos son espurios. Las utilidades de Linux yacc y bison, por defecto, producir lalr (1) analizadores.

Históricamente, los analizadores LALR (1) se construyeron típicamente a través de un método diferente que se basaba en el analizador LR (1) mucho más potente, por lo que a menudo verá LALR (1) descrito de esa manera. Para comprender esto, necesitamos hablar sobre los analizadores LR (1). En un analizador LR (0), el analizador funciona haciendo un seguimiento de dónde podría estar en medio de una producción. Una vez que ha descubierto que ha llegado al final de una producción, sabe tratar de reducir. Sin embargo, es posible que el analizador no pueda saber si está al final de una producción y en el medio de otro, lo que conduce a un cambio de cambio/reducción, o a cuál de las dos producciones diferentes ha alcanzado el final de (una reducción// reducir el conflicto). En LR (0), esto conduce inmediatamente a un conflicto y el analizador falla. En SLR (1) o Lalr (1), el analizador toma la decisión de cambiar o reducir en función de la siguiente token de Lookhead.

En un analizador LR (1), el analizador realiza un seguimiento de la información adicional a medida que opera. Además de realizar un seguimiento de la producción que el analizador cree que se está utilizando, realiza un seguimiento de lo que puede aparecer los posibles tokens después de que se complete esa producción. Debido a que el analizador realiza un seguimiento de esta información en cada paso, y no solo cuando necesita tomar la decisión, el analizador LR (1) es sustancialmente más potente y preciso que cualquiera de los LR (0), SLR (1) o Lalr (1) analizadores de los que hemos hablado hasta ahora. LR (1) es una técnica de análisis extremadamente poderosa, y se puede mostrar utilizando algunas matemáticas difíciles de que cualquier lenguaje que pueda ser analizado determinista por ningún cambiar/reducir el analizador tiene una gramática que podría analizarse con un autómata LR (1). (Tenga en cuenta que esto no significa que todos gramática que se pueden analizar determinista es LR (1); Esto solo dice que un lenguaje que podría analizarse determinista tiene algo de gramática LR (1)). Sin embargo, este poder tiene un precio, y un analizador LR (1) generado puede requerir tanta información para operar que no se puede usar en la práctica. Un analizador LR (1) para un lenguaje de programación real, por ejemplo, podría requerir decenas a cientos de megabytes de información adicional para operar correctamente. Por esta razón, LR (1) no se usa típicamente en la práctica, y en su lugar se usan analizadores más débiles como Lalr (1) o SLR (1).

Más recientemente, un nuevo algoritmo de análisis llamado GLR (0) ("LR generalizado (0)") ha ganado popularidad. En lugar de tratar de resolver los conflictos que aparecen en un analizador LR (0), el analizador GLR (0) funciona intentando todas las opciones posibles en paralelo. Usando algunos trucos inteligentes, esto se puede hacer que funcione de manera muy eficiente para muchas gramáticas. Además, GLR (0) puede analizar cualquier gramática sin contexto en absoluto, incluso gramáticas que no pueden ser analizadas por un analizador LR (k) para ningún k. Otros analizadores también son capaces de hacer esto (por ejemplo, el Parser Earley o un analizador Cyk), aunque GLR (0) tiende a ser más rápido en la práctica.

Si está interesado en aprender más, durante este verano enseñé un curso introductorio de compiladores y pasé poco menos de dos semanas hablando de técnicas de análisis. Si desea obtener una introducción más rigurosa a LR (0), SLR (1) y una gran cantidad de otras poderosas técnicas de análisis, puede disfrutar de mis diapositivas de conferencias y tareas sobre el análisis. Todos los materiales del curso están disponibles aquí en mi sitio personal.

¡Espero que esto ayude!

Answer 2

Esto es lo que he aprendido. Por lo general, el analizador LR (0) puede tener ambigüedad, es decir, un cuadro de la tabla (deriva para crear el analizador) puede tener múltiples valores (o) para ponerlo mejor: el analizador conduce a dos estados finales con la misma entrada. Entonces, el analizador SLR se crea para eliminar esta ambigüedad. En orden de construirlo, encuentre todas las producciones que conducen a los estados de GOTO, encuentre lo siguiente para el símbolo de producción en el lado izquierdo e solo incluya los estados de GOTO que están presentes a continuación. Esto significa que no incluye una producción que no sea posible utilizando el grammer original (porque ese estado no está en el siguiente conjunto)