Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
Profesor Adolfo Di Mare
CI-1322
I Semestre 2002
[<=] [home] [<>] [\/] [=>]
CI-1322 Autómatas y compiladores

Examen Final [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 todas las preguntas. ¡No haga más de lo que se le pide!

 

1) [33 pts] Es bien sabido que si ya se cuenta con un autómata determinista (sin movimientos ε) que reconoce el lenguaje L, es fácil obtener el autómata complementario, que reconoce Σ*-L: basta cambiar en L los estados finales por no finales, y los no finales por finales.

1.a) [5 pts] Haga el diagrama del autómata L3 que reconozca hileras en el alfabeto Σ = {0,1} en las que aparecen 3*i símbolos separando a el símbolo "1" de otro "1", con i ≥ 0.

1.b) [14 pts] Encuentre el autómata noL3 que reconoce el lenguaje complementario de L3, esto es, el autómata que cumple estas condiciones: (Σ* = L3 U noL3) & (Σ* - L3 = noL3) & (L3 ∩ noL3 =Θ)

1.c) [14 pts] Minimice el autómata noL3. Muestre el diagrama final del autómata minimizado.

1.d) [0 pts] Recuerde que siempre debe explicar y justificar lo que hace al resolver cada pregunta.

 

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

2.a) [0 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.

2.b) [0 pts] Escoga un expresión que tenga al menos 10 tokens, incluidos ahí algunos paréntesis, y muestre el árbol de sintáxis para esa expresión. (No se moleste en dibujar el árbol de análisis sintáctico).

2.c) [4 pts] Explique cómo modificar el compilador para que construya el árbol de sintaxis que corresponde a la expresión evaluada. No use la hilera en formato posfijo que produce el compilador.

2.d) [10 pts] Haga un programa Lex/Flex que sirva para obtener los tokens del compilador.

2.e) [4 pts] Declare las clases y métodos que se necesitan para que ese compilador construya el árbol de sintaxis que corresponde a al expresión evaluada.

2.f) [15 pts] Modifique el compilador para que, en lugar de evaluar la expresión, produzca el árbol de sintáxis para la expresión.

 

3) [33 pts] Considere la gramática G cuyas producciones son las siguientes:
(1)   A -> M = E
(2)   M -> id
(3)   E -> E + T
(4)   E -> T
(5)   T -> T * F
(6)   T -> F
(7)   F -> ( E )
(8)   F -> M

3.a) [3 pts] Suponga que ha construido la tabla LL(1) para esta gramática: ¿Qué forma especial tendría? ¿Por qué?

3.b) [6 pts] Calcule los conjuntos Primero() y Siguiente() para los no terminales de G.

3.c) [14 pts] Construya la tabla SLR(1) para G. ¿Es G una gramática SLR(1)?

3.d) [0 pts] Si en la tabla SLR(1) para G hay conflictos, elimínelos usando estas dos reglas: a) Deje el desplazamiento en lugar de una reducción y b) Deje la reducción que corresponde a la producción que está primero.

3.e) [10 pts] Escoja una hilera del lenguaje L(G) que tenga al menos 10 terminales y que incluya todos los terminales de la gramática. Muestre cómo la procesa el analizador SLR(1) con la tabla que construyó anteriormente.

 

Soluciones

[mailto:] Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2002
Derechos de autor reservados © 2002
[home] <> [/\]