Nuevos algoritmos tabulares para el análisis de LIG^{∗}

Miguel A. Alonso, Jorge Graña y Manuel Vilares Departamento de Computación, Universidad de La Coruña Campus de Elviña s/n, 15071 La Coruña, España

                    {alonso,grana,vilares}@dc.fi.udc.es
                       http://coleweb.dc.fi.udc.es/

Resumen

A partir de un algoritmo de tipo CYK se desarrolla una serie de nuevos algoritmos tabulares para el análisis de Gramáticas Lineales de Índices que incluye algoritmos ascendentes y algoritmos de tipo Earley con y sin la propiedad del prefijo válido, creando un camino evolutivo continuo en el que cada algoritmo puede ser obtenido mediante transformaciones simples del algoritmo precedente. Los nuevos algoritmos creados permiten establecer un paralelismo con los algoritmos disponibles para Gramáticas de Adjunción de Árboles.

1 Introducción

Las Gramáticas de Índices [1] son una extensión de las gramáticas independientes del contexto en las cuales cada símbolo no-terminal tiene asociado una pila de índices. Si restringimos la forma de las producciones de tal modo que la pila asociada al no-terminal del lado izquierdo de una producción (denominado padre) sólo pueda transmitirse a un no-terminal del lado derecho (denominado hijo dependiente) y los demás no-terminales estén asociados con pilas de tamaño acotado, obtenemos las Gramáticas Lineales de Índices (LIG) [6]. Además del interés que este tipo de gramáticas presentan por sí mismos como formalismo descriptivo, en lingüística computacional presentan una relevancia especial puesto que son habitualmente utilizadas como formalismo intermedio a través del cual se realiza el análisis sintáctico de las Gramáticas de Adjunción de Árboles (TAG) [12, 9, 10, 13].

Formalmente, una LIG es un quíntupla (V_{T} , V_{N}, V_{I}, S, P), donde V_{T} es un conjunto finito de terminales, V_{N} es un conjunto finito de no-terminales, V_{I} es un conjunto finito de índices (elementos que se almacenan en las pilas asociadas a los no-terminales), S ∈ V_{N} es el axioma de la gramática y P es un conjunto finito de producciones que tienen alguna de las formas siguientes:

A_{0}[∘∘γ] → A_{1}[ ] … A_{i−1}[ ] A_{i}[∘∘] A_{i−1}[ ] … A_{m}[ ] A_{0}[∘∘] → A_{1}[ ] … A_{i−1}[ ] A_{i}[∘∘] A_{i−1}[ ] … A_{m}[ ] A_{0}[∘∘] → A_{1}[ ] … A_{i−1}[ ] A_{i}[∘∘γ] A_{i−1}[ ] … A_{m}[ ] A_{0}[ ] → a

donde A_{j} ∈ V_{N} para todo 0 ≤ j ≤ m, A_{i} es el hijo dependiente, γ ∈ V_{I}, ∘∘ representa la parte de la pila transmitida del padre al hijo dependiente, m es la longitud de la producción y a ∈ V_{T} ∪ {ϵ}.

La relación de derivación ⇒ se define en LIG como Υ ⇒ Υ′

• si Υ = Υ_{1}A[αγ] Υ_{4} y existe una producción A[∘∘γ] → Υ_{2}A′[∘∘γ′] Υ_{3} de tal modo que Υ′ = Υ_{1}Υ_{2}A′[αγ′] Υ_{3}Υ_{4}

• o bien si Υ = Υ_{1}A[ ] Υ_{4} y existe una producción A[ ] → a de modo que Υ′ = Υ_{1} a Υ_{4}

donde A ∈ V_{N}, α ∈ V_{I}^{∗} y γ, γ′ ∈ V_{I} ∪ {ϵ}. Denotamos por ⇒^{∗} el cierre reflexivo y transitivo de ⇒. El lenguaje generado por una LIG queda definido por todos los w ∈ V_{T}^{∗} tales que S[ ] ⇒^{∗} w.

∗Financiado en parte por FEDER (1FD97-0047-C04-02) y por la Xunta de Galicia (XUGA20402B97).

En cuanto al análisis sintáctico de este tipo de gramáticas, la propiedad de independencia del contexto de LIG desempeña un papel fundamental, como se verá en las siguientes secciones. Dicha propiedad establece que si A[γ] ⇒^{∗} uB[ ]w , donde u, v, w ∈ V_{T}^{∗}, A, B ∈ V_{N}, B[ ] es el descendiente dependiente de A[γ] y γ ∈ V_{I} ∪ {ϵ}, entonces para cualquier β ∈ V_{I}^{∗} se cumple que A[βγ] ⇒^{∗} uB[β]w y para cualquier Υ_{1}, Υ_{2} ∈ (V_{N}[V_{I}^{∗}] ∪ V_{T})^{∗} se cumple que Υ_{1}A[βγ]Υ_{2} ⇒^{∗} Υ_{1}uB[β]wΥ_{2} . Si además B[β] ⇒^{∗} v, donde v ∈ V_{T}^{∗}, entonces Υ_{1}A[βγ]Υ_{2} ⇒^{∗}

