Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
Profesor Adolfo Di Mare
CI-1322
I Semestre 2002
[<=] [home] [<>] [\/] [=>]
CI-1322 Autómatas y compiladores

Examen #1 [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 el compilador que usted modificó en la primera tarea programada.

1.a) [7 pts] Explique porqué el método Compilador::aparea() del compilador de la primera tarea programada no necesita recibir como parámetro el siguiente token a procesar.

1.b) [7 pts] Explique cómo modificar el compilador para que construya el árbol de sintaxis que corresponde a la expresión evaluada.

1.c) [19 pts] Especifique, declare y defina las clases y métodos que se necesitan para que ese compilador construya el árbol de sintaxis que corresponde a al expresión evaluada.

 

2) [33 pts] Considere la expresión regular r = (a b* c) | (a b c*)

2.a) [11 pts] Construya el autómata no determinista "N" que reconoce el lenguaje de "r".

2.b) [11 pts] Obtenga a partir de "N" un autómata determinista "D" que reconoce el mismo lenguaje que "N".

2.c) [11 pts] Obtenga a partir de "D" un autómata determinista "M" que reconoce el mismo lenguaje que "D", pero que además es óptimo porque tiene una cantidad mínima de estados.

 

3) [33 pts] La gramática G tiene estas producciones: S --> S(S) | ε

3.a) [11 pts] Describa en palabras el lenguaje que esta gramática genera.

3.b) [11 pts] Haga una derivación de una hilera "w" en L(G) en la que aplique por lo menos 10 producciones de "G".

3.d) [11 pts] Aplique el algoritmo para eliminar la recursividad izquierda para obtener, partir de "G", una gramática equivalente que no sea recursiva izquierda.

 

4) [33 pts] Considere el siguiente bloque de código, escrito en un lenguaje similar a Pascal: 

FOR numero := 1 TO N BEGIN
    suma := 0;
    temp := numero;
    WHILE temp <> 0 BEGIN          { suma de dígitos }
        digito := temp MOD 10;     { al cubo         }
        suma   := suma + (digito * digito * digito);
        temp   := temp DIV 10;
    END;
    IF suma = numero THEN BEGIN
        WriteLn(numero,' Suma de sus dígitos al cubo ', suma);
    END;
END;

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

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

4.c) [11 pts] Haga un programa Lex que sirva para obtener los tokens y lexemas de este lenguaje.

 

Soluciones

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