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

parsing compiler-construction

Question

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

¿Los analizadores SLR y LR (0) son iguales? Si no, ¿cuál es la diferencia?

Answer 1

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

Answer 2

Los analizadores LR (0) y SLR (1) son analizadores sintácticos direccionales y ascendentes . Esto significa que

• Los analizadores intentan aplicar producciones al revés 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 aplicar sin necesariamente ver toda la entrada ( predictiva )

Tanto LR (0) como SLR (1) son analizadores de desplazamiento / reducción , lo que significa que procesan los tokens de la secuencia de entrada colocándolos en una pila, y en cada punto cambiando una ficha presionándola en la pila o reduciendo secuencia de terminales y no terminales encima de la pila hacia atrás a algún símbolo no terminal. Se puede demostrar que cualquier gramática se puede analizar de abajo arriba usando un analizador de desplazamiento / reducción, pero ese analizador puede 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 el analizador de desplazamiento / reducción determinista que construya, nunca podrá analizar todas las gramáticas.

Cuando se utiliza un analizador de desplazamiento / reducción determinista para analizar una gramática que no puede manejar, se produce un cambio / reducción de conflictos o reducción / reducción de conflictos , donde el analizador puede entrar en un estado en el que no puede decir qué acción tomar. En un conflicto de desplazamiento / 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 debe reemplazar los símbolos superiores de la pila con algunos no terminales, pero no puede decir qué reducción usar.

Me disculpo si esta es una exposición larga, pero necesitamos que esto sea capaz de abordar la diferencia entre el análisis LR (0) y el SLR (1). Un analizador LR (0) es un analizador de desplazamiento / reducción que usa cero tokens de anticipación 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: cambia un símbolo específico o aplica una reducción específica. Si alguna vez hay dos o más opciones para hacer, el analizador falla y decimos que la gramática no es LR (0).

Recuerde que los dos posibles conflictos LR son shift / reduce y reduce / reduce. 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 ellas usar. Dado que al menos una de las acciones en conflicto es una reducción, una línea de ataque razonable sería intentar que el analizador tenga más cuidado sobre cuándo realiza una reducción particular. Más específicamente, supongamos que el analizador puede mirar el siguiente token de entrada para determinar si debería cambiar o reducirse. Si solo permitimos que el analizador se reduzca cuando tiene "sentido" hacerlo (para alguna definición de "tiene sentido"), entonces podremos eliminar el conflicto haciendo que el autómata seleccione específicamente desplazar o reducir en una paso particular.

En SLR (1) ("LR simplificado (1)"), el analizador puede ver un símbolo de búsqueda anticipada al decidir si debe cambiar o reducirse. En particular, cuando el analizador intenta reducir algo de la forma A → w (para A no terminal y la cadena w), mira el siguiente token de entrada. Si ese token podría aparecer legalmente después del A no terminal en alguna derivación, el analizador se reduce. De lo contrario, no es así. 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 el token próximo, no hay forma posible de que la reducción sea alguna vez 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 analizada por un analizador SLR (1). Sin embargo, los analizadores SLR (1) pueden analizar un mayor número de gramáticas que LR (0).

En la práctica, sin embargo, SLR (1) sigue siendo un método de análisis bastante débil. Más comúnmente, verá analizadores LALR (1) ("Lookahead LR (1)") que se utilizarán. 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 usadas 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ífico, los analizadores de SLR (1) intentan resolver conflictos al observar la estructura de la gramática para obtener más información sobre cuándo cambiar y cuándo reducirla. Los analizadores LALR (1) miran la gramática y 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 ver 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 , de forma predeterminada, producen analizadores LALR (1).

Históricamente, los analizadores LALR (1) se construían típicamente a través de un método diferente que dependía del analizador LR (1) mucho más potente, por lo que a menudo verás LALR (1) descrito de esa manera. Para entender 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 el medio de una producción. Una vez que ha descubierto que se ha llegado al final de una producción, sabe que debe intentar reducirla. Sin embargo, el analizador podría no ser capaz de decir si está al final de una producción y en el medio de otra, lo que lleva a un conflicto de cambio / reducción, o a cuál de dos producciones diferentes ha llegado al 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 del siguiente token de búsqueda anticipada.

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 los tokens posibles que pueden aparecer después de que se complete la producción. Como 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 poderoso y preciso que cualquiera de los LR (0), SLR (1) o Analizadores LALR (1) de los que hemos hablado hasta ahora. LR (1) es una técnica de análisis extremadamente poderosa, y se puede demostrar usando algunos cálculos complicados que cualquier lenguaje que pueda ser analizado de manera determinista por cualquier analizador de cambio / reducción tiene alguna gramática que podría ser analizada con un autómata LR (1). (Tenga en cuenta que esto no significa que todas las gramáticas que pueden analizarse de manera determinista son LR (1), lo que solo indica que un lenguaje que puede analizarse de manera determinista tiene alguna 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 pueda ser utilizado en la práctica. Un analizador LR (1) para un lenguaje de programación real, por ejemplo, puede requerir de decenas a cientos de megabytes de información adicional para funcionar correctamente. Por esta razón, LR (1) no se usa normalmente en la práctica, y en su lugar se utilizan 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 al intentar todas las opciones posibles en paralelo. Usando algunos trucos ingeniosos, esto se puede hacer para ejecutar de manera muy eficiente para muchas gramáticas. Además, GLR (0) puede analizar cualquier gramática libre de contexto , incluso gramáticas que no pueden ser analizadas por un analizador LR (k) para ninguna k. Otros analizadores son capaces de hacer esto también (por ejemplo, el analizador de Earley o un analizador de CYK), aunque GLR (0) tiende a ser más rápido en la práctica.

Si estás 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 sintáctico. Si desea obtener una introducción más rigurosa a LR (0), SLR (1) y una serie de otras poderosas técnicas de análisis sintáctico, puede disfrutar de mis diapositivas de conferencias y tareas sobre el análisis sintáctico. Todos los materiales del curso están disponibles aquí en mi sitio personal .

¡Espero que esto ayude!