CI-1322 Examen #2


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

1) [33 pts] Estas son las producciones de la gramática G:

(1)   E -> + E E
(2)   E -> * E E
(3)   E -> a

1.a) [6 pts] Calcule los conjuntos Primero() y Siguiente() para los no terminales de la gramática G.

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

1.c) [7 pts] Escoja una hilera de L(G) de al menos 10 símbolos y muestre como la reconoce el autómata LL(1).

1.d) [5 pts] Repita el ejercicio anterior, pero use la hilera invertida para realizar su trabajo.

1.e) [3 pts] Escriba un programa C++ que reconozca este lenguaje.

2) [33 pts] Para contrarrestar el terrorismo le han pedido a usted que examine varios millones de páginas Internet escritas en español. En esas páginas las letras tildadas se representan con la hileras { á...ú } y que las letras "ñ" se representan con "ñ" o Ñ y los párrafos termina con un punto (ignore las etiquetas HTML). Las palabras que hay que detectar están en 5 categorías diferentes, numeradas en el rango [0..4]. Un párrafo se supone terrorista si contiene 3 palabras de manera que cada una de ellas sea de una categoría superior a la anterior. Por ejemplo, si un párrafo contiene las palabras Cat5+Cat2+Cat4 no se supone que le párrafo sea terrorista. Pero al reordenar las palabras Cat2+Cat3+Cat5 sí sería un párrafo terrorista. Escriba un programa que lea archivos y descubra los párrafos terroristas. Use Lex/Flex.

3) [33 pts]

[LR] +  -  $    S A B
   +----------+-------+     (1)  S → A + A -
 0 | r3 r4    | 9 1 2 |     (2)  S → B - B +
 1 | d3       |       |     (3)  A → ε
 2 |    d4    |       |     (4)  B → ε
 3 |    r3    |   5   |
 4 | r4       |     6 |   [AF]  -   +
 5 |    d7    |       |       +---+---+
 6 | d8       |       |     A | C | B |   F = { A }
 7 |       r1 |       |     B | D | A |  q0 = A
 8 |       r2 |       |     C | A | D |
 9 |       SI |       |     D | B | C |
   +----------+-------+       +---+---+

3.a) [6 pts] Procese la hilera "+-++++-+++" con la tabla AF y diga si esa hilera está en el lenguaje de la gramática del autómata AF.

3.b) [6 pts] Diga cuál es la gramática del autómata AF.

3.c) [6 pts] Calcule las tabla LL(1) para el autómata AF.

3.d) [6 pts] Procese la misma hilera "+-++++-+++" con la tabla LR(1).

3.e) [6 pts] Demuestre que la gramática de LR sí es LL(1). No haga la tabla.

3.f) [3 pts] Diga cuál es el lenguaje de LR y el de AF.

Soluciones

$[/\]$