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 2011

$[\/]$

CI-1322 Autómatas y compiladores

Examen Final [solución]

Duración: Ciento veinte minutos. Lea bien el examen antes de hacerlo. El examen es a libro abierto. Cuenta la documentación. 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 la gramática G cuyas producciones son las siguientes:

(1) E -> T + E (2) E -> T * E (3) E -> id (4) T -> ( E )

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

1.b) [6 pts] Dibuje el autómata SLR(1) para esta gramática y luego calcule la tabla SLR(1). Explique lo que hace.

1.c) [8 pts] Calcule la tabla LALR(1) para esta gramática. Explique lo que hace.

1.d) [11 pts] Dibuje el autómata LR(1) para esta gramática y luego calcule la tabla LR(1). Explique lo que hace.

1.e) [8 pts] Muestre como su autómata LALR(1) acepta una hilera de al menos 5 símbolos.

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

2) [33 pts] La CIA encontró una nueva forma de distribución de contraseñas terroristas, embebidas en programas de computación. El truco es relativamente simple, pues lo que los malos hacen es poner la contraseña en un programa disfrazándola como si fuera un identificador en un bloque de código, pero lo colocan siempre anidada entre por lo 3 niveles de paréntesis. Por ejemplo, la hilera 'Anul' es un identificador válido que tiene al menos una letra mayúscula y otra minúscula y que además está anidado dentro de 3 niveles en el bloque de código { { { Anul = 23; } } }. Hay otras variantes de anidamiento que también son válidas, si se usan otro tipo de paréntesis como "" <> () [] {}:
A[ fun( VIL, Malo( Passwd01,"no" ),"feo"( ((no)) ), "Si" ) ]
En este último ejemplo, las hileras 'Passwd01' y '"Si"' son candidatos de contraseña, pero ninguno de los identificadores 'A', 'fun', 'VIL', 'Malo', '"no"' '"feo"' o 'no' lo es.
Escriba un programa completo Lex/Yacc para procesar muchos archivos que contienen programas para extraerles los identificadores que son candidatos a ser contraseñas. Use las parejas anidadas "" <> () [] {} para detectar hileras candidatas, pero asegúrese de que cada posible contraseña tenga al menos una letra mayúscula y otra minúscula. Clasifique las contraseñas en grupos, dándole mayor importancia a las que incluyen dígitos (como 'Passwd01') y también a las que son de mayor longitud.

3) [33 pts] Considere la siguiente gramática libre de contexto G:

    !  -> a 6
    6  ->   9 | O
    9  ->   M | U
    M  ->   R | G
    U  ->   C | A
    R  -> b I
    C  -> a E
    I  ->   G
    E  ->   C | A
    G  ->   L
    A  ->   L
    L  ->   9 | O
    O  -> b S
    S  -> ε

3.a) [1 pts] Dibuje el autómata finito para la gramática G.

3.b) [10 pts] Obtenga el autómata finito determinista D a partir del diagrama de estados de G. Incluya el diagrama de estados del autómata finito.

3.c) [10 pts] Obtenga el autómata finito determinista M minimizando D. Incluya el diagrama de estados de M.

3.d) [12 pts] Muestre cómo reconoce M las siguientes hileras:

a b b b
a a b a

Explique lo que ocurre con cada una de estas hileras.

Soluciones

$[/\]$