Procesadores de Lenguaje Analizadores sint´acticos descendentes: LL(1)

Cristina Tˆırn˘auc˘a Dept. Matesco, Universidad de Cantabria

Fac. Ciencias – Ing. Inform´atica – Primavera de 2013

Analizadores sint´acticos

Los analizadores descendentes: I Corresponden a un aut´ omata con pila determinista. I Construyen un ´ arbol sint´ actico de la ra´ız hacia las hojas (del s´ımbolo inicial hacia los s´ımbolos terminales). I Por ejemplo: el analizador LL o predictivo lee los datos de izquierda a derecha (Left to right) y construye la derivaci´ on izquierda (Leftmost). I Emplea una pila para mantener un resumen de lo que espera ver a continuaci´ on hasta el final de los datos. I La recursividad izquierda les puede causar problemas.

Los analizadores ascendentes (shift-reduce): I Corresponden a un aut´ omata con pila determinista. I Construyen un ´ arbol sint´ actico de las hojas hacia la ra´ız (de los terminales hacia el s´ımbolo inicial de la gram´ atica). I Por ejemplo: los analizadores LR leen los datos de izquierda a derecha (Left to right) y construyen la derivaci´ on derecha (Rightmost). (“al rev´ es”) I Emplean una pila para mantener un resumen de lo que llevan visto hasta el momento. I Son m´ as eficientes con recursividad izquierda.

Planteamiento Suponemos que un analizador l´exico nos proporciona el siguiente token cuando pedimos leer uno, o un token “nulo” (representado por $) en caso de fin de datos. (Algunas referencias incluyen tambi´en un nuevo s´ımbolo inicial que deriva en el s´ımbolo inicial seguido del marcador de fin de datos: S’ → S $.)

Idea clave: La entrada se deriva del s´ımbolo inicial si y s´ olo si lo que queda por leer se deriva de lo que hay en la pila.

Herramientas conceptuales auxiliares

Tres nociones importantes Sobre palabras formadas por s´ımbolos de la gram´atica, tanto terminales como no terminales. I

Anulabilidad de una palabra,

I

FIRST de una palabra (terminales por los que puede empezar una parte de la entrada que derive de esa palabra),

I

FOLLOW de una palabra (terminales que pueden aparecer en una entrada v´alida justo a continuaci´ on de una parte de la entrada que derive de esa palabra).

AnulabilidadFIRSTFOLLOWUn ejemplo (Anulabilidad, FIRST y FOLLOW) Es decir, capacidad para “desaparecer”

Una palabra es anulable si puede derivar en la palabra vac´ıa. I Palabras que contienen alg´ un s´ımbolo terminal: Nunca pueden derivar en la palabra vac´ıa, porque un s´ımbolo terminal que participa en una derivaci´ on ya no puede desaparecer de ella. I

Palabras que s´olo contienen s´ımbolos no terminales: I I I

λ es anulable; si α y β son anulables, αβ son anulables; si la gram´ atica contiene una regla X → α y α es anulable, X es anulable.

Lo calculamos de manera iterativa, alternativamente para s´ımbolos no terminales y para partes derechas de las reglas: nada es anulable hasta que se demuestra lo contrario. FIRST(α) = {a | α puede derivar en aγ}, donde a es un s´ımbolo terminal y α y γ son palabras formadas por s´ımbolos terminales o no terminales.

Gram´aticas y lenguajes LL(1)

Definici´on Una gram´atica libre de contexto G = (V , Σ, S, P) es LL(1) si I

S ⇒∗lm wX γ ⇒ w αγ ⇒∗lm wu,

I

S ⇒∗lm wX δ ⇒ w βδ ⇒∗lm wv ,

I

FIRST (u) = FIRST (v )

implican α = β, donde u, v , w ∈ Σ∗ y X ∈ V . Se dice sobre un lenguaje que es LL(1) si se puede generar con una gram´atica LL(1).

Ejemplos Gram´aticas LL(1) I

G = ({S}, {(, )}, S, P = {S → (S)|λ}) En esta gram´atica es obvio que la primera producci´on se usa cuando aparece un par´entesis abierto y la segunda cuando aparece el primer par´entesis cerrado.

