CI-1322 Examen Final


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
I Semestre 2008

$[\/]$

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

1) [33 pts] Considere este autómata cuyo estado inicial es 1, y cuyos estados finales son { 2,3,4,6 }:

      | 0 | 7 | 9 | X | A |
------+---+---+---+---+---+
==> 1 | 2 | 4 | 4 |   |   | 0 ==>    0 == { 0 }
------+---+---+---+---+---+
**  2 | 3 | 3 |   | 5 |   | 7 ==>  1-7 == { 1,2,3,4,5,6,7 }
------+---+---+---+---+---+
**  3 | 3 | 3 |   |   |   | 9 ==>  8-9 == { 8,9 }
------+---+---+---+---+---+
**  4 | 4 | 4 | 4 |   |   | X ==>  x X == { x,X }
------+---+---+---+---+---+
    5 | 6 | 6 | 6 |   | 6 | A ==>  A-F == { A,B,C,D,E,F } U { a,b,c,d,e,f }
------+---+---+---+---+---+
**  6 | 6 | 6 | 6 |   | 6 |
------+---+---+---+---+---+
      | 0 |1-7|8-9|x X|A-F|
      +---+---+---+---+---+

1.a) [0 pts] Dibuje este autómata. Explique cómo es el lenguaje reconocido por este autómata.

1.b) [3 pts] Diga a qué expresión regular corresponde este autómata.

1.c) [11 pts] Minimice este autómata. Explique lo que hace en cada paso.

1.d) [11 pts] Construya la tabla LL(1) para esta gramática. Justifique por qué incluye cada producción en la tabla.

1.e) [8 pts] Muestre cómo procesa la hilera "0x1A2B3C" el autómata LL(1).

2) [33 pts] Considere la siguiente gramática U: S -> id = S | S + S | id

2.a) [9 pts] Demuestre que esta gramática es ambigua y modifíquela para obtener G, una gramática equivalente pero que no es ambigua.

2.b) [8 pts] Hagas las tablas SLR(1) para G. Explique lo que hace.

2.c) [8 pts] Hagas las tablas LALR(1) para G. Explique lo que hace.

2.d) [8 pts] Hagas las tablas LR(1) para G. Explique lo que hace.

3) [33 pts]

Año	Ganancia	Pérdidas	Reclamos
2007	1,200,000	1,400,000	600,000
2008	1,500,000	1,900,000	800,000

<TABLE BORDER="1" CELLPADDING="0" CELLSPACING="0">
<TR>  <TH> Año </TH>       <TH> Ganancia </TH>
      <TH> Pérdidas </TH>  <TH> Reclamos </TH>  </TR>
<TR>  <TD> 2007 </TD>             <TD> 1,200,000 </TD>
      <TD> 1,400,000 </TD>        <TD>   600,000 </TD> </TR>
<TR>  <TD> 2008 </TD>             <TD> 1,500,000 </TD>
      <TD> 1,900,000 </TD>        <TD>   800,000 </TD> </TR>
</TABLE>

Con el fin de colectar información financiera la firma Arracache INC le ha contratado para que extraiga información financiera de los computadores de la competencia. Después de sobornar varios empleados, usted ha logrado colectar más de un millón archivos con datos, organizados todos en archivos HTML que contienen tablas bidimensionales enmarcadas en las etiquetas TABLE, TR, TH y, TD. Para procesar esta cantidad enorme de archivos usted debe escribir un programa Lex/Yacc que procese todos los archivos y que grabe en formato CSV todas las tablas extraídas de los documentos HTML fuente. Use setQuotedCSV().

void setQuotedCSV( std::string & res, const std::string & value )
Prepara "value" para ser grabado en un archivo CSV.

Almacena un valor nuevo en la hilera "res".
Rodea el resultado de comillas dobles cuando "value" tiene espacios en blanco (whitespace).
Rodea el resultado de comillas dobles cuando "value" tiene comillas dobles.
Rodea el resultado de comillas dobles cuando "value" tiene comas ",".
Sustitutye cada comilla doble '"' dentro de "value" por 2 comillas dobles [""].
Trabaja con char; no ha sido probada con wchar_t.

{{  // test::setQuotedCSV()
    std::string res;
    setQuotedCSV( res, ","    );  assertTrue( res == "\",\"" );     // [","]
    setQuotedCSV( res, "2"    );  assertTrue( res == "2" );         // [2]
    setQuotedCSV( res, ""     );  assertTrue( res == "" );          // []
    setQuotedCSV( res, "4,5"  );  assertTrue( res == "\"4,5\"" );   // ["4,5"]
    setQuotedCSV( res, "K\""  );  assertTrue( res == "\"K\"\"\"" ); // ["K"""]
    setQuotedCSV( res, "\r\n" );  assertTrue( res == "\"\r\n\"" );  // ["\r\n"]
}}

Soluciones

$[/\]$