Análisis descendente LL o por tablas

De FIWIKI
Saltar a: navegación, buscar

Sigue el siguiente esquema de trabajo:

Esquema de trabajo del analizador LL.png

  • Buffer de entrada: el programa es genérico, válido para cualquier gramática no recursiva por la izquierda.
  • Pila de trabajo: La pila se inicializa con el axioma. En ella puede haber símbolos terminales y no terminales.
  • Tabla de decisión: La tabla del análisis descendente es bidimensional y en ella se toman las decisiones en función de un símbolo no terminal y un símbolo terminal: M(A,a)

Situaciones posibles

El programa puede tomar dos decisiones y lo hace en función de la cabeza de la pila (X) y el elemento siguiente de la cadena de entrada (ai).

  • Si X = ai => $ => Aceptar la cadena. Fin.
  • Si X = ai => Quitar X de la pila. Leer siguiente token (ai+1). Esto es validar el token (símbolo).
  • Si CimaPila ε N => Consultar la tabla de decisión:
    • Si M(x,ai) = ∅ (casilla vacía) => Error.
    • Si M(x,ai) = X -> X1X2..Xn (regla de la gramática) => Quitar X de la pila. Meter en la pila la parte derecha de la producción dejando X1 en la cima (queremos derivar por la izquierda). Esto es derivar por dicha regla.

Ascendente VS Descendente

  • Reducir es ahora expandir.
  • Desplazar es ahora consumir el terminal.

Construcción de la tabla de decisión

Para cada producción A - > α ε G

  • Si t ε First(α) => M(A, t) = A - > α (t εT)
  • Si λ ε First(α) => M(A, t) = A - > α ∀t ε Follow(A)

Una casilla en blanco indica error. En la tabla no puede haber ni columnas ni filas completamente en blanco. Una columna en blanco significa que el terminal nunca se obtiene, por lo que la gramática estaría mal construida o el terminal sería innecesario. Una fila en blanco significa que el símbolo no terminal no se puede derivar.

Ejemplo

  • E - > E+T / T
  • T - >T*F / F
  • F - > (E) / id

Primero eliminamos recursividad por la izquierda:

  • E - > TE’
  • E’ - >+TE’ / λ
  • T - > FT’
  • T’ - > *FT’ / λ
  • F - > (E) / id

Sin problemas de factorización.

T = {id, +, *, (, )} N = {E, E', T, T'. F}

Calculamos los First:

  • First(+) = {+}; First(*) = {*}; First( ( ) = { ( }; First( )) = { ) }; First(id) = {id}
  • First(E)= { ( , id}
  • First (E’) = {+, λ}
  • First (T) = {(, id}
  • First (T’) = {*, λ}
  • First (F) = {(, id}

E - > TE’ => First (TE’) = {(,id} Se hace el First de cada producción de las reglas y esta regla se sitúa en la tabla bajo el símbolo que sea su First.

Calculamos los Follow:

  • Follow (E) = {), $}
  • Follow (E’) = {), $}
  • Follow (T) = {+, ), $}
  • Follow (T’) = {+, ), $}
  • Follow (F) = {*, +, ), $}

Construimos la tabla:

Ejemplo tabla LL.png

  • E => First(TE') = First(T) = {(, id}
  • E' => First(+TE') = {+}; Follow (E’) = { ), $} Por E' - > λ para cada símbolo del Follow(E') aparecerá la regla en la tabla. Ejemplo: M(E', $) = E' - > λ
  • T => First(FT') = First(F) = {(, id}
  • T' => First(*FT’)={ * }; Follow (T') = {+, ), $}. Por T' - > λ para cada símbolo del Follow(T') aparecerá la regla en la tabla. Ejemplo: M(T', +) = T' - > λ
  • F => First( (E) )= { ( }; First (id) = {id}