The Use of Shared Forests in Tree Adjoining Grammar Parsing

The Use of Shared Forests in Tree Adjoining Grammar Parsing* K. Vijay-Shanker Department of Computer & Information Sciences University of Delaware Newark, DE 19716 USA vijay@udel.edu David J. Weir School of Cognitive & Computing Sciences University of Sussex Falmer, Brighton BN1 9QH UK davidw@ cogs. sussex, ac.uk Abstract We study parsing of tree adjoining gram- mars with particular emphasis on the use of shared forests to represent all the parse trees deriving a well-formed string. We show that there are two distinct ways of representing the parse forest one of which involves the use of linear indexed grammars and the other the use of context-free gram- mars. The work presented in this paper is intended to give a general framework for studying tag parsing. The schemes using lig and cfg to represent parses can be seen to underly most of the existing tag parsing algorithms, 1 Introduction We study parsing of tree adjoining grammars (tag) with particular emphasis on the use of shared forests to represent all the parse trees deriving a well- formed string. Following Billot and Lang [1989] and Lang [1992] we use grammars as a means of recording all parses. Billot and Lang used context-free gram- mars (cfg) for representing all parses in a cfg parser demonstrating that a shared forest grammar can be viewed as a specialization of the grammar for the given input string. Lang [1992] extended this ap- proach considering both the recognition problem as well as the representation of all parses and suggests how this can be applied to tag. This paper examines this approach to tag pars- ing in greater detail. In particular, we show that *We are very grateful to Bernard Lang for helpful discussions. there are two distinct ways of representing the parse forest. One possibility is to use linear indexed grammars (lig), a formalism that is e~uivalent to tag [Vijay-Shanker and Weir, in pressa]. The use of lig is not surprising in that we would expect to be able to represent parses of a formalism in an equiva- lent formalism. However, we also show that there is a second way of representing parses that makes use ofa cfg. The work presented in this paper is intended to give a general framework for studying tag parsing. The schemes using lig and cfg to represent parses can be seen to underly most of the existing tag parsing algorithms. We begin with brief definitions of the tag and lig formalisms. This is followed by a discussion of the methods for cfg recognition and the representation of parses trees that were described in [Billot and Lang, 1989; Lang, 1992]. In the remainder of the paper we examine how this approach can be applied to tag. We first consider the representation of parses using a cfg and give the space and time complexity of recogni- tion and extraction of parses using this representa- tion. We then consider the same issues where lig is used as the formalism for representing parses. We conclude by comparing …

Content truncated to 500 words