Segundo Parcial 1C 2012 (Teoría de Lenguajes)

Ejercicio 1

Dada la gramática extendida: $G1=<\{a,b,c,d,e\},\{S,A,B,C,D\},P,S>$ con P:

• $S\rightarrow B$
• $B\rightarrow BbDda\ |\ a$
• $D\rightarrow (e(ce)*\ |\ B)^{+}$

a) Dar una gramática LL(1) que reconozca el mismo lenguaje que G1.

b) Dar la implementación del parser recursivo iterativo ELL(1) para los no terminales B y D de la gramática original.

Ejercicio 2

Dada la gramática $G=<\{x,a,b\},\{S',S,A\},P1,S'>$, con P1:

• $S'\rightarrow S\$$
• $S\rightarrow A\ |\ xb$
• $A\rightarrow aAb\ |\ x$

Decidir si G es SLR. Para eso, construir la tabla. De haber conflictos, solucionarlos modificando la tabla, pero no la gramática.

Ejercicio 3

Dado un generador de notas de canciones (en cifrado estadounidense), se solicita agregarle una funcionalidad que permita detectar la presencia de versos de distintas cancione conocidas y rechazar algunas melodías que no satisfacen ciertas características.

Dados dos versos de cada una de las famosas canciones Funky Town y Low Rider:

FunkyTown(FT): ccacg - gcfec LowRider(LR): bbbbbcdg - bcbg

y la gramática G2, se pide dar una gramática de atributos que sintetice:

a) la cantidad de versos de cada canción (FT y LR) contenidos en una canción dada.

b) la cantidad de versos que no son de ninguna de estas canciones (FT,LR).

Además, se solicita que las canciones generadas sean de tal forma que no puedan aparecer versos contiguos de FT y de LR (dados versos de distinta canción, entre ellos tiene que haber al menos un verso que no pertenezca a ninguna de ellas).

$G2=<\{-,a,b,c,d,e,f,g\},\{M,T,A,B,C\},M,P3>$ con P3:

• $M\rightarrow T-M\ |\ \lambda$
• $T\rightarrow AcBC$
• $A\rightarrow bbbbb\ |\ b\ |\ c\ |\ g$
• $B\rightarrow d\ |\ b\ |\ ac\ |\ fe$
• $C\rightarrow g\ |\ c$

Ejemplos:

• ccacg-gcfec-bbbbbcdg-bcbg- no es una canción generable, dado que no hay un verso de otra canción que separe cgfec-bbbbbcdg.
• gcfec-ccbc-bcbg-bbbbbcdg-ccbc-gcbc- es una canción posible. Devuelve 2 versos de LR, 1 verso de FT y 3 versos que no son de ninguna de ellas.

Notas:

• Dos versos iguales cuentan como 2, no como 1.
• Se puede asumir que se cuenta con una función de igualdad de strings.