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 2003

$[\/]$

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 1 y estado final 2:

a b c d

1 { 2 }

2 { 3 } { 4 }

3 { 4 }
4 { 1 }

1.a) [0 pts] Haga el diagrama de este autómata.

1.b) [8 pts] Muestre paso a paso cómo el autómata original reconoce la hilera "abcdacda".

1.c) [5 pts] Considere la expresión regular ( ( bcda | cda ) * | a ) Explique si este autómata es equivalente a esta expresión regular. Si no lo es, indique cuál es la expresión regular correcta.

1.d) [20 pts] Obtenga una expresión regular para este autómata usando el algoritmo respectivo.

2) [33 pts] Considere la expresión regular r = (a b+ c?) | (a? b+ c)

2.a) [11 pts] Construya el autómata no determinista "N" que reconoce el lenguaje de "r".

2.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".

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

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

3.b) [7 pts] Escriba una gramática que sirva para generar expresiones similares a ésta. Recuerde que la exponenciación tiene mayor precedencia que la multiplicación y la división. También tome en cuenta que la exponenciación es asociativa a la derecha.

3.c) [20 pts] Suponga que usted ya cuenta con un analizador léxico que retorna los tokens para procesar hileras generadas por su gramática. Implemente en C++ un analizador sintáctico que use ese analizador léxico para evaluar este tipo de expresiones. Puede asumir que ya existe una función EVAL() que puede evaluar expresiones de tokens escritas en posfijo.

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

(defun valid-subst-list (sub-list) (mapcan (lambda (sub) (let ((new-sub (valid-subst sub))) (cond ((null (eql new-sub fail)) (list new-sub))))) sub-list)) (defun select-apple () (let ( (no (random 3)) ) (cond ((= no 0) granny-smith) ((= no 1) golden-delicious) ((= no 2) cooker) (t (error Weirdness in Select-apple))))

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

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

4.c) [11 pts] Haga un programa Lex que sirva para obtener los tokens y lexemas de este lenguaje.

Soluciones

$[/\]$