Tesis Doctoral

Información general
Resumen
Estructura de la memoria
Difución de resultados
Descarga
Más información

[This page in English]


Título

Interpretación tabular de autómatas para lenguajes de adjunción de árboles

Autor

D. Miguel A. Alonso Pardo

Directores

Fecha

25 de septiembre de 2000

Tribunal

Calificación

Sobresaliente Cum Laude


Resumen

Las gramáticas de adjunción de árboles son una extensión de las gramáticas independientes del contexto que utilizan árboles en vez de producciones como estructuras elementales y que resultan adecuadas para la descripción de la mayor parte de las construcciones sintácticas presentes en el lenguaje natural. Los lenguajes generados por esta clase de gramáticas se denominan lenguajes de adjunción de árboles y son equivalentes a los lenguajes generados por las gramáticas lineales de índices y otros formalismos suavemente dependientes del contexto.

En la primera parte de esta memoria se presenta el problema del análisis sintáctico de los lenguajes de adjunción de árboles. Para ello, se establece un camino evolutivo continuo en el que se sitúan los algoritmos de análisis sintáctico que incorporan las estrategias de análisis más importantes, tanto para el caso de las gramáticas de adjunción de árboles como para el caso de las gramáticas lineales de índices.

En la segunda parte se definen diferentes modelos de autómata que aceptan exactamente los lenguajes de adjunción de árboles y se proponen técnicas que permiten su ejecución eficiente. La utilización de autómatas para realizar el análisis sintáctico es interesante porque permite separar el problema de la definición de un algoritmo de análisis sintáctico del problema de la ejecución del mismo, al tiempo que simplifica las pruebas de corrección. Concretamente, hemos estudiado los siguientes modelos de autómata:

Hemos definido esquemas de compilación para todos estos modelos de autómata. Estos esquemas permiten obtener el conjunto de transiciones correspondiente a la implantación de una determinada estrategia de análisis sintáctico para una gramática dada.

Todos los modelos de autómata pueden ser ejecutados en tiempo polinomial con respecto a la longitud de la cadena de entrada mediante la aplicación de técnicas de interpretación tabular. Estas técnicas se basan en la manipulación de representaciones colapsadas de las configuraciones del autómata, denominadas ítems, que se almacenan en una tabla para su posterior reutilización. Con ello se evita la realización de cálculos redundantes.

Finalmente, hemos analizado conjuntamente los diferentes modelos de autómata, los cuales se pueden dividir en tres grandes grupos: la familia de los autómatas generales, de la que forman parte los autómatas lineales de índices fuertemente dirigidos y los autómatas con dos pilas fuertemente dirigidos; la familia de los autómatas descendentes, en la que se encuadran los autómatas a pila embebidos y los autómatas lineales de índices orientados a la izquierda; y la familia de los autómatas ascendentes, en la que se enmarcan los autómatas a pila embebidos ascendentes, los autómatas lineales de índices orientados a la derecha y los autómatas con dos pilas ascendentes.


Estructura de la memoria

La memoria se estructura en tres partes. En la primera se presentan los lenguajes de adjunción de árboles y las técnicas de análisis sintáctico para dicha clase de lenguajes. En la segunda, que constituye el núcleo de la memoria, se presentan diversos modelos de autómata para esta clase de lenguajes junto con las técnicas que permiten realizar la interpretación tabular de cada uno de ellos. La tercera parte la constituyen una serie de apéndices en los que se presenta material que, si bien no es imprescindible, es de interés en el ámbito de la tesis. A continuación presentamos un breve resumen del contenido de cada uno de los capítulos.

Capítulo 1. Introducción

Parte I. Lenguajes de adjunción de árboles

Capítulo 2. Lenguajes de adjunción de árboles

En este capítulo se realiza una presentación de los lenguajes de adjunción de árboles, situándolos en la jerarquía de Chomsky. Se tratan en detalle dos formalismos gramaticales que generan esta clase de lenguajes, las gramáticas de adjunción de árboles y las gramáticas lineales de índices, pues son los formalismos sobre los que se trabajará en el resto de la memoria. También se presentan brevemente otros formalismos que generan la misma clase de lenguajes.

