Tabular Algorithms for TAG Parsing

Proceedings of EACL '99 Tabular Algorithms for TAG Parsing Miguel A. Alonso Departamento de Computacidn Univesidad de La Corufia Campus de Elvifia s/n 15071 La Corufia SPAIN alonso@dc.fi.udc.es David Cabrero Departamento de Computacidn Univesidad de La Corufia Campus de Elvifia s/n 15071 La Corufia SPAIN cabreroQdc.fi.udc.es Eric de la Clergerie INRIA Domaine de Voluceau Rocquencourt, B.P. 105 78153 Le Chesnay Cedex FRANCE Eric.De_La_Clergerie@inria.fr Manuel Vilares Departamento de Computacidn Univesidad de La Corufia Campus de Elvifia s/n 15071 La Corufia SPAIN vilares@dc.fi.udc.es Abstract We describe several tabular algorithms for Tree Adjoining Grammar parsing, creating a continuum from simple pure bottom-up algorithms to complex pre- dictive 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 rep- resenting 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; Sch- abes, 1994; Nederhof, 1997). However, it is diffi- cult to inter-relate different parsing algorithms. In this paper we study several tabular algorithms for TAG parsing, showing their common characteris- tics 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 ~ = (VN,VT, S,I,A), where VN is a finite set of non-terminal symbols, VT a finite set of terminal symbols, S the axiom of the grammar, I a finite set of initial trees and A a finite set of auxiliary trees. IUA is the set of elementary trees. Internal nodes are labeled by non-terminals and leaf nodes by terminals or ~, except for just one leaf per auxiliary tree (the foot) which is labeled by the same non-terminal used as the label of its root node. The path in an elementary tree from the root node to the foot node is called the spine of the tree. New trees are derived by adjoining: let a be a tree contaiIiing a node N ~ labeled by A and let be an auxiliary tree whose root and foot nodes are also labeled by A. Then, the adjoining of at the adjunction node N ~ is obtained by excising the subtree of a with root N a, attaching j3 to N ° and attaching the excised subtree to the foot of ~. We use ~ E adj(N ~) to denote that a tree ~ may be adjoined at node N ~ of the elementary tree a. In order to describe the parsing algorithms for TAG, we must be able to represent the partial recognition of elementary trees. Parsing algo- rithms for context-free grammars usually denote partial recognition of productions by dotted pro- ductions. We can extend this approach to the case of TAG by considering …

Content truncated to 500 words