En la introducción al Analisis Sintactico Descendente (ASD) vimos como las implementaciones de los analizadores sintácticos recursivos con retroceso (ASDRR) podían producir programas sumamente ineficientes por el carácter no determinista de la solución subyacente.

Por ejemplo, en la siguiente gramática:

1. A → BC
2. B → e
3. B → DB
4. C → abb
5. D → a
6. D → b

observamos que, ante una configuración: (w$, Ba$) para hacer el análisis eficiente debíamos hacer la sustitución B → e solo si los siguientes cuatro símbolos en la entrada eran abb$, y la sustitución B → DB de lo contrario.

Es posible transformar la gramática en una equivalente de manera que el analizador recursivo resultante sea eficiente:

1. A → abb$
2. A → DA
3. D → a
4. D → b

Ante esta situación, debemos preguntarnos:

1. ¿Es siempre posible decidir cual es la producción (substitución ) correcta mirando los siguientes k símbolos de la secuencia entrada?
2. ¿Cómo sabemos cuántos símbolos debemos mirar (el valor de k)?

Gramáticas LL(k)

En general no es posible (no sabemos como) construir analizadores sintácticos eficientes para cualquier gramática. A pesar de eso, dada una Gramatica Independiente del Contexto y un entero k específico, si podemos hacer lo siguiente:

1. Determinar si para dicha gramática es posible decidir la producción correcta en casa paso de una derivación mirando solo los k símbolos siguientes en lo que resta de la secuencia de entrada.
2. Si la respuesta a lo anterior es si, podemos construir de manera sistemática una analizador sintáctico descendente determinista para esa gramática.

Las gramáticas para las cuales podemos decidir de manera inambigua la producción a utilizar en cada paso de una derivación mirando solo k símbolos de entrada se llaman gramáticas LL(k) y los lenguajes generados por esas gramáticas se llaman lenguajes LL(k). El nombre LL(k) significa lo siguiente:

• L: La entrada se examina de izquierda a derecha (Left to right).
• L: El análisis produce una derivación izquierda (Left derivation).
• k: El análisis se hace mirando a lo sumo k símbolos de lo que resta de la secuencia de entrada.

La mayoría de los lenguajes de programación de uso común se describen mediante gramáticas LL(1).

Se puede demostrar que para que una gramática G sea LL(k), G debe ser:

1. No-ambigua
2. Carente de recursión por la izquierda.

Determinar el valor de k es No-Decidible

Desafortunadamente, dada una gramática G no es posible en general darle respuesta a la pregunta: ¿Es G una gramática LL(k) para algún k? Más formalmente, la pregunta es no-decidible; es decir, la única manera de contestarla es probar (tal vez indefinidamente) con distintos valores de k hasta encontrar uno para el cual la gramática sea LL(k).

Ambigüedad, Recursión Izquierda, Prefijos Comunes, y LL(k)

A pesar de que el problema LL(k) es en general no-decidible, es fácil demostrar que ninguna gramática que posea alguna de las siguientes características es LL(k):

• La gramática es ambigua.
• La gramática es recursiva por la izquierda.
• La gramática posee prefijos comunes de longitud mayor o igual a k.

Por eso, antes de tratar de comprobar si una gramática es LL(k), primero eliminamos la recursión izquierda, y examinamos los prefijos comunes para decidir si debemos eliminarlos.

Definición Formal de LL(k)

Sea G=(N, S, P,S) una gramática inambigua y w=a₁a₂...a_n una sentencia o frase en L(G) (el lenguaje generado por G). Entonces (por la definición de ambigüedad) existe una secuencia única de formas sentenciales izquierdas α₀,α₁,..,α_n tal que:

S ⇒ α₀
α_i ⇒^* α_i+1
y
α_n=w

La derivación izquierda de w es entonces p₀,p₁,...,p_n, donde p_i es la producción con el número i. Deseamos encontrar dicha derivación conociendo solo:

• La secuencia de símbolos de entrada que ya hemos leído.
• La forma sentencial actual.
• Los siguientes k símbolos en la secuencia de entrada, para un k pequeño.

Dada una forma sentencial izquierda α=xβ, donde x ∈ Σ^* y β comienza por un no-terminal o es ε, decimos que x es la parte cerrada de α y que β es la parte abierta de α.

Función FIRST

Definimos la función FIRST_k(α) de la siguiente manera:

FIRST_k(α)= { w ∈ Σ^* | α ⇒^* wx, |w|=k ∨ x = ε }

La función FIRST_k(α) regresa el conjunto de prefijos de longitud k de las secuencias de terminales que pueden ser derivadas de α, o de longitud menor que k si α genera secuencias de terminales de longitud menor a k.

