stringtranslate.com

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).

Cuando se procesa mediante 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 anticipación esperado. Si la gramática no es SLR, las tablas de análisis tendrán conflictos de desplazamiento/reducción o conflictos de reducción/reducción para algún estado y algunos símbolos de anticipación, y el analizador rechazado resultante ya no es determinista. El analizador no puede decidir si desplazar o reducir a continuación, o no puede decidir entre dos reducciones candidatas. Los analizadores SLR utilizan un cálculo Follow(A) para elegir los símbolos de anticipación que se esperan para cada no terminal completado.

Los analizadores LALR utilizan un cálculo diferente que, a veces, proporciona conjuntos de anticipación más pequeños y más ajustados para los mismos estados del analizador. Esos conjuntos más pequeños pueden eliminar la superposición con las acciones de cambio de estado y la superposición con las anticipaciones para otras reducciones en este mismo estado. Los conflictos de superposición informados por los analizadores SLR son entonces falsos, resultado del cálculo aproximado utilizando Follow(A).

Una gramática ambigua tendrá conflictos inevitables de cambio/reducción o de reducción/reducción para cada método de análisis LR, incluido 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

Definiciones

Se dice que una regla de la forma B → y • dentro de un estado de un autómata SLR(1) es irreducible o está en un estado reducido porque se ha expandido completamente y es incapaz de 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 más a la derecha de su RHS (lado derecho).

Normas

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

  1. Para cualquier regla reducible A → a • Xb en el estado s (donde X es algún terminal), no debe existir ninguna regla irreducible, B → a • en el mismo estado s tal que el conjunto siguiente de B contenga al terminal X . En términos más formales, la intersección del conjunto que contiene al terminal X y el conjunto siguiente de B debe estar vacía. La violación de esta regla es un conflicto de desplazamiento-reducción .
  2. Para dos elementos completos cualesquiera A → a • y B → b • en s , Follow(A) y Follow(B) son disjuntos (su intersección es el conjunto vacío). La violación de esta regla es un Conflicto de reducción-reducción .

Algoritmo de análisis

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

  1. Si el estado s contiene cualquier elemento de la forma A → a • Xb , donde X es una terminal y X es el siguiente token en la cadena de entrada, entonces la acción es desplazar el token de entrada actual a la pila, y el nuevo estado que se insertará en la pila es el estado que contiene el elemento A → aX • b .
  2. Si el estado s contiene el elemento 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 . Una reducción por la regla S' → S , donde S es el estado inicial, es equivalente a la aceptación; esto sucederá solo si el siguiente token de entrada es $ . En todos los demás casos, el nuevo estado se calcula de la siguiente manera. Elimine la cadena y y todos sus estados correspondientes de la pila de análisis. En consecuencia, retroceda en el DFA hasta el estado desde el que comenzó la construcción de y . Por construcción, este estado debe contener un elemento de la forma B → a • Ab . Empuje A en la pila e inserte el estado que contiene el elemento B → aA • b .
  3. Si el siguiente token de entrada es tal que ninguno de los dos casos anteriores se aplica, se declara un error.

Véase también

Referencias