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

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

• Los analizadores intentan aplicar producciones en sentido inverso para reducir la oración de entrada al símbolo de inicio (bottom-up)
• Los analizadores analizan la entrada de izquierda a derecha ( direccional)
• Los analizadores intentan predecir qué reducciones aplicar sin necesariamente ver toda la entrada (predictivo)

Ambos LR (0) y SLR(1) son analizadores shift/reduce, lo que significa que procesan los tokens del flujo de entrada colocándolos en una pila, y en cada punto desplazando un token empujándolo a la pila o reduciendo alguna secuencia de terminales y no terminales encima de la pila de nuevo a algún símbolo no terminal. Se puede demostrar que cualquier gramática se puede analizar de abajo hacia arriba usando un analizador shift/reduce, pero ese analizador podría no ser determinista. Es decir, el parser 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 determinista shift/reduce que construyas, nunca será capaz de analizar todas las gramáticas.

Cuando un analizador determinista shift / reduce se usa para analizar una gramática que no puede manejar, resulta en shift / reduce conflicts o reduce / reduce conflicts , donde el analizador puede ingresar un estado en el que no puede decir qué acción tomar. En un conflicto shift / reduce, 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 reducir / reducir, el analizador sabe que necesita reemplazar los símbolos superiores de la pila con algún no terminal, 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 shift/reduce que usa cero tokens 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 que cambie un símbolo específico o aplique una reducción específica. Si hay dos o más elecciones que hacer, el analizador falla y decimos que la gramática no es LR(0).

Recordemos que los dos posibles conflictos de RL 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 conflictivas es una reducción, una línea de ataque razonable sería intentar que el analizador sea más cuidadoso cuando realiza una reducción en particular. Más específicamente, supongamos que al analizador sintáctico se le permite mirar el siguiente token de entrada para determinar si debe cambiar o reducir. Si solo permitimos el analizador para reducir cuando" tiene sentido " hacerlo (para alguna definición de "tiene sentido"), entonces podemos ser capaces de eliminar el conflicto haciendo que el autómata elija específicamente cambiar o reducir en un paso en particular.

En SLR(1) ("Simplified LR(1)"), al analizador se le permite mirar un 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 no terminal A y cadena w), mira la siguiente ficha de entrada. Si ese token podría aparecer legalmente después del no terminal A 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 el próximo token, no hay forma posible 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 conflicto. 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 están utilizando. También funcionan tratando de resolver conflictos en un analizador LR (0), pero las reglas que usan para resolver conflictos son mucho más precisas que las que se usan en SLR (1), y consecuentemente 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 SLR (1) intentan resolver conflictos mirando la estructura de la gramática para aprender más información sobre cuándo cambiar y cuándo reducir. Los analizadores LALR(1) analizan 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 cuando ciertos conflictos son espurios. Las utilidades Linux yacc y bison, por defecto, producen analizadores LALR(1).

Históricamente, los analizadores LALR(1) se construyeron típicamente a través de un método diferente que dependía del mucho más potente analizador LR(1), por lo que a menudo verá LALR(1) descrito de esa manera. Para entender esto, necesitamos hablar de los analizadores LR(1). En un analizador LR (0), el analizador funciona manteniendo un registro de dónde podría estar en medio de una producción. Una vez que ha encontró que ha llegado al final de una producción, sabe tratar de reducir. Sin embargo, el analizador podría no ser capaz de decir si está al final de una producción y en la mitad de otra, lo que conduce a un conflicto de cambio/reducción, o cuál de dos producciones diferentes ha llegado al final de (un conflicto de reducción/reducción). En LR (0), esto inmediatamente conduce a un conflicto y el analizador falla. En SLR(1) o LALR (1), el analizador entonces toma la decisión de cambiar o reducir basado en el siguiente token de lookahead.

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 posibles tokens que podrían aparecer después de que se complete la 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 usando algunas matemáticas complicadas que cualquier lenguaje que podría ser analizado deterministamente por cualquier shift/reduce parser 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 se pueden analizar deterministamente son LR(1); esto solo dice que un lenguaje que se puede analizar deterministamente tiene alguna gramática LR(1)). Sin embargo, esta potencia tiene un precio, y un analizador LR(1) generado puede requerir tanta información para operar que no puede 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 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) ("Generalized LR (0)") ha ganado popularidad. En lugar de intentar resolver los conflictos que aparecen en un analizador LR(0), el analizador GLR(0) funciona probando todas las opciones posibles en paralelo. Usando algunos trucos inteligentes, esto se puede hacer para funcionar 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 cualquier k. Otros analizadores también son capaces de hacer esto (por ejemplo, el Earley parser o un parser 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 sobre técnicas de análisis. 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, 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!