CI-1322 Examen #2


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
II Semestre 2007

$[\/]$

CI-1322 Autómatas y compiladores

Examen #2 [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] Considere la gramática G que contiene las siguientes producciones:

W ==> X W ==> W Y W ==> ε X ==> 0 ε X ==> Y X ==> ε Y ==> 1 ε Y ==> P P ==> ε P ==> R P R P ==> P R P R ==> ε

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

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

1.c) [6 pts] Transforme G' para obtener una gramática LL(1) G", equivalente a G'. Calcule la tabla LL(1) para G".

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

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

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

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

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

2) [33 pts] Las expresiones lógicas C++ se escriben usando los operadores lógiocs && (and) || (or) y ! (not), como en

(a && b) || c || (! 
e)

2.a) [5 pts] Escriba una gramática que genere las expresiones lógicas C++.

2.b) [6 pts] Elimine la recursividad por la izquierda de la gramática anterior y obtenga una gramática equivalente.

2.c) [11 pts] Explique si la gramática resultado del punto anterior es o no apropiada para traducir las expresiones a la forma postfija. Si no lo fuera, corríjala. Demuestre lo que dice.

2.d) [11 pts] Implemente en C/C++ un programa que realice el análisis sintáctico predictivo para la gramática obtenida en el punto anterior. Asegúrese que al finalizar el análisis la expresión quede en postfijo para que pueda ser evaluada.

2.e) [0 pts] Implemente la función de evaluación para este analizador sintáctico.

3) [33 pts]

       a         b       c      $
   +--------+--------+--------+---+
 S | S==>Aa | S==>Bb | S==>cC |   |
 C | C==>Ba | C==>Ab |        |   |
 A | A==>D  | A==>D  |        |   |
 B | B==>D  | B==>D  |        |   |
 D | D==>ε  | D==>ε  |        |   |
   +--------+--------+--------+---+

3.a) [0 pts] Explique cuál es la gramática G a la que corresponde esta tabla. Describa en palabras el lenguaje L(G).

3.b) [11 pts] Escoga una hilera de L(G) que contenga al menos 10 símbolos. Muestre como la acepta el autómata de pila.

3.c) [5 pts] Dibuje el árbol de análisis sintáctico para la hilera que escogió en el punto anterior.

3.d) [11 pts] Calcule los conjuntos Primero() y Siguiente() para G.

3.e) [6 pts] Transforme la gramática de manera que contenga una cantidad mínima de símbolos y producciones. Dibuje el autómata determinista correspondiente.

3.f) [0 pts] Explique cómo obtener los conjuntos Primero() y Siguiente() para G a partir de la tabla. Dibuje el diagrama de G.

Soluciones

$[/\]$