Algoritmos de análisis para gramáticas de inserción de árboles: Relaciones (LSI-2003-01)

Abstract

Tree Insertion Grammar (TIG) es un compromiso entre Context Free Grammar (CFG) y Tree Adjoining Grammar (TAG) que puede ser analizada con un coste temporal de O(n3). En la literatura, tan sólo han sido descritos dos algoritmos de análisis para TIGs, basados en los ya conocidos CYK y Earley para CFGs. En este informe se describen en detalle los analizadores para TIGs presentados en [7, 5, 4], así como las relaciones formales existentes entre ellos. El objetivo es definir la espina dorsal del núcleo de una taxonomía de analizadores basados en el algoritmo de Earley, similar a las ya existentes para CFGs [20] y TAGs [1] [9].