Algoritmos tabulares para el análisis de TAG^{∗}

Miguel A. Alonso Pardo Departamento de Computación

Facultad de Informática Campus de Elviña s/n 15071 La Coruña, España

alonso@dc.fi.udc.es

David Cabrero Souto Centro Ramón Piñeiro para a Investigación en Humanidades

Estrada Santiago-Noia km 3, A Barcia 15896 Santiago de Compostela, España

     dcabrero@cirp.es

Eric de la Clergerie

INRIA Domaine de Voluceau Rocquencourt, B.P. 105

78153 Le Chesnay Cedex, Francia

Eric.De La Clergerie@inria.fr

Manuel Vilares Ferro Departamento de Computación

Facultad de Informática Campus de Elviña s/n 15071 La Coruña, España

    vilares@dc.fi.udc.es

Resumen

En este trabajo se realiza una descripción de varios algoritmos tabulares para el análisis sintáctico de las Gramáticas de Adjunción de Árboles, creando una línea evolutiva continua desde los algoritmos más simples a los más complejos y mostrando las transformaciones que deben ser aplicadas a cada uno de ellos para obtener el siguiente en la cadena evolutiva. Varios de los algoritmos descritos lo son por vez primera, tal es el caso del algoritmo de tipo Earley ascendente y la versión propuesta del algoritmo de tipo Earley sin la propiedad del prefijo válido.

1. Introducción

Las Gramáticas de Adjunción de Árboles (TAG) [4] son una extensión de las gramáticas independientes del contexto que utilizan árboles en vez de producciones como estructuras elementales. Formalmente, una TAG es una quíntupla (V_{N}, V_{T} , S, I, A), donde V_{N} es un conjunto finito de noterminales, V_{T} es un conjunto finito de terminales, S es el axioma de la gramática, I es un conjunto finito de árboles iniciales y A es un conjunto finito de árboles auxiliares. I ∪ A es el conjunto de árboles elementales. Los nodos internos de dichos árboles están etiquetados por no-terminales mientras que los nodos hoja lo están por terminales o bien por la cadena vacía ϵ, excepto un único nodo hoja, denominado pie, de cada árbol auxiliar que está etiquetado por el mismo no-terminal que etiqueta la raíz del árbol. El camino que recorre los nodos desde la raíz hasta el pie se denomina espina.

La derivación de nuevos árboles se realiza mediante la operación de adjunción: dado un árbol elemental α con un nodo etiquetado por el mismo no-terminal que la raíz y el pie de un árbol auxiliar β, la adjunción de β en α se realiza escindiendo el subárbol de α que tiene como raíz el nodo que se está considerando (que recibe el nombre de nodo de adjunción), pegando β a dicho nodo y pegando el subárbol escindido al pie de β. Notaremos mediante β ∈ adj(A^{α}) la posibilidad de que el nodo A de α sea nodo de adjunción de β.

En la descripción de los algoritmos de análisis para TAG, tenemos que representar el reconocimiento parcial de los árboles elementales. En las gramáticas independientes del contexto se utilizan habitualmente reglas punteadas para este fin. En el caso de TAG, consideraremos cada árbol elemental γ como constituido por un conjunto de reglas independientes del contexto P(γ) e indicaremos la posición del punto en el árbol indicando la posición en la regla correspondiente. Los elementos de las reglas serán los nodos del árbol, excepto en el caso de los elementos del lado derecho de las reglas cuyas etiquetas pertenecen a V_{T} ∪ ε, puesto que al no poder tener descendientes ni ser susceptibles de ser nodos de adjunción consideraremos directamente su etiqueta a la hora de escribir las reglas.

∗Financiado en parte por la Unión Europea mediante el proyecto 1FD97-0047-C04-02, por los ministerios de Educación y Cultura y Asuntos Exteriores a través de la acción integrada HF97-223 y por la Xunta de Galicia mediante los proyectos XUGA10505B96 y XUGA20402B97.

Con el fin de simplificar la descripción de los algoritmos seguiremos el enfoque de [5] de considerar la regla adicional ⊤ → R^{α} para cada árbol inicial α y las dos reglas adicionales siguientes para cada árbol auxiliar β: ⊤ → R^{β} y F^{β} → ⊥, donde R^{β} y F^{β} se refieren a los nodos raíz y pie de β, respectivamente. Con el fin de no modificar la capacidad generativa de las gramáticas, los nuevos nodos ⊤ y ⊥ no pueden ser nodos de adjunción.

1.1 Esquemas de análisis sintáctico

