Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
Profesor Adolfo Di Mare
CI-1322
II Semestre 2006
[<=] [home] [<>] [\/] [=>]
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 las tres preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] r = ( a+ | b? ) +             s = ( a* | b* ) +

1.a) [5 pts] Para la expresión regular "r" construya el autómata no determinista "Nr" que reconoce L(r).

1.b) [5 pts] Para la expresión regular "s" construya el autómata no determinista "Ns" que reconoce L(s).

1.c) [7 pts] Obtenga el autómata determinista "Dr" para L(r). Incluya el diagrama del autómata en su respuesta.

1.d) [7 pts] Obtenga el autómata determinista "Ds" para L(s). Incluya el diagrama del autómata en su respuesta.

1.e) [9 pts] Demuestre que L(r) = L(s).

 

2) [33 pts] Considere la siguiente gramática para la generación de expresiones lógicas: 

E --> E and E
E --> E or  E
E --> id

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

2.b) [8 pts] ¿Es la gramática resultado del punto anterior apropiada para traducir las expresiones a la forma postfija? Si no lo fuera, arregle el problema.

2.c) [17 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 (usted no tiene que implementar la función de evaluación).

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

 

3) [33 pts] 

<P ALIGN="CENTER">
&#191;Es &eacute;sta la pregunta del examen?
</P>

Texto libre.

<BLOCKQUOTE>
  <OL START="6">
    <LI>
      <IMG
        SRC="../../../img/index.gif"
        ALT="[&lt;&gt;]"
        BORDER="0" />
    </LI>
    <LI>
      <CODE>
        <A HREF="./ac-ea-2.htm#XML">
          http://www.di-mare.com/
         <BR/>adolfo/cursos/2006-2/
         <BR/>ac-ea-2.htm#XML
        </A>
      </CODE>
    </LI>
  </OL>
</BLOCKQUOTE>

¿Es ésta la pregunta del examen?

Texto libre.
  1. [<>]
  2. http://www.di-mare.com/
    adolfo/cursos/2006-2/
    ac-ea-2.htm#XML

3.a) [5 pts] Use el documento XML de la izquierda y dibuje el árbol que contiene los nodos y etiquetas del documento. Recuerde que cada "nodo" se reconoce porque está a la par del paréntesis angular "<" y cada etiqueta está seguida de un argumento encerrado entre comillas. Por ejemplo, en "<CODE>" el "nodo" es "CODE" y una de las etiquetas del nodo "IMG" se llama "ALT" y tiene asociado el atributo "[&lt;&gt;]". Tome en cuenta que algunos nodos XML no están emparejados, como ocurre con "<BR/>".

3.b) [6 pts] Explique cuáles son los tokens y los lexemas para el lenguaje XML.

3.c) [11 pts] Escriba una grámatica que genere documentos XML.

3.d) [11 pts] Use su grámatica para derivar el primer bloque "<LI>" de este documento XML.

 

Soluciones

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