Υ_{1}uB[β]wΥ_{2} ⇒^{∗} Υ_{1}uvwΥ_{2} .

1.1 Esquemas de análisis sintáctico

Describiremos los algoritmos de análisis mediante esquemas de análisis sintáctico [11], 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 ℙ = ⟨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 de la forma \frac{η_{1},...,η_{k}}{ξ} cond, denominadas pasos deductivos, mediante las cuales se derivan nuevos ítems ξ a partir de los ítems η_{i} existentes si las condiciones cond son satisfechas. La presencia de un conjunto F ⊆ I de ítems finales indica el reconocimiento de la cadena de entrada.

Un esquema de análisis sintáctico es un sistema de análisis ℙ parametrizado para cualquier gramática y cadena de entrada. Un esquema de análisis puede ser generalizado a partir de otro mediante 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) y extensión (considerando una clase más amplia de gramáticas).

Las operaciones de filtrado permiten disminuir el número de ítems y pasos deductivos de un esquema de análisis mediante la eliminación de pasos redundantes (filtrado estático) y la utilización de información contextual para determinar la validez de los ítems (filtrado dinámico). La operación de contracción de pasos permite que una secuencia de pasos deductivos sea reemplazada por un solo paso.

2 Algoritmo de tipo CYK

Como punto de partida tomaremos una extensión para LIG del algoritmo CYK. Nos basaremos en una versión modificada del algoritmo descrito por Vijay-Shanker y Weir en [12]. Asumiremos que cada producción posee dos elementos en el lado derecho o bien un único elemento que debe ser un terminal. Este condicionante puede verse como una trasposición de la forma normal de Chomsky al caso de las gramáticas lineales de índices.

El algoritmo trabaja reconociendo de forma ascendente la parte de la cadena de entrada cubierta por cada posible elemento gramatical. Para ello utiliza un conjunto de ítems

[A, γ, i, j | B, p, q]

que representan uno de los siguientes tipos de derivaciones:

• A[γ] ⇒^{∗} a_{i+1} … a_{p} B[ ] a_{q+1} … a_{j} si y sólo si

(B, p, q) ≠ (−, −, −) y donde B[ ] es un descendiente dependiente de A[γ] .

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

(−, −, −).

donde − se utiliza para denotar que el valor de un componente está indefinido.

Estos ítems se corresponden con los propuestos para la tabulación de los autómatas lineales de índices [8] y los autómatas ascendentes con dos pilas [5] y son ligeramente diferentes de los propuestos por Vijay-Shanker y Weir en [12] para su algoritmo de tipo CYK, que presentaban la forma [A, γ, i, j | B, η, p, q], con η ∈ V_{I}. El elemento η es redundante puesto que por la propiedad de independencia del contexto de las gramáticas lineales de índices

tenemos que si A[γ] ⇒^{∗} a_{i+1} … a_{p} B[ ] a_{q+1} … a_{j}

entonces para cualquier β se cumple que A[βγ] ⇒^{∗} a_{i+1} … a_{p} B[β] a_{q+1} … a_{j}.

Esquema 1 El sistema de análisis ℙ_{CYK} que se corresponde con el algoritmo de análisis de tipo CYK para una gramática lineal de índices G y una cadena de entrada a_{1} … a_{n} se define como sigue:

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

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

D_{CYK}^{Scan} = \frac{[a, j, j + 1]}{[A, −, j, j + 1 | −, −, −]} A[ ] → a ∈ P

D_{CYK}^{[∘∘γ][ ][∘∘]} = \frac{\begin{matrix}[B, −, i, k | −, −, −], \\ [C, η, k, j | D, p, q] \end{matrix}}{[A, γ, i, j | C, k, j]}

tal que A[∘∘γ] → B[ ] C[∘∘] ∈ P.

D_{CYK}^{[∘∘γ][∘∘][ ]} = \frac{\begin{matrix}[B, η, i, k | D, p, q], \\ [C, −, k, j | −, −, −] \end{matrix}}{[A, γ, i, j | B, i, k]}

tal que A[∘∘γ] → B[∘∘] C[ ] ∈ P.

D_{CYK}^{[∘∘][ ][∘∘]} = \frac{\begin{matrix}[B, −, i, k | −, −, −], \\ [C, η, k, j | D, p, q] \end{matrix}}{[A, η, i, j | D, p, q]}

tal que A[∘∘] → B[ ] C[∘∘] ∈ P.

D_{CYK}^{[∘∘][∘∘][ ]} = \frac{\begin{matrix}[B, η, i, k | D, p, q], \\ [C, −, k, j | −, −, −] \end{matrix}}{[A, η, i, j | D, p, q]}

