CI-1322 Examen #1


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
I Semestre 2010

$[\/]$

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 las tres preguntas. ¡No haga más de lo que se le pide!

1) [33 pts]

            T(1,b)=2   T(2,ε)=1
   --> 0    T(3,a)=1   T(0,ε)=3
  (( 3 ))   T(2,b)=3   T(1,ε)=0
            T(0,a)=1   T(3,ε)=1

1.a) [4 pts] Haga el diagrama o la tabla para el autómata cuyas transiciones están definidas por la función T().

1.b) [8 pts] Construya un autómata finito determinista que reconozca L(T()). Explique lo que hace.

1.c) [11 pts] Encuentre el autómata finito mínimo para L(T()). Escriba los pasos intermedios en la construcción para que muestre cómo aplica los algoritmos. Explique lo que hace.

1.d) [5 pts] Escoja una hilera de al menos 7 símbolos que esté en L(T()). Muestre cómo la acepta el autómata no determinista. Explique lo que hace.

1.e) [5 pts] Use la misma hilera de al menos 7 símbolos para mostrar que el autómata mínimo también la reconoce. Explique lo que hace.

1.f) [0 pts] Explique cuál autómata necesita más iteraciones para reconocer la hilera.

1.g) [0 pts] Recuerde que siempre debe explicar y justificar lo que hace al resolver cada pregunta.

2) [33 pts]

Escriba un programa C++ que reciba como entrada un archivo C++ y determine si los corchetes { } están correctamente a anidados. Implemente los métodos que corresponden a las producciones de la clase Analizador_Sintactico de la tercera tarea programada. Use Lex/Flex para implementar el analizador léxico. Recuerde que si los corchetes aparecen dentro de comentarios [ /* */ // ] o dentro de hileras [".{.}.." '{' '}' ] su analizador léxico no debe tomarlos en cuenta. Explique lo que hace.

3) [33 pts] Considere la gramática G que contiene estas producciones:

stmt  -> IF expr THEN stmt ELSE stmt
      |  IF expr THEN stmt
      |  BEGIN stmtList END
      |  ETC

stmtList-> stmtList ';' stmt
      |  stmt

3.a) [15 pts] Obtenga una gramática G' equivalente a G que no presente inconvenientes para obtener un programa que reconoce L(G). Explique lo que hace.

3.b) [18 pts] Escriba un programa C++ que reconozca L(G). Implemente los métodos que corresponden a las producciones de la clase Analizador_Sintactico de la tercera tarea programada.

3.c) [0 pts] Haga el árbol de análisis sintáctico para esta hilera de L(G): IF e1 THEN IF e2 THEN s1 ELSE s2. También explique cómo la reconoce su programa.

Soluciones

$[/\]$