CI-1322 Examen #3


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

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

R -> R Q | 0 Q -> Q R | 1

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

1.b) [6 pts] Demuestre que esta gramática no es LL(1).

1.c) [6 pts] A partir de G obtenga la gramática G' a la que le ha eliminado la recursividad izquierda.

1.d) [6 pts] Calcule Primero() y Siguiente() para la gramática G'.

1.e) [15 pts] Construya las tablas SLR(1) para G'.

1.f) [0 pts] Muestre cómo procesa el autómata SLR(1) la hilera "01a".

2) [33 pts] Considere el lenguaje de las listas, en que las hileras tienen esta forma: ( ( a ( a a ) ) ( a a ) ( ( ( ) ) ) ( a a a ) a a )

2.a) [11 pts] Escriba una gramática LL(1) que sirva para generar todas las listas. Recuerde también generar la hilera nula.

2.b) [11 pts] Encuentre las tablas que un analizador sintáctico LL(1) usaría para reconocer hileras de este lenguaje.

2.c) [11 pts] Muestre cómo un analizador sintáctico que use las tablas que usted calculó reconocería la siguiente hilera (suponga que el analizador léxico salta sobre los espacios en blanco):

( a ( a a ) )

3) [33 pts] Considere el siguiente autómata con estado inicial 0 y estado final 2:

	a	b	ε
0	{ 1 }		{ 2 }
1	{ 0 }	{ 0, 2 }	{ 2 }
2		{ 1 }

3.a) [5 pts] Dibuje el autómata.

3.b) [14 pts] Obtenga un autómata determinista a partir de este autómata. Escriba los pasos intermedios en la construcción para que muestre cómo aplica el algoritmo para hacerlo.

3.c) [14 pts] Minimice su autómata determinista. Escriba los pasos intermedios en la construcción para que muestre cómo aplica el algoritmo para hacerlo.

4) [33 pts] Considere el siguiente autómata M con estado inicial 0 y estado final 2:

	a	b	ε
0	{ 1 }		{ 2 }
1	{ 0 }	{ 0, 2 }	{ 2 }
2		{ 1 }

4.a) [0 pts] Dibuje el autómata.

4.b) [11 pts] Obtenga la gramática G que reconoce el lenguaje L(M). Asegúrese de que G sea una gramática LL(1).

4.c) [11 pts] Construya las tablas de LL(1) para G.

4.d) [11 pts] Muestre cómo un analizador sintáctico que use las tablas que usted calculó reconocería la siguiente hilera:

ababa

Soluciones

$[/\]$