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 2011

$[\/]$

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

1) [33 pts] Considere la siguiente gramática G:

(1) S ==> a (2) S ==> ( L ) (3) L ==> S L (4) L ==> ε

1.a) [11 pts] Calcule la tabla LL(1) para esta gramática.

1.b) [8 pts] Muestre cómo es reconocida la hilera ( a ( a ( a a a ) ) ) . Explique cómo obtener la derivación más izquierda para esta hilera.

1.c) [14 pts] Escriba un programa Plis.c++, escrito en C++, que puede reconocer L(G). Obtenga su programa directamente de la gramática G. Los lexemas válidos para el token "a" deben ser identificadores que comienzan con una letra. Debe usar Lex.

1.d) [0 pts] Modifique su programa Plis.c++ de manera que a cada identificador "a" que esté al principio de una "lista" sea "ejecutado" usando como argumentos los demás elementos de la "lista". Llame a su programa modificado Lisp.c++. Suponga que cuenta con un diccionario de nombres de identificadores con el que puede ejecutar algunas rutinas predefinidas; por ejemplo SUM puede calcular la suma de los argumentos. Si un identificador no aparece en su diccionario, use como valor del identificador el almacenado en su "propiedad", que contiene el atributo "valor".

2) [33 pts] Considere la gramática G definida de la siguiente manera:

    |    c     |    d     |    $     ||  S  C |
----+----------+----------+----------++-------+
 0  |   D36    |   D47    |          ||  1  2 |
 1  |          |          | S'->S    ||       |
 2  |   D36    |   D47    |          ||     5 |
36  |   D36    |   D47    |          ||    89 |
47  |  C -> d  |  C -> d  | C -> d   ||       |
 5  |          |          | S -> C C ||       |
89  | C -> c C | C -> c C | C -> c C ||       |
----+----------+----------+----------++-------+

2.a) [0 pts] Explique por qué S' es el símbolo inicial de esta gramática. Muestre las producciones de G.

2.b) [10 pts] Calcule los conjuntos Primero() y Siguiente() para esta gramática.

2.c) [10 pts] Escoja una hilera de al menos 7 símbolos que esté en L(G). Muestre cómo la reconoce este autómata LALR(1).

2.d) [7 pts] Encuentre el árbol de análisis sintáctico para la hilera del punto anterior. Explique cómo lo obtuvo.

2.e) [6 pts] Escoja una hilera de al menos 17 símbolos que no esté en L(G). Muestre cómo la rechaza este autómata.

3) [33 pts]

3.a) [11 pts] Construya un autómata finito que sirva para determinar si la cantidad de letras de una hilera sobre el alfabeto { a b } es par.

3.b) [6 pts] Construya una gramática G que sirva para determinar si la cantidad de letras sobre el alfabeto { a b } es par.

3.c) [11 pts] Calcule las tablas LL(1) para G.

3.d) [5 pts] Muestr cómo rechaza su autómata LL(1) la hilera "aabba".

Soluciones

$[/\]$