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 2007

$[\/]$

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] Considere el siguiente autómata con estado inicial y final 1:

	a	b	ε
==> [1]		{ 3 }	{ 2 }
2	{ 3 }	{ 4 }
3	{ 3,4 }
4			{ 1 }

1.a) [0 pts] Dibuje el autómata.

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) [3 pts] Obtenga una expresión regular para el lenguaje de este autómata. Justifique su respuesta.

2) [33 pts] Considere la expresión (17 * 41) / 22 ** 3.8 ** 12 en la que el operador ** denota la exponenciación, y los otros dos son la multiplicación y la división.

2.a) [6 pts] Para esta expresión indique cuáles son los tokens y lexemas que un analizador léxico retornaría.

2.b) [27 pts] Escriba un programa Lex/Flex que permita obtener los tokens y lexemas para un reconocedor de este tipo de expresiones.

3) [33 pts] Los números de cédula en Costa Rica constan de 3 partes: el número de provincia y 2 números de cuatro dígitos cada uno. Estas partes deben estar separadas por un guión "-".

3.a) [11 pts] Separe los números en 2 categorías: "0" (cero) y "d" (el resto [1-9]). Escriba una expresión regular "r" para los números de cédula ticos. Luego construya el autómata no determinista "N" que reconoce el lenguaje de "r". Permita que las 2 últimas partes sean escritas eliminando los ceros del principio, de manera que la cédula "2-0320-0028" pueda escribirse de todas estas maneras:

2-0320-0028
2-320-0028
2-0320-028
2-0320-28
2-320-28

3.b) [11 pts] Obtenga a partir de "N" un autómata determinista "D" que reconoce el mismo lenguaje que "N". Dibuje el diagrama de "D".

3.c) [11 pts] Obtenga a partir de "D" un autómata determinista "M" que reconoce el mismo lenguaje que "D", pero que además es óptimo porque tiene una cantidad mínima de estados. Dibuje el diagrama de "M".

3.d) [0 pts] Dibuje de nuevo los diagramas que obtuvo en los puntos anteriores

4) [33 pts] Considere el siguiente bloque de código, escrito en un dialecto de Prolog [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.

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

4.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 el lenguaje Prolog.

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

4.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 Prolog es sintácticamente correcto.

Soluciones

$[/\]$