Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
Profesor Adolfo Di Mare
CI-1322
II Semestre 2001
[<=] [home] [<>] [\/] [=>]
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 el siguiente autómata con estado inicial a y estado final D:

  a b c D e f g h
0 b a D D D g f g
1 a c b a f e g D

1.a) [2 pts] Haga el diagrama de este autómata.

1.b) [20 pts] Minimice el autómata. Muestre claramente los cálculos que realice. Incluya un diagrama del autómata resultante.

1.c) [11 pts] Escriba una expresión regular que reconozca el lenguaje del autómata.

 

2) [33 pts] Esta gramática es muy particular, pues es LL(1) pero no es SLR(1):
X --> 1U2U | 2D1D
U --> ε
D --> ε

2.a) [11 pts] Calcule las tablas LL(1) para esta gramática.

2.b) [11 pts] Calcule las tablas SLR(1) para esta gramática.

2.c) [5 pts] Muestren cómo se comporta el autómata LL(1) al reconocer la hilera "12".

2.d) [6 pts] Muestren cómo se comporta el autómata LL(1) al reconocer la hilera "111112".

 

3) [33 pts] 

<P></P>
<BLOCKQUOTE>
  <TABLE>
    <TR>
      <TD>
        <PRE>Contenedor primero
        </PRE>
      </TD>
    </TR>

    <TR>
      <TD>
        <PRE>  Cambios y pruebas 
        </PRE>
      </TD>
    </TR>
  </TABLE>
</BLOCKQUOTE>

<P></P>
<BLOCK-QUOTE>
  <TABLE>
    <TR>
      <TD>
        <PRE>Contenedor primero
        </PRE>
      </TD>
    </TR>

    <TR>
      <TD>
        <PRE>  Cambios y pruebas 
        </PRE>
      </TD>
    </TR>
  <TABLE>
</BLOCKQUOTE>

XML es estándard internacional para el intercambio de datos entre aplicaciones. Los documentos XML contienen etiquetas que abren y cierran un bloque de datos, con la ventaja de que también pueden estar anidadas. La etiquetas se encierran entre paréntesis angulares, y la etiqueta que cierra un bloque de datos tiene el mismo nombre que la que lo abre, con la diferencia de incluye el caracter "/". En la Figura, el documento XML de la izquierda está bien formado, mientras que el de la derecha no, pues en el de la derecha la etiqueta <TABLE> está mal cerrada porque no aparece el caracter "/", no existe la etiqueta de cierre para <BLOCK-QUOTE> y sobra al etiqueta de cierre </BLOCKQUOTE>. El valor de los datos del documento, representado en este ejemplo por las hileras "Contenedor primero" y "Cambios y prueba", no pueden contener los caracteres "<", ">" o "&".

3.a) [11 pts] Haga un programa Lex para reconocer los identificadores válido en C++, para que pueda usarlos como etiquetas XML.

3.b) [11 pts] Escriba una gramática que genere documentos XML bien formados.

3.c) [11 pts] Haga un programa Bison que determine si un documento XML está bien formado.

Soluciones

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