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 2008

$[\/]$

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 siguiente gramática G:

E → A a B b
A → B E | ε | A
B → b

                         a        b        $
  Pr()      Sg()       +--------+--------+-----+
{ a b }   { $ a }    E | E→AaBb | E→AaBb |     |
{ b ε }   {  a  }    A |        | A→BE   | A→ε |
{  b  }   { a b }    B |        | B→b    |     |

1.a) [5 pts] Calcule los conjuntos Primero() y Siguiente() para G.

1.b) [7 pts] Calcule las tablas LL(1) para G. Explique lo que hace.

1.c) [7 pts] Calcule las tablas SLR(1) para G. Explique lo que hace.

1.d) [7 pts] Calcule las tablas LALR(1) para G. Explique lo que hace.

1.e) [7 pts] Calcule las tablas LR(1) para G. Explique lo que hace.

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 L03i que reconozca hileras en el alfabeto Σ = {0,1} que comienzan con cero, pero que tienen una cantidad divisible por tres de unos.

2.b) [0 pts] Haga un autómata que reconozca los prefijos válidos para una hilera que está en el lenguaje L.

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

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

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

$[/\]$