tal que A[∘∘] → B[∘∘] C[ ] ∈ P.

D_{CYK}^{[∘∘][ ][∘∘γ]} = \frac{\begin{matrix}[B, −, i, k | −, −, −], \\ [C, γ, k, j | D, p, q], \\ [D, η, p, q | E, r, s] \end{matrix}}{[A, η, i, j | E, r, s]}

tal que A[∘∘] → B[ ] C[∘∘γ] ∈ P.

D_{CYK}^{[∘∘][∘∘γ][ ]} = \frac{\begin{matrix}[B, γ, i, k | D, p, q], \\ [C, −, k, j | −, −, −], \\ [D, η, p, q | E, r, s] \end{matrix}}{[A, η, i, j | E, r, s]}

tal que A[∘∘] → B[∘∘γ] C[ ] ∈ P.

D_{CYK} = D_{CYK}^{Scan} ∪ D_{CYK}^{[∘∘γ][ ][∘∘]} ∪ D_{CYK}^{[∘∘γ][∘∘][ ]}∪
D_{CYK}^{[∘∘][ ][∘∘]} ∪ D_{CYK}^{[∘∘][∘∘][ ]} ∪ D_{CYK}^{[∘∘][ ][∘∘γ]}∪
D_{CYK}^{[∘∘][∘∘γ][ ]}

F_{CYK} = { [S, −, 0, n | −, −, −] }

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 sistemas de análisis del artículo. Por consiguiente, no nos volveremos a referir explícitamente a ellas.

Los pasos D_{CYK}^{Scan} son los encargados de iniciar el procesamiento ascendente de la cadena de entrada. Los demás pasos se encargan de combinar los ítems correspondientes a los elementos del lado derecho de las producciones involucradas para generar el ítem correspondiente al lado izquierdo de la producción, propagando la información necesaria acerca de la pila de índices.

La complejidad espacial del algoritmo con respecto a la cadena de entrada es O(n^{4}) puesto que cada ítem almacena cuatro posiciones de dicha cadena. La complejidad temporal con respecto a la cadena de entrada es O(n^{6}) y viene dada por los pasos deductivos D_{CYK}^{[∘∘][ ][∘∘γ]} y D_{CYK}^{[∘∘][∘∘γ][ ]}. Aunque dichos pasos manipulan en principio 7 posiciones de la cadena de entrada, mediante aplicación parcial cada uno de ellos se puede descomponer en una sucesión de pasos que manipulan a lo sumo 6 posiciones de la cadena de entrada.

Vijay-Shanker y Weir describen en [13] un algoritmo de tipo CYK generalizado para gramáticas lineales de índices que manipulan más de un índice de la pila de índices en cada producción. La misma generalización puede ser aplicada al esquema de análisis sintáctico propuesto.

3 Algoritmo de tipo Earley ascendente

El algoritmo de tipo CYK presenta una limitación muy importante: sólo es aplicable a gramáticas lineales de índices cuyas producciones tienen a lo sumo dos elementos en el lado derecho. Como primer paso para eliminar esta limitación procederemos a introducir un punto en las producciones, que nos permitirá distinguir la parte de la producción ya reconocida de aquella que resta por reconocer. Con respecto a la notación, utilizaremos A para referirnos al elemento LIG de una producción constituido por el no-terminal A y una pila de índices asociada, cuando la forma de dicha pila sea irrelevante en el contexto de utilización. Los ítems

[A → Υ_{1} • Υ_{2}, γ, i, j | B, p, q]

del nuevo esquema de análisis sintáctico, que denominaremos buE, son un refinamiento de los ítems de CYK y representan alguno de los siguientes tipos de derivaciones:

• A[γ] ⇒ Υ_{1}Υ_{2} ⇒^{∗} a_{i+1} … a_{p} B[ ] a_{q+1} … a_{j} Υ_{2} si

y sólo si (B, p, q) ≠ (−, −, −), donde B[ ] es un descendiente dependiente de A[γ] .

• Υ_{1} ⇒^{∗} a_{i+1} … a_{j} si y sólo si γ = − y (B, p, q) =

(−, −, −). Si Υ_{1} incluye al hijo dependiente entones su pila asociada está vacía.

Los pasos deductivos sufrirán también un refinamiento puesto que los pasos de tipo D_{CYK}^{[∘∘γ][ ][∘∘]}, D_{CYK}^{[∘∘γ][∘∘][ ]}, D_{CYK}^{[∘∘][ ][∘∘]}, D_{CYK}^{[∘∘][∘∘][ ]}, D_{CYK}^{[∘∘][ ][∘∘γ]} y D_{CYK}^{[∘∘][∘∘γ][ ]} serán separados en diferentes pasos de tipo Init y Comp. Finalmente, la extensión del dominio permitirá tratar gramáticas lineales de índices con producciones de longitud arbitraria.

