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 2009

$[\/]$

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

1) [33 pts] Considere el siguiente bloque de código SQL:

-- Entidad Relación Atributo Valor CREATE TABLE [ERAV] ( [ID_ENT] INTEGER NOT NULL, -- <K+++> <E> Entidad -- [REL] NOT NULL, <R> Relación [REL_ID] SMALLINT NOT NULL, -- <+K++> [REL_SUB] SMALLINT NOT NULL, -- <++K+> [REL_TYPE] CHAR(01) NOT NULL, [ATTRIB] INTEGER NOT NULL, -- <+++K> <A> Atributo -- [VAL] NOT NULL, -- Solo uno no es NULL <V> Valor [VAL_INT] INTEGER, -- entero o referencia a "WORD" [VAL_FLOAT] FLOAT, -- punto flotante [VAL_TIME] TIMESTAMP, -- tiempo [VAL_DATE] DATE, -- fecha [VAL_HOUR] TIME, -- hora [VAL_BLOB] BLOB, -- valor binario enorme CONSTRAINT [ERAV_KEY] UNIQUE ( [ID_ENT],[REL_ID],[REL_SUB],[ATTRIB] ) );

1.a) [11 pts] Encuentre una gramática LL(1) para este lenguaje. Explique lo que hace y muestre con un ejemplo pequeño que su gramática es correcta.

1.b) [11 pts] Haga un programa Lex/Flex que sirva para obtener los tokens y lexemas de este lenguaje.

1.c) [11 pts] Escriba un programa C++ que sirva para reconocer este lenguaje. Implemente los métodos relevantes de la clase "Analizador_Sintactico" que usó en su solución a la tercera tarea programada.

1.d) [0 pts] Recuerde que siempre debe explicar y justificar lo que hace al resolver cada pregunta.

2) [33 pts] Considere la gramática G cuyas producciones son las siguientes:

(1) A -> c B B (2) A -> d B B (3) B -> e A (4) B -> f (5) B -> ε

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

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

2.c) [4 pts] Resuelva conflictos en su tabla LL(1) dejando solo la producción que aparece primero en la gramática.

2.d) [6 pts] Muestre como procesa y acepta una hilera de 6 o más símbolos su autómata LL(1).

2.e) [4 pts] Dibuje el árbol de análisis sintáctico para la hilera que usó en el punto anterior.

2.f) [3 pts] Muestre como rechaza su autómata una hilera de 12 o más símbolos su autómata LL(1).

2.g) [3 pts] Demuestre si su autómata reconoce o no L(G).

2.h) [0 pts] Recuerde que siempre debe explicar y justificar lo que hace al resolver cada pregunta.

3) [33 pts] Considere la gramática G cuyas producciones son las siguientes:

(1) A -> c B B (2) A -> d B B (3) B -> e A (4) B -> f (5) B -> ε

3.a) [2 pts] Calcule los conjuntos Primero() y Siguiente() para los no terminales de G.

3.b) [11 pts] Dibuje el autómata SLR(1) para esta gramática.

3.c) [4 pts] Calcule la tabla SLR(1) para esta gramática.

3.d) [4 pts] Resuelva conflictos en su tabla SLR(1) dándole prioridad a los desplazamientos o dejando solo la producción que aparece primero en la gramática.

3.e) [6 pts] Muestre como procesa y acepta una hilera de 6 o más símbolos su autómata SLR(1).

3.f) [3 pts] Muestre como rechaza su autómata una hilera de 12 o más símbolos su autómata SLR(1).

3.g) [3 pts] Demuestre si su autómata reconoce o no L(G).

3.h) [0 pts] Recuerde que siempre debe explicar y justificar lo que hace al resolver cada pregunta.

Soluciones

$[/\]$