tailieunhanh - Báo cáo khoa học: "The Use of Shared Forests in Tree Adjoining Grammar Parsing"

We study parsing of tree adjoining grammars 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 grammars. The work presented in this paper is intended to give a general framework for studying tag 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@ David J. Weir School of Cognitive Computing Sciences University of Sussex Falmer Brighton BN1 9QH UK davidw@ Abstract We study parsing of tree adjoining grammars 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 grammars. 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 grammars 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 approach 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 parsing 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 equivalent to tag Vijay-Shianker 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 equivalent .