Esquema 2 El sistema de análisis ℙ_{buE} que se corresponde con el algoritmo de análisis de tipo Earley ascendente para una gramática lineal de índices G y una cadena de entrada a_{1} … a_{n} se define como sigue:

I_{buE} = \{ \begin{matrix}[A → Υ_{1} • Υ_{2}, γ, i, j | B, p, q] | \\ A → Υ_{1}Υ_{2} ∈ P , B ∈ V_{N}, γ ∈ V_{I}, \\ 0 ≤ i ≤ j , (p, q) ≤ (i, j) \end{matrix} \}

D_{buE}^{Init} = \overline{[A → •Υ, −, i, i | −, −, −]}

D_{buE}^{Scan} = \frac{\begin{matrix}[A[ ] → •a, −, j, j | −, −, −], \\ [a, j, j + 1] \end{matrix}}{[A[ ] → a•, −, j, j + 1 | −, −, −]}

D_{buE}^{Comp^{1}} = \frac{\begin{matrix}[A → Υ_{1} • B[ ] Υ_{2}, γ, i, k | C, p, q], \\ [B → Υ_{3}•, −, k, j | −, −, −] \end{matrix}}{[A → Υ_{1} B[ ] • Υ_{2}, γ, i, j | C, p, q]}

D_{buE}^{Comp^{2}} = \frac{\begin{matrix}[A[∘∘γ] → Υ_{1} • B[∘∘] Υ_{2}, −, i, k | −, −, −], \\ [B → Υ_{3}•, η, k, j | C, p, q] \end{matrix}}{[A[∘∘γ] → Υ_{1} B[∘∘] • Υ_{2}, γ, i, j | B, k, j]}

D_{buE}^{Comp^{3}} = \frac{\begin{matrix}[A[∘∘] → Υ_{1} • B[∘∘] Υ_{2}, −, i, k | −, −, −], \\ [B → Υ_{3}•, η, k, j | C, p, q] \end{matrix}}{[A[∘∘] → Υ_{1} B[∘∘] • Υ_{2}, η, i, j | C, p, q]}

D_{buE}^{Comp^{4}} = \frac{\begin{matrix}[A[∘∘] → Υ_{1} • B[∘∘γ] Υ_{2} , −, i, k | −, −, −], \\ [B → Υ_{3}• , γ, k, j | C, p, q], \\ [C → Υ_{4}•, η, p, q | D, r, s] \end{matrix}}{[A[∘∘] → Υ_{1} B[∘∘γ] • Υ_{2}, η, i, j | D, r, s]}

D_{buE} = D_{buE}^{Init} ∪ D_{buE}^{Scan} ∪ D_{buE}^{Comp^{1}} ∪ D_{buE}^{Comp^{2}}∪
D_{buE}^{Comp^{3}} ∪ D_{buE}^{Comp^{4}}

F_{buE} = { [S → Υ• , −, 0, n | −, −, −] }

La complejidad espacial con respecto a la cadena de entrada es O(n^{4}) puesto que cada ítem almacena 4 posiciones de dicha cadena. La complejidad temporal con respecto a la cadena de entrada es O(n^{6}) y viene dada por el conjunto de pasos D_{buE}^{Comp^{4}}.

4 Algoritmo de tipo Earley

El algoritmo descrito por el esquema de análisis sintáctico buE no toma en consideración si la parte de la cadena de entrada que se reconoce en cada ítem es derivable del axioma de la gramática. Los algoritmos de tipo Earley limitan el número de pasos deductivos aplicables mediante la predicción de las producciones que son candidatas a formar parte de la derivación atendiendo a su derivabilidad a partir del axioma.

En primer lugar, consideraremos que la predicción se realiza únicamente atendiendo al esqueleto independiente del contexto de la gramática lineal de índices, obteniendo un esquema de análisis que denominaremos E y que se deriva del esquema buE mediante la aplicación de un filtrado dinámico:

• El paso deductivo Init sólo contendrá producciones cuyo lado izquierdo se refiera al axioma de la gramática.

• En lugar de generar ítems de la forma [A → •Υ, −, i, i | −, −, −] para todas las posibles A → Υ ∈ P y todas las posibles posiciones i y j de la cadena de entrada, un conjunto de pasos deductivos Pred se ocupará de generar únicamente aquellos ítems que involucren producciones cuyo esqueleto independiente del contexto sea relevante durante el proceso de análisis.

Esquema 3 El sistema de análisis ℙ_{E} que se corresponde con el algoritmo de análisis de tipo Earley para una gramática lineal de índices G y una cadena de entrada a_{1} … a_{n} se define como sigue:

I_{E} = I_{buE}

D_{E}^{Init} = \overline{[S → •Υ, −, 0, 0 | −, −, −]}

D_{E}^{Pred} = \frac{[A → Υ_{1} • B Υ_{2}, γ, i, j | C, p, q]}{[B → •Υ_{3}, −, j, j | −, −, −]}

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

D_{buE}^{Comp^{3}} ∪ D_{buE}^{Comp^{4}}

