Algoritmos de análisis para gramáticas de inserción de árboles

• Autores: Miguel Á. Alonso , Vicente Carrillo Montero, Víctor Jesús Díaz Madrigal
• Localización: Procesamiento del lenguaje natural, ISSN 1135-5948, Nº. 29, 2002 (Ejemplar dedicado a: XVII Congreso de la SEPLN. Universidad de Valladolid, 11-13 septiembre 2002), págs. 89-96
• Idioma: español
• Enlaces
  • Texto completo
• Resumen
  • español

    Tree Insertion Grammar (TIG) es un compromiso entre Context FreeGrammar (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 trabajo definimos cuatro nuevos analizadores para TIGs: tres son ascendentes y otro ascendente predictivo.

  • English

    Tree Insertion Grammar (TIG) is a compromise between Context Free Grammar (CFG) and Tree Adjoining Grammar (TAG) that can be parsed in O(n3)- time. In the literature, just two parsers for TIGs have been defined, based on the well-known CYK and Earley algorithms for CFGs. In this paper, we define four new parsers for TIGs: three parsers use a bottom-up strategy and the other one uses a predictive bottom-up strategy.