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 2001

$[\/]$

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

1) [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 }

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

1.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.

1.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.

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] El lenguaje C tiene una instrucción con la siguiente forma: for ( exp₁; exp₂; exp₃ ) { stmt }

Escriba un esquema de traducción por sintaxis que transforme un ciclo for en el siguiente código:

{ exp₁; while ( exp₂ ) { stmt; exp₃; } }

4) [33 pts] La compañía SinTon acaba de descubrir que necesita renovarse tecnológicamente, pues sus programas usan bases de datos obsoletas. Para eso lo contratan a usted, pues necesitan cambiar los nombres de los campos y registros usados en la base de datos.

Cualquier campo que aparece en una relación debe estar calificado por el nombre de la relación. En un programa siempre se sustituye el nombre de una relación aunque aparezca solo, pero no ocurre lo mismo con el nombre de un campo, como se puede ver en el siguiente trozo de código:

{ Trabaja sobre el registro EMPLE }
Procese("EMPLE", "KEY=EMPLE.NOM03", "SX");

Usted ha sido contratado para escribir un programa Perl que transforme los nombres de campos y relaciones de acuerdo a una tabla de traducción. Esa tabla es un diccionario contenido en un archivo de texto que tiene renglones de dos hileras, o más. El nombre de una relación siempre aparece cargado a la izquierda (a partir de la columna uno), y el de un campo aparece luego de la columna uno. Un ejemplo de esta tabla de traducción es el siguiente:

EMPLE    R_empleado      // Esto es un comentario:
  NOM03    nombre        //   su programa sólo procesa
  APE=#    apellido      //   las primeras dos hileras
  SX       tip_sexo
  DPT00    cod_depto     // Ignore los renglones en blanco

SAL      R_salario       // SAL es nombre de relación
  KID      cod_empleado  //   pues está en la columna 1
  MONT     mon_salario   // MONT es el nombre de un campo de SAL
  FECHA    fch_salario   //   pues está después

Si se usa su programa Perl para traducir los programas fuente de los sistemas de la compañía SinTon, el bloque de código que aparece arriba quedaría traducido así:

{ Trabaja sobre el registro R_empleado }
Procese("R_empleado", "KEY=R_empleado.nombre", "SX");

Cuide de evitar traducir una hilera ("SX") en un contexto en que no esté calificada por el nombre de relación ("EMPLE"). Note que las comillas no afectan el resultado final de su programa.

Soluciones

$[/\]$