This page last changed on Nov 15, 2006 by juanca.

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=a1a2...an 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 α01,..,αn tal que:

S ⇒ α0
αi* αi+1
y
αn=w

La derivación izquierda de w es entonces p0,p1,...,pn, donde pi 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 FIRSTk(α) de la siguiente manera:

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

La función FIRSTk(α) 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 FOLLOWk(A) para A ∈ N de la siguiente manera:

FOLLOWk(A)= { w ∈ Σ* | S ⇒* xAα ⇒ xβα, w ∈ FIRSKk(α) }

Es decir, FOLLOWk(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:

FIRSTk(x) = FIRSTk(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 (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:

FIRSTk(α FOLLOWk(A)) ∩ FIRSTk(β FOLLOWk(A)) = ∅

también:

FIRSTk(α) ⋅k FOLLOWk(A) ∩ FIRSTk(β) ⋅k FOLLOWk(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:

LAk(A → α) = FIRSTk(α) ⋅k FOLLOWk(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 LAk(A → α).

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

Cálculo de FIRSTk(α)

Calculamos FIRSTk(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 → X1X2...Xn ∈ 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. FIRSTk(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 FIRSTk(A) = F(A).

Nótese que:

FIRSTk(αβ) = FIRSTk(α) ⋅k FIRSTk(β)

Entonces, calculamos FIRSTk(α), donde α=Y1Y2...Yn de la siguiente manera:

FIRSTk(α) = FIRSTk(Y1) ⋅k FIRSTk(Y2) ⋅k ... ⋅k FIRSTk(Yn)

o

FIRSTk(α) = FIRSTk(Y1 ⋅ FIRSTk(Y2 ⋅ ... ⋅ FIRSTk(Yn)))

Cálculo de FOLLOWk(α)

  1. FL(S) := {ε}
  2. for each A ∈ N - {S} do
         FL(A) := ∅
  3. repeat
         foreach A ∈ N do
              FL'(A) := FL(A)
         foreach A → X1X2...Xn P do
              L := FL'(A)
              for i := n downto 1 do
                   L := FIRSTk(Xi+1)⋅k L
                   if Xi ∈ N then
                        FL(Xi) := FL(Xi) ∪ L
              end for
         end for
    until FL(A) = FL'(A) A ∈ N
  4. FOLLOWk(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 → X1X2...Xn P do
              for i := n downto 1 do
                   if Xi ∈ N then
                        FL(Xi) := FL(Xi) ∪ FIRSTk(Xi+1) ⋅k FIRSTk(Xi+2) ⋅k ... ⋅k FIRSTk(Xn) ⋅k FL'(A)
              end for
         end for
    until FL(A) = FL'(A) A ∈ N
  4. FOLLOWk(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í:

LAk(A → α) = FIRSTk(α) ⋅k FOLLOWk(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 ∈ LAk(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 FIRST2

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

F0(S) = ∅
F0(A) = ∅
F0(B) = {ε}
F0(C) = ∅

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

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

Y las simplificamos así:

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

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

  F(S) F(A) F(B) F(C)
0 {ε}
1 {ε,bc} {ac,ad}
2 {ac,ad,bc} {ε,bc,bb,ba} {ac,ad}
3 {ac,ad,bc} {ac,ad,bc,aa,ab} {ε,bc,bb,ba} {ac,ad}
4 {ac,ad,bc,aa,ab} {ac,ad,bc,aa,ab,bb,ba} {ε,bc,bb,ba} {ac,ad}
5 {ac,ad,bc,aa,ab,bb,ba} {ac,ad,bc,aa,ab,bb,ba} {ε,bc,bb,ba} {ac,ad}
6 {ac,ad,bc,aa,ab,bb,ba} {ac,ad,bc,aa,ab,bb,ba} {ε,bc,bb,ba} {ac,ad}

Cálculo de FOLLOW2

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

FL0(S) = {$}
FL0(A) = ∅
FL0(B) = ∅
FL0(C) = ∅

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

FLn(A) = FLn-1(A) ∪ FLn-1(S)
FLn(A) = FLn-1(A) ∪ FIRST2({d}) ⋅2 FLn-1(A) = FLn-1(A) ∪ {d} ⋅2 FLn-1(A)
FLn(C) = FLn-1(C) ∪ FLn-1(A)
FLn(B) = FLn-1(B) ∪ FIRST2(C) ⋅2 FLn-1(A) = FLn-1(B) ∪ {ac,ad} ⋅2 = FLn-1(B) ∪ {ac,ad} = FLn-1(B) ∪ {ac,ad}
FLn(B) = FLn-1(B) ∪ FIRST2({c}) ⋅2 FLn-1(B) = FLn-1(B) ∪ {c} ⋅2 FLn-1(B)

Simplificando:

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

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

  FL(S) FL(A) FL(B) FL(C)
0 {ε}
1 {ε} {ε} {ad,ac,ca} {ε}
2 {ε} {ε,d} {ad,ac,ca,cc} {ε,d}
3 {ε} {ε,d,dd} {ad,ac,ca,cc} {ε,d,dd}
4 {ε} {ε,d,dd} {ad,ac,ca,cc} {ε,d,dd}

Cálculo de secuencias predictivas LA2

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

LA2(X → β) = FIRST2(β) ⋅2 FOLLOW2(X)

Dado que:

  FIRST2 FOLLOW2
S {ac,ad,bc,aa,ab,bb,ba} {ε}
A {ac,ad,bc,aa,ab,bb,ba} {ε,d,dd}
B {ε,bc,bb,ba} {ad,ac,ca,cc}
C {ad,ac} {ε,d,dd}

Construimos las Secuencias Predictivas así:

i X → β FIRST2(β) ⋅2 FOLLOW2(X) LA2(X → β)
1 S → A FIRST2(A) ⋅2 FOLLOW2(S) {ac,ad,bc,aa,ab,bb,ba}
2 A → aAd FIRST2(aAd) ⋅2 FOLLOW2(A) {aa,ab}
3 A → BC FIRST2(BC) ⋅2 FOLLOW2(A) {bc,bb,ba,ad,ac}
4 B → bBc FIRST2(bBc) ⋅2 FOLLOW2(B) {bb,bc}
5 B → ε FIRST2(ε) ⋅2 FOLLOW2(B) {ad,ac,ca,cc}
6 C → acC FIRST2(acC) ⋅2 FOLLOW2(C) {ac}
7 C → ad FIRST2(ad) ⋅2 FOLLOW2(C) {ad}

Tabla de Análisis Sintáctico Descendente Predictivo

Para cada X ∈ N y cada secuencia w ∈ Σ2 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:

  ε a b c d aa ab ac ad ba bb bc bd ca cb cc cd da db dc dd
S           A/1 A/1 A/1     A/1                    
A               ε/5 ε/5   bBc/4 bBc/4   ε/5   ε/5          
B               acC/6 ad/7                        
C                 acC/6 ad/7                      
a   pop       pop pop pop pop                        
b     pop             pop pop pop pop                
c       pop                   pop pop pop pop        
d         pop                         pop pop pop pop

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 FIRST1

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

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

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

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

Y las simplificamos así:

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

Calculamos FIRST1(A) , A ∈ N:

F S L L' P D
0 {ε} {ε}
1     {o,ε} {n} {t,n,ε}
2   {n} {o,ε} {n} {t,n,ε}
3 {n} {n} {o,ε} {n} {t,n,ε}
3 {n} {n} {o,ε} {n} {t,n,ε}

Cálculo de FOLLOW1

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

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

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

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

Calculamos FOLLOW1(X), X ∈ N:

  S L L' P D
0 {ε}
1 {ε} {ε} {ε} {o,ε} {ε}
2 {ε} {ε} {ε} {o,ε} {o,ε}

Secuencias predictivas

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

i A → β FIRST1(β) ⋅1 FOLLOW1(A) LA(A → β)
1 S → L FIRST1(L) ⋅1 FOLLOW1(S) {n}
2 L → P L' FIRST1(PL')⋅1 FOLLOW1(L) {n}
3 L' → o L FIRST1(oG) ⋅1 FOLLOW1(L') {o}
4 L' → ε FIRST1(ε) ⋅1 FOLLOW1(S) {ε}
5 P → n f D FIRST1(nfD)⋅1 FOLLOW1(P) {n}
6 D → t D FIRST1(tD) ⋅1 FOLLOW1(D) {t}
7 D → n D FIRST1(nD) ⋅1 FOLLOW1(D) {n}
8 D → ε FIRST1(ε) ⋅1 FOLLOW1(D) {o,ε}

Tabla de análisis sintáctico LA1

Calculamos la tabla LA1(A,w), para todo A ∈ N y w ∈&SIGMA;1:

  ε n o f t
S   L/1      
L   PL'/2      
L' ε/4   oG/3    
P   nfD/5      
D ε/8 nD/7 ε/8   tD/6
n   pop      
o     pop    
f       pop  
t         pop
Document generated by Confluence on Oct 04, 2010 11:24