CI-1322 Examen #2


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
II 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 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] Haga la tabla LL(1) para esta gramática.

1.b) [8 pts] Muestre cómo es reconocida la hilera ( ( ( a a a ) a ) a )

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. Puede usar Lex.

1.d) [2 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] Obtenga una expresión regular para este autómata usando el algoritmo respectivo. q1 es el estado inicial y final del autómata.

0 1

q1 q1 q2

q2 q3 q2

q3 q1 q2

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

(1) R ==> R + R (2) R ==> R R (3) R ==> R* (4) R ==> ( R ) (5) R ==> a (6) R ==> b

3.a) [0 pts] Demuestre que esta gramática es ambigua y que genera todas las expresiones regulares para los símbolos "a" y "b". Recuerde que la cerradura de Kleene tiene mayor precedencia que la concatenación. Además, la concatenación tiene mayor precedencia que la unión. También tome en cuenta que todos estos operadores binarios son asociativos a la izquierda.

3.b) [11 pts] Construya el autómata de prefijos viables para esta gramática G.

3.c) [9 pts] Haga la tabla SLR(1) para G. Muestre claramente los conflictos.

3.d) [7 pts] Arregle los conflictos en la tabla SLR(1) de G tomando en cuenta la asociatividad y precedencia de los operadores.

3.e) [6 pts] Muestre cómo reconoce su autómata SLR(1) la hilera ( a + b * b ) *

4) [33 pts] Suponga que usted cuenta con una clase C++ en que han sido implementadas las operaciones aritméticas para números racionales, los que impresos se ven de la siguiente manera: [31/23] o [12]. Implemente usando Lex+Yacc una calculadora de números racionales.

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

(1) E ==> - E T (2) E ==> T (3) T ==> ( E ) (4) T ==> id

5.a) [11 pts] Calcule las tablas LL(1) para G. Explique lo que ha obtenido.

5.b) [0 pts] Calcule las tablas SLR(1) para G. Explique lo que ha obtenido.

5.c) [11 pts] Calcule las tablas LALR(1) para G. Explique lo que ha obtenido.

5.d) [11 pts] Calcule las tablas LR(1) para G. Explique lo que ha obtenido.

Soluciones

$[/\]$