F_{E} = F_{buE}

Este esquema, cuya complejidad espacial es O(n^{4}) y la temporal O(n^{6}), está muy relacionado con el algoritmo de tipo Earley descrito por Schabes y Shieber en [10] aunque aquel sólo es aplicable a una clase específica de gramáticas lineales de índices obtenida a partir de una gramática de adjunción de árboles. Sin embargo, ambos comparten una característica muy importante, como es que el tipo de predicción realizado es muy poco potente puesto que no toma en consideración el contenido de la pila de índices. Aunque aparentemente el algoritmo propuesto por Schabes y Shieber en [10] utiliza información de la pila de índices para realizar la predicción, un análisis más profundo nos lleva a la conclusión de que esto no es realmente así, puesto que dichos autores optaron por almacenar el esqueleto independiente del contexto de los árboles elementales en las pilas de índices, reduciendo el conjunto de noterminales de la LIG resultante a {t, b}. En efecto, una producción b[∘∘η] → t[η_{1}] … t[∘∘η_{s}] … t[η_{n}] es equivalente a η^{b}[∘∘] → η_{1}^{t}[ ] … η_{s}^{t}[∘∘] … η_{n}^{t}[ ] y una producción b[∘∘η] → t[η_{1}] … t[η_{n}] es equivalente a η^{b}[ ] → η_{1}^{t}[ ] … η_{n}^{t}[ ].

5 Algoritmo de tipo Earley que preserva la VPP

Los analizadores sintácticos que satisfacen la propiedad del prefijo válido (VPP) 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 porqué formar parte de la cadena de entrada, tal que a_{1} … a_{k}b_{1} … b_{m} es una cadena válida del lenguaje.

En el caso de LIG, para mantener la propiedad del prefijo válido es necesario comprobar cada vez que se predice una regla si se cumple que S[ ] ⇒^{∗} w A[αγ] Υ, donde A[∘∘γ] es el lado izquierdo de dicha regla.

Para obtener un algoritmo de tipo Earley con la propiedad del prefijo válido es preciso modificar el esquema E de tal modo que los pasos Pred predigan información acerca de las pilas de índices. Para ello también será necesario modificar la forma de los ítems para permitir seguir el rastro de las pilas de índices que se van prediciendo. Definiremos por tanto un nuevo conjunto de ítems de la forma

[E, h | A → Υ_{1} • Υ_{2}, γ, i, j | B, p, q]

que representan alguno de los siguientes tipos de derivaciones:

• E[ ] ⇒^{∗} a_{h+1} … a_{i} A[γ] Υ_{3} ⇒^{∗}

a_{h+1} … a_{i} … a_{p} B[ ] a_{q+1} … a_{j} Υ_{2}Υ_{3} si y sólo si (B, p, q) ≠ (−, −, −), donde A[γ] es un descendiente dependiente de E[ ] y B[ ] es un descendiente dependiente de A[γ] . Este tipo de derivación se corresponde con la compleción del hijo dependiente de una regla que tiene el no-terminal A como lado izquierdo. Además, la pila asociada a dicho no-terminal no debe estar vacía.

• E[ ] ⇒^{∗} a_{h+1} … a_{i} A[γ] Υ_{3} ⇒^{∗}

a_{h+1} … a_{i} … a_{j} Υ_{2}Υ_{3} si y sólo si (E, h) ≠ (−, −) y (B, p, q) = (−, −, −), donde A[γ] es un descendiente dependiente de E[ ] y Υ_{1} no contiene el hijo dependiente de A[γ] . Este tipo de derivación se refiere a la predicción del no-terminal A con una pila de índices no vacía.

• Υ_{1} ⇒^{∗} a_{i+1} … a_{j} si y sólo si (E, h) = (−, −),

γ = − y (B, p, q) = (−, −, −). Si Υ_{1} incluye al hijo dependiente de A entones la pila asociada a dicho hijo dependiente está vacía. Este tipo de derivación se refiere a la predicción o compleción del no-terminal A con una pila de índices vacía.

El nuevo conjunto de ítems así definido es un refinamiento de los ítems del esquema E: el elemento γ se utiliza para almacenar la cima de la pila de índices predicha (en el esquema E los ítem resultado de una predicción tenían γ = −) y el par de elementos (E, h) permite seguir la traza del ítem involucrado en la predicción. En principio podríamos suponer que para guardar dicha traza es necesario almacenar (E, η, h, k). Sin embargo, por la propiedad de independencia del contexto de LIG dicho elemento no es necesario puesto que la derivación será válida independiente del resto de la pila de índices. El índice k no es necesario puesto que al ser todos los ítems predichos en el esquema E de la forma [A → •Υ, h, h | B, p, q] su presencia sería redundante. Con respecto a los pasos deductivos, será necesario adaptar los pasos de compleción para que manipulen adecuadamente los nuevos componentes E y h y refinar los pasos predictivos con el fin de diferenciar los diferentes casos que se pueden dar.

