tailieunhanh - Báo cáo khoa học: "Tabular Algorithms for TAG Parsing"

We describe several tabular algorithms for Tree Adjoining G r a m m a r parsing, creating a continuum from simple pure bottom-up algorithms to complex predictive algorithms and showing what transformations must be applied to each one in order to obtain the next one in the continuum. | Proceedings of EACL 99 Tabular Algorithms for TAG Parsing Miguel A. Alonso Departamento de Computación Univesidad de La Coruna Campus de Elvina s n 15071 La Coruna Spain alonso@ Eric de la Clergerie INRIA Domaine de Voluceau Rocquencourt . 105 78153 Le Chesnay Cedex France Abstract We describe several tabular algorithms for Tree Adjoining Grammar parsing creating a continuum from simple pure bottom-up algorithms to complex predictive algorithms and showing what transformations must be applied to each one in order to obtain the next one in the continuum. 1 Introduction Tree Adjoining Grammars are a extension of CFG introduced by Joshi in Joshi 1987 that use trees instead of productions as the primary representing structure. Several parsing algorithms have been proposed for this formalism most of them based on tabular techniques ranging from simple bottom-up algorithms Vijay-Shanker and Joshi 1985 to sophisticated extensions of the Earley s algorithm Schabes and Joshi 1988 Schabes 1994 Nederhof 1997 . However it is difficult to inter-relate different parsing algorithms. In this paper we study several tabular algorithms for TAG parsing showing their common characteristics and how one algorithm can be derived from another in turn creating a continuum from simple pure bottom-up to complex predictive algorithms. Formally a TAG is a 5-tuple Q Výv Vr s I A where VXr is a finite set of non-terminal symbols Vt a finite set of terminal David Cabrero Departamento de Computación Univesidad de La Coruna Campus de Elvina s n 15071 La Coruna Spain cabrero@ Manuel Vilares Departamento de Computación Univesidad de La Coruna Campus de Elvina s n 15071 La Coruna Spain vilares@ symbols s the axiom of the grammar I a finite set of initial trees and A a finite set of auxiliary trees. luA is the set of elementary trees. Internal nodes are labeled by non-terminals and leaf nodes by terminals or E except for just one leaf