CI-1322 Examen Final


  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 de Ampliación [solución]

Duración: dos horas. Lea bien el examen antes de hacerlo. 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+1 símbolos separando a el símbolo "1" de otro "1", con i ≥ 1.

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 -> id = E (2) E -> E or T (3) E -> T (4) T -> T and F (5) T -> F (6) F -> id (7) F -> ( E )

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

$[/\]$