Describiremos los algoritmos de análisis mediante esquemas de análisis sintáctico [8], una estructura para realizar descripciones de alto nivel de algoritmos de análisis sintáctico que permite estudiar fácilmente las relaciones entre diferentes algoritmos mediante el análisis de las relaciones formales entre los esquemas de análisis subyacentes.

Un sistema de análisis sintáctico para una gramática G y una cadena de entrada a_{1} … a_{n} es un triple IP = ⟨I, H, D⟩, donde I es un conjunto de ítems que representan resultados intermedios del proceso de análisis, H es un conjunto inicial de ítems denominado hipótesis que representan la cadena que va a ser analizada y D es un conjunto de reglas de inferencia denominadas pasos deductivos, mediante las cuales se derivan nuevos ítems ξ a partir de los ítems η_{i} existentes. Estos pasos deductivos tienen la forma \frac{η_{1},...,η_{k}}{ξ} y su significado es el siguiente: si todos los antecedentes η_{i} ∈ H ∪ I de un paso deductivo ya existen, entonces el consecuente ξ deberá ser generado por el analizador sintáctico. Los pasos deductivos se suponen cuantificados universalmente para todas las posibles variables que aparezcan en los ítems a menos que se indique explícitamente lo contrario.

La presencia de un conjunto F ⊆ I de ítems finales indica el reconocimiento de la cadena de entrada.

Un sistema de análisis sintáctico no instanciado para una gramática G es un triple ⟨I, H, D⟩ con H una función que asigna un conjunto de hipótesis a cada cadena de entrada a_{1} … a_{n} ∈ V_{T}^{∗}, tal que ⟨I, H(a_{1} … a_{n}), D⟩ es un sistema de análisis sintáctico.

Un esquema de análisis sintáctico P para una clase de gramáticas es una función que asigna un sistema de análisis sintáctico no instanciado a cada gramática en dicha clase. Un esquema de análisis puede ser generalizado a partir de otro mediante las siguientes transformaciones:

• Refinamiento de los ítems, rompiendo un ítem individual en varios.

• Refinamiento de los pasos deductivos, descomponiendo un paso deductivo simple en una secuencia de pasos.

• Extensión de un esquema considerando una clase más amplia de gramáticas.

Las siguientes operaciones de filtrado permiten disminuir el número de ítems y pasos deductivos de un esquema de análisis:

• Filtrado estático, en el cual los pasos redundantes son simplemente descartados.

• Filtrado dinámico, utilizando información contextual para determinar la validez de los ítems .

• Contracción de pasos, en la cual una secuencia de pasos deductivos es reemplazada por un sólo paso.

2. Algoritmo de tipo CYK

Como punto de partida tomaremos el algoritmo de tipo CYK descrito en [9]. Asumiremos que todo nodo de un árbol elemental de la gramática tiene a lo sumo dos descendientes. Definimos el siguiente conjunto de ítems de la forma

[A^{γ}, i, j | p, q | adj]

tal que A^{γ} ⇒^{∗} a_{i+1} … a_{p} F^{γ} a_{q+1} … a_{j} ⇒^{∗}

a_{i+1} … a_{j} si y sólo si (p, q) ≠ (−, −) mientras

que A^{γ} ⇒^{∗} a_{i+1} … a_{j} si y sólo si (p, q) =

(−, −).

Estos ítems corrigen los definidos en [9] introduciendo un nuevo elemento que toma su valor del conjunto {true, false} y que indica, si su valor es true que el ítem es el resultado de una operación de adjunción ya totalmente realizada, si su valor es false que el ítem no es el resultado de una adjunción. Con ello podremos limitar a una sola la cantidad de adjunciones que se pueden realizar sobre cada nodo de un árbol elemental, ajustándonos de este modo a lo establecido en el formalismo de las gramáticas de adjunción [7]. También elimina la restricción de que los árboles auxiliares deban derivar al menos un símbolo terminal [9].

Esquema 1 El sistema de análisis IP_{CYK} que se corresponde con el algoritmo CYK para una TAG G y una cadena de entrada a_{1} … a_{n} se define como sigue:

I_{CYK} = \{ \begin{matrix}[A^{γ}, i, j | p, q | adj] | \\ A^{γ} ∈ V_{N}, γ ∈ I ∪ A, \\ 0 ≤ i ≤ j, (p, q) ≤ (k, j), \\ adj ∈ \{true, false\} \end{matrix} \}

H_{CYK} = { [a, i − 1, i] | a = a_{i}, 1 ≤ i ≤ n }

D_{CYK}^{Scan} = \frac{[a, i − 1, i]}{[A^{γ}, i − 1, i | −, − | false]} A^{γ} → a

