CI-1322 Examen Final


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
I Semestre 2007

$[\/]$

CI-1322 Autómatas y compiladores

Examen Final [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] Una base de datos relacional está compuesta de relaciones cuyo nombre está formado como un identificador C++ pero que tiene al principio el prefijo "REL_" (con un subrayado "_"). Entre paréntesis aparecen los nombres de los campos cuyo prefijo indica el tipo del campo: "IDX_" para los números seriales de identificación, "STR_" para las hileras, "DAT_" para las fechas, "MON_" para las monedas, "COD_" para códigos y "NUM_" para los números enteros. Por ejemplo, la siguiente es una descripción de una base de datos de para mantener las notas de los estudiantes:

REL_Alumno( STR_Carnet, STR_Nombre, STR_Apellidos, COD_Sexo, STR_email, NUM_telefono);
REL_Grupo( NUM_Grupo, DAT_Horario, NUM_Aula );
REL_Matricula( NUM_Grupo, STR_Carnet, NUM_Nota_Final );
REL_Nota( STR_Carnet, NUM_Grupo, IDX_Sec, NUM_Porcentaje, NUM_Nota );

Escriba un programa Bison/Yacc junto con Lex/Flex que lea de un archivo el esquema de una base de datos relacional y que imprima las asociaciones que hay entre relaciones. Una asociación entre 2 relaciones se deduce del esquema porque las 2 relaciones tienen el mismo campo. Por ejemplo, su programa imprimiría el siguiente listado para esta base de datos:

REL_Alumno < STR_Carnet > REL_Matricula
REL_Alumno < STR_Carnet > REL_Nota

REL_Grupo < NUM_Grupo > REL_Matricula
REL_Grupo < NUM_Grupo > REL_Nota

REL_Matricula < STR_Carnet > REL_Alumno
REL_Matricula < NUM_Grupo > REL_Grupo

REL_Nota < STR_Carnet > REL_Alumno
REL_Nota < NUM_Grupo > REL_Grupo
REL_Nota < NUM_Grupo > REL_Matricula

2) [33 pts] Considere este autómata cuyo estado inicial es A, y cuyo estado final es E.

       a   b
     +---+---+
-> A | D | C |
   B | F | E |
   C | C | E |
   D | D | C |
** E | A | C |
   F | E | F |
     +---+---+

2.a) [3 pts] Dibuje este autómata. Explique cómo es el lenguaje reconocido por este autómata.

2.b) [11 pts] Minimice este autómata. Explique lo que hace.

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

2.d) [8 pts] Muestre el resultado de procesar la hilera "aababbaabb" con el autómata LL(1).

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

A → Bb
A → C
B → aC
C → a
C → aA

3.a) [5 pts] Calcule los conjuntos Primero() y Siguiente() para G. Explique lo que hace.

3.b) [7 pts] Hagas las tablas LL(1) para G. Explique lo que hace.

3.c) [7 pts] Hagas las tablas SLR(1) para G. Explique lo que hace.

3.d) [7 pts] Hagas las tablas LALR(1) para G. Explique lo que hace.

3.e) [7 pts] Hagas las tablas LR(1) para G. Explique lo que hace.

Soluciones

$[/\]$