Esquema 4 El sistema de análisis ℙ_{Earley_{1}} que se corresponde con el algoritmo de análisis de tipo Earley que preserva la propiedad del prefijo válido para una gramática lineal de índices G y una cadena de entrada a_{1} … a_{n} se define como sigue:

I_{Earley_{1}} = \{ \begin{matrix}[E, h | A → Υ_{1} • Υ_{2}, γ, i, j | B, p, q] | \\ A → Υ_{1}Υ_{2} ∈ P , B, C ∈ V_{N}, γ ∈ V_{I}, \\ 0 ≤ h ≤ i ≤ j , (p, q) ≤ (i, j) \end{matrix} \}

D_{Earley_{1}}^{Init} = \overline{[−, − | S → •Υ, −, 0, 0 | −, −, −]}

D_{Earley_{1}}^{Scan} = \frac{\begin{matrix}[−, − | A[ ] → •a, −, j, j | −, −, −], \\ [a, j, j + 1] \end{matrix}}{[−, − | A[ ] → a•, −, j, j + 1 | −, −, −]}

D_{Earley_{1}}^{Pred^{1}} = \frac{[E, h | A → Υ_{1} • B[ ] Υ_{2}, γ, i, j | C, p, q]}{[−, − | B → •Υ_{3}, −, j, j | −, −, −]}

D_{Earley_{1}}^{Pred^{2}} = \frac{\begin{matrix}[E, h | A[∘∘γ] → Υ_{1} • B[∘∘] Υ_{2}, γ, i, j | −, −, −], \\ [M, m | E → •Υ_{3}, γ′, h, h | −, −, −] \end{matrix}}{[M, m | B → •Υ_{4}, γ′, j, j | −, −, −]}

D_{Earley_{1}}^{Pred^{3}} = \frac{[E, h | A[∘∘] → Υ_{1} • B[∘∘] Υ_{2}, γ, i, j | −, −, −]}{[E, h | B → •Υ_{3}, γ, j, j | −, −, −]}

D_{Earley_{1}}^{Pred^{4}} = \frac{[E, h | A[∘∘] → Υ_{1} • B[∘∘γ] Υ_{2}, γ′, i, j | −, −, −]}{[A, i | B → •Υ_{3}, γ, j, j | −, −, −]}

D_{Earley_{1}}^{Comp^{1}} = \frac{\begin{matrix}[E, h | A → Υ_{1} • B[ ] Υ_{2}, γ, i, j | C, p, q], \\ [−, − | B → Υ_{3}•, −, j, k | −, −, −] \end{matrix}}{[E, h | A → Υ_{1} B[ ] • Υ_{2}, γ, i, k | C, p, q]}

D_{Earley_{1}}^{Comp^{2}} = \frac{\begin{matrix}[E, h | A[∘∘γ] → Υ_{1} • B[∘∘] Υ_{2}, γ, i, j | −, −, −], \\ [M, m | E → •Υ_{3}, γ′, h, h | −, −, −], \\ [M, m | B → Υ_{4}•, γ′, j, k | C, p, q] \end{matrix}}{[E, h | A[∘∘γ] → Υ_{1} B[∘∘] • Υ_{2}, γ, i, k | B, j, k]}

D_{Earley_{1}}^{Comp^{3}} = \frac{\begin{matrix}[E, h | A[∘∘] → Υ_{1} • B[∘∘] Υ_{2}, γ, i, j | −, −, −], \\ [E, h | B → Υ_{3}•, γ, j, k | C, p, q] \end{matrix}}{[E, h | A[∘∘] → Υ_{1} B[∘∘] • Υ_{2}, γ, i, k | C, p, q]}

D_{Earley_{1}}^{Comp^{4}} = \frac{\begin{matrix}[E, h | A[∘∘] → Υ_{1} • B[∘∘γ] Υ_{2} , γ′, i, j | −, −, −], \\ [A, i | B → Υ_{3}• , γ, j, k | C, p, q], \\ [E, h | C → Υ_{4}•, γ′, p, q | D, r, s] \end{matrix}}{[E, h | A[∘∘] → Υ_{1} B[∘∘γ] • Υ_{2}, γ′, i, k | D, r, s]}

D_{Earley_{1}} = D_{Earley_{1}}^{Init} ∪ D_{Earley_{1}}^{Scan} ∪ D_{Earley_{1}}^{Pred^{1}}∪
D_{Earley_{1}}^{Pred^{2}} ∪ D_{Earley_{1}}^{Pred^{3}} ∪ D_{Earley_{1}}^{Pred^{4}}∪

D_{Earley_{1}}^{Comp^{1}} ∪ D_{Earley_{1}}^{Comp^{2}} ∪ D_{Earley_{1}}^{Comp^{3}} ∪ D_{Earley_{1}}^{Comp^{4}}