D_{CYK}^{ε} = \overline{[A^{γ}, i, i | −, − | false]} A^{γ} → ε

D_{CYK}^{Foot} = \overline{[F^{γ}, i, j | i, j | false]}

D_{CYK}^{LeftDom} = \frac{\begin{matrix}[B^{γ}, i, k | p, q | adj], \\ [C^{γ}, k, j | −, − | adj′] \end{matrix}}{[A^{γ}, i, j | p, q | false]}

tal que A^{γ} → B^{γ}C^{γ} y B^{γ} domina F^{γ}.

D_{CYK}^{RightDom} = \frac{\begin{matrix}[B^{γ}, i, k | −, − | adj], \\ [C^{γ}, k, j | p, q | adj′] \end{matrix}}{[A^{γ}, i, j | p, q | false]}

tal que A^{γ} → B^{γ}C^{γ} y C^{γ} domina F^{γ}.

D_{CYK}^{NoDom} = \frac{\begin{matrix}[B^{γ}, i, k | −, − | adj], \\ [C^{γ}, k, j | −, − | adj′] \end{matrix}}{[A^{γ}, i, j | −, − | false]}

tal que A^{γ} → B^{γ}C^{γ} y ni B^{γ} ni C^{γ} domina al nodo pie de γ.

D_{CYK}^{Unary} = \frac{[B^{γ}, i, j | p, q | adj]}{[A^{γ}, i, j | p, q] | false} A^{γ} → B^{γ}

D_{CYK}^{Adj} = \frac{\begin{matrix}[R^{β}, i′, j′ | i, j | adj], \\ [A^{γ}, i, j | p, q | false] \end{matrix}}{[A^{γ}, i′, j′ | p, q | true]}

tal que β ∈ A y β ∈ adj(A^{γ}).

D_{CYK} = D_{CYK}^{Scan} ∪ D_{CYK}^{ε} ∪ D_{CYK}^{Foot}∪

D_{CYK}^{LeftDom} ∪ D_{CYK}^{RightDom} ∪ D_{CYK}^{NoDom}∪

D_{CYK}^{Unary} ∪ D_{CYK}^{Adj}

F_{CYK} = { [R^{α}, 0, n | −, − | adj] | α ∈ I }

La definición de las hipótesis realizada en este sistema de análisis sintáctico se corresponde con la estándar y es la misma que se utilizará en los restantes. Por consiguiente, no nos volveremos a referir explícitamente a ellas.

Los pasos clave en el sistema de análisis IP_{CYK} son D_{CYK}^{Foot} y D_{CYK}^{Adj}, puesto que son los que definen el mecanismo de adjunción. Los demás pasos se encargan de recorrer de forma ascendente los árboles elementales, propagando la información relativa a la porción de la cadena de entrada cubierta por el pie en el caso de los árboles auxiliares.

El paso deductivo D_{CYK}^{Foot} hace posible el análisis ascendente de los árboles auxiliares, puesto que predice todas las posibles porciones de la cadena de entrada que puede cubrir el pie. Como consecuencia, pueden existir múltiples análisis diferentes para cada árbol auxiliar, diferentes únicamente en las posición de la cadena de entrada que se supone en cada caso que cubre el pie. Sólo algunos de esos árboles podrán formar parte del árbol de derivación, aquellos que hayan predicho correctamente el pie. La realización de esta comprobación le corresponde al paso D_{CYK}^{Adj}. Efectivamente, cuando se ha alcanzado la raíz de un árbol auxiliar, se comprueba si existe un subárbol de un árbol inicial cuya raíz pueda ser un nodo de adjunción para dicho árbol auxiliar y que además cubra la porción de la cadena de entrada que espera ser cubierta por el pie. En caso de que así sea, se eliminará la posibilidad de realizar otras adjunciones en ese nodo y el análisis continuará ascendiendo por el nuevo árbol elemental.

3. Algoritmo de tipo Earley ascendente

Para superar la limitación de las gramáticas binarias definiremos un algoritmo de tipo Earley ascendente. Como primer paso precisamos introducir puntos en las producciones que representan los árboles elementales, por lo que los ítems serán de la forma

[A^{γ} → δ • ν, i, j | p, q]

tal que δ ⇒^{∗} a_{i+1} … a_{p} F^{γ} a_{q+1} … a_{j} ⇒^{∗}

a_{i+1} … a_{j} si y sólo si (p, q) ≠ (−, −) mientras

que δ ⇒^{∗} a_{i+1} … a_{j} si y sólo si (p, q) = (−, −).

