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 2009

$[\/]$

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] Considere el lenguaje de todos los identificadores válidos en C++.

1.a) [0 pts] Escriba un programa Lex/Flex que reconozca este lenguaje.

1.b) [11 pts] Obtenga un autómata determinista para el el lenguaje de todos los identificadores válidos (si lo necesita, use las funciones isalpha() junto con isdigit() de la biblioteca estándar de C++). Explique lo que hace.

1.c) [11 pts] A partir del autómata determinista que obtuvo en la pregunta anterior, obtenga una gramática LL(1) para el lenguaje de las expresiones. Explique lo que hace.

1.d) [0 pts] Explique por qué su gramática LL(1) se puede usar como analizador léxico. Incluya un ejemplo en que reconoce varias hileras.

1.e) [11 pts] Escriba un programa C++ que reciba como entrada un archivo C++ y produzca una lista de todos los identificadores C++ que contiene. Para implementar su analizador léxico complete e implemente los métodos que corresponden a las producciones de la clase Analizador_Sintactico de la tercera tarea programada. Explique lo que hace.

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

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] 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)

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

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

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

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

$[/\]$