A Bidirectional Bottom-up Parser for TAG

Víctor Jesús Díaz Madrigal
Vicente Carrillo Montero
Miguel Angel Alonso Pardo

in Proc. of Sixth International Workshop on Parsing Technologies (IWPT 2000), Trento, Italy, February 2000.


Several parsing algorithms have been proposed for Tree Adjoining Grammars (TAGs), most of them derived from context-free tabular parsers. However, only a few bidirectional parsing algorithms have been proposed although this kind of strategy seems to be naturally adapted for TAG. In this paper, we present a new bidirectional bottom-up parser for TAG derived from the context-free parser defined by de Vreught and Honig, which has several interesting characteristics: (i) the bidirectional strategy allow us to implement the recognition of the adjoining operation in a simple way, (ii) the bottom-up behavior allow us to take advantage of lexicalization, reducing the number of trees under consideration during the parsing process, and (iii) in the case of ungrammatical input sentences, the parser is able to recover most of partial parsings according to lexical entries.

Víctor Jesús Díaz Madrigal / vjdiaz@lsi.us.es
Vicente Carrillo Montero / carrillo@lsi.us.es
Miguel Angel Alonso Pardo / alonso@dc.fi.udc.es