Función FOLLOW

Definimos la función FOLLOW_k(A) para A ∈ N de la siguiente manera:

FOLLOW_k(A)= { w ∈ Σ^* | S ⇒^* xAα ⇒ xβα, w ∈ FIRSK_k(α) }

Es decir, FOLLOW_k(A) es el conjunto de todas las secuencias de k símbolos que pueden seguir a los lados derechos de A en una derivación.

Definición de LL(k)

Dada una gramática libre de contexto G=(N, Σ, P,S), decimos que G es LL(k) para un entero dado k si siempre que hay dos derivaciones izquierdas:

S ⇒^* wAα ⇒ wβα ⇒^* wx
y
S ⇒^* wAα ⇒ wδα ⇒^* wy

y además:

FIRST_k(x) = FIRST_k(y)

entonces:

β=δ

Es decir, una gramáticas es LL(k) si dada una forma sentencial izquierda wAα y, z, los siguientes k símbolos a ser derivados de Aα (la parte abierta de la forma sentencial), entonces hay a lo sumo una única producción cuyo lado derecho puede ser sustituida por A para derivar una sentencia con prefijo wz.

k-Concatenacion

Definimos el operador ⋅_k de la siguiente manera:

x⋅_ky = los primeros k símbolos de x⋅y, o x⋅y si |x⋅y| < k

Si L y M son subconjuntos de Σ^*, entonces definimos:

L ⋅_k M = { x ⋅_k y | x ∈ L ∧ y ∈ M }

Gramáticas Fuertemente LL(k)

Una gramática es fuertemente LL(k) si para todo par de producciones A → α y A → β en P se cumple que:

FIRST_k(α FOLLOW_k(A)) ∩ FIRST_k(β FOLLOW_k(A)) = ∅

también:

FIRST_k(α) ⋅_k FOLLOW_k(A) ∩ FIRST_k(β) ⋅_k FOLLOW_k(A) = ∅

Todas las gramáticas LL(1) son fuertemente LL(1), pero no todas las gramáticas LL(k) con k > 1 son fuertemente LL(k). Por ejemplo, la siguiente gramática es LL(2) (cumple con la definición de LLk para k=2), pero no es fuertemente LL(2):

S → aAaa | bAba
A → b | ε

El lenguaje generado por esa gramática es:

abaa
aaa
bbba
bba

Secuencias Predictivas para Lenguajes Fuertemente LL(k)

Las secuencias predictivas para las producciones A → α son las concatenaciones:

LA_k(A → α) = FIRST_k(α) ⋅_k FOLLOW_k(A)

Dichas secuencias indican que cuando:

1. A está en el tope de la pila
2. El símbolo en la secuencia de entrada pertenece a LA_k(A → α).

La producción a emplear en ese paso de la derivación es sin duda A → α.

Cálculo de FIRST_k(α)

Calculamos FIRST_k(X), para todo X ∈ (Σ ∪ N) de la siguiente manera:

1. foreach a ∈ Σ do
        F(a) := {a}
2. for each A ∈ N do
        if A→ε ∈ P then
             F(A) := {ε}
        else
             F(A) := ∅
3. repeat
        for each A ∈ N do
             F'(A) := F(A)
        for each A → X₁X₂...X_n ∈ P do
             if n > 0 then
                  F(A) := F(A) ∪ F'(X1) ⋅_k F'(X2) ⋅_k ... ⋅_k F'(Xn)
   until F(A) = F'(A) forall A ∈ N
4. FIRST_k(X) := F(X) forall X ∈ (Σ ∪ N)

Como F(A) ∈ Σ^0..k, y Σ^0..k es finito, entonces debemos llegar a un punto en el cual todo F(A)=F'(A) (en que ninguno de los conjuntos crece) para todo A ∈ N. Entonces nos detenemos, y hacemos FIRST_k(A) = F(A).

Nótese que:

FIRST_k(αβ) = FIRST_k(α) ⋅_k FIRST_k(β)

Entonces, calculamos FIRST_k(α), donde α=Y₁Y₂...Y_n de la siguiente manera:

FIRST_k(α) = FIRST_k(Y₁) ⋅_k FIRST_k(Y₂) ⋅_k ... ⋅_k FIRST_k(Y_n)

o

FIRST_k(α) = FIRST_k(Y₁ ⋅ FIRST_k(Y₂ ⋅ ... ⋅ FIRST_k(Y_n)))

Cálculo de FOLLOW_k(α)

1. FL(S) := {ε}
2. for each A ∈ N - {S} do
        FL(A) := ∅
