Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
Profesor Adolfo Di Mare
CI-1322
II Semestre 2002
[<=] [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 todas las preguntas. ¡No haga más de lo que se le pide!

 

1) [33 pts]

   Sistema Contable: CIA Ejemplo
   menú      1    trans.hlp      Proceso de Transacciones
   ejecute   2    inclmv.prg          Incluir un sólo asiento
   ejecute   2    inclas.prg          Incluir varios asientos
   ejecute   2    balmv.prg           Balancear asientos
   ejecute   2    aplmv.prg           Aplicar asientos
   antes     2    abre.prg            Abrir archivos
   antes     2    limp.prg            Limpiar números de cuenta
   después   2    cerrdb.prg          Cerrar archivos
   menú      1    cons.hlp       Consultas
   ejecute   2    leacta.prg          Lea número de cuenta
   ejecute   2    despcta.prg         Despliegue cuenta
   menú      1    rep.hlp        Reportes
   ejecute   1    borr.prg       Borrar un registro
+-------------------------------+
| Sistema Contable: CIA Ejemplo |
|         Menú Principal        |
+-------------------------------+

+-------------------------------+
| A.  Proceso de Transacciones  |
| B.  Consultas                 |
| C.  Reportes                  |
| D.  Borrar un registro        |
+-------------------------------+
+-------------------------------+
| Sistema Contable: CIA Ejemplo |
|    Proceso de Transacciones   |
+-------------------------------+

 +-----------------------------+
 | A.  Incluir un sólo asiento |
 | B.  Incluir varios asientos |
 | C.  Balancear asientos      |
 | D.  Aplicar asientos        |
 +-----------------------------+

      En el sistema viejo se usaba un generador de programas que recibe un archivo de texto de entrada en que se describe la jerarquía de menús, a partir de la que se genera un programa que los despliega. El nuevo sistema no usa ese tipo de archivos, por lo que hay que traducir a XML todos los archivos de definición de menús.

1.a) [15 pts] Escriba un programa Lex/Flex que sirva para obtener los tokens para esta aplicación. La jerarquía de menús puede ser arbitrariamente profunda. Explique lo que hace. Documente bien su programa.

1.b) [18 pts] Escriba un programa Yacc/Bison que genere el documento XML. Use el analizador léxico que obtuvo en el punto anterior. Documente bien su programa.

 

2) [33 pts] Es bien sabido que si ya se cuenta con un autómata determinista (sin movimientos ε) que reconoce el lenguaje L, es fácil obtener el autómata complementario, que reconoce Σ*-L: basta cambiar en L los estados finales por no finales, y los no finales por finales.

2.a) [0 pts] Explique la diferencia entre una "sub-hilera" y una "sub-secuencia".

2.b) [5 pts] Haga el diagrama del autómata finito L:bbc que reconozca hileras en el alfabeto Σ = {b,c} en las que aparece la subsecuencia "bbc".

2.c) [14 pts] Encuentre el autómata noL:bbc que reconoce el lenguaje complementario de L:bbc, esto es, el autómata que cumple estas condiciones: (Σ* = L:bbc U noL:bbc) & (Σ* - L:bbc = noL:bbc) & (L:bbc ∩ noL:bbc = Θ)

2.d) [14 pts] Minimice el autómata noL:bbc. Muestre el diagrama final del autómata minimizado.

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:
(1)   E -> + E E
(2)   E -> * E E
(3)   E -> a
(4)   E -> b
(5)   E -> c

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

3.b) [6 pts] Construya la tabla LL(1) para esta gramática. ¿Es G una gramática LL(1)?

3.c) [8 pts] Construya la tabla SLR(1) para G. ¿Es G una gramática SLR(1)?

3.d) [5 pts] Si en la tabla LL(1) para G hay conflictos, elimínelos apropiadamente. A partir de la expresión aritmética
   ( (a+b) * (a+c) ) + b * c
obtenga una hilera que esté en el lenguaje generado por G. Muestre cómo la procesa el analizador LL(1) con la tabla que construyó anteriormente.

3.e) [8 pts] Si en la tabla SLR(1) para G hay conflictos, elimínelos usando las mismas reglas de Yacc/Bison. A partir de la expresión
   ( (a+b) * (a+c) ) + b * c
obtenga una hilera que esté en el lenguaje generado por G. Muestre cómo la procesa el analizador SLR(1) con la tabla que construyó anteriormente.

 

Soluciones

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