F_{Earley_{1}} = { [−, − | S → Υ• , −, 0, n | −, −, −] }

La complejidad espacial con respecto a la longitud n de la cadena de entrada del algoritmo descrito por el esquema de análisis Earley_{1} es O(n^{5}) puesto que cada ítem hace uso de 5 posiciones. La complejidad temporal con respecto a la cadena de entrada es O(n^{7}) y viene dada por el conjunto de pasos deductivos D_{Earley_{1}}^{Comp^{4}}. Para rebajar la complejidad temporal del algoritmo recurriremos a una técnica similar a la utilizada en [4, 3] para disminuir la complejidad de los modelos de autómata para el análisis de lenguajes de adjunción de árboles. En el caso que nos ocupa, dividiremos cada paso deductivo de D_{Earley_{1}}^{Comp^{4}} en dos pasos de tal forma que la complejidad de cada uno de ellos sea a lo sumo O(n^{6}), obteniendo el siguiente esquema de análisis.

Esquema 5 El sistema de análisis ℙ_{Earley} que se corresponde con el algoritmo de análisis de tipo Earley que preserva la propiedad del prefijo válido para una gramática lineal de índices G y una cadena de entrada a_{1} … a_{n} se define como sigue:

I_{Earley}^{1} = \{ \begin{matrix}[E, h | A → Υ_{1} • Υ_{2}, γ, i, j | B, p, q]| \\ A → Υ_{1}Υ_{2} ∈ P , B, C ∈ V_{N}, \\ γ ∈ V_{I}, 0 ≤ h ≤ i ≤ j, (p, q) ≤ (i, j) \end{matrix}\}

I_{Earley}^{2} = \{ \begin{matrix}[[A → Υ•, γ, i, j | B, p, q]] | \\ A → Υ ∈ P , B ∈ V_{N}, \\ γ ∈ V_{I}, i ≤ j , (p, q) ≤ (i, j) \end{matrix} \}

I_{Earley} = I_{Earley}^{1} ∪ I_{Earley}^{2}

D_{Earley}^{Comp^{4.0}} = \frac{\begin{matrix}[A, i | B → Υ_{3}• , γ, j, k | C, p, q], \\ [E, h | C → Υ_{4}•, γ′, p, q | D, r, s] \end{matrix}}{[[B → Υ_{3}• , γ, j, k | D, r, s]]}

D_{Earley}^{Comp^{4.1}} = \frac{\begin{matrix}[[B → Υ_{3}• , γ, j, k | D, r, s]], \\ [E, h | A[∘∘] → Υ_{1} • B[∘∘γ] Υ_{2} , γ′, i, j | −, −, −], \\ [E, h | C → Υ_{4}•, γ′, p, q | D, r, s] \end{matrix}}{[E, h | A[∘∘] → Υ_{1} B[∘∘γ] • Υ_{2}, γ′, i, k | D, r, s]}

D_{Earley} = D_{Earley_{1}}^{Init} ∪ D_{Earley_{1}}^{Scan} ∪ D_{Earley_{1}}^{Pred^{1}}∪
D_{Earley_{1}}^{Pred^{2}} ∪ D_{Earley_{1}}^{Pred^{3}} ∪ D_{Earley_{1}}^{Pred^{4}}∪
D_{Earley_{1}}^{Comp^{1}} ∪ D_{Earley_{1}}^{Comp^{2}} ∪ D_{Earley_{1}}^{Comp^{3}}∪
D_{Earley}^{Comp^{4.0}} ∪ D_{Earley}^{Comp^{4.1}}

F_{Earley} = F_{Earley_{1}}

El primer paso genera un pseudo-ítem intermedio de la forma [[B → Υ_{3}• , γ, j, k | D, r, s]] que a su vez es un antecedente del segundo paso y que representa una derivación

B[γ′γ] ⇒^{∗} a_{j+1} … a_{r} D[ ] a_{s+1} … a_{k}

para algún γ′. Los pasos de D_{Earley}^{Comp^{4.1}} combinan dicho pseudo-ítem con el ítem [E, h | A[∘∘] → Υ_{1} • B[∘∘γ] Υ_{2} , γ′, i, j | −, −, −] que representa una derivación

\begin{aligned}E[ ] & ⇒^{∗} a_{h+1} … a_{i} A[γ′] Υ_{3} \\ & ⇒^{∗} a_{h+1} … a_{i} … a_{j} B[γ′γ] Υ_{2}Υ_{3} \end{aligned}

y con el ítem [E, h | C → Υ_{4}•, γ′, p, q | D, r, s] que representa una derivación

\begin{aligned}E[ ] & ⇒^{∗} a_{h+1} … a_{p} C[γ′] Υ_{5} \\ & ⇒^{∗} a_{h+1} … a_{p} … a_{r} D[ ] a_{s+1} … a_{q} Υ_{5} \end{aligned}

