Departamento de Ingeniería de Sistemas Telemáticos
Universidad Politécnica de Madrid

Programación

Plan 64M2

1. Práctica especial
2. Enunciado de la Práctica Especial
3. Requisitos
4. Reglas de Reescritura
5. El Fichero de Reglas
6. Ejemplo de Ejecución
7. Implementación
8. Pruebas
ATENCION: Se han modificado las pruebas para corregir algunos errores.
9. Ficheros utiles

1. Práctica especial.

Para las convocatorias extraordinarias de la asignatura de Programación del plan 64M2, los alumnos podrán elegir entre dos opciones para superar la parte práctica:

2. Enunciado de la Práctica Especial

La práctica especial consiste en realizar un programa filtro, llamado REWRITE, que transforme las expresiones que le introduzcan por su entrada estándar, de acuerdo con una lista de reglas de reescritura.

REWRITE cargará inicialmente de un fichero las reglas de reescritura que tiene que aplicar sobre las expresiones que se lean. Estas reglas deben almacenarse internamente en una tabla, para aplicarlas posteriormente sobre todas las expresiones que se introduzcan.

Una vez cargada la tabla de reglas, el filtro leerá por su entrada estándar las expresiones que debe reescribir, presentando el resultado de cada reescritura por la salida estándar. REWRITE debe realizar todas las reescrituras posibles sobre cada expresión introducida, hasta que no pueda aplicarse ninguna regla más.

3. Requisitos

El filtro deberá satisfacer los siguientes requisitos:

4. Reglas de Reescritura

Las reglas de reescritura que se manejarán en este trabajo estarán formadas por un patrón de búsqueda, un patrón de sustitución y opcionalmente una premisa. El patrón de búsqueda identifica la parte de la expresión que queremos reemplazar por el patrón de sustitución, siempre y cuando la premisa se cumpla.

Ejemplo:

La regla: 
          
          patrón de búsqueda    =  a + a
          patrón de sustitución =  2 * a
indica que en todos los puntos de una expresión en que se sumen dos subexpresiones sintacticamente (no el resultado de su evaluación) iguales (a+a), deberá sustituirse por una multiplicación por 2.

Así, la expresión "3*((5-4)+(5-4))/(3+3)" se transformaría en "3*(2*(5-4))/(2*3)".

Se ha aplicado la regla dos veces. La primera vez para sustituir "(5-4)+(5-4)" por "2*(5-4)", (la variable "a" estaba asociada a "(5-4)"); y la segunda para sustituir "3+3" por "2*3" (la variable "a" estaba asociada a "3").

Nótese que no se debe evaluarse ninguna parte de la expresión para ver si encaja el patrón de búsqueda. Sólo deben realizarse comparaciones sintácticas.

Ejemplo:
La regla 
     
          patrón de búsqueda    = a + b
          patrón de sustitución = 2 * a
          premisa               =  a = b
indica que la suma de dos subexpresiones cualesquiera debe sustituirse por una multiplicación por dos por la primera subexpresión, siempre y cuando las dos subexpresiones representen el mismo valor.

Como en el ejemplo anterior, primero debe buscarse una expresión que encaje sintácticamente con el patrón de búsqueda. Una vez encontrada esta expresión, se evaluará la premisa para ver si puede aplicarse la regla. Caso de poder aplicarse, se sustituirá por el patrón de sustitución.

Esta regla difiere de la del ejemplo anterior en que para aplicarla, las dos subexpresiones que se están sumando deben valer lo mismo, aunque sean sintácticamente diferentes.

En una regla de reescritura pueden utilizarse muchas variables para indicar cualquier subexpresión. Pero siempre que se repita una misma variable, debe estar asociada a la misma subexpresión para que la regla pueda aplicarse. Es decir, el patrón de búsqueda "a + a" no encaja con "2+4", pero si encajaría con el patrón "a + b". El alumno deberá mantener una tabla donde almacenará las variables y expresiones asociadas cada vez que intente aplicar una regla.

