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 #1 [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] Considere la siguiente gramática G ambigua:
  R -> Q R | 0
  Q -> R Q | 1

1.a) [0 pts] Explique qué significa que una gramática es ambigua.

1.b) [8 pts] Encuentre una hilera de al menos 10 símbolos para la que existan 2 árboles de derivación diferentes. Explique cómo obtuvo esa hilera.

1.c) [8 pts] Dibuje los 2 árboles de derivación que correspondan a la hilera que encontró en el punto anterior.

1.d) [8 pts] Dibuje el autómata finito P que averigua si es par la cantidad de ceros o unos de una subhilera de (0+1)*.

1.e) [9 pts] Explique si L(P) == L(G). Apoye su explicación con un ejemplo o un contraejemplo.

 

2) [33 pts] Considere la expresión (23 * 32) / 15 ** 1.5 en la que el operador ** denota la exponenciación, y los otros dos son la multiplicación y la división.

2.a) [6 pts] Para esta expresión indique cuáles son los tokens y lexemas que un analizador léxico retornaría.

2.b) [7 pts] Escriba una gramática que sirva para generar expresiones similares a ésta. Recuerde que la exponenciación tiene mayor precedencia que la multiplicación y la división.

2.c) [20 pts] Suponga que usted ya cuenta con un analizador léxico que retorna los tokens para procesar hileras generadas por su gramática. Implemente en C++, Java o C# un analizador sintáctico que use ese analizador léxico para evaluar este tipo de expresiones.

 

3) [33 pts] La gramática G tiene estas producciones: S --> S(S) | ε

3.a) [11 pts] Describa en palabras el lenguaje que esta gramática genera.

3.b) [11 pts] Haga una derivación de una hilera "w" en L(G) en la que aplique por lo menos 10 producciones de "G".

3.d) [11 pts] Aplique el algoritmo para eliminar la recursividad izquierda para obtener, partir de "G", una gramática equivalente que no sea recursiva izquierda.

 

Soluciones

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