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 2008

$[\/]$

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

1) [33 pts] Estas son las producciones de la gramática G:

(1)  P -> ε
(2)  P -> P P +
(3)  P -> P + Q
(4)  Q -> - P

1.a) [0 pts] Calcule los conjuntos Primero() y Siguiente() para los no terminales de la gramática G. Demuestre que esta no es una gramática LL(1).

1.b) [11 pts] Obtenga a partir de G una nueva gramática G' que sí sea LL(1). Explique cómo lo hace.

1.c) [11 pts] Construya la tabla LL(1) para la gramática G'. Justifique por qué incluye cada producción en la tabla.

1.d) [6 pts] Escoja una hilera de L(G) de al menos 6 símbolos y muestre cómo la reconoce el autómata LL(1). Asegúrese de que su hilera incluya todos los terminales de la gramática.

1.e) [5 pts] Repita el ejercicio anterior, pero ahora use la hilera inversa del punto anterior.

1.f) [0 pts] Escriba un programa C++ que reconozca este lenguaje.

2) [33 pts] Estas son las producciones de la gramática G:

(1)  S -> M A R
(2)  S -> R A M
(3)  M -> ( A
(4)  M -> ε
(5)  A -> + R
(6)  A -> ε
(7)  R -> )

2.a) [5 pts] Calcule los conjuntos Primero() y Siguiente() para G.

2.b) [3 pts] Calcule las tablas SLR(1) para G.

2.c) [5 pts] Calcule las tablas LALR(1) para G.

2.d) [14 pts] Calcule las tablas LR(1) para G.

2.e) [6 pts] Escoja una hilera de L(G) de al menos 6 símbolos y muestre cómo la reconoce el autómata LR(1). Asegúrese de que su hilera incluya todos los terminales de la gramática.

3) [33 pts]

 Notas-CI-1322.txt
+-----------------------------+   Nombre   P1   P2   P3   T1   T2   T3   T4
| Nombre,P1,P2,P3,T1,T2,T3,T4 |  +-------+----+----+----+----+----+----+----+
| Juana,25,35,45,12,12,12,12  |  | Juana | 25 | 35 | 45 | 12 | 12 | 12 | 12 |
| Ana,98,95,95,,25,25,25      |  | Ana   | 98 | 95 | 95 |    | 25 | 25 | 25 |
+-----------------------------+  +-------+----+----+----+----+----+----+----+

Las notas de los cursos tienen una estructura bastante simple, pues consisten de los mismos ítemes: exámenes, tareas, quices y proyectos. Lo usual es que para un grupo de alumnos la cantidad de cada uno de ésos ítemes sea la misma. Por ejemplo, si Juana hizo 3 exámenes y 4 tareas, también Ana tendrá 3 notas de examen y 4 de tareas. Los problemas surgen cuando algunos alumnos pierden exámenes o quices, pues la casilla correspondiente aparecerá en blanco.

3.a) [11 pts] Defina una gramática para leer un archivo de notas. Muestre que su gramática sí genera adecuadamente las notas.

3.b) [22 pts] Implemente un esquema de traducción por sintaxis en la forma de un programa Lex/Yacc que use la gramática y, a partir del análisis sintáctico, extraiga las notas. Como salida, su programa debe grabarlas en una matriz tabulada.

Soluciones

$[/\]$