En el proceso de localización de un patrón de búsqueda que encaje con una expresión, sólo deben realizarse comparaciones sintácticas. En ningún momento debe evaluarse nada. De esta forma el patrón de búsqueda "a + a" no encajaría con "2*2+4", al ser ambos sumandos distintos sintácticamente. Las únicas expresiones sobre las que deben realizarse evaluaciones son las premisas y las variables de evaluación.

Si una subexpresión encaja con un patrón de búsqueda, debe evaluarse la premisa para ver si debe realizarse o no la sustitución. Debe realizarse la sustitución indicada por los patrones sólo si la premisa se cumple. Una premisa se cumple si al evaluarla se obtiene un valor numérico distinto de cero. Si al evaluar la premisa se obtiene una expresión con variables no debe realizarse la sustitución, ya que dependiendo del valor que tomen las variables la premisa podría ser verdadera o no.

No confundir las variables que aparecen en las reglas de reescritura con las que puedan contener las expresiones de entrada. No tienen nada que ver unas con otras.

Para realizar el proceso de búsqueda y sustitución de patrones, lo ideal es trabajar con las expresiones en formato arboreo. En este formato es muy simple realizar las funciones de comparación, sustitución, etc.

5. El Fichero de Reglas

Las reglas de reescritura se almacenarán en un fichero de reglas utilizando una línea por regla. El formato utilizado será el siguiente: 
     <patron de busqueda> : <patron de sustitucion> : <premisa>
Los corchetes finales indican que la premisa final es opcional, no deben escribirse.

Ejemplo:

Si se desea crear un fichero con las reglas siguientes: el contenido del fichero de reglas será: 
   
          a*(b+c) : a*b+a*c
          (a+b)*c : (a*c)+(b*c)
          a+b : b+a : a<b
          a*1 : a
          1*a : a

6. Ejemplo de Ejecución

Como ilustración del proceso de reescritura, calcularemos el resultado de aplicar las reglas de la sección anterior sobre la expresión "( 4 + x ) * ( 1 + 5 )".

Primero se sustituirá "1+5" por "5+1" al aplicar la tercera regla ya que "a" y "b" se corresponden con "1" y "5" , cumpliéndose la premisa.

Luego se sustituirá "(4+x)*(5+1)" por "(4+x)*5 + (4+x)*1" al aplicar la primera regla de reescritura, donde "a", "b" y "c" se corresponden con "4+x", "5" y "1".

Aquí se aplicará dos veces la segunda regla, en el primer caso para "a" igual a "4", "b" igual a "x" y "c" igual a "5", y en el segundo caso para para "a" igual a "4", "b" igual a "x" y "c" igual a "1", obteniéndose como resultado "(4*5+x*5) + (4*1+x*1)".

Finalmente se sustituye "4*1" por "4", y "x*1" por "x" al aplicar la cuarta regla, obteniéndose como resultado final "(4*5+x*5) + (4+x)" al no poderse aplicar ninguna regla más.

Nótese que si en la expresión de entrada la variable "x" se hubiera llamado "a", el resultado no habría variado, ya que las variables en las reglas y en las expresiones de entrada no tienen nada que ver entre si. No almacenan el mismo valor, ni se refieren a una misma expresión.

7. Implementación

Esta sección da algunas sugerencias sobre como debe realizarse la práctica del filtro reescribidor de expresiones. Unicamente pretende orientar en líneas generales sobre la realización de la práctica, por lo que no se comentarán todos los detalles de la realización. El alumno deberá refinar estos detalles por su propia cuenta.

7.1. Programa principal y UNITs necesarias

Para realizar esta práctica pueden reutilizarse las units que se emplearon en el curso 95-96 en la práctica B del filtro evaluador para leer las expresiones, construir los árboles, etc.

El programa principal será parecido también. Debe modificarse ParseCommandLine para que lea el nombre del fichero de reglas, y el bucle principal deberá llamar a la función ReescribeExpr en lugar de llamar a SustVarExpr y a EvalExpr.

