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!

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.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.

(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

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2002
Derechos de autor reservados © 2002