Gramática SLR

Las gramáticas SLR son la clase de gramáticas formales aceptadas por un analizador LR simple. Las gramáticas SLR son un superconjunto de todas las gramáticas LR(0) y un subconjunto de todas las gramáticas LALR(1) y LR(1).

Al ser procesada por un analizador SLR, una gramática SLR se convierte en tablas de análisis sin conflictos de desplazamiento/reducción o reducción/reducción para cualquier combinación de estado del analizador LR(0) y símbolo de búsqueda anticipada esperado. Si la gramática no es SLR, las tablas de análisis presentarán conflictos de desplazamiento/reducción o reducción/reducción para algún estado y algunos símbolos de búsqueda anticipada, y el analizador rechazado resultante deja de ser determinista. El analizador no puede decidir si desplazar o reducir a continuación, ni entre dos posibles reducciones. Los analizadores SLR utilizan un cálculo Follow(A) para seleccionar los símbolos de búsqueda anticipada esperados para cada no terminal completado.Los analizadores LALR utilizan un cálculo diferente que, en ocasiones, genera conjuntos de anticipación más pequeños y precisos para los mismos estados del analizador. Estos conjuntos más pequeños pueden eliminar la superposición con las acciones de desplazamiento del estado y con las previsiones para otras reducciones en este mismo estado. Los conflictos de superposición que reportan los analizadores SLR son, por lo tanto, falsos, resultado del cálculo aproximado con Follow(A).

Una gramática ambigua presentará inevitablemente conflictos de desplazamiento/reducción o de reducción/reducción para cualquier método de análisis LR, incluido el SLR. Una forma común de que las gramáticas de lenguajes informáticos sean ambiguas es si algún no terminal es recursivo tanto a la izquierda como a la derecha:

Expr → Expr * Val

Expr → Val + Expr

Expr → Val

Una regla de la forma B → y • dentro de un estado de un autómata SLR(1) se dice que es irreducible o está en un estado reducido porque se ha expandido completamente y no puede experimentar ninguna transición de desplazamiento. Las reglas en este estado tendrán un punto (• la posición actual de anticipación) ubicado en el extremo derecho de su lado derecho (RHS).

Se dice que una gramática es SLR(1) si y solo si, para cada estado s en el autómata SLR(1), no se viola ninguna de las siguientes condiciones:

1. Para cualquier regla reducible A → a • Xb en estado s (donde) X es algún terminal), no debe existir alguna regla irreducible, B → a • en el mismo estado s tal que seguir conjunto de B contiene el terminal X. En términos más formales, la intersección del conjunto que contiene el terminal X y el conjunto de seguimiento B Debe estar vacío. La violación de esta norma es una Conflicto Shift-Reduce.
2. Para cualquier dos elementos completos A → a y B → b dentro s, Follow(A) y Follow(B) son disjoint (su intersección es el conjunto vacío). La violación de esta norma es una Reducir el conflicto.

Se dice que una gramática es SLR(1) si el siguiente algoritmo simple del analizador LR no genera ninguna ambigüedad.

1. Si el estado s contiene cualquier artículo del formulario A → a • Xb, donde X es un terminal, y X es el siguiente token en la cadena de entrada, entonces la acción es cambiar el token de entrada actual en la pila, y el nuevo estado a ser empujado en la pila es el estado que contiene el elemento A → aX • b.
2. Si el estado s contiene el artículo completo A → y • y el siguiente token en la cadena de entrada está en Follow(A), entonces la acción es reducir por la regla A → y. Reducción de la norma S' → S, donde S es el estado de inicio, es equivalente a la aceptación; esto sucederá sólo si la siguiente ficha de entrada es $. En todos los demás casos, el nuevo estado computado como sigue. Quitar la cuerda Sí. y todos sus estados correspondientes de la pila de persiana. Correspondientemente, respaldo en el DFA al estado desde el cual la construcción Sí. Comenzó. Por construcción, este estado debe contener un elemento de la forma B → a • Ab. Empuja A en la pila, y empujar el estado que contiene el elemento B → aA • b.
3. Si la siguiente señal de entrada es tal que ninguno de los dos casos anteriores se aplica, se declara un error.

• Gramática LR
• Gramática LL

• "Compiler Construction: Principles and Practice" de Kenneth C. Louden.