7.2. Tabla de Reglas de reescritura

El fichero de reglas de reescritura debe leerse al principio del programa principal y almacenar todas las reglas en una tabla. Esa tabla se consultará para reescribir todas las expresiones que se introduzcan al filtro. No debe leerse el fichero de reglas cada vez que se quiera reescribir una expresión, sino que se leerá una vez al principio ya que siempre son las mismas reglas, y es una pérdida de tiempo repetir una y otra vez el mismo proceso. Por esto, debe tenerse cuidado de no alterar la tabla donde se guarden las reglas durante el funcionamiento del programa. Si al reescribir una expresión modificamos esa tabla, cuando introduzcamos nuevas expresiones tendremos errores o resultados incorrectos.

Las reglas deben almacenarse en la tabla en formato arbóreo ya que las operaciones de escritura se harán en este formato. Así, sólo realizamos el paso a formato arbóreo de las reglas una sola vez.

Dado que una regla está formada por tres expresiones, el patrón de búsqueda, el patrón de sustitución y la premisa (puede no existir), la tabla tendrá tres dimensiones.

Se recomienda realizar una función que imprima en pantalla el fichero de reglas. Esta función puede emplearse para comprobar que la función que lee el fichero de reglas y construye la tabla está bien hecha. También puede emplearse en cualquier punto del programa para depurarlo, asegurándonos de que nadie ha modificado la tabla de reglas durante los procesos de reescritura.

Se recomienda hacer una unit separada para el manejo de las tablas de reglas.

7.3. Reescritura de una Expresión

El proceso de reescritura de una expresión es muy laborioso pues debe comprobarse continuamente si una regla puede aplicarse en algún punto de la expresión. Nótese que una regla que no puede aplicarse en un momento dado, puede que si pueda aplicarse en una fase posterior despues de haber aplicado otras reglas.

Para reescribir una expresión debe realizarse una función llamada ReescribeExpr. Esta función tomará como argumento la expresión a reescribir, e intentará aplicar todas las reglas de reescritura una y otra vez sobre todas sus subexpresiones. Esta función terminará cuando no pueda aplicar ninguna regla sobre ningún punto de la expresión. Para lograr esto, la función ReescribeExpr llamará repetidamente a la AplicaRegla.

La labor de la función AplicaRegla(expresion,regla) es aplicar una determinada regla de reescritura, que se pasa como parámetro, sobre cualquier punto de la expresión. Es decir, mirará si el patrón de búsqueda de la regla dada encaja en algún punto de la expresión para realizar una reescritura. Este proceso lo repetirá mientras pueda. Esta función devolverá un booleano que indique si pudo aplicar la regla alguna vez sobre la expresión. El valor devuelto es usado por ReescribeExpr para saber cuando debe terminar. Esta función se construye apoyándose en AplicaReglaRaíz. AplicaRegla invocará a AplicaReglaRaíz pasándole como argumento todas las subexpresiones que forman la expresión a reescribir.

AplicaReglaRaíz(subexpresión,regla) intenta aplicar la regla de reescritura regla sobre la raíz de la subexpresión, es decir, mira si el patrón de sustitución de la regla encaja con subexpresión. Si es así, sustituirá la subexpresión por el patrón de sustitución debidamente actualizado siempre y cuando la premisa sea verdadera.

Para ver si una expresión y un patrón de búsqueda encajan, debe realizarse una comparación de los árboles teniendo en cuenta los siguientes puntos :

Este proceso de comparación se realizará con la función ComparaSalvoVariable(expresión,patrón de búsqueda). Esta función compara las dos expresiones pasadas como argumentos, para ver si son iguales o no, siguiendo los criterios explicados arriba.

Además, según realiza la comparación rellenará la tabla de pares variable-subexpresión. Esta tabla es necesaria cuando una comparación es exitosa para sustituir en el patrón de sustitución las variables por expresiones. En el ejemplo anterior, el patron de sustitución podría ser "2*a", con lo cual deberíamos hacer una copia del patron de sustitución y reemplazar la variable "a" por "2*3".

