CI-1322 Examen Final


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
II Semestre 2009

$[\/]$

CI-1322 Autómatas y compiladores

Examen Final [solución]

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

1) [33 pts] Considere la gramática G cuyas producciones son las siguientes:

(1) B -> ε (2) B -> f (3) B -> e A (4) A -> c B B (5) A -> d B B

1.a) [0 pts] Calcule los conjuntos Primero() y Siguiente() para los no terminales de G.

1.b) [4 pts] Dibuje el autómata SLR(1) para esta gramática.

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

1.d) [8 pts] Dibuje el autómata LR(1) para esta gramática.

1.e) [8 pts] Calcule la tabla LALR(1) para esta gramática.

1.f) [4 pts] Resuelva conflictos en su tabla LALR(1) dándole prioridad a los desplazamientos o dejando solo la producción que aparece primero en la gramática.

1.g) [5 pts] Muestre como procesa y acepta una hilera de 6 o más símbolos su autómata LALR(1).

1.h) [0 pts] Demuestre si su autómata reconoce o no L(G). ¿Existe alguna hilera que sí pertenece a L(G) pero que no es aceptada por el autómata LALR(1) modificado?

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

2) [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 (siempre y cuando la tabla de transiciones esté completa).

2.a) [11 pts] Haga el diagrama del autómata determinista Lpi que reconozca hileras en el alfabeto Σ = {0,1} que siempre tienen una cantidad par de unos seguida por una impar de ceros.

2.b) [11 pts] Encuentre el autómata noLpi que reconoce el lenguaje complementario de Lpi, esto es, el autómata que cumple estas condiciones:
(Σ^* = Lpi U noLpi) & (Σ^* - Lpi = noLpi) & (Lpi ∩ noLpi = Ø).

2.c) [11 pts] Minimice el autómata Lpi. Muestre el diagrama final del autómata minimizado.

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

3) [33 pts]

Al examinar el texto de un programa C++ es posible determinar cuales rutinas invocan a las demás. En la figura adjunta se muestra un ejemplo de cómo podría ser el resultado de la ejecución del programa ArbolCPP.exe que examina un archivo C++ y produce el listado jerárqico de las invocaciones de funciones y métodos.

Implemente ArbolCPP.exe usando las herramientas Lex/Yacc. Tome en cuenta los siguientes requerimientos:

Procese un archivo.
Elimine comentarios.
Construya en memoria el árbol de invocaciones.
Imprima el árbol recursivamente.

main()
  MVC::controlador()
    MVC::run()
      MVC::interfaz()
        MVC::menu()
        MVC::opciones()
      MVC::algoritmo()
        MVC::datos()
          MVC::obtieneCarnet()
            SQLite::select()
          MVC::agregaAlumno()
            SQLite::update()
          MVC::obtieneAlumno_MUCHOS()
            SQLite::select()
          MVC::obtieneAlumno_Nombre()
            SQLite::select()

Soluciones

$[/\]$