con lo cual podemos generar un ítem de la forma [E, h | A[∘∘] → Υ_{1} B[∘∘γ] • Υ_{2}, γ′, i, k | D, r, s] que representa la existencia de una derivación

E[ ] ⇒^{∗} a_{h+1} … a_{i} A[γ′] Υ_{3}

⇒^{∗} a_{h+1} … a_{i} … a_{j} B[γ′γ] Υ_{2}Υ_{3}

⇒^{∗} a_{h+1} … a_{i} … a_{j} … a_{r} D[ ] a_{s+1} … a_{k} Υ_{2}Υ_{3}

6 Conclusión

Se ha descrito un conjunto de algoritmos de análisis sintáctico de LIG que constituyen una línea evolutiva continua que tiene como punto de partida el algoritmo de tipo CYK de Vijay-Shanker y Weir [12] y que a través de nuevos algoritmos de tipo Earley ascendente y de tipo Earley sin la propiedad del prefijo válido permite llegar a un nuevo algoritmo de tipo Earley que preserva dicha propiedad manteniendo la complejidad temporal O(n^{6}) con respecto a la cadena de entrada. En esta línea evolutiva podrían haberse 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.

Es interesante destacar la relación existente entre los algoritmos de análisis de LIG y aquellos destinados al análisis de TAG [2]. En particular, la técnica utilizada para reducir la complejidad del algoritmo de tipo Earley con la propiedad del prefijo válido puede trasponerse directamente al caso de TAG, con lo cual la fase de compleción de adjunción del algoritmo de tipo Earley para TAG con la propiedad del prefijo válido propuesto por Nederhof [7] quedaría definida por los dos pasos siguientes en lugar de los tres pasos D_{Earley}^{AdjComp^{0}}, D_{Earley}^{AdjComp^{1}} y D_{Earley}^{AdjComp^{2}} descritos en [2]:

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

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

D_{Earley}^{AdjComp^{1′}} = \frac{\begin{matrix}[[M^{γ} → υ•, j, m | p, q]], \\ [h, M^{γ} → υ•, k, l | p, q], \\ [h, N^{γ} → δ • M^{γ}ν, i, j | p′, q′] \end{matrix}}{[h, N^{γ} → δM^{γ} • ν, i, m | p ∪ p′, q ∪ q′]}

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

En este caso explotamos la información del ítem [h, M^{γ} → υ•, k, l | p, q] en vez de utilizar un ítem redundante [h, F^{γ} → ⊥•, p, q | p, q] y se preserva igualmente la complejidad O(n^{6}).

Referencias

[1] Alfred V. Aho. Indexed grammars — an extension of context-free grammars. Journal of the Association for Computer Machinery, 15(4):647–671, 1968.

[2] Miguel A. Alonso, David Cabrero, Eric de la Clergerie y Manuel Vilares. Tabular algorithms for TAG parsing. In Proc. of EACL’99, Bergen, Noruega, junio de 1999.

[3] Miguel A. Alonso, Eric de la Clergerie y David Cabrero. Tabulation of automata for tree adjoning languages. In Proc. of MOL-6, Orlando, FL, EE.UU., julio de 1999.

[4] Eric de la Clergerie y Miguel A. Alonso. A tabular interpretation of a class of 2-Stack Automata. In Proc. of COLING-ACL’98, pp. 1333–1339, Montreal, Quebec, Canadá, agosto de 1998.

[5] Eric de la Clergerie, Miguel A. Alonso y David Cabrero. A tabular interpretation of bottom-up automata for TAG. In Proc. of TAG+4, pp. 42–45, Filadelfia, PA, EE.UU., agosto de 1998.

[6] Gerald Gazdar. Applicability of indexed grammars to natural languages. In U. Reyle y C. Rohrer, editores, Natural Language Parsing and Linguistic Theories, pp. 69–94. D. Reidel Publishing Company, 1987.

[7] Mark-Jan Nederhof. Solving the correct-prefix property for TAGs. In T. Becker y H.-V. Krieger, editores, Proc. of MOL-5, pp. 124–130, Schloss Dagstuhl, Saarbruecken, Alemania, agosto de 1997.

[8] Mark-Jan Nederhof. Linear indexed automata and tabulation of TAG parsing. In Proc. of TAPD’98, pp. 1–9, París, Francia, abril de 1998.

[9] Yves Schabes. Stochastic lexicalized tree-adjoining grammars. In Proc. of COLING’92, pp. 426–432, Nantes, Francia, agosto de 1992.

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

[11] Klaas Sikkel. Parsing Schemata — A Framework for Specification and Analysis of Parsing Algorithms. Springer-Verlag, Berlín/Heidelberg/Nueva York, 1997.

[12] K. Vijay-Shanker y David J. Weir. Polynomial parsing of extensions of context-free grammars. In Masaru Tomita, editor, Current Issues in Parsing Technology, capítulo 13, pp. 191–206. Kluwer Academic Publishers, Norwell, MA, EE.UU., 1991.

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