Práctica 9: Parsers descendentes (Teoría de Lenguajes)

Ejercicio 01

Para cada una de las siguientes gramáticas:

1. Decir si es LL(1) verificando la condición correspondiente
2. Decir si es LL(1) construyendo la tabla correspondiente
3. Para las que no seas LL(1), intentar hacer alguna modificación a la gramática (por ejemplo, factorizar), de tal modo que se conviertan en otras que lo sean).

Hacer el seguimiento del reconocimiento de una cadena por un parser LL(1) para alguna de las gramáticas.

(a)
S -> aAS | b
A -> a | bSA

(b)
S -> aaSbb | a | λ

(c)
S -> A | B
A -> aA | λ
B -> bB | λ

(d)
S -> aAaa | bAba
A -> b | λ

(e)
S -> aS | a
A -> Sd | d

Resolución:

a) 1. Verificamos que sea LL(1) (ver definición) mirando sus símbolos directrices:

Símbolos no terminales	¿Es anulable?	primeros	siguientes
S	No	{a,b}	{a,b}
A	No	{a,b}	{a,b}

I) SD(S -> aAs) = primeros(aAs) = {a}
II) SD(S -> b) = primeros(b) = {b}
III) SD(A -> a) = primeros(a) = {a}
IV) SD(A -> bSA) = primeros(bSA) = {b}

Como $I\cap II=III\cap IV=\emptyset$ entonces la gramática es LL(1)

a) 2. Creamos la tabla poniendo en cada casilla la producción que nos permite obtener como primer símbolo el terminal de la columna partiendo del no terminal de la fila:

Símbolos no terminales	a	b
S	S -> aAS	S -> b
A	A -> a	A -> bSA

Como no hay entradas con mas de una producción en las tablas entonces la gramática es LL(1)

b) 1. Realizamos el mismo chequeo:

Símbolos no terminales	¿Es anulable?	primeros	siguientes
S	Si	{a}	{b}

I) SD(S -> aaSbb) = primeros(aAs) = {a}
II) SD(S -> a) = primeros(a) = {a}

Como $I\cap II=\{a\}$ entonces la gramática NO es LL(1)

b) 2. Creamos la tabla que utiliza el analizador sintáctico:

Símbolos no terminales	a	b
S	S -> aaSbb, S -> a	S -> aaSbb

Como hay una entrada con mas de una producción entonces la gramática NO es LL(1)

c) Es LL(1), similar a a) solo que los no terminales son anulables entonces hay que calcular los siguientes para obtener los símbolos directrices.

d)

e)

Ejercicio 02

Para cada una de las gramáticas del ejercicio 1 escribir un parser recursivo descendente.

Resolución:

Cuando nos piden hacer un parser recursivo descendente la idea es hacer un procedure por no terminal que fuerce la cadena a seguir los patrones indicados por las producciones. Resolvemos este ejercicio para el item 'c' como ejemplo:

Proc S() {
   switch (tc):
       case 'a':
           A();
       case 'b':
           B();
       case default:
           error();    
}

Proc A() {
     switch (tc):
          case 'a':
              match('a');
              A();
          case default:
              error();
}

Proc B() {
     switch (tc):
         case 'b':
             match('b');
             B();	
         case default:
             error();	
}

Ejercicio 03

Para cada Gi:

1. Decidir si es LL(1). En ese caso construir su tabla LL(1). En caso contrario dar una gramática que sea LL(1) y genere L(Gi) y construir su tabla LL(1).
2. Reconocer las cadenas que se indican mediante el método LL(1).

a) G1 = <{S,A};{a,c};P1;S>, con P1:

S -> Sc | cA | λ
A -> aA | a

alfa1 = caac

b) G2 = <{S,P,M,T,L};{para,aprobar,desaprobar,de,otras,materias,teoria,lenguajes};P2;S>, con P2:

S -> PM
P -> para aprobar | para desaprobar
M -> T de L | otras materias
T -> teoria
L -> lenguajes

alfa2 = "para aprobar teoria de lenguajes".

c) G3 = <{S,A,L};{(,),,,f,x};P3;S>, con P3:

S -> fA
A -> (L)
L -> x | x,L | S

alfa3 = f(x,f(x))

d) G4 = <{S,A};{a,b};P4;S>, con P4:

S -> SAa | aA
A -> Aa | b

alfa4 = baaba

e) G5 = <{S,T};{a,b};P5;S>, con P5:

S -> b | Sb | Tb
T -> aTb | ab

alfa5 = aaabb, beta = aaabbbbb

Resolución:

a)

b)

c)

d) Esta gramática NO es LL(1). Como es recursiva a izquierda aplicamos desrecursivización a las producciones:

S -> SAa           S  -> AaS'
S -> Aa     ==>    S' -> AaS'
                   S' -> λ

A -> Aa            A  -> bA'
A -> b      ==>    A' -> aA'
                   A' -> λ

NOTA: Lo que viene a continuación es una resolucion que supone que la gramática resultante es LL(1). Esto no es cierto pues la intersección entre SD(A' -> aA') y SD(A' -> λ) es no vacía. Hasta el momento no se ha encontrado una forma de hacer LL(1) esta gramática. Por favor colaborá poniendo la solución correcta si la encontrás.

PRINCIPIO DE RESOLUCIÓN INCORRECTA:

La gramática resultante es LL(1). Creamos la tabla LL(1):

Símbolos no terminales	¿Es anulable?	primeros	siguientes
S	No	{b}	{}
S'	Si	{b}	{$}
A	No	{b}	{a}
A'	Si	{a}	{a}

Símbolos no terminales	a	b
S		S -> AaS'
S'		S' -> AaS'
A		A -> bA'
A'	A' -> aA'

FIN DE RESOLUCIÓN INCORRECTA.

El problema de esta resolucion es que copio mal una produccion la de S -> SAa | aA (no Aa como puso). Este error hace que no haya simbolos directrices en comun en las producciones de A': A' -> lambda y A' -> aA', ya que SIGUIENTES(A')={b} Entonces SD(A'->aA') = {a} y SD(A' -> lambda) = {b}

e) Esta gramática no es LL(1), hay que aplicar desrecursivización y factorización.

Ejercicio 04

A veces es posible utilizar un parser LL(1) para reconocer una gram'atica que no lo es. Esto puede realizarse tomando algunas decisiones en el momento de construir la tabla. Por ejemplo, la siguiente gram'atica representa el problema del if - then - else:

G1 = < { S, E, C }; { if, then, sent, else, cond }; P; S >

S --> if C then S E | sent
E --> else S | lambda
C --> cond

1. Mostrar que G1 no es LL(1).
2. Construir la tabla LL(1) para G1.
3. En los lugares donde haya conflicto, modificar la tabla eligiendo una de las entradas de manera que cada else quede asociado con el if m'as cercano. Justificar.
4. Mostrar un parseo top-down y el 'arbol de derivaci'on resultante para: if cond then if cond then sent else sent.

Resolución:

1. G1 no es LL(1)

Podemos ver que G1 no es LL(1). dado que el token "else" pertenece a los s'imbolos directrices de ambas producciones de E. Puede no resultar obvio para la producci'on E --> lambda, pero queda claro si tomamos por ejemplo la siguiente forma sentencial:

if C then if C then sent E E --> if cond then if cond then sent E else sent

2. Tabla LL(1) para G1

	if	then	sent	cond	else
S	S --> if C then S E		S --> sent
E					E --> else S, E --> lambda
C				C --> cond