CI-1322 Examen #1


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
I Semestre 2011

$[\/]$

CI-1322 Autómatas y compiladores

Examen #1 [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]

             T(3,a)=3    T(2,b)=2
   --> 3     T(3,b)=2    T(1,b)=1
  (( 1 ))    T(2,a)=1    T(2,ε)=3
             T(1,a)=1    T(4,ε)=2
             T(4,a)=1    T(1,ε)=2

1.a) [4 pts] Haga el diagrama o la tabla para el autómata cuyas transiciones están definidas por la función T().

1.b) [10 pts] Construya un autómata finito determinista que reconozca L(T()). Explique lo que hace.

1.c) [8 pts] Encuentre el autómata finito mínimo para L(T()). Escriba los pasos intermedios en la construcción para que muestre cómo aplica los algoritmos. Explique lo que hace.

1.d) [6 pts] Escoja una hilera de al menos 7 símbolos que esté en L(T()). Muestre cómo la acepta el autómata no determinista. Explique lo que hace.

1.e) [5 pts] Use la misma hilera de al menos 7 símbolos para mostrar que el autómata mínimo también la reconoce. Explique lo que hace.

1.f) [0 pts] Explique cuál autómata necesita más iteraciones para reconocer la hilera.

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

2) [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] ) );

2.a) [0 pts] Diga cuáles son los tokens y cuáles son los lexemas en este bloque de código.

2.b) [0 pts] Declare la clase Token que contiene el token y el lexema que se usaría en la implementación de un compilador para el lenguaje SQL.

2.c) [18 pts] Escriba una gramática que genere la mayor parte de los programas similares éste. Recuerde que los caracteres "--" sirven para incluir comentarios en el código.

2.d) [15 pts] Use su gramática para mostrar el árbol de análisis sintáctico para este programa SQL:

              CREATE TABLE [ERAV] (
                  [ID_ENT] INTEGER NOT NULL,
                  [ATTRIB] INTEGER NOT NULL, 

                  CONSTRAINT [ERAV_KEY] UNIQUE
                      ( [ID_ENT],[REL_ID] )
              );

3) [33 pts] Escriba un programa Lex/Flex que reconozca los token del lenguaje SQL. Explique cómo maneja los comentarios SQL que comienzan con la hilera "--".

Soluciones

$[/\]$