Examen #2 [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] La compañía Sin­Ton 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 Sin­Ton, 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.

2.a) [7 pts] Escriba una expresión regular que sirva para reconocer todas estas expresiones (si su respuesta es trivial obtendrá una calificación mínima). Ignore los espacios y suponga que los números siempre tienen un dígito, en el rango [1..3].

2.b) [8 pts] Transforme la expresión regular en un autómata no determinista que sirva para reconocerla.

2.c) [18 pts] Minimice el autómata que obtuvo en el punto anterior. Incluya el dibujo del autómata minimizado.

3.a) [7 pts] Escriba una gramática libre de contexto G que genere este tipo de expresiones (si su gramática es trivial obtendrá una calificación mínima).

3.b) [18 pts] Construya las tablas de análisis sintáctico SLR para esta gramática.

3.c) [8 pts] Muestre cómo reconoce su analizador la expresión: 2 - - 3

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

Las expresiones expi son expresiones aritméticas de la forma:

en donde todos los operadores aritméticos son asociativos hacia la derecha.

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2001
Derechos de autor reservados © 2001