3. repeat
        foreach A ∈ N do
             FL'(A) := FL(A)
        foreach A → X₁X₂...X_n ∈ P do
             L := FL'(A)
             for i := n downto 1 do
                  L := FIRST_k(X_i+1)⋅_k L
                  if X_i ∈ N then
                       FL(X_i) := FL(X_i) ∪ L
             end for
        end for
   until FL(A) = FL'(A) ∀ A ∈ N
4. FOLLOW_k(A) := FL(A)

Otra versión del mismo algoritmo es:

1. FL(S) := {ε}
2. for each A ∈ N - {S} do
        FL(A) := ∅
3. repeat
        foreach A ∈ N do
             FL'(A) := FL(A)
        foreach A → X₁X₂...X_n ∈ P do
             for i := n downto 1 do
                  if X_i ∈ N then
                       FL(X_i) := FL(X_i) ∪ FIRST_k(X_i+1) ⋅_k FIRST_k(X_i+2) ⋅_k ... ⋅_k FIRST_k(X_n) ⋅_k FL'(A)
             end for
        end for
   until FL(A) = FL'(A) ∀ A ∈ N
4. FOLLOW_k(A) := FL(A)

Cálculo se Secuencias Predictivas

Dada una Gramatica G=(Σ N, P, S) obtenemos la secuencia predictiva Fuertemente LLk para cada producción A → α ∈ P así:

LA_k(A → α) = FIRST_k(α) ⋅_k FOLLOW_k(A)

Cálculo de la Tabla de Análisis Predictivo (Tabla LA)

Una tabla de análisis predictivo (Look-Ahead Table, o LA Table) para una Gramatica Fuertemente LLk se genera de la siguiente manara.

1. Agregamos una fila por cada símbolo X ∈(Σ ∪ N).
2. Agregamos una columna por cada secuencia w ∈ Σ^k.
3. En casa casilla (a ∈ Σ, ax) colocamos pop.
4. En cada casilla (A ∈ N, w), colocamos β/i si A → β es la producción i, y w ∈ LA_k(A → β).
5. Dejamos el resto de las casillas en blanco, o colocamos error en las mismas.

Ejemplo LL(2)

Consideremos la siguiente Gramatica:

S → A
A → aAd | BC
B → bBc | ε
C → acC | ad

Primero reescribimos la gramática numerando las producciones:

1. S → A
2. A → aAd
3. A → BC
4. B → bBc
5. B → ε
6. C → acC
7. C → ad

Cálculo de FIRST₂

Los conjuntos F(X) iniciales según el algoritmo de cálculo de la fución FIRST son:

F₀(S) = ∅
F₀(A) = ∅
F₀(B) = {ε}
F₀(C) = ∅

Cada iteración del algoritmo de cálculo de la fución FIRST lleva a cabo las siguientes operaciones:

F_n(S) = F_n-1(S) ∪ F_n-1(A)
F_n(A) = F_n-1(A) ∪ {a} ⋅₂ F_n-1(A) ⋅₂ {d}
F_n(A) = F_n-1(A) ∪ F_n-1(B) ⋅₂ F_n-1(C)
F_n(B) = F_n-1(B) ∪ {b} ⋅₂ F_n-1(B) ⋅₂ {c}
F_n(C) = F_n-1(C) ∪ {a} ⋅₂ {c} ⋅₂ F_n-1(C) = F_n-1(C) ∪ {ac}
F_n(C) = F_n-1(C) ∪ {a} ⋅₂ {d} = F_n-1(C) ∪ {ad}

Y las simplificamos así:

F_n(S) = F_n-1(S) ∪ F_n-1(A)
F_n(A) = F_n-1(A) ∪ {a} ⋅₂ F_n-1(A) ⋅₂ {d} ∪ F_n-1(B) ⋅₂ F_n-1(C)
F_n(B) = F_n-1(B) ∪ {b} ⋅₂ F_n-1(B) ⋅₂ {c}
F_n(C) = F_n-1(C) ∪ {ac,ad}

Calculamos FIRST⋅₂(X) para todo X ∈ N iterativamente, de la siguiente manera:

Cálculo de FOLLOW₂

Los conjuntos FL(X) iniciales según el algoritmo de cálculo de la función FOLLOW_k son:

FL₀(S) = {$}
FL₀(A) = ∅
FL₀(B) = ∅
FL₀(C) = ∅

Cada iteración del algoritmo de cálculo de la fución FOLLOW_k lleva a cabo las siguientes operaciones:

