CI-1322 Examen #1


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

1) [33 pts] En la empresa TurboMan tienen una máquina troqueladora robot que se descompone mucho, porque los operarios le mueven la palanca y la ponen a hacer movimientos indebidos. Por ejemplo, ya les han dicho que si está para atras ←, los movimientos válidos son para arriba ↑ o para abajo ↓, pero no se puede ir hacia adelante →. Además, en cualquier momento se puede poner el taladro Θ.

1.a) [11 pts] A usted le piden que conecte la troqueladora de TurboMan con la computadora de manera que la computadora analice los comandos { ← ↑ ↓ → Θ} y determine si al ejecutarlos se quiebra la máquina. Diseñe un autómata que haga el trabajo. Use la tecnología vista en el curso (a menos que quiera sacar 0 puntos).

1.b) [11 pts] Muestre un ejemplo de al menos 10 comandos que su autómata rechazará porque quiebran la máquina. También muestre un ejemplo de 5 comandos que la máquina sí puede procesar.

1.c) [11 pts] Escriba un programa C++ que resuelva el problema.

2) [33 pts] L es el lenguaje formado por letras en el alfabeto { a , b } en donde cada hilera tiene 2 o 3 a's o contiene como subhilera a "ba".

2.a) [5 pts] Obtenga una expresión regular "r" para L = L(r).

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

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

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

3) [33 pts] HTML es un lenguaje de marcas usadas para definir cómo debe ser desplegado el texto de un documento. Por ejemplo, la pareja de etiquetas <STRONG> </STRONG> sirve para que el hojeador ponga en letra negra el texto. Escriba un programa Lex/Flex que recibe como entrada un archivo de texto escrito en formato HTML y produzca como salida el texto del archivo, omitiendo todas las etiquetas HTML. Recuerde que algunas etiquetas HTML incluyen parámetros como los siguientes:

<IMG SRC="http://www.di-mare.com/img/index.gif" ALT="[<>]" BORDER="0">

4) [33 pts] Considere el siguiente bloque de código, escrito en Haskell:

dohanoi(0, _, _, _) = [] dohanoi(n, from, to, using) = dohanoi(n - 1, from, using, to) ++ [(from, to)] ++ dohanoi(n - 1, using, to, from) hanoi(n) = dohanoi(n, 1, 3, 2)

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 Haskell.

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

Soluciones

$[/\]$