Capítulo 3. Algoritmos de análisis sintáctico para TAG

Este capítulo constituye un estudio sobre el estado actual del análisis sintáctico de las gramáticas de adjunción de árboles, aunque incluye aportaciones novedosas. En particular, se presenta una línea evolutiva continua en la cual se sitúan los algoritmos tabulares correspondientes a las principales estrategias de análisis para gramáticas de adjunción de árboles, abarcando desde estrategias puramente ascendente hasta estrategias de tipo Earley que preservan la propiedad del prefijo válido. Todos estos algoritmos se definen mediante esquemas de análisis sintáctico, de tal modo que los algoritmos más complejos se derivan a partir de los menos complejos aplicando una secuencia de transformaciones simples. También se presentan aquellos algoritmos que incorporan estrategias bidireccionales, que realizan el proceso de análisis en varias fases, que basan el análisis en una compilación en gramáticas lineales de índices, que precompilan parte de la información en forma de un autómata de tipo LR y aquellos diseñados específicamente para su ejecución en máquinas paralelas.

Capítulo 4. Algoritmos de análisis sintáctico para LIG

En este capítulo se realiza un estudio sobre el estado actual del análisis sintáctico de las gramáticas lineales de índices, al que se ha contribuido con el desarrollo de algoritmos tabulares de tipo Earley con y sin la propiedad del prefijo válido. El diseño de estos algoritmos nos ha permitido crear una línea evolutiva continua paralela a la desarrollada en el capítulo precedente para el caso de las gramáticas de adjunción de árboles.

Parte II. Modelos de autómata para los lenguajes de adjunción de árboles

Capítulo 5. Autómatas a pila

Antes de proceder a la definición de nuevos modelos de autómata, se presenta en este capítulo un repaso de los autómatas a pila y de las técnicas de tabulación disponibles para los mismos.

Capítulo 6. Autómatas a pila embebidos

En este capítulo se presentan los autómatas a pila embebidos, en los cuales la estructura principal de almacenamiento la constituye una pila de pilas. Junto a la definición clásica se presenta una nueva formulación en la cual se elimina el control de estado finito y se simplifica la forma de las transiciones al tiempo que se mantiene la potencia expresiva. Esta nueva formulación permite diseñar una técnica de tabulación para la ejecución eficiente de los diversos esquemas de compilación para gramáticas de adjunción de árboles y gramáticas lineales de índices que se definen en el capítulo.

Capítulo 7. Autómatas a pila embebidos ascendentes

La versión dual del modelo de autómata tratado en el capítulo anterior la constituyen los autómatas a pila embebidos ascendentes. En este capítulo se realiza una definición formal de los mismos, algo que no se había logrado hasta el momento. La eliminación del control de estado finito permite simplificar la forma de las transiciones, lo cual facilita la definición de una técnica de tabulación para este modelo de autómata.

Capítulo 8. Autómatas lógicos a pila restringidos

En este capítulo mostramos cómo las gramáticas lineales de índices constituyen un tipo específico de gramáticas de cláusulas definidas en el cual los predicados tienen un único argumento en forma de pila de índices. Aprovechamos esta característica para definir una versión restringida de los autómatas lógicos a pila adecuada al tratamiento de este tipo de gramáticas y de las gramáticas de adjunción de árboles. Dependiendo de la forma de las transiciones permitidas, podemos distinguir tres tipos diferentes de autómata, uno que permite el análisis ascendente de los índices o adjunciones, otro que permite el análisis descendente y otro que permite estrategias mixtas. En los dos últimos casos es preciso establecer restricciones en la combinación de las transiciones para garantizar que dichos autómatas aceptan exactamente la clase de los lenguajes de adjunción de árboles. Se presentan esquemas de compilación y técnicas de tabulación para los tres tipos de autómata.

Capítulo 9. Autómatas lineales de índices

