CI-1322 Examen Final


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
II 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 preguntas. ¡No haga más de lo que se le pide!

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

(1) S ==> L A B A B O S a (5) O ==> L A A L A B A (3) B ==> L A L A (7) A ==> A A L A (6) L ==> (4) A ==> (2) S ==>

1.a) [6 pts] Transforme a G en G', una gramática equivalente, que no contenga producciones redundantes. Justifique lo que hace.

1.b) [4 pts] Calcule los conjuntos Primero() y Siguiente() para G'.

1.c) [5 pts] Haga la tabla LL(1) para G'. Explique si G' es o no una gramática LL(1).

1.d) [3 pts] Muestre cómo es reconocida la hilera ( ( ( a a a a a a ) a ) a ) por el autómata LL(1).

1.e) [0 pts] Calcule las tablas SLR(1) para G'. Explique lo que ha obtenido.

1.f) [2 pts] Calcule las tablas LALR(1) para G'. Explique lo que ha obtenido.

1.g) [7 pts] Calcule las tablas LR(1) para G'. Incluya el diagrama del autómata. Explique lo que ha obtenido.

1.h) [6 pts] Muestre cómo es reconocida la hilera a a a por el autómata LR(1).

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

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

2.a) [11 pts] Haga la tabla LR(1) para esta gramática. Incluya el diagrama del autómata.

2.b) [6 pts] Haga la tabla LALR(1) y la tabla SLR(1) para esta gramática.

2.c) [16 pts] Muestre cómo es reconocida la hilera ( ( a ) a ( a a a ) ) con alguno de esos autómatas.

3) [33 pts] Escriba un programa Lex + Yacc que reciba como entrada un archivo .INI y construya un árbol sintáctico, similar al que usted produjo en la tercera tarea programada (Cálculo del árbol de análisis sintáctico para la calculadora). Los antiguos archivos de configuración .INI de Windows tienen una estructura bastante simple:

C:\WINDOWS\win.ini
; for 16-bit app support [fonts] [extensions] [mci extensions] [files] [Mail] MAPI=1 CMC=1 CMCDLLNAME=mapi.dll MAPIX=1 MAPIXVER=1.0.0.1 OLEMessaging=1 [MCI Extensions.BAK] aifc=MPEGVideo aiff=MPEGVideo

C:\WINDOWS\system.ini
; for 16-bit app support [drivers] wave=mmdrv.dll timer=timer.drv [mci] [driver32] [386enh] woafont=dosapp.FON EGA80WOA.FON=EGA80WOA.FON EGA40WOA.FON=EGA40WOA.FON CGA40WOA.FON=CGA40WOA.FON

C:\WINDOWS\intuprof.ini
[Products] QW=1 [QW] country=~~ICG0T()))0/",+#@ [ODBC 32 bit Data Sources] MS Access Database=Microsoft Access Driver (*.mdb) dBASE Files=Microsoft dBase Driver (*.dbf) (32 bit) Excel Files=Microsoft Excel Driver (*.xls) (32 bit) [MS Access Database] Driver32=C:\WINDOWS\System32\odbcjt32.dll [dBASE Files] Driver32=C:\WINDOWS\System32\odbcjt32.dll [Excel Files] Driver32=C:\WINDOWS\System32\odbcjt32.dll

C:\WINDOWS\URLPROXY.INI
[General] BrowserPath= DDEserver= ReuseBrowserWindow=Yes

3.a) [6 pts] Primero analice estos ejemplos de archivos .INI y luego defina la forma y estructura del árbol que su programa producirá. Recuerde que el punto y coma ";" marca el comienzo de un comentario.

3.b) [0 pts] Especifique e implemente la función que produzca una salida anidada de acuerdo a la jerarquía de los nodos en el árbol, de manera similar a como lo hizo en la tercera tarea programada. Haga lo mismo con la clase árbol.

3.c) [11 pts] Escriba el programa Lex para reconocer los tokens en los archivos .INI.

3.d) [16 pts] Escriba el programa Yacc que construya el árbol y luego lo imprima. Defina cómo es la interfaz entre sus programa Lex y Yacc; su implementación debe ser completa. Si usa C++ en su implementación, puede ignorar los problemas de interfaz C vs C++.

Soluciones

$[/\]$