Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
Profesor Adolfo Di Mare
CI-1322
I Semestre 2009
[<=] [home] [<>] [\/] [=>]
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

[mailto:] Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2009
Derechos de autor reservados © 2009
[home] <> [/\]