CI-1322 Examen #2


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
I Semestre 2009

$[\/]$

CI-1322 Autómatas y compiladores

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

1) [33 pts] Considere la gramática G cuyas producciones son las siguientes:

(1) E -> T ** E (2) E -> T (3) T -> T * F (4) T -> F (5) F -> id (6) F -> ( E )

1.a) [2 pts] Demuestre que esta gramática no es LL(1).

1.b) [4 pts] Obtenga a partir de G una gramática G' equivalente que sí sea LL(1).

1.c) [4 pts] Calcule los conjuntos Primero() y Siguiente() para los no terminales de G'.

1.d) [8 pts] Construya las tablas LL(1) para G'.

1.e) [3 pts] Muestre como rechaza su gramática una hilera de al menos 12 símbolos.

1.f) [8 pts] Muestre cómo procesa su gramática la hilera: id ** id ** id.

1.g) [4 pts] Explique cuál es la asociatividad, izquierda o derecha, de los operadores '*' y '**'.

1.h) [0 pts] Recuerde que siempre debe explicar y justificar lo que hace al resolver cada pregunta.

2) [33 pts] Considere la gramática G cuyas producciones son las siguientes:

(1) A -> M = E (2) M -> id (3) E -> E + T (4) E -> T (5) T -> ( E ) (6) T -> M

2.a) [3 pts] Suponga que ha construido la tabla LL(1) para esta gramática: ¿Qué forma especial tendría? ¿Por qué?

2.b) [6 pts] Calcule los conjuntos Primero() y Siguiente() para los no terminales de G.

2.c) [14 pts] Construya la tabla SLR(1) para G. ¿Es G una gramática SLR(1)? Explique lo que hace e incluya el diagrama de autómata.

2.d) [0 pts] Si en la tabla SLR(1) para G hay conflictos, elimínelos usando estas dos reglas: a) Deje el desplazamiento en lugar de una reducción y b) Deje la reducción que corresponde a la producción que está primero.

2.e) [10 pts] Escoja una hilera del lenguaje L(G) que tenga al menos 7 terminales y que incluya todos los terminales de la gramática. Muestre cómo la procesa el analizador SLR(1) con la tabla que construyó anteriormente.

2.f) [0 pts] Recuerde que siempre debe explicar y justificar lo que hace al resolver cada pregunta.

3) [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))))

3.a) [11 pts] Encuentre una gramática LL(1) para este lenguaje. Explique lo que hace y muestre con un ejemplo pequeño que su gramática es correcta.

3.b) [11 pts] Haga un programa Lex/Flex que sirva para obtener los tokens y lexemas de este lenguaje.

3.c) [11 pts] Haga un programa Yacc/Bison que sirva para reconocer este lenguaje.

3.d) [0 pts] Recuerde que siempre debe explicar y justificar lo que hace al resolver cada pregunta.

Soluciones

$[/\]$