CI-1322 Examen #1


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1322
II Semestre 2006

$[\/]$

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

$[/\]$