PRINCIPAR - An Efficient, Broad-coverage, Principle-based Parser

PRINCIPAR--An Efficient, Broad-coverage, Principle-based Parser Dekang Lin Department of Computer Science, University of Manitoba Winnipeg, Manitoba, Canada RaT 2N2, lindek@cs.umanitoba.ca Abstract We present an efI]cient, broad-coverage, principle-based parser for English. The parser has been implemented in C++ and runs on SUN Sparcstations with X-windows. It con- rains a lexicon with over 90,000 entries, con- structed automatically by applying a set of ex- traction and conversion rules to entries from machine readable dictionaries. 1. Introduction Principle-based grammars, such as Govern- ment-Binding (GB) theory (Chomsky, 1981; Haegeman, 1991), offer many advantages over rule-based and unification-based grammars, such as the universality of principles and mod- ularity of components in the grammar. Prin- ciples are constraints over X-bar structures. Most previous principle-based parsers, e.g., (Dorr, 1991; Font, 1991; Johnson, 1991), es- sentially generate all possible X-bar structures of a sentence and then use the principles to fil- ter out the illicit ones. The drawback of this approach is the inefficiency due 1;o the large number of candidate structures to be. filtered out. The problem persists even when w~rions techniques such as optimal ordering of princi- ples (Fong, 1991), and corontining (Dorr, 1991; Johnson, 1991) are used. This problem may also account for the fact that these parsers are experimental and have limited coverage. This paper describes an efficient, broad- coverage, principle-based parser, called PRIN- CIPAR. The main innovation in PRINCIPAR is that it applies principles to descriptions o17 X- bar structures rather than the structures them- selves. X-bar structures of a sentence are only built when their descriptions have satisfied all the pri ncil)les. O dynamic data [~ static dala l)rocegsing module data flow Figure 1: '.Pile architecture of PRINCIPAR Figure I shows the architecture of PRIN- CIPAR. Sentence analysis is divided into three steps. The lexical analyser first converts the in- put sentence into a set of texical items. Then, a message passing algorithm for OB-parsing is used to construct a shared parse forest. Fi- nally, a parse tree retriever is used to enumer- ate the parse trees. The key idea of the parsing algorithm was presented in (tin, 199:1). This paper presents some implementation details and experimental results. 2. Parsing by Message Passing The parser in PIHNCIPAR is based on a message-passing framework proposed by ],in (1993) and l,in and Ooebel (1993), which uses a network to encode the grammar. The nodes in tile grammar network represent grammati- cal categories (e.g., NP, Nbar, N) or subcate- gories, such as V:NP (transitive verbs that take NPs as complements). The links in the net- work re.present relationships bel;ween the cat- egories. GB-principles are implemented as lo- cal constraints attached to the nodes and 482 percolation cormtraints attached to links in the network. Figure'2 depicts ~ port:ion C" tile gr;unmar network for |Dnglish. '2\ I t " "IP cpspe~.. , -/~/\~ i AAI ~ I'P " NI i VI : 1 t.. ".,.... "...".. ...." "".... A ul , P ,, ,. ' .......... ': '....".v.v.v.v.v.v.v; ................. .'"' "" ,~ V:N~ V:(,~x ' adjullct dominance …

Content truncated to 500 words