I

G = ({S}, {a, b}, S, P = {S → aAb|b, A → aSAa|b})

Una gram´atica LL(2) que no es LL(1) G = ({S}, {a, b}, S, P = {S → abSba|aa})

Ejemplo de lenguaje que no es LL(k) para ning´un k L = {an cb n | n ≥ 1} ∪ {an db 2n | n ≥ 1}

El analizador LL descendente El analizador LL est´a utilizando: I

un “buffer” para la entrada

I

una pila, con s´ımbolos terminales y no terminales

I

una tabla de an´alisis

En cada paso, el analizador lee un s´ımbolo del buffer y el s´ımbolo que est´a en la cima de la pila. I

si coinciden, el analizador los elimina del buffer y de la pila

I

si en la cima de la pila hay un s´ımbolo terminal distinto, devuelve ERROR (la palabra no est´a aceptada)

I

si en la cima de la pila hay un s´ımbolo no terminal X , el analizador “mira” la tabla para ver que regla se debe aplicar, y substituye X por la parte derecha de esa regla.

Al principio la pila contiene el s´ımbolo inicial S y el s´ımbolo especial $ (el fondo de la pila).

Ejemplo G = ({S, F }, {a, (, )}, S, P) con P dado por las reglas siguientes: 1. S → F 2. S → (S + F ) 3. F → a

Table: FIRST y FOLLOW

S F

Anulable no no

FIRST a, ( a

Entrada: w = (a + a)

FOLLOW +, $ +, ), $

Table: Tabla de an´alisis

S F

( 2 -

) -

a 1 3

+ -

$ -

Tabla de an´alisis

Para cada s´ımbolo no terminal X y cada s´ımbolo terminal a, a˜ nadimos la regla X → α si: I

a ∈ FIRST(α), o

I

α es anulable y a ∈ FOLLOW(X )

Si la tabla contiene a lo sumo una regla para cada una de sus celdas, entonces el analizador siempre sabe que regla se debe utilizar en cada momento.

La tabla de an´alisis es un aut´omata con pila Mode de acceptaci´ on: estado final

Sea G = (V , Σ, S, P) una gram´atica LL(1).

A = (Q, Σ ∪ {$}, Γ, δ, q0 , $, F ) I

Q = {q0 , qe , qf } ∪ {qx | x ∈ Σ}

I

Γ = V ∪ Σ ∪ {$}

I

F = {qf }

I

δ(q0 , x, x) = (q0 , λ) para todo x ∈ Σ δ(q0 , $, $) = (qf , λ) δ(q0 , x, y ) = (qe , λ) para todo x, y ∈ Σ ∪ {$} con x 6= y δ(qe , x, X ) = (qe , X ) para todo x ∈ Σ ∪ {$}, X ∈ Γ δ(q0 , x, X ) = (qx , α) si X → α est´a en la fila X y columna x δ(qx , λ, X ) = δ(q0 , x, X ) para todo X ∈ Γ, x ∈ Σ

Conflictos

I

I

I

FIRST/FIRST conflict (dos alternativas empiezan igual) A → XB A → Xα | Xβ B→α|β FIRST/FOLLOW conflict (el FIRST y el FOLLOW de un s´ımbolo no terminal anulable tienen algo en com´ un) S → Aab S → aab | ab A→a|λ Recursividad izquierda E → TZ E →E +T |T Z → +TZ | λ

Conflictos (II)

Recursividad Izquierda La bendici´ on del an´ alisis ascendente

La maldici´on del an´alisis descendente: el recursivo entra en bucle. Garantiza ambig¨ uedad en la tabla LL(1). Frecuentemente se puede resolver el problema cambiando un poco la gram´atica: E → E α1 | E α2 | ... | E αk E → β1 | β2 | ... | βm (donde las β no pueden derivar en nada que empiece por E) E es: (β1 |β2 | . . . |βm )(α1 |α2 | . . . |αk )* Z → α1 Z | α2 Z | ... | αk Z | λ E → β1 Z | β2 Z | ... | βm Z