Download Aspectos formales en la lexicalización de CFG mediante TAG

UN ALGORITMO DE LEXICALIZACIÓN DE CFG
MEDIANTE TAG
Díaz Madrigal, Víctor Jesús
Toro Bonilla, Miguel
Departamento de Lenguajes y Sistemas Informáticos
Universidad de Sevilla
e-mail: vjdiaz@lsi.us.es
Carrillo Montero, Vicente
Departamento de Lenguajes y Sistemas Informáticos
Universidad de Cádiz
e-mail: vicente.carrillo@uca.es
Abstract
Most current linguistic theories give lexical accounts of several phenomena that used to be considered purely syntactic.
A lexicalized grammar consists of a lexicon where each lexical item is associated with a finite number of structures for
which that item is the anchor and a set of rules which tell us how these structures are composed. In general, Context
Free Grammars (CFG) are not lexicalized, but the operation of adjuntion , the base operation in Tree Adjoining
Grammars (TAG), give us the freedom to lexicalize CFGs. In this paper we present an algorithm that given a CFG G,
constructs a TAG that generates the same language and tree set as G.
1 Introducción
Un número importante de formalismos gramaticales tienden a desviar al lexicón cierta clase de
información que anteriormente era contemplada a nivel sintáctico. Dentro de este grupo podemos
nombrar, entre otras, las gramáticas funcionales léxicas LFG o las gramáticas de estructuras de
frases generalizadas GPSG.
Este nuevo escenario ha propiciado el estudio de cómo rentabilizar el aumento de información
léxica en el procesamiento de formalismos gramaticales. Esta rentabilidad puede obtenerse de una
forma natural mediante las gramáticas lexicalizadas.
Definición
Una gramática está lexicalizada [Shabes90 si consta de:
1. Un conjunto finito de estructuras, cada una de ellas asociada a un ítem léxico, al cual se
denomina ancla. Las estructuras definen el dominio de localidad sobre el que se
especifican las restricciones.
2. Un conjunto de operaciones de composición de estructuras.
Como restricciones adicionales hay que imponer que el tamaño de dichas estructuras sea finito y
que las operaciones conduzcan también a un número finito de resultados. Estas imposiciones nos
garantizan, por una parte, que las gramáticas lexicalizadas sean finitamente ambiguas, es decir, que
toda sentencia finita puede ser analizada mediante un número finito de formas. Y, por otra, que el
problema del reconocimiento de una sentencia por una gramática lexicalizada sea decidible.
El lexicón, desde este punto de vista, es un conjunto de estructuras ancladas, que
denominaremos estructuras elementales. Mientras a las estructuras obtenidas mediante
composiciones de éstas las denominaremos estructuras derivadas.
En el siguiente apartado definiremos el formalismo TAG y veremos como se enmarca dentro de
las gramáticas lexicalizadas.
2 Gramáticas TAG
Las gramáticas de adjunción de árboles TAG1 (Tree Adjoining Grammars) están basadas en un
sistema de reescritura de árboles frente a los sistemas de reescritura de cadenas habituales. Una
TAG [Joshi75] se define como una quíntupla (, NT, I, A, S), donde:
1.  es un conjunto finito de símbolos terminales
2. NT es un conjunto finito de símbolos no terminales
  NT =  ,   NT = V
3. S es un símbolo no terminal distinguido S  NT
4. I es un conjunto finito de árboles finitos sobre V, llamados árboles iniciales, que están
caracterizados de la siguiente forma:
 Los nodos interiores están etiquetados con símbolos no terminales y el nodo raíz con
S.
 Los nodos situados en la frontera del árbol están etiquetados mediante símbolos
terminales.
5. A es un conjunto finito de árboles finitos sobre V, llamados árboles auxiliares, que están
caracterizados de la siguiente forma:
 Los nodos interiores están etiquetados con símbolos no terminales.
 Los nodos situados en la frontera del árbol están etiquetados mediante símbolos
terminales, salvo uno, denominado nodo pie. El nodo pie será marcado con * y su
etiqueta debe coincidir con la etiqueta de la raíz.
Los árboles en I  A se denominan árboles elementales, y se corresponden con las mencionadas
estructuras elementales. En general, un árbol elemental presenta en su frontera varios ítems léxicos,
de forma que disponemos de diversas opciones en la decisión de cuál de ellos jugará el papel de
ancla.
En el formalismo TAG se define una operación básica de composición llamada adjunción. Los
árboles construidos mediante la composición de otros árboles se denominan árboles derivados, y se
corresponden con las mencionadas estructuras derivadas.
La adjunción construye un nuevo árbol ´ a partir de un árbol auxiliar  y otro árbol  (inicial,
auxiliar o derivado). Sea  un árbol que contiene un nodo n cuya etiqueta es X. Sea  un árbol cuya
Este formalismo fue presentado por Joshi, Levy y Takahashi [Joshi75]. Para más detalles sobre aspectos lingüísticos y
computacionales remitimos a [KroJos85] , [Vijay88] y [VijJos85].
1
raíz está etiquetada con X. El árbol resultante de adjuntar  en el nodo n de  se obtiene de la
siguiente forma (ver figura 1):
1. Se poda el subárbol de  dominado por n, dejando una copia de n. Denominemos a este
subárbol t.
2. El árbol  se copia sobre el nodo n, identificando su nodo raíz con n.
3. El subárbol t se copia sobre el nodo pie de , identificando la raíz de t con el nodo pie de .
Aunque la operación de adjunción es suficiente para componer estructuras derivadas , se
presenta una compactación importante al añadir la operación de sustitución al formalismo TAG.
Detalles significativos del empleo de esta operación en las TAG se pueden encontrar en [Abeille91.
Observando la definición anterior podemos deducir que las gramáticas de adjunción de árboles
TAG se encuentran dentro de la categoría de gramáticas lexicalizadas.

´
X
X
t
X
X

t
X*
Figura 1 Operación de adjunción
3 Lexicalización de CFG
En contraposición a lo que sucede con las gramáticas TAG, no todas las gramáticas CFG están
lexicalizadas. Basta con que alguna de sus reglas (estructuras elementales) no contenga ningún
símbolo terminal a la derecha para que la gramática no se encuentre lexicalizada. Teniendo esto en
cuenta, si tenemos una gramática GCFG, bastaría transformarla a su forma normal de Greibach
[Greiba65 para obtener una versión lexicalizada GCFG’ de la misma. Sin embargo, lo que
obtenemos es una gramática GCFG’ con solo una equivalencia en sentido débil a GCFG . Por tanto,
podemos decir que la forma normal de Greibach no es un método general de lexicalización.
Para permitir que aparezcan ítems léxicos en las estructuras elementales es necesario extender el
dominio de localidad [JosVij89. Para conseguirlo se pueden usar gramáticas basadas en sistemas de
reescritura de árboles y utilizar éstas como formalismo de lexicalización de CFG. En [Shabes90 se
demuestra que dada una gramática GCFG finitamente ambigua es posible obtener otra GTAG que es
equivalente en sentido fuerte a GCFG y está lexicalizada naturalmente. Es decir, las gramáticas TAG
tiene la capacidad de lexicalizar a las CFG.
Como dijimos, la definición de gramáticas lexicalizadas implican que son finitamente
ambiguas. Debido a ello las reglas recursivas derivadas (X * X) o simples (X  X) no se permiten,
ya que generan ramas infinitamente ambiguas.
Considerando que el formalismo CFG es la base teórica de una gran parte de formalismos
lingüísticos y que la lexicalización aporta las ventajas ya comentadas, creemos interesante la
búsqueda de un método general que nos permita la conversión de gramáticas CFG a gramáticas
TAG.
4 Algoritmo
Nuestro objetivo consiste justamente en desarrollar un algoritmo que, dada una gramática GCFG ,
obtenga una gramática GTAG que cumpla los requisitos expuestos en el punto anterior. Para ello
nuestro interés consistirá en la captura de todas aquellos árboles de análisis que se adapten a las
siguientes clases de derivaciones
S * 
X *  X 
siendo S y X símbolos no terminales (el primero de ellos además inicial), y  y  cadenas de
símbolos terminales. De esta forma los árboles de análisis se corresponden con los árboles
elementales de una gramática TAG.
El algoritmo se basará en la generación de los árboles de análisis relacionados con todas las
posibles derivaciones aplicables entre las distintas estructuras elementales de la gramática CFG,
considerando de partida que sus reglas son árboles de altura unitaria y las derivaciones se obtienen
aplicando la operación de sustitución en alguno de sus nodos frontera. En una etapa determinada
dispondremos de un conjunto de árboles de análisis asociados a derivaciones de la forma X  ,
siendo X un no terminal y  una cadena de terminales y no terminales. El objetivo del algoritmo
consiste en alcanzar derivaciones de las dos formas expuestas inicialmente.
El algoritmo que a continuación detallaremos se fundamenta en el siguiente teorema de Joshi,
Levy y Takahashi [Joshi75].
Teorema
Para toda gramática GCFG existe otra GTAG con equivalencia en sentido fuerte. Además dicha
GTAG cumple las siguientes restricciones:
1. Si  es un árbol inicial, entonces en cualquiera de sus ramas ningún no terminal aparece más
de una vez.
2. Si  es un árbol auxiliar, entonces en cualquiera de sus ramas ningún no terminal aparece
más de una vez, no siendo considerado el no terminal que etiqueta el nodo raíz de .
Este teorema, por una parte, nos garantiza la existencia de una gramática TAG dada una
gramática CFG. Pero también nos aporta un mecanismo de rechazo de generación de árboles, ya que
para cada nueva sustitución bastará comprobar si el árbol resultante cumple o no esta propiedad.
En el momento que un árbol cumpla la propiedad de ser elemental quedará agotado. Si fuera
inicial, todos sus nodos frontera serian terminales y no habría posibilidad de aplicar nuevas
sustituciones. Si fuera auxiliar, todos sus nodos frontera serian terminales salvo el nodo pie. Sin
embargo, nuevas sustituciones sobre dicho nodo implicaría la duplicación de, al menos, el símbolo
raíz, lo cual supondría la violación del teorema anteriormente expuesto.
Esta reflexión nos conduce a que si en el proceso de construcción de las nuevas estructuras
algunos de los árboles son elementales, podemos incorporarlos a la gramática final e ignorarlos en
la siguiente etapa.
El proceso de construcción es finito y su demostración se basa de nuevo en el teorema anterior.
Supongamos que la gramática tiene un alfabeto de símbolos no terminales NT de tamaño finito n, si
el proceso lleva a cabo más de n sustituciones sobre un árbol de análisis, al menos en una de las
ramas habrá un símbolo no terminal repetido, lo que viola el teorema y provoca la eliminación de
dicho árbol. Por tanto, el número máximo de iteraciones del algoritmo coincide con la cardinalidad
de NT.
El algoritmo que proponemos para llevar a cabo el proceso de construcción es el siguiente
{Precondición: CFG sin reglas espúreas}
LEX := {P}
CFG := {P}
TAG := 
mientras LEX  
LEX’ := 
para cada t1  LEX
si
es_elemental(t1) :
TAG := TAG  {t1}
otras :
C := 
para cada t2  CFG
C := C  sustituciones_válidas(t2 , t1)
fpara
LEX’ := LEX’  C
fsi
fpara
LEX := LEX’
fmientras
{Postcondición: TAG equivalente fuerte a CFG}
La estructuras de datos que usa el algoritmo son árboles y conjunto de árboles. Son árboles t1 y
t2 , y conjuntos de árboles las variables CFG, TAG, LEX, LEX’ y C.
 CFG es un conjunto de tamaño fijo que contiene los árboles de altura unitaria que
representan las reglas de la gramática CFG (P).
 TAG es el conjunto en el que se van almacenando los árboles agotados (elementales) que
formarán la gramática TAG a la finalización del proceso.
 LEX es el conjunto formado por los árboles de análisis en cada etapa del proceso.
 LEX’ es el conjunto formado por todos los árboles que se derivan a partir del conjunto LEX
en cada etapa del proceso.
 C es el conjunto de árboles que se derivan a partir de un árbol de LEX en cada etapa del
proceso.
Se utilizan dos funciones en el proceso
 es_elemental(árbol) devuelve el valor Cierto si árbol es un árbol inicial o auxiliar.
 sustituciones_válidas(árbol2, árbol1) devuelve el conjunto de árboles derivados a partir de
todas las posibles sustituciones de árbol2 en árbol1. Si un árbol derivado no cumple el
teorema descrito anteriormente, no se incluye en el conjunto.
5 Un ejemplo
Para ilustrar el funcionamiento del algoritmo supongamos la siguiente gramática CFG
S  NP VP
VP  adv VP  v
NP  n
Veamos como evolucionan los conjuntos TAG y LEX en cada etapa del algoritmo. Para ello
determinaremos sus valores en el comienzo del bucle mientras.
Etapa 0
TAG = 
LEX = CFG = { (1) , (2) , (3) , (4) }
S
VP
(1)
VP
(2)
NP
VP
adv
(3)
VP
NP
(4)
v
n
Inicialmente se transforman las reglas de la CFG en árboles de altura unitaria.
Etapa 1
TAG = { (2) }
VP
(2)
adv
VP*
El árbol (2) de la etapa 0 es un árbol auxiliar.
LEX = { (1.3) , (1.4) }
S
S
(1.3)
(1.4)
NP
VP
NP
v
n
VP
El árbol (1.2), resultado de sustituir (2) en (1), no es incluido por existir un no terminal (VP)
duplicado en una de sus ramas. Los árboles (3) y (4) no son árboles elementales y tampoco
generan árboles derivados, por tanto, en esta etapa desaparecen como árboles de análisis. Los
árboles (1.3) y (1.4) son productos de las sustituciones de (3) y (4) sobre los nodos etiquetados
VP y NP en (1), respectivamente.
Etapa 2
TAG = { (2) }
LEX = { (1.3.4) }
S
(1.3.4)
NP
VP
n
v
El árbol (1.4.2) no se incluye por existir un no terminal (VP) duplicado en una de sus ramas. El
árbol (1.4.3) si se incluye, sin embargo, es igual a (1.3.4) y la operación de unión (LEX’ :=
LEX’  C) evita que se repita.
Etapa 3
TAG = { (2) , (1.3.4) }
LEX = 
VP
S
(2)
adv
(1.3.4)
VP*
NP
VP
n
v
Este conjunto de árboles forman la gramática TAG que lexicaliza nuestra gramática CFG de
ejemplo.
6 Conclusiones
El formalismo TAG, en sentido puro, conduce necesariamente a gramáticas lexicalizadas, lo que
supone una clara inclusión en las últimas tendencias en lingüística computacional. El hecho de que
el formalismo TAG incluya la operación de adjunción nos permite, por una parte, lexicalizar
naturalmente las gramáticas CFG, y por otra, la eliminación de las restricciones que imponen las
gramáticas CFG en la elección de los ítems léxicos. El algoritmo que presentamos aporta un método
de transformación de gramáticas CFG a TAG.
7 Referencias
Abeill91 Abeille, A. (1991). “Une grammaire lexicalisée d'Arbres adjoints pour le Français:
Application à l'analyse automatique”. Tesis doctoral: Université Paris 7, Paris, France.
Greiba65 Greibach, S. A. (1965). “A new normal-form theorem for context-free phrase-structure
grammars”. J.ACM 12:42-52
Joshi75 Joshi, A. J.; Levy, L.; Takahashi, M. (1975). “Tree Adjunct grammars”. Journal of
Computer and System Science. 10(1) Pags. 136-163.
JosVij89 Joshi, A. K. ; Vijay-Shanker, K. (1989). “Treatment of Long Distance Dependencies in
LFG and TAG: Functional Uncertainty in LFG is a Corollary in TAG”. Proceedings 27th
Annual Meeting of ACL. Pags. 220-227.
JosSha92 Joshi, A. K.; Shabes Y. (1992). “Tree Adjoining Grammars and Lexicalized Grammars”.
En Tree Automata and Lenguages, ed. Nivat M. y Podelsky A. Pags. 409-431. Elservier
Science Publishers B.V.
KroJos85 Kroch, A.; Joshi, A. K. (1985). “Linguistic Relevance of Tree Adjoining Grammars”.
Technical Report MS-CIS-85-18, Department of Computer and Information Science,
University of Pennsylvania.
Shabes90 Shabes, Y. (1990). “Mathematical and Computational Aspects of Lexicalized
Grammars”. Tesis doctoral: University of Pennsylvania, Philadelphia, USA.
VijJos85 Vijay-Shanker, K.; Joshi, A. K. (1985). “Some Computacional Properties of Tree
Adjoining Grammars”. 3rd Meeting of ACL. Pags. 82-93.
Vijay88 Vijay-Shanker, K. (1988). “A Study of Tree Adjoining Grammars”. Tesis doctoral:
University of Pennsylvania, Philadelphia, USA.