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

Examen de Ampliación [solución]

Resuelva en la computadora estas preguntas. Su respuesta debe ser completa.

 

1) [33 pts] Un ejemplo de la uso del lenguaje Snobol es el programa WordSize.sno que lee un archivo y calcula la cantidad de palabras de longitudes de entre 3 y nueve letras: 

       &TRIM    =      1
       WORDPAT  =      BREAK(&LCASE &UCASE) SPAN(&LCASE &UCASE "'-") . WORD
       COUNT    =      ARRAY('3:9',0)
READ   LINE     =      INPUT                           :F(DONE)
NEXTW  LINE WORDPAT =                                  :F(READ)
       COUNT<SIZE(WORD)> = COUNT<SIZE(WORD)>+ 1        :(NEXTW)
DONE   OUTPUT   =      "WORD LENGTH     NUMBER OF OCCURRENCES"
       I        =      2
PRINT  I        =      I + 1
       OUTPUT   =      LPAD(I,5) LPAD(COUNT<I>,20)     :S(PRINT)
END

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

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

1.c) [11 pts] Haga un programa Lex que sirva para reconocer los tokens de este lenguaje.

1.c) [22 pts] Haga un programa Yacc que sirva para reconocer este lenguaje. Su programa debe usar el analizador léxico del punto anterior. Su respuesta debe ser completa. No caiga en el error de usar una gramática trivial.

 

2) [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 "&".

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

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

2.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 © 2003
Derechos de autor reservados © 2003
[home] <> [/\]