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 2003

$[\/]$

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

1) [33 pts] Considere las siguientes gramáticas libres de contexto:

G1 G2 G3

P -> Q Q -> ε Q -> 1 1 Q P -> Q Q -> ε Q -> 1 Q 1 P -> Q Q -> ε Q -> Q 1 1

G1	G2	G3
`P -> Q Q -> ε Q -> 1 1 Q`	`P -> Q Q -> ε Q -> 1 Q 1`	`P -> Q Q -> ε Q -> Q 1 1`

Note que L= L(G1) = L(G2) = L(G3)

1.a) [10 pts] Construya las tablas LL(1) para G1. ¿Es G1 LL(1)?

1.b) [10 pts] Construya las tablas LL(1) para G2. ¿Es G2 LL(1)?

1.c) [7 pts] ¿Es G3 LL(1)? ¿Por qué?

1.d) [6 pts] Describa el lenguaje L, y defínalo de la forma más concisa y exacta posible.

2) [33 pts] Recuperación de errores

2.a) [5 pts] Explique por qué la forma de manejar errores expuesta en el ejemplo 4.20 del libro de texto es incorrecta. En su explicación use la hilera ") id * + id".

2.b) [10 pts] Modifique el algoritmo 4.3 del libro de texto para incorporarle el método de manejo de errores expuesto en el ejemplo 4.20. Corrija en su algoritmo el problema que usted describe en la primera parte de esta pregunta. Muestre que su algoritmo funciona correctamente con la hilera ") id * + id".

2.c) [4 pts] Muestre cómo se comporta su algoritmo con la hilera "id id * id".

2.d) [4 pts] Muestre cómo se comporta su algoritmo con la hilera "id + id)".

2.e) [10 pts] Explique si es posible construir una hilera que haga que su algoritmo elimine todos los tokens de la hilera de entrada. Use una o más hileras como ejemplo para demostrar lo que afirma.

3) [33 pts] Considere la gramática que contiene las siguientes producciones:

L -> L P M -> P P -> a L -> M M -> b L -> ε M -> ε

3.a) [8 pts] Muestre que esta gramática es ambigua.

3.b) [5 pts] Para esta gramática, obtenga dos derivaciones más derechas para la misma hilera.

3.c) [5 pts] Para esta gramática, obtenga dos derivaciones más izquierdas para la misma hilera.

3.d) [8 pts] Corrija gramática para eliminarle la ambigüedad y la recursividad izquierda.

3.e) [7 pts] Muestre si la gramática corregida es o no LL(1).

4) [33 pts] Un ejemplo de la expresividad del lenguaje Prolog es el siguiente programa, que resuelve el problema de las Torres de Hanoi con una sola instrucción Move() [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] Escriba una gramática que genere la mayor parte de los programas similares éste. Tome en cuenta que en Prolog las "variables" comienzan con el carácter "_" o con letras mayúsculas, y los identificadores o literales comienzan con minúsculas.

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

4.d) [22 pts] Haga un programa Yacc que sirva para reconocer este lenguaje. Su programa debe usar el analizador léxico del punto anterior. Su respuesta debe ser completa. [Gramática=16, resto=6].

Soluciones

$[/\]$