Bidirectional Parsing of Lexicalized Tree Adjoining Grammars

BIDIRECTIONAL PARSING OF LEXICALIZED TREE ADJOINING GRAMMARS* Alberto Lavelli and Giorgio Satta Istituto per ia Ricerca Scientifica e Teenologica I - 38050 Povo TN, Italy e-mail: lavelli/satta@irst.it Abstract In this paper a bidirectional parser for Lexicalized Tree Adjoining Grammars will be presented. The algorithm takes advantage of a peculiar characteristic of Lexicalized TAGs, i.e. that each elementary tree is associated with a lexical item, called its anchor. The algorithm employs a mixed strategy: it works bot- tom-up from the lexical anchors and then expands (partial) analyses making top-down predictions. Even if such an algorithm does not improve tim worst-case time bounds of already known TAGs parsing meth- ods, it could be relevant from the perspective of linguistic information processing, because it em- ploys lexical information in a more direct way. 1. Introduction Tree Adjoining Grammars (TAGs) are a formal- ism for expressing grammatical knowledge that ex- tends the domain of locality of context-free gram- mars (CFGs). TAGs are tree rewriting systems spec- ified by a finite set of elementary trees (for a detailed description of TAGs, see (Joshi, 1985)). TAGs can cope with various kinds of unbounded dependencies in a direct way because of their extended domain of locality; in fact, the elementary trees of TAGs are the appropriate domains for characterizing such de- pendencies. In (Kroch and Joshi, 1985) a detailed dis- cussion of the linguistic relevance of TAGs can be found. Lexicalized Tree Adjoining Grammars (Schabes et al., 1988) are a refinement of TAGs such that each elementary tree is associated with a lexieal item, called the anchor of the tree. Therefore, Lexicalized TAGs conform to a common tendency in modem theories of grammar, namely the attempt to embed grammatical information within lexical items. Notably, the association between elementary trees and anchors improves also parsing performance, as will be discussed below. Various parsing algorithms for TAGs have been proposed in the literature: the worst-case time com- plexity varies from O(n 4 log n) (Harbusch, 1990) to O(n 6) (Vijay-Shanker and Joshi, 1985, Lang, 1990, Schabes, 1990) and O(n 9) (Schabes and Joshi, 1988). *Part of this work was done while Giorgio Satta was completing his Doctoral Dissertation at the University of Padova (Italy). We would like to thank Yves Schabes for his valuable comments. We would also like to thank Anne Abeill6. All errors are of course our own. As for Lexicalized TAGs, in (Schabes et al., 1988) a two step algorithm has been presented: during the first step the trees corresponding to the input string are selected and in the second step the input string is parsed with respect to this set of trees. Another paper by Schabes and Joshi (1989) shows how parsing strategies can take advantage of lexicalization in order to improve parsers' performance. Two major advantages have been discussed in the cited work: grammar filtering (the parser can use only a subset of the entire grammar) and bottom-up information (further constraints are imposed on the way trees can be combined). Given these premises and …

Content truncated to 500 words