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 2010

$[\/]$

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) E -> op E E (2) E -> a

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

1.b) [6 pts] Dibuje el autómata SLR(1) para esta gramática y luego calcule la tabla SLR(1). Explique lo que hace.

1.c) [8 pts] Calcule la tabla LALR(1) para esta gramática. Explique lo que hace.

1.d) [11 pts] Dibuje el autómata LR(1) para esta gramática y luego calcule la tabla LR(1). Explique lo que hace.

1.e) [8 pts] Muestre como su autómata LALR(1) acepta una hilera de al menos 9 símbolos.

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

2) [33 pts] El problema que tienen los semáforos es que a veces se quedan pegados en una de las luces. Si se pegan en Rojo, se hace una gran presa porque ningún vehículo puede pasar, pero si se pegan en Verde es un tortón peor porque todos los carros chocan. La manera más simple de modelar un semáforo es usar una pareja de variables ([x][y]) en donde cada una puede tomar un valor de { R=Rojo, V=Verde, X=Pegado en Rojo, S=Pegado en Verde }.

2.a) [6 pts] Suponga que hay 2 tipos de eventos que hacen que el semáforo cambie de estado. El evento "0" es catastrófico, porque hace que el semáforo se trabe. El evento "1" es el que ocurre cada 97 segundos, cuando el semáforo pasa de verde a rojo o de rojo a verde. Haga el diagrama del autómata que muestra cómo interactúan estos eventos.

2.b) [11 pts] Minimice el autómata del semáforo. Explique qué hace en cada paso.

2.c) [5 pts] Muestre cómo rechaza el autómata minimizado una hilera de al menos 15 símbolos.

2.d) [5 pts] Construya la gramática LL(1) que corresponde al autómata. Explique qué hace.

2.e) [6 pts] Construya la tabla LL(1) para la gramática de los semáforos.

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árquico 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

$[/\]$