Esquemas basados en Left Corner sin prefijo válido para TAGs: Relaciones (LSI-2002-03)

Abstract

Las Gramáticas de Adjunción de Árboles (TAGs, Tree Adjoining Grammars) es un formalismo ampliamente usado en el procesamiento del lenguaje natural, sin embargo, el coste computacional teórico que requieren los analizadores sintácticos definidos para el mismo es excesivamente elevado respecto al requerido en otros formalismos también muy empleados, aunque con menor poder expresivo, como podrían ser las Gramáticas Independientes del Contexto (CFGs, Context Free Grammars). En la literatura podemos encontrar numerosos trabajos que intentan minimizar el coste real del análisis, ya sea aplicando restricciones al formalismo ó aplicando técnicas de compactación de gramáticas. Nuestra propuesta va en la línea de aumentar las prestaciones prácticas de los analizadores basados en Earley para TAGs, mediante la aplicación de un filtro left corner al estilo de los ya conocidos para CFGs. En este trabajo mostramos cuatro nuevos analizadores para TAGs que hacen uso de este tipo filtrado y establecemos las relaciones formales que existen entre ellos. Usaremos los esquemas de análisis como método general para descripción de algoritmos de análisis sintáctico, ya que, entre otras ventajas, nos permiten definir analizadores sintácticos de manera abstracta y establecer relaciones formales entre ellos.