Principle-Based Parsing Without Overgeneration

PRINCIPLE-BASED PARSING WITHOUT OVERGENERATION 1 Dekang Lin Department of Computing Science, University of Manitoba Winnipeg, Manitoba, Canada, l~3T 2N2 E-mail: lindek@cs.umanitoba.ca Abstract Overgeneration is the main source of computational complexity in previous principle-based parsers. This paper presents a message passing algorithm for principle-based parsing that avoids the overgenera- tion problem. This algorithm has been implemented in C++ and successfully tested with example sen- tences from (van Riemsdijk and Williams, 1986). 1. Introduction Unlike rule-based grammars that use a large num- ber of rules to describe patterns in a language, Government-Binding (GB) Theory (Chomsky, 1981; Haegeman, 1991; van Riemsdijk and Williams, 1986) ezplains these patterns in terms of more foundmental and universal principles. A key issue in building a principle-based parser is how to procedurally interpret the principles. Since GB principles are constraints over syntactic struc- tures, one way to implement the principles is to 1. generate candidate structures of the sentence that satisfy X-bar theory and subcategoriza- tion frames of the words in the sentence. 2. filter out structures that violates any one of the principles. 3. the remaining structures are accepted as parse trees of the sentence. This implementation of GB theory is very ineffi- cient, since there are a large number of structures being generated and then filtered out. The prob- lem of producing too many illicit structures is called overgenera~ion and has been recognized as the cul- prit of computational difficulties in principle-based parsing (Berwick, 1991). Many methods have been proposed to alleviate the overgeneration problem by detecting illicit structures as early as possible, such as optimal ordering of principles (Fong, 1991), coroutining (Doff, 1991; Johnson, 1991). ] The author wishes to thank the anonymous referees for their helpful comments and suggestions. This research was supported by Natural Sciences and Engineering Research Council of Canada grant OGP121338. This paper presents a principle-based parser that avoids the overgeneration problem by applying prin- ciples to descriptions of the structures, instead of the structures themselves. A structure for the input sentence is only constructed after its description has been found to satisfy all the principles. The struc- ture can then be retrieved in time linear to its size and is guaranteed to be consistent with the princi- ples. Since the descriptions of structures are constant- sized attribute vectors, checking whether a struc- tural description satisfy a principle takes constant amount of time. This compares favorably to ap- proaches where constraint satisfaction involves tree traversal. The next section presents a general framework for parsing by message passing. Section 3 shows how linguistic notions, such as dominance and govern- ment, can be translated into relationships between descriptions of structures. Section 4 describes in- terpretation of GB principles. Familiarity with GB theory is assumed in the presentation. Section 5 sketches an object-oriented implementation of the parser. Section 6 discusses complexity issues and related work. 2. Parsing by Message Passing The message passing algorithm presented here is an extension to a message passing algorithm for context-free grammars (Lin and Goebel, 1993). We encode the …

Content truncated to 500 words