FL_n(A) = FL_n-1(A) ∪ FL_n-1(S)
FL_n(A) = FL_n-1(A) ∪ FIRST₂({d}) ⋅₂ FL_n-1(A) = FL_n-1(A) ∪ {d} ⋅₂ FL_n-1(A)
FL_n(C) = FL_n-1(C) ∪ FL_n-1(A)
FL_n(B) = FL_n-1(B) ∪ FIRST₂(C) ⋅₂ FL_n-1(A) = FL_n-1(B) ∪ {ac,ad} ⋅₂ = FL_n-1(B) ∪ {ac,ad} = FL_n-1(B) ∪ {ac,ad}
FL_n(B) = FL_n-1(B) ∪ FIRST₂({c}) ⋅₂ FL_n-1(B) = FL_n-1(B) ∪ {c} ⋅₂ FL_n-1(B)

Simplificando:

FL_n(A) = FL_n-1(A) ∪ FL_n-1(S)
FL_n(A) = FL_n-1(A) ∪ {d} ⋅₂ FL_n-1(A)
FL_n(C) = FL_n-1(C) ∪ FL_n-1(A)
FL_n(B) = FL_n-1(B) ∪ {ac,ad} ∪ {c} ⋅₂ FL_n-1(B)

Calculamos FOLLOW₂(X) para todo X ∈ N iterativamente, de la siguiente manera:

Cálculo de secuencias predictivas LA₂

Las secuencias predictivas para las producciones *X → β son:

LA₂(X → β) = FIRST₂(β) ⋅₂ FOLLOW₂(X)

Dado que:

Construimos las Secuencias Predictivas así:

Tabla de Análisis Sintáctico Descendente Predictivo

Para cada X ∈ N y cada secuencia w ∈ Σ² colocamos el lado derecho y el número de la producción correspondiente en la celda correspondiente. Podemos también colocar filas para los símbolos terminales aunque el contenido de las celdas asociadas sea obvio:

Ejemplo LL(1)

Sea la gramática:

S → L
L → P o L | P
P → n f D
D → D t | D n | ε

Transformaciones requeridas

Primero eliminamos la recursión izquierda:

S → L
L → P o L | P
P → n f D
D → D'
D' → t D' | n D' | ε

Simplificamos sustituyendo D por D':

S → L
L → P o L | P
P → n f D
D → t D | n D | ε

Ahora eliminamos el prefijo común P en las producciones con lado izquierdo L:

S → L
L → P L'
L' → o L | ε
P → n f D
D → t D | n D | ε

Numeramos las producciones:

1. S → L
2. L → P L'
3. L' → o L
4. L' → ε
5. P → n f D
6. D → t D
7. D → n D
8. D → ε

Cálculo de FIRST₁

Los conjuntos iniciales F(A), A ∈ N, son:

F₀(S) = ∅
F₀(L) = ∅
F₀(L') = {ε}
F₀(P) = ∅
F₀(D) = {ε}

Producimos las fórmulas para FIRST₁(A), A ∈ N:

F_n(S) = F_n-1(S) ∪ F(L)
F_n(L) = F_n-1(L) ∪ F(P) ⋅₁ F(L')
F_n(L') = F_n-1(L') ∪ {o} ⋅₁ F(L) = {o}
F_n(L') = F_n-1(L') ∪ {ε}
F_n(P) = F_n-1(P) ∪ {n} ⋅₁ {f} ⋅₁ F(D) = {n}
F_n(D) = F_n-1(D) ∪ {t} ⋅₁ F(D) = {t}
F_n(D) = F_n-1(D) ∪ {n} ⋅₁ F(D) = {n}
F_n(D) = F_n-1(D) ∪ {ε}

Y las simplificamos así:

F_n(S) = F_n-1(S) ∪ F(L)
F_n(L) = F_n-1(L) ∪ F(P) ⋅₁ F(L')
F_n(L') = {o, ε}
F_n(P) = {n}
F_n(D) = {t,n,ε}

Calculamos FIRST₁(A) , A ∈ N:

Cálculo de FOLLOW₁

Los conjuntos iniciales FL(A), A ∈ N, son:

FL₀(S) = {ε}
FL₀(L) = ∅
FL₀(L') = ∅
FL₀(P) = ∅
FL₀(D) = ∅

Producimos las fórmulas para FOLLOW₁(A), A ∈ N:

FL_n(L) = FL_n-1(L) ∪ FL(S)
FL_n(L') = FL_n-1(L') ∪ FL(L)
FL_n(P) = FL_n-1(P) ∪ FIRST1(L') ⋅₁ FL(L)
FL_n(L) = FL_n-1(L) ∪ FL(L')
FL_n(D) = FL_n-1(D) ∪ FL(P)

Calculamos FOLLOW₁(X), X ∈ N:

Secuencias predictivas

Calculamos las secuencias predictivas LA(p), p ∈ P:

Tabla de análisis sintáctico LA₁

Calculamos la tabla LA₁(A,w), para todo A ∈ N y w ∈&SIGMA;¹: