next up previous contents
Next: La recuperación parcial Up: La recuperación incremental Previous: La recuperación incremental

La recuperación total

Para que la recuperación total sea posible a partir de una posición i en la cadena de entrada es necesario asegurarse de que todas las futuras transiciones que eliminen elementos de la pila no dependan de la parte de la entrada modificada. Esto quiere decir que las modificaciones sólo deben causar perturbaciones locales, es decir, que sólo afectan a ramas interiores del bosque de análisis.

Para que se pueda realizar una recuperación completa a partir del itemset correspondiente a la posición i de la entrada es condición suficiente que para cada item que cumpla las siguientes condiciones, I sea estable y t<l, siendo l el punto de modificación relativa de w y x. Las condiciones son:

  1. I es el argumento en una transición que elimina elementos de la pila realizada desde un punto en el sufijo de . Es decir, desde la parte de la entrada que queda más a la derecha que .
  2. Todas las transiciones que eliminan elementos de la pila y que tienen a I como argumento, hacen la transición a un itemset con t<i-1.

A los items que satisfacen las condiciones 1 y 2 se les denomina o más simplemente cuando no hay confusión posible.

Una condición suficiente para la recuperación total es la siguiente: Dada una cadena con , que tiene alguna modificación con respecto a , y un punto de modificación relativa de w y x, tal que se verifica que y

entonces, desde el punto de vista del reconocedor,

Esto quiere decir que si las transiciones que eliminan elementos de la pila son las mismas y la porción de texto que falta por analizar es la misma, entonces el proceso de análisis será idéntico a partir de ahí.

Este resultado se puede extender al caso de varias modificaciones simultáneas en la cadena de entrada definiendo un punto recuperado totalmente de una modificacion relativa a w y x como el punto en el proceso de recuperación tal que dicha modificación ha sido totalmente recuperada [Vilares y Dion 94].

Hasta aquí en lo que se refiere al reconocedor. En lo concerniente al analizador sintáctico, se debe encontrar además el alcance de las modificaciones en el bosque compartido inicial, una tarea relativamente sencilla ya que los nodos que se ven afectados por cambios en su estructura son los comunes con el nuevo bosque que tienen al menos un descendiente cambiado con respecto al nuevo desarrollo. Para actualizar uno de estos nodos es suficiente con encontrar sus descendientes estables en el bosque que han sido realmente recalculados y reemplazarlos por la estructura original correspondiente en el bosque de análisis recuperado.

Como sólo se recuperan itemsets completos, este fenómeno está limitado a los items que representan nodos triviales estables para los cuales sus ancestros en el bosque no se calculan en el mismo itemset en el que ellos están incluidos. A esos items se les denomina o simplemente cuando no hay confusión posible.

Con el fin de extender la recuperación total al analizador, se debe asignar para todos los , donde y representan el mismo nodo en el bosque de análisis, es decir .


next up previous contents
Next: La recuperación parcial Up: La recuperación incremental Previous: La recuperación incremental

Miguel A. Alonso Pardo
Thu Nov 20 15:31:06 CET 1997