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 2002

$[\/]$

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 el siguiente autómata con estado inicial 0 y estado final 2:

a b ε

0 { 1 } { 2 }

1 { 0 } { 0, 2 } { 2 }

2 { 1 }

1.a) [0 pts] Haga el diagrama de este autómata.

1.b) [5 pts] Escriba una gramática LL(1) para este autómata. Explique qué es lo que hace.

1.c) [12 pts] Construya el autómata LL(1) para esta gramática.

1.d) [12 pts] Construya el autómata SLR(1) para esta gramática.

1.e) [4 pts] Muestre cómo se procesa la hilera "ababba" usando algunos de los dos autómatas que usted obtuvo anteriormente.

2) [33 pts] Considere la gramática G definida de la siguiente manera:

S -> S * U S -> * U T -> S T -> c U -> T y

2.a) [3 pts] Explique por qué esta gramática no es LL(1).

2.b) [12 pts] Convierta esta gramática a otra equivalente, que sí sea LL(1). Explique cómo transforma la gramática.

2.c) [12 pts] Construya el autómata LL(1) para esta gramática.

2.d) [6 pts] Escoga una hilera de al menos 7 símbolos que esté en el lenguaje L(G) y muestre cómo se procesa la hilera usando el autómata LL(1) que usted obtuvo en el punto anterior.

3) [33 pts] Considere el compilador que usted modificó en la primera tarea programada.

3.a) [7 pts] Explique porqué el método Compilador::aparea() del compilador de la primera tarea programada no necesita recibir como parámetro el siguiente token a procesar.

3.b) [7 pts] Explique cómo modificar el compilador para que construya el árbol de sintaxis que corresponde a la expresión evaluada.

3.c) [19 pts] Especifique, declare y defina las clases y métodos que se necesitan para que ese compilador construya el árbol de sintaxis que corresponde a la expresión evaluada.

4) [33 pts] Esta gramática es muy particular, pues es LL(1) pero no es SLR(1):

S --> G i G k S --> H k H i G --> ε H --> ε

4.a) [12 pts] Calcule la tabla LL(1) para esta gramática.

4.b) [12 pts] Calcule la tabla SLR(1) para esta gramática.

4.c) [3 pts] Muestren cómo se comporta el autómata LL(1) al reconocer la hilera "ik".

4.d) [6 pts] Muestren cómo se comporta el autómata LL(1) al reconocer la hilera "iiiiik".

Soluciones

$[/\]$