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 2003

$[\/]$

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

1) [33 pts] Considere la siguiente gramática G:

(1) S ==> a (2) S ==> ( L ) (3) L ==> S (4) L ==> L S

1.a) [0 pts] Explique por qué G no una gramática LL(1).

1.b) [5 pts] Transforme a G en un gramática equivalente G' que no tenga recursividad izquierda. Explique con detalle, paso por paso, qué hace.

1.c) [6 pts] Transforme a G' en G", una gramática factorizada. Explique con detalle, paso por paso, qué hace. Explique si G" es o no una gramática LL(1).

1.d) [11 pts] Haga las tablas SLR(1) para G, la gramática inicial. Explique con detalle, paso por paso, qué hace.

1.e) [5 pts] Muestre qué ocurre al tratar de reconocer la hilera ((aa)a) con el autómata SLR(1) de G. Obtenga la derivación más derecha para esta hilera

1.f) [6 pts] Muestre qué ocurre al tratar de reconocer la hilera (a((a)) con el autómata SLR(1) de G. Obtenga la derivación más derecha para esta hilera.

2) [33 pts] Considere la gramática G que contiene las siguientes producciones:

E ==> L E ==> E T E ==> ε L ==> b ε L ==> T L ==> ε T ==> a ε T ==> Q Q ==> ε Q ==> R Q R Q ==> Q R Q R ==> ε

2.a) [5 pts] Transforme a G en un gramática equivalente G' que sea LL(1). Explique qué hace. Elimine producciones inútiles.

2.c) [6 pts] Calcule las tablas LL(1) para G'. Use esas tablas LL(1) para obtener una gramática G" equivalente a G', en la que se han eliminado producciones inútiles.

2.c) [0 pts] Especifique e implemente en C++ una analizador léxico para esta gramática.

2.d) [5 pts] Escriba en C++ una analizador sintáctico recursivo descendente para esta gramática. Use el analizador léxico del punto anterior.

2.e) [6 pts] Obtenga un autómata determinista M para G.

2.f) [6 pts] Minimice M y obtenga M', el autómata determinista mínimo equivalente a M.

2.g) [5 pts] Construya una expresión regular que reconozca L(M).

2.h) [0 pts] Escriba un programa Perl que reconozca L(G).

3) [33 pts] Un ejemplo de la uso del lenguaje Snobol es el programa WordSize.sno que lee un archivo y calcula la cantidad de palabras de longitudes de entre 3 y nueve letras:

&TRIM = 1 WORDPAT = BREAK(&LCASE &UCASE) SPAN(&LCASE &UCASE "'-") . WORD COUNT = ARRAY('3:9',0) READ LINE = INPUT :F(DONE) NEXTW LINE WORDPAT = :F(READ) COUNT<SIZE(WORD)> = COUNT<SIZE(WORD)>+ 1 :(NEXTW) DONE OUTPUT = "WORD LENGTH NUMBER OF OCCURRENCES" I = 2 PRINT I = I + 1 OUTPUT = LPAD(I,5) LPAD(COUNT<I>,20) :S(PRINT) END

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

3.b) [0 pts] Escriba una gramática que genere la mayor parte de los programas similares éste.

3.c) [11 pts] Haga un programa Lex que sirva para reconocer los tokens de este lenguaje.

3.c) [22 pts] Haga un programa Yacc que sirva para reconocer este lenguaje. Su programa debe usar el analizador léxico del punto anterior. Su respuesta debe ser completa. No caiga en el error de usar una gramática trivial.

Soluciones

$[/\]$