Los ítems del nuevo esquema de análisis sintáctico, que denominaremos P_{buE_{1}}, son por tanto un refinamiento de los ítems de P_{CYK}. Al incluirse reglas con punto en la forma de los nuevos ítems ya no es necesario el elemento que indicaba si se había realizado una adjunción en el nodo situado en el lado izquierdo de la producción contenida en dicho ítem.

Esquema 2 El sistema de análisis IP_{buE} que se corresponde con el algoritmo de tipo Earley ascendente, dada una gramática de adjunción de árboles G y una cadena de entrada a_{1} … a_{n} se define como sigue:

I_{buE} = \{ \begin{matrix}[A^{γ} → δ • ν, i, j | p, q] | \\ A^{γ} → δ • ν ∈ P(γ), γ ∈ I ∪ A, \\ 0 ≤ i ≤ j, (p, q) ≤ (i, j) \end{matrix} \}

D_{buE}^{Init} = \overline{[A^{γ} → •δ, i, i | −, −]} D_{buE}^{Foot} = \overline{[F^{β} → ⊥•, i, j | i, j]}

D_{buE}^{Scan} = \frac{\begin{matrix}[A^{γ} → δ • aν, i, j − 1 | p, q], \\ [a, j − 1, j] \end{matrix}}{[A^{γ} → δa • ν, i, j | p, q]}

D_{buE}^{Comp} = \frac{\begin{matrix}[A^{γ} → δ • B^{γ}ν, i, k | p, q], \\ [B^{γ} → υ•, k, j | p′, q′] \end{matrix}}{[A^{γ} → δB^{γ} • ν, i, j | p ∪ p′, q ∪ q′]}

D_{buE}^{AdjComp} = \frac{\begin{matrix}[⊤ → R^{β}•, k, j | l, m], \\ [B^{γ} → υ•, l, m | p′, q′], \\ [A^{γ} → δ • B^{γ}ν, i, k | p, q], \end{matrix}}{[A^{γ} → δB^{γ} • ν, i, j | p ∪ p′, q ∪ q′]}

tal que β ∈ A y β ∈ adj(γ).

D_{buE} = D_{buE}^{Init} ∪ D_{buE}^{Foot} ∪ D_{buE}^{Scan} ∪ D_{buE}^{Comp}∪
D_{buE}^{AdjComp}

F_{buE} = { [⊤ → R^{α}•, 0, n | −, −] | α ∈ I }

donde p ∪ q se refiere a la operación de unión de índices:

