CI-1322 Examen #1


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
I Semestre 2008

$[\/]$

CI-1322 Autómatas y compiladores

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

1) [33 pts] Obtenga el NFA para la expresión regular a+(c*+**b?)

1.a) [3 pts] Obtenga una autómata que reconozca el lenguaje definido por esta expresión regular. Nombre a los estados de su autómata usando letras minúsculas.

1.b) [15 pts] Obtenga un autómata determinista a partir de este autómata. Escriba los pasos intermedios en la construcción para que muestre cómo aplica el algoritmo para hacerlo.

1.c) [15 pts] Minimice su autómata determinista. Escriba los pasos intermedios en la construcción para que muestre cómo aplica el algoritmo para hacerlo.

1.d) [0 pts] Obtenga una expresión regular para el lenguaje del autómata óptimo. Justifique su respuesta.

2) [33 pts] Un ejemplo de la expresividad del lenguaje Prolog es el siguiente programa, que resuelve el problema de las Torres de Hanoi con una sola instrucción Move() [CM-83] (pg 136-137):

hanoi(N) :- move(N, left, center, right). move(0,_,_,_) :- !. move(N,A,B,C) :- M is N-1, move(M,A,C,B), w(A,B), move(M,C,B,A). w(From,To) :- write([move, from, From, to, To]), nl.

2.a) [0 pts] Diga cuáles son los tokens y cuáles son los lexemas en este bloque de código.

2.b) [0 pts] Declare la clase Token que contiene el token y el lexema que se usaría en la implementación de un compilador para este lenguaje.

2.c) [13 pts] Escriba una gramática que genere la mayor parte de los programas similares éste.

2.d) [20 pts] Suponga que usted ya cuenta con un analizador léxico getNextToken() que retorna los tokens para procesar hileras generadas por su gramática. Implemente en C++ o Java un analizador sintáctico que use ese analizador léxico para determinar si un programa es sintácticamente correcto.

3) [33 pts]

 Notas-CI-1322.txt
+-----------------------------+   Nombre   P1   P2   P3   T1   T2   T3   T4
| Nombre,P1,P2,P3,T1,T2,T3,T4 |  +-------+----+----+----+----+----+----+----+
| Juana,25,35,45,12,12,12,12  |  | Juana | 25 | 35 | 45 | 12 | 12 | 12 | 12 |
| Ana,98,95,95,,25,25,25      |  | Ana   | 98 | 95 | 95 |    | 25 | 25 | 25 |
+-----------------------------+  +-------+----+----+----+----+----+----+----+

Las notas de los cursos tienen una estructura bastante simple, pues consisten de los mismos ítemes: exámenes, tareas, quices y proyectos. Lo usual es que para un grupo de alumnos la cantidad de cada uno de ésos ítemes sea la misma. Por ejemplo, si Juana hizo 3 exámenes y 4 tareas, también Ana tendrá 3 notas de examen y 4 de tareas. Los problemas surgen cuando algunos alumnos pierden exámenes o quices, pues la casilla correspondiente aparecerá en blanco.

3.a) [11 pts] Escriba un programa Lex/Flex que sirva para obtener la tabla de notas a partir del archivo de entrada. Use el archivo "Notas-CI-1322.txt" que se muestra aquí. Como salida, su programa debe grabarlas en una matriz tabulada.

3.b) [22 pts] Use el descriptor del archivo de notas para generar un programa Lex/Flex que sirva para obtener un programa que las grabe en forma tabulada. Por ejemplo, si su programa recibe como entrada el archivo "Notas-CI-1322.txt" que se muestra aquí, como salida generaría el programa que usted escribió en el punto anterior.

4) [33 pts]

 Notas-CI-1322.txt
+-----------------------------+   Nombre   P1   P2   P3   T1   T2   T3   T4
| Nombre,P1,P2,P3,T1,T2,T3,T4 |  +-------+----+----+----+----+----+----+----+
| Juana,25,35,45,12,12,12,12  |  | Juana | 25 | 35 | 45 | 12 | 12 | 12 | 12 |
| Ana,98,95,95,,25,25,25      |  | Ana   | 98 | 95 | 95 |    | 25 | 25 | 25 |
+-----------------------------+  +-------+----+----+----+----+----+----+----+

4.a) [11 pts] Defina una gramática para leer un archivo de notas. Muestre que su gramática sí genera adecuadamente las notas.

4.b) [22 pts] Implemente un esquema de traducción por sintaxis en la forma de un programa C++ que siga la estructura de la gramática y, a partir del análisis sintáctico, extraiga las notas. Como salida, su programa debe grabarlas en una matriz tabulada.

Soluciones

$[/\]$