tailieunhanh - Báo cáo khoa học: "BIDIRECTIONAL PARSING OF LEXICALIZED TREE ADJOINING GRAMMARS"

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, . that each elementary tree is associated with a lexical item, called its anchor. The algorithm employs a mixed strategy: it works bottom-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 methods, it could be relevant from the perspective of linguistic information processing, because it employs lexical information in a more direct. | BIDIRECTIONAL PARSING OF LEXICALIZED TREE ADJOINING GRAMMARS Alberto Lavelli and Giorgio Satta Istituto per la Ricerca Scientifica e Tecnologica I - 38050 Povo TN Italy e-mail lavelli satta@ Abstract In this paper a bidừectional parser for Lexicalized Tree Adjoining Grammars will be presented. The algorithm takes advantage of a peculiar characteristic of Lexicalized TAGs . that each elementary tree is associated with a lexical item called its anchor. The algorithm employs a mixed strategy it works bottom-up from the lexical anchors and then expands partial analyses making top-down predictions. Even if such an algorithm does not improve the worst-case time bounds of already known TAGS parsing methods it could be relevant from the perspective of linguistic information processing because it employs lexical information in a more dữect way. 1. Introduction Tree Adjoining Grammars TAGs are a formalism for expressing grammatical knowledge that extends the domain of locality of context-free grammars CFGs . TAGS are tree rewriting systems specified 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 dependencies. In Kroch and Joshi 1985 a detailed discussion of the linguistic relevance of TAGS can be found. Lexicalized Tree Adjoining Grammars Schabes el al. 1988 are a refinement of TAGs such that each elementary tree is associated with a lexical 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 .