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 2009

$[\/]$

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 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 el siguiente autómata F de estado inicial 0 y estados finales 6 y 8:

| + | - | ε | -----+---+---+---+ -> 0 | 3 | 9 | 1 | -----+---+---+---+ 1 | |9,4| 2 | -----+---+---+---+ 2 | 7 | | 2 | -----+---+---+---+ 3 | 6 | | | -----+---+---+---+ 4 | |5,2| | -----+---+---+---+ 5 | | | 4 | -----+---+---+---+ [] 6 | | | 8 | -----+---+---+---+ 7 | 8 | | | -----+---+---+---+ [] 8 | | | 6 | -----+---+---+---+ 9 | 3 | 9 | 9 | -----+---+---+---+

2.a) [11 pts] Convierta F en un autómata determinista D. Explique lo que hace.

2.b) [11 pts] Minimice D y obtenga el autómata determinista mínimo M. Explique lo que hace.

2.c) [11 pts] Calcule las tablas LL(1) para el autómata complementario de M. Explique lo que hace.

2.d) [0 pts] Dibuje los autómatas F, D y M.

2.e) [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:

(0) E'-> E (1) E -> T (2) E -> T * E (3) T -> a (4) T -> T + a

3.a) [2 pts] Demuestre que esta gramática no es LL(1) (no se limita a hablar de la recursividad izquierda).

3.b) [6 pts] Demuestre que existe una gramática G' equivalente a G que sí es LL(1).

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

3.d) [10 pts] Construya las tablas LALR(1) para G (la original). Dibuje el autómata de prefijos viables. Si hay conflictos, resuélvalos como lo hace Yacc/Bison.

3.e) [3 pts] Muestre como rechaza su autómata LALR(1) una hilera de al menos 12 símbolos.

3.f) [6 pts] Muestre cómo procesa su autómata LALR(1) la hilera: a * a + a.

3.g) [4 pts] Explique cuál es la asociatividad, izquierda o derecha, de los operadores '*' y '+'.

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

Soluciones

$[/\]$