CI-1322 Examen #2


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
I Semestre 2001

$[\/]$

CI-1322 Autómatas y compiladores

Examen #2 [solución]

Duración: dos horas. Lea bien el examen antes de hacerlo. El examen es a libro abierto. Cuenta la redacción y la ortografía. Puede hacer el examen con lápiz. Resuelva tres de las cuatro preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] Considere los lenguajes L(G₁) y L(G₂) definidos de la siguiente manera:

L(G₁) = { aⁿb^n+r / n>0 & r>0 }
L(G₂) = { a^n+rbⁿ / n>0 & r>0 }

1.a) [11 pts] Escriba las gramáticas libres de contexto G₁ y G₂ para L(G₁) y L(G₂).

1.b) [11 pts] Muestre que tanto G₁ como G₂ son LL(1).

1.c) [2 pts] Escriba la gramática libre de contexto para L(G₁) U L(G₂).

1.d) [9 pts] ¿Es la gramática de L(G₁) U L(G₂) una gramática LL(1)?

2) [33 pts] Considere el lenguaje de paréntesis anidados, en que las hileras tienen esta forma: [] () [[[]]] ((())) [([ ([( )]) ])]

2.a) [11 pts] Escriba una gramática LL(1) que sirva para generar todas las hileras de paréntesis anidados. Evite que la hilera nula sea generada.

2.b) [11 pts] Encuentre las tablas que un analizador sintáctico LL(1) usaría para reconocer hileras este lenguaje.

2.c) [11 pts] Muestre cómo un analizador sintáctico que use las tablas que usted calculó reconocería la siguiente hilera (suponga que el analizador léxico salta sobre los espacios en blanco):

[] () [[]] (()) [([ ])]

3) [33 pts] El lenguaje C tiene una instrucción con la siguiente forma: for ( exp₁; exp₂; exp₃ ) { stmt }

3.a) [11 pts] Haga un diagrama en el que muestre cómo debe quedar compilado este código.

3.b) [22 pts] Escriba un esquema de traducción por sintaxis que transforme un ciclo for en código objeto para una máquina de pila.

4) [33 pts] La gramática Gno parece remediar el problema de ambigüedad del "else":

stmt   ==> if expr then stmt
         | m_stmt
m_stmt ==> if expr then m_stmt else stmt
         | other

4.a) [11 pts] Encuentre las tablas que un analizador sintáctico LL(1) usaría para reconocer hileras de L(Gno).

4.b) [8 pts] Muestre que la gramática Gno no es LL(1): encuentre una hilera que tenga dos derivaciones más izquierdas. Dibuje los dos árboles de derivación para la hilera.

4.c) [3 pts] Arregle esta gramática para solucionar el problema de ambigüedad del "else". Explique por qué su gramática sí soluciona el problema, en contraposición a Gno .

4.d) [11 pts] Encuentre las tablas que un analizador sintáctico LL(1) usaría para reconocer hileras generados con su gramática.

Soluciones

$[/\]$