p ∪ q = \{ \begin{matrix}p & si q = − \\ q & si p = − \\ − & si p = q = − \end{matrix}

Se ha aplicado un refinamiento a los pasos deductivos puesto que los pasos de tipo LeftDom, RightDom y NoDom han sido separados en diferentes pasos de tipo Init y Comp, mientras que los pasos de tipo Unary y ε ya no son necesarios puesto que todas las producciones son tratadas uniformemente con independencia de su longitud. También se ha realizado una extensión del dominio de las producciones permitiendo árboles con un grado arbitrario de ramificación.

El algoritmo reconoce ascendentemente los árboles auxiliares mediante la aplicación de pasos D_{buE_{1}}^{Comp}, propagando también la información correspondiente a la porción de la cadena de entrada cubierta por el pie en el caso de los árboles auxiliares. Un conjunto de pasos deductivos D_{buE}^{Init} que expresan la expectativa de que una determinada regla pueda ser aplicada para reconocer una porción de la cadena de entrada son los encargados de lanzar el análisis ascendente.

Se ha aplicado un filtro al esquema de análisis sintáctico P_{CYK}, consistente en la contracción de pasos deductivos puesto que un ítem generado por un paso deductivo de tipo Adj sólo podría ser utilizado en un paso de tipo Comp para avanzar el punto en la regla que había predicho el no terminal del lado izquierdo de su producción. Por ello, hemos creado un nuevo paso deductivo AdjComp y eliminado los pasos Adj.

4. Algoritmo de tipo Earley

Incorporando predicción descendente podemos obtener un algoritmo de tipo Earley. Para ello debemos aplicar dos filtros dinámicos: el paso deductivo D_{buE}^{Init} sólo contendrá producciones cuyo lado izquierdo corresponda con la raíz de un árbol inicial mientras que un nuevo conjunto de pasos predictivos controlará la generación de nuevos ítems tratando de limitarla únicamente a aquellos que puedan resultar útiles en el proceso de análisis.

Esquema 3 El sistema de análisis IP_{E} que se corresponde con el algoritmo de tipo Earley sin la propiedad del prefijo válido, dada una gramática de adjunción de árboles G y una cadena de entrada a_{1} … a_{n} se define como sigue:

I_{E} = I_{buE}

D_{E}^{Init} = \overline{[⊤ → •R^{α}, 0, 0 | −, −]} α ∈ I

D_{E}^{Pred} = \frac{[A^{γ} → δ • B^{γ}ν, i, j | p, q]}{[B^{γ} → •υ, j, j | −, −]}

D_{E}^{AdjPred} = \frac{[A^{γ} → δ • B^{γ}ν, i, j | p, q]}{[⊤ → •R^{β}, j, j | −, −]}

tal que β ∈ adj(B^{γ}).

D_{E}^{FootPred} = \frac{\begin{matrix}[F^{β} → •⊥, k, k | −, −], \\ [A^{γ} → δ • B^{γ}ν, i, j | p, q] \end{matrix}}{[B^{γ} → •δ, k, k | −, −]}

tal que β ∈ adj(B^{γ}).

D_{E}^{FootComp} = \frac{\begin{matrix}[B^{γ} → δ•, k, l | p, q], \\ [F^{β} → •⊥, k, k | −, −], \\ [A^{γ} → δ • B^{γ}ν, i, j | p′, q′] \end{matrix}}{[F^{β} → ⊥•, k, l | k, l]}

tal que β ∈ adj(B^{γ}) y p ∪ p′ así como q ∪ q′ están definidos.

D_{E}^{AdjComp^{1}} = \frac{\begin{matrix}[⊤ → R^{β}•, j, m | k, l], \\ [B^{γ} → δ•, k, l | p, q], \\ [F^{γ} → ⊥•, p, q | p, q], \\ [A^{γ} → δ • B^{γ}ν, i, j | −, −] \end{matrix}}{[A^{γ} → δB^{γ} • ν, i, m | p, q]}

tal que β ∈ adj(B^{γ}).

D_{E}^{AdjComp^{2}} = \frac{\begin{matrix}[⊤ → R^{β}•, j, m | k, l], \\ [B^{γ} → δ•, k, l | −, −], \\ [A^{γ} → δ • B^{γ}ν, i, j | p, q] \end{matrix}}{[A^{γ} → δB^{γ} • ν, i, m | p, q]}

tal que β ∈ adj(B^{γ}).

D_{E} = D_{E}^{Init} ∪ D_{buE}^{Scan} ∪ D_{E}^{Pred} ∪ D_{buE}^{Comp}∪

D_{E}^{AdjPred} ∪ D_{E}^{FootPred} ∪ D_{E}^{FootComp}∪

D_{E}^{AdjComp^{1}} ∪ D_{E}^{AdjComp^{2}}

F_{E} = F_{buE}

El análisis comienza creando un ítem correspondiente a una producción del nodo raíz de un árbol inicial con el punto situado en el extremo izquierdo. Posteriormente, los pasos D_{E}^{Pred} y D_{E}^{AdjComp} se encargan de ir recorriendo cada árbol elemental. Los pasos D_{E}^{AdjPred} predicen la adjunción de un árbol β en un nodo de un árbol elemental γ, comenzando el análisis del árbol β. Una vez alcanzado el pie de dicho árbol auxiliar, deberemos retomar el análisis del subárbol de γ que pende del nodo de adjunción. Al no conocer en qué nodo de qué árbol elemental se ha producido la adjunción, los pasos D_{E}^{FootPred} predecirán todos los posibles nodos donde esté permitida la adjunción de β. Una vez terminado de analizar todo el subárbol predicho por D_{E}^{FootPred}, los pasos D_{E}^{FootComp} retoman el análisis del árbol auxiliar β a partir del pie. Una vez terminado de analizar completamente β, la operación de adjunción concluye con la aplicación de uno de los pasos D_{E}^{AdjComp^{1}} o D_{E}^{AdjComp^{2}}, que verifican que el subárbol escindido del nodo de adjunción y el árbol auxiliar han sido correctamente reconstruidos. D_{E}^{AdjComp^{1}} se aplica en el caso de que el nodo de adjunción forme parte de la espina de un árbol auxiliar, en caso contrario se aplica D_{E}^{AdjComp^{2}}.

5. La propiedad del prefijo válido

Los analizadores sintácticos que satisfacen la propiedad del prefijo válido garantizan que, en tanto que leen la cadena de entrada de izquierda a derecha, las subcadenas leídas son prefijos válidos del lenguaje definido por la gramática. Más formalmente, un analizador sintáctico satisface la propiedad del prefijo válido si al leer la subcadena a_{1} … a_{k} de la cadena de entrada a_{1} … a_{k}a_{k+1} … a_{n} garantiza que hay una cadena b_{1} … b_{m}, donde b_{i} no tiene porque formar parte de la cadena de entrada, tal que a_{1} … a_{k}b_{1} … b_{m} es una cadena válida del lenguaje.

El mantenimiento de la propiedad del prefijo válido exige ir reconociendo los posibles árboles derivados de forma prefija. Este recorrido consta de dos fases que deben actuar coordinadamente, una descendente que dado un nodo expande sus nodos hijos y una ascendente que agrupa los nodos hijos para indicar el reconocimiento del nodo padre. La fase descendente debe estar restringida para evitar expansiones que lleven al reconocimiento de prefijos no válidos [6].

Durante el reconocimiento de un árbol derivado en forma prefija, la expansión de un nodo puede depender de operaciones de adjunción previamente realizadas en la parte recorrida del árbol. Esta dependencia del contexto conlleva que el conjunto de caminos sea un lenguaje independiente del contexto [11]. Un algoritmo básicamente ascendente (p.ej.: de tipo CYK o de tipo Earley ascendente) puede ir apilando las dependencias indicadas por el lenguaje que define el conjunto de caminos. Con ello se conseguiría un algoritmo de análisis correcto pero sin la propiedad del prefijo válido. Para preservar esta propiedad es necesario disponer de una fase descendente, que también tendría que realizar apilamientos para satisfacer las restricciones impuestas por el lenguaje que define el conjunto de caminos.

Al tener que coordinar los apilamientos de la fase ascendente y descendente, la transformación directa de un algoritmo sin la propiedad del prefijo válido en otro que sí la posea puede aumentar la complejidad del algoritmo resultante. Para evitarlo, será preciso refinar cuidadosamente dicho algoritmo [5].

Los algoritmos descritos hasta este punto no preservan la propiedad del prefijo válido puesto que al no ser la fase de predicción del pie lo suficientemente restrictiva no se puede verificar que el subárbol pegado al nodo pie se corresponda con la instancia del árbol que ha sido utilizada en la operación de adjunción. Para obtener un esquema de análisis que se corresponda con un algoritmo del tipo Earley que posea la propiedad del prefijo válido es necesario refinar los ítems incluyendo un nuevo elemento que indique la posición del extremo izquierdo de la frontera del árbol al que se refieren los nodos de cada ítem:

[h, A^{γ} → δ • ν, i, j | p, q]

tal que R^{γ} ⇒^{∗} a_{h+1} … a_{i}δνυ y además δ ⇒^{∗}

a_{i} … a_{p} F^{γ} a_{q+1} … a_{j} ⇒^{∗} a_{i} … a_{j} si y sólo si

(p, q) ≠ (−, −) mientras que δ ⇒^{∗} a_{i} … a_{j} si y sólo si (p, q) = (−, −).

En consecuencia, un ítem [A^{γ} → δ • ν, i, j | p, q] de P_{E_{3}} se corresponde ahora con el conjunto de ítems [h, A^{γ} → δ • ν, i, j | p, q] ∀h ∈ [0, n].

Esquema 4 El sistema de análisis IP_{Earley} del algoritmo de tipo Earley con la propiedad del prefijo válido, dada una TAG y una cadena de entrada se define:

I_{Earley} = \{ \begin{matrix}[h, A^{γ} → δ • ν, i, j | p, q] | \\ A^{γ} → δ • ν ∈ P(γ), γ ∈ I ∪ A, \\ 0 ≤ h ≤ i ≤ j, (p, q) ≤ (i, j) \end{matrix} \}

D_{Earley}^{Init} = \overline{⊢ [0, ⊤ → •R^{α}, 0, 0 | −, −]} α ∈ I

D_{Earley}^{Scan} = \frac{\begin{matrix}[h, A^{γ} → δ • aν, i, j − 1 | p, q], \\ [a, j − 1, j] \end{matrix}}{[h, A^{γ} → δa • ν, i, j | p, q]}

D_{Earley}^{Pred} = \frac{[h, A^{γ} → δ • B^{γ}ν, i, j | p, q]}{[h, B^{γ} → •υ, j, j | −, −]}

D_{Earley}^{Comp} = \frac{\begin{matrix}[h, A^{γ} → δ • B^{γ}ν, i, k | p, q], \\ [h, B^{γ} → υ•, k, j | p′, q′] \end{matrix}}{[h, A^{γ} → δB^{γ} • ν, i, j | p ∪ p′, q ∪ q′]}

D_{Earley}^{AdjPred} = \frac{[h, A^{γ} → δ • B^{γ}ν, i, j | p, q]}{[j, ⊤ → •R^{β}, j, j | −, −]}

tal que β ∈ adj(B^{γ}).

D_{Earley}^{FootPred} = \frac{\begin{matrix}[j, F^{β} → •⊥, k, k | −, −], \\ [h, A^{γ} → δ • B^{γ}ν, i, j | p, q] \end{matrix}}{[h, B^{γ} → •δ, k, k | −, −]}

tal que β ∈ adj(B^{γ}).

D_{Earley}^{FootComp} = \frac{\begin{matrix}[h, B^{γ} → δ•, k, l | p, q], \\ [j, F^{β} → •⊥, k, k | −, −], \\ [h, A^{γ} → δ • B^{γ}ν, i, j | p′, q′] \end{matrix}}{[j, F^{β} → ⊥•, k, l | k, l]}

tal que β ∈ adj(B^{γ}) y tanto p ∪ p′ como q ∪ q′ están definidos.

D_{Earley}^{AdjComp^{1}} = \frac{\begin{matrix}[j, ⊤ → R^{β}•, j, m | k, l], \\ [h, B^{γ} → δ•, k, l | p, q], \\ [h, F^{γ} → ⊥•, p, q | p, q], \\ [h, A^{γ} → δ • B^{γ}ν, i, j | −, −] \end{matrix}}{[h, A^{γ} → δB^{γ} • ν, i, m | p, q]}

tal que β ∈ adj(B^{γ}).

D_{Earley}^{AdjComp^{2}} = \frac{\begin{matrix}[j, ⊤ → R^{β}•, j, m | k, l], \\ [h, B^{γ} → δ•, k, l | −, −], \\ [h, A^{γ} → δ • B^{γ}ν, i, j | p, q] \end{matrix}}{[h, A^{γ} → δB^{γ} • ν, i, m | p, q]}

tal que β ∈ adj(B^{γ}).

D_{Earley} = D_{Earley}^{Init} ∪ D_{Earley}^{Scan} ∪ D_{Earley}^{Pred}∪

D_{Earley}^{Comp} ∪ D_{Earley}^{AdjPred} ∪ D_{Earley}^{FootPred}∪

D_{Earley}^{FootComp} ∪ D_{Earley}^{AdjComp^{1}}∪

D_{Earley}^{AdjComp^{2}}

F_{Earley} = { [0, ⊤ → R^{α}•, 0, n | −, −] | α ∈ I }

La complejidad del paso D_{Earley}^{AdjComp^{1}} haciendo uso de aplicación parcial es O(n^{7}) y coincide con la complejidad del algoritmo descrito por el esquema P_{Earley}. Los algoritmos descritos anteriormente presentaban una complejidad O(n^{6}). El aumento de complejidad es debido al índice adicional incorporado a los ítems. Este índice es necesario para controlar que se están utilizando los árboles correctos al tratar el pie de un árbol auxiliar. En consecuencia, dicho índice sólo es útil en los pasos D_{Earley}^{FootPred} y D_{Earley}^{FootComp}

y por tanto los pasos D_{Earley}^{AdjComp^{1}} y D_{Earley}^{AdjComp^{2}} pueden ser refinados, dividiéndolos en varios pasos con el fin de generar ítems intermedios carentes de dicho índice. La corrección de la transformación está garantizada por la propiedad de independencia del contexto de TAG [10] que establece la independencia de cada operación de adjunción con respecto a cualquier otra operación de adjunción.

Obtenemos de este modo el algoritmo de tipo Earley descrito por Nederhof en [5], que preserva la propiedad del prefijo válido con una complejidad O(n^{6}). Debemos definir un tipo adicional de ítem

[A^{γ} → δ • ν, i, j | p, q]

tal que δ ⇒^{∗} a_{i} … a_{p} F^{γ} a_{q+1} … a_{j} ⇒^{∗} a_{i} … a_{j}

si y sólo si (p, q) ≠ (−, −) mientras que

δ ⇒^{∗} a_{i} … a_{j} si y sólo si (p, q) = (−, −).

También debemos refinar los pasos que completan la adjunción, de modo que los pasos AdjComp^{1} y AdjComp^{2} serán equivalentes a la aplicación de un paso AdjComp^{0} más un paso AdjComp^{1′} o AdjComp^{2′}:

D_{Earley}^{AdjComp^{0}} = \frac{\begin{matrix}[j, ⊤ → R^{β}•, j, m | k, l], \\ [h, B^{γ} → δ•, k, l | p, q], \end{matrix}}{[B^{γ} → δ•, j, m | p, q]}

tal que β ∈ adj(B^{γ}).

D_{Earley}^{AdjComp^{1′}} = \frac{\begin{matrix}[B^{γ} → δ•, j, m | p, q], \\ [h, F^{γ} → ⊥•, p, q | p, q], \\ [h, A^{γ} → δ • B^{γ}ν, i, j | −, −] \end{matrix}}{[h, A^{γ} → δB^{γ} • ν, i, m | p, q]}

tal que β ∈ adj(B^{γ}).

D_{Earley}^{AdjComp^{2′}} = \frac{\begin{matrix}[B^{γ} → δ•, j, m | −, −], \\ [h, A^{γ} → δ • B^{γ}ν, i, j | p, q] \end{matrix}}{[h, A^{γ} → δB^{γ} • ν, i, m | p, q]}

tal que β ∈ adj(B^{γ}).

6. Conclusiones

Se ha descrito un conjunto de algoritmos de análisis sintáctico de TAG que constituyen una línea evolutiva continua que tiene como punto de partida el algoritmo de tipo CYK de Vijay-Shanker y Joshi [9] y como punto de llegada el algoritmo de tipo Earley de Nederhof [5] que preserva la propiedad del prefijo válido con complejidad O(n^{6}). Como algoritmos intermedios, se ha descubierto un algoritmo de tipo Earley ascendente y una nueva versión de un algoritmo de tipo Earley sin la propiedad del prefijo válido. Se ha mostrado cómo se pueden transformar unos algoritmos en otros mediante transformaciones simples. En esta línea evolutiva se podrían haber considerado más algoritmos intermedios, pero las restricciones en el espacio disponible han aconsejado considerar solamente los hitos más importantes en dicha evolución.

Actualmente estamos trabajando en la conversión de los algoritmos descritos a los modelos de interpretación tabular presentados en [2] y [3] para autómatas que manejan dos pilas [1].

Referencias

[1] Tilman Becker. A New Automaton Model for TAGs: 2-SA. Computational Intelligence, 10(4):422–430, 1994.

[2] Eric de la Clergerie, y Miguel A. Alonso Pardo. A Tabular Interpretation of a Class of 2-Stack Automata. In Proc. of COLING/ACL’98, Montreal, Canadá, agosto de 1998. ACL.

[3] Eric de la Clergerie, Miguel A. Alonso Pardo, y David Cabrero Souto. A tabular interpretation of bottom-up automata for TAG. In Proc. of TAG+, Fourth Workshop on Tree-Adjoining Grammars and Related Frameworks, Filadelfia, PA, Estados Unidos, agosto de 1998.

[4] Aravind K. Joshi, Leon S. Levy, y M. Takahashi. Tree adjunt grammars. Journal of Computer and System Sciences, 10(1):136–162, febrero de 1975.

[5] Mark-Jan Nederhof. Solving the correctprefix property for TAGs. In T. Becker y H.-V. Krieger, editores, Proc. of the Fifth Meeting on Mathematics of Language, páginas 124–130, Schloss Dagstuhl, Saarbruecken, Alemania, agosto de 1997.

[6] Yves Schabes. The valid prefix property and left to right parsing of treeadjoining grammar. In Proc. of II International Workshop on Parsing Technologies, IWPT’91, páginas 21–30, Cancún, Méjico, 1991.

[7] Yves Schabes y Stuart M. Shieber. An alternative conception of tree-adjoining derivation. Computational Linguistics, 20(1):91–124, 1994.

[8] Klaas Sikkel. Parsing Schemata — A Framework for Specification and Analysis of Parsing Algorithms. Texts in Theoretical Computer Science — An EATCS Series. Springer-Verlag, Berlín/Heidelberg/Nueva York, 1997.

[9] Krishnamurti  Vijay-Shanker  y

Aravind K. Joshi. Some computational properties of tree adjoining grammars. In 23rd Annual Meeting of the Association for Computational Linguistics, páginas 82–93, Chicago, IL, Estados Unidos, julio de 1985. ACL.

[10] Krishnamurti Vijay-Shanker y David J. Weir. Parsing some constrained grammar formalisms. Computational Linguistics, 19(4):591–636, 1994.

[11] Krishnamurti Vijay-Shanker, David J. Weir, y Aravind K. Joshi. Characterizing structural descriptions produced by various grammatical formalisms. In Proc. of the 25th Annual Meeting of the Association for Computational Linguistics, páginas 104–111, Buffalo, NY, Estados Unidos, junio de 1988. ACL.