stringtranslate.com

gramática réflex

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 es 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 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 cambiar o reducir a continuación, o no puede decidir entre dos reducciones candidatas. Los analizadores SLR utilizan un cálculo de seguimiento (A) para seleccionar 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 estrictos para los mismos estados del analizador. Esos conjuntos más pequeños pueden eliminar la superposición con las acciones de cambio del estado y superponerse con las anticipaciones para otras reducciones en este mismo estado. Los conflictos de superposición informados por los analizadores SLR son entonces falsos, como resultado del cálculo aproximado utilizando Follow(A).

Una gramática que es ambigua tendrá inevitables conflictos de cambio/reducción o conflictos de reducción/reducción para cada método de análisis LR, incluido SLR. Una forma común en que las gramáticas del lenguaje informático sean ambiguas es si algún no terminal es recursivo tanto hacia la izquierda como hacia 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 sufrir ninguna transición de cambio. Las reglas en este estado tendrán un punto ( • , la posición actual de anticipación) ubicado en el extremo derecho de su RHS (lado derecho).

Normas

Se dice que una gramática es SLR(1) si y sólo si, para todos y cada uno de los estados del 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 alguna regla irreducible, B → a • en el mismo estado s tal que el siguiente conjunto de B contenga el terminal X. En términos más formales, la intersección del conjunto que contiene el terminal X y el siguiente conjunto de B debe estar vacía. La violación de esta regla es un conflicto Shift-Reduce .
  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 simple del analizador LR no produce ambigüedad.

  1. Si el estado s contiene cualquier elemento de la forma A → a • Xb , donde X es un terminal y X es el siguiente token en la cadena de entrada, entonces la acción es mover el token de entrada actual a la pila y el nuevo estado a ser empujado a 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 según la regla A → y . Una reducción por la regla S' → S , donde S es el estado inicial, equivale a aceptación; Esto sucederá sólo 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 al 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 a la pila y empuje 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.

Ver también

Referencias