En este capítulo se presentan los autómatas lineales de índices, que utilizan la misma estructura de almacenamiento que los autómatas lógicos a pila restringidos pero con un juego diferente de transiciones. Distinguimos tres tipos diferentes de autómata: los autómatas lineales de índices orientados a la derecha para estrategias en las cuales las pilas de índices se evalúan de modo ascendente, los autómatas lineales de índices orientados a la izquierda en los cuales las pilas de se evalúan de modo descendente y los autómatas lineales de índices fuertemente dirigidos que permiten definir estrategias mixtas de análisis para el tratamiento de las pilas de índices. Es precisamente la definición de este último tipo de autómatas y de la correspondiente técnica de tabulación la principal aportación de este capítulo.

Capítulo 10. Autómatas con dos pilas

En este capítulo se opta por un modelo de autómata con una nueva estructura de almacenamiento. Se preserva la pila de los autómatas a pila tradicionales, a la que acompaña una pila auxiliar cuyo contenido restringe el conjunto de transiciones aplicables es un momento dado. Los autómatas con dos pilas fuertemente dirigidos permiten definir esquemas de compilación arbitrarios para gramáticas de adjunción de árboles y gramáticas lineales de índices. Por su parte, los autómatas con dos pilas ascendentes sólo permiten describir esquemas de compilación que incorporan estrategias ascendentes en lo referente al tratamiento de las adjunciones y de las pilas de índices. Se presentan las técnicas de tabulación que permiten una ejecución eficiente de ambos modelos de autómata.

Capítulo 11. Recapitulación

Una vez definidos los diferentes modelos de autómata, llega el momento de analizarlos conjuntamente, percibiéndose la existencia de tres grandes grupos de autómatas: los autómatas generales, entre los que se incluyen los autómatas lineales de índices fuertemente dirigidos y los autómatas con dos pilas fuertemente dirigidos; los autómatas descendentes, entre los que se encuadran los autómatas a pila embebidos y los autómatas lineales de índices orientados a la izquierda; y los autómatas ascendentes, que incluyen los autómatas a pila embebidos ascendentes, los autómatas lineales de índices orientados a la derecha y los autómatas con dos pilas ascendentes.

Capítulo 12. Conclusiones

Parte III. Apéndices

Apéndice A. Esquemas de análisis sintáctico

En este apéndice se presenta un resumen de los esquemas de análisis sintáctico, la estructura formal en la cual se describen los algoritmos de análisis sintáctico para los diferentes formalismos gramaticales utilizados en esta memoria.

Apéndice B. Algoritmos de análisis sintáctico para CFG

Este apéndice contiene la definición de los algoritmos de análisis sintáctico CYK y Earley para gramáticas independientes del contexto, que constituyen la base de la mayor parte de los algoritmos de análisis sintáctico para gramáticas de adjunción de árboles y para gramáticas lineales de índices.

Apéndice C. Análisis sintáctico LR generalizado

A partir del algoritmo de Earley se derivan las técnicas de interpretación tabular de los diferentes tipos de algoritmos LR para gramáticas independientes del contexto. A continuación se presenta un algoritmo de tipo LR para extensiones basadas en unificación de las gramáticas independientes del contexto, finalizando con la presentación de un algoritmo LR para gramáticas lineales de índices.


Difusión de resultados

El material generado durante la realización de la presente tesis doctoral ha dado lugar a varios artículos de revista, capítulos de libro y ponencias en congresos. A continuación detallamos los trabajos surgidos de los diferentes capítulos.

Capítulo 3.

Capítulo 4.

Capítulo 6.

Capítulo 7.

Capítulo 8.

Capítulo 9.

Capítulo 10.

Apéndice C.


Descarga


Más información

Los comentarios y sugerencias acerca de esta memoria y del trabajo en ella reflejado son bienvenidos. Se puede contactar con el autor en la dirección postal

            Miguel A. Alonso Pardo
            Departamento de Computación
            Facultad de Informática
            Campus de Elviña s/n
            15071 La Coruña (España)
      

o bien mediante correo electrónico en la dirección de correo electrónico alonso@dc.fi.udc.es.

En las páginas web del autor está disponible información adicional referente a esta tesis y a trabajos relacionados. La dirección es http://www.dc.fi.udc.es/~alonso/


Miguel Angel Alonso Pardo / alonso@dc.fi.udc.es
Last modified: Tue Nov 28 12:40:05 CET 2006