Si la comparación no tiene éxito, no debe generarse la tabla de pares antes indicada.

Llegados al punto de que un patrón de sustitución y una expresión encajan (ComparaSalvoVariable ha devuelto TRUE y ha construido la tabla de pares), es el momento de evaluar la premisa. Para ello se hará una copia de la premisa y se reemplazarán las variables por los valores asociados según indica la tabla de pares. Se evaluará la premisa, y si como resultado se obtiene un valor numérico distinto de cero se procederá a sustituir la expresión encontrada por el patrón de sustitución. Se hará una copia del patrón de sustitución y se sustituirán las variables según indique la tabla de pares.

Nótese que el motivo de realizar una copia del patrón de sustitución y de la premisa es no modificar (corromper) la tabla de reglas de reescritura. Esta tabla no debe alterarse nunca.

Se recomienda crear una unit independiente para todas las labores de reescritura. También es aconsejable implementar estas funciones siguiendo un enfoque de abajo a arriba, es decir, implementar primero las funciones de más bajo nivel, las más específicas, y probarlas intensivamente. Una vez que funcionen se construirán las funciones de más alto nivel, y así sucesivamente hasta llegar a la función ReescribeExpr, que se implementará la última de todas.

7.4. Construcción de los árboles.

Una de las tareas que debe realizar la práctica es transformar expresiones reales, representandas como strings, en árboles binarios. Para realizar esta taréa se propone crear una función llamada CreaArbol que implemente el pseudocódigo presentado a continuación.

CreaArbol tendrá tres argumentos, el string que contiene la expresión a transformar, una marca que indica hasta que punto hemos avanzado en la exploración del string, y el valor de la prioridad del último operador. Esta función debe llamarse inicialmente con pos apuntando al principio de la expresión, y con up igual a cero. 

   exp:  1 * (4.2 * x - 5 ) / 3
                      ^
                     pos         (up=2)

La función que crea el árbol es: 

FUNCTION CreaArbol(exp ; VAR pos ; up) : Arbol
VAR nodo, nodo2 : Arbol;
BEGIN
   IF pos apunta al final de string THEN Error;
   IF pos apunta a un numero THEN BEGIN
      nodo := crear un nodo que contenga el numero apuntado por pos;
      avanzar la posicion pos detras del numero
   END ELSE IF pos apunta a una letra THEN BEGIN
      nodo := crear un nodo que contenga la variable apuntada por pos;
      avanzar la posicion pos detras de la variable
   END ELSE IF pos apunta a abre parentesis THEN BEGIN
      avanzar pos detras del abre parentesis;
      nodo := CreaArbol(exp,pos,0);
      IF pos no apunta a un cierra parentesis THEN Error;
      avanzar pos detras del cierra parentesis;
   END ELSE BEGIN
      Error 
      {las expresiones solo pueden empezar con un numero, una variable
       o un abre parentesis}
   END;
   WHILE pos apunta a un operador de prioridad mayor que up DO BEGIN
      nodo2 := crear un nodo que contenga el operador apuntado por pos;
      avanzar la posicion pos detras del operador;
      nodo2^.izq := nodo;
      nodo2^.der := CreaArbol(exp,pos,prioridad de nodo2^.dato);
      nodo := nodo2;
   END;
   IF (pos no apunta al final de exp) and 
      (pos no apunta a un operador) THEN Error;
   CreaArbol := nodo;
END;

donde Error presenta un mensaje de error y aborta la función.

La prioridad de los operadores es la siguiente:

Operador Priodidad
) 0
+ - 1
* / 2

8. Pruebas

8.1. Prueba

8.2. Prueba

8.3. Prueba

8.4. Prueba

8.5. Prueba

8.6. Prueba

8.7. Prueba

8.8. Prueba

8.9 Prueba

9. Ficheros utiles

Ficheros proporcionados en el curso 94-95 para la realización de las prácticas:
Página actualizada el dia 14 de Mayo de 1998.