Análisis ascendente LR

De FIWIKI
Saltar a: navegación, buscar

Existe un grupo de métodos que llamaremos de forma genérica métodos LR(K), donde las iniciales tiene el siguiente significado:

  • L = Left. La cadena de entrada se lee (analiza) de izquierda a derecha.
  • R = Right. Se realiza un análisis a derechas, es decir, un análisis ascendente.
  • K. Indica el número de símbolos de la cadena de entrada (número de tokens) que debemos conocer anticipadamente para tomar decisiones (hacer el análisis). K suele valer 0 ó 1 => LR(0) ó LR(1).

De manera general, con LR nos estaremos refiriendo a LR(1).

Hay diferentes métodos LR:

  • LR Simple (SLR).
  • LR canónico.
  • Look Ahead LR (LALR). LR con análisis anticipado. Es el que implementa la herramienta YACC (Yet Another Compiler-Compiler).

Estos métodos LR son los más generales para realizar un análisis sintáctico ascendente de reducción-desplazamiento, más generales que el de precedencia de operador pues aceptan gramáticas que generan cualquier construcción posible de un lenguaje de programación común. Las gramáticas con precedencia de operador son un subconjunto de las gramáticas que reconoce el análisis LR. Los LR admiten más gramáticas de tipo 2.

Estos métodos son tan eficientes como el resto de antecedentes y detectan los errores en el primer instante que se puedan detectar. Como inconveniente, es mucho más complejo elaborar la información necesaria para aplicar el método LR.

Los tres métodos antes nombrados se diferencian en las tablas que hay que crear para poder aplicar el algoritmo.

Esquema general del análisis sintáctico LR

Esquema general del análisis sintáctico LR.png


Acción: cuándo actuamos.

Go To : Dónde ir después de una reducción.

La pila siempre va a tener alternancia de estado y símbolo. En la cabeza siempre debe haber un estado.

Los estados tratan de resumir lo que ha pasado por la pila. Incluyen el conocimiento de qué hemos hecho hasta el momento.

Operaciones permitidas

Sean Si los estados con i 0..n y aj los símbolos de la cadena de entrada con j 0..n y $ como fin.

  • Desplazamiento

Si Acción (sn, ai) = dj Se pide un token al léxico (ai) y se pasa a la cima de la pila. Se transita al estado j (se introduce en la pila, quedando en la cima siempre un estado. ¡Nunca un token!).

  • Reducción

Si Acción (sn, ai) = rk. Reducir por la regla k.

regla k: A -> α (α es el consecuente de la regla k)

|α| = r (r es el número de elementos de α)

El siguiente estado vendrá determinado por GOTO(Sn-r, A). Siendo A el antecedente de la regla k. También lo introducimos en la pila sustituyendo a los últimos elementos que coincidían con el consecuente de la regla k.

  • Error

Si Acción (sn, ai) = vacío.

  • Aceptar

Indica cuándo termina con éxito el análisis sintáctico.

Ejemplo con tabla de decisión construida

  • Gramática

E - > E + T (r1)

E - > T (r2)

T - > T * F (r3)

T - > F (r4)

F - > (E) (r5)

F - > id (r6)

  • Cadena de entrada

w = id * id

  • Tabla de decisión

Tabla de decisión ejemplo simple LR.png

Solo veremos la construcción de tablas LR con SLR.

  • Algoritmo

A la hora de tomar decisiones se tiene en cuenta el estado y el token actual.

Mirando la tabla de decisión:

S0 con id indica D5, desplazar al estado 5. Entonces se añade el token a la pila, se elimina de la cadena y, como siempre debe haber un estado en la cima de la pila, añadimos el estado 5.

Ahora tenemos estado 5 y * como token. Eso nos da R6 (reducir por la regla 6), es decir, reducir por F - > id. En la pila se eliminan tantos símbolos como el doble de elementos a la derecha de la regla. En este caso hay un símbolo (F - > id), por tanto en la pila se eliminan dos símbolos (id, S5).Uno de los símbolos debe coincidir con el que está a la derecha de la regla: en este caso, es correcto. Entonces en la pila se coloca el símbolo a la izquierda de la regla (S0F). Para conocer qué estado hay que poner a continuación se va a la tabla GOTO con el estado en la pila (S0) y el símbolo (F): nos lleva al estado 3.

Así vamos utilizando el algoritmo LR y poco a poco se llega a la situación de la pila final.

Algoritmo ejemplo simple LR.png