CI-1322 Examen #2


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
II Semestre 2008

$[\/]$

CI-1322 Autómatas y compiladores

Examen #2 [solución]

Duración: Ciento veinte minutos. Lea bien el examen antes de hacerlo. El examen es a libro abierto. Cuenta la documentación. 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] Considere la siguiente gramática G:

stmt → emparejado
stmt → des-emparejado
emparejado → IF expr THEN emparejado ELSE emparejado
emparejado → OTHER
des-emparejado → IF expr THEN stmt
des-emparejado → IF expr THEN emparejado ELSE des-emparejado

1.a) [5 pts] Factorice esta gramática para obtener G', una gramática equivalente a G que no es amibgua.

1.b) [6 pts] Calcule los conjuntos Primero() y Siguiente() para G'.

1.c) [11 pts] Calcule las tablas LL(1) para G'.

1.d) [11 pts] Calcule las tablas SLR(1) para G'.

2) [33 pts] Considere la siguiente gramática G:

   Pr()  Sg()    a   b    c    $
S  abc    $    S→Aa S→Bb S→cC
C  ab     $    C→Ba C→Ab
A  ε      ab   A→D  A→D
B  ε      ab   B→D  B→D
D  ε      ab   D→ε  D→ε

2.a) [6 pts] Escoja una hilera que del al menos 13 símbolos no esté en L(G) y muestre cómo la rechaza el autómata.

2.b) [5 pts] Escoja una hilera de al menos 7 símbolos que sí esté en L(G) y muestre cómo la procesa el autómata.

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

2.d) [5 pts] Muestre cómo procesa el autómata SLR(1) la hilera que usted escogió en el punto a) de esta pregunta.

2.e) [6 pts] Muestre cómo procesa el autómata SLR(1) la hilera que usted escogió en el punto b) de esta pregunta.

3) [33 pts] HTML es un lenguaje de marcas usadas para definir cómo debe ser desplegado el texto de un documento. Por ejemplo, la pareja de etiquetas <STRONG> </STRONG> sirve para que el hojeador ponga en letra negra el texto. Escriba un programa Lex/Flex que recibe como entrada un archivo de texto escrito en formato HTML y produzca como salida el texto del archivo, omitiendo todo menos las etiquetas HTML. Recuerde que algunas etiquetas HTML incluyen parámetros como los siguientes:

<IMG SRC="http://www.di-mare.com/img/index.gif" ALT="[<>]" BORDER="0">

Soluciones

$[/\]$