Simplifying Deterministic Parsing

Simplifying Deterministic Parsing Alan W. Carter z Department of Computer Science University of British Columbia Vancouver, B.C. V6T IW5 Michael J. Frelllng 2 Department of Computer Science Oregon State University Corvallis, OR 07331 ABSTRACT This paper presents a model for deterministic parsing which was designed to simplify the task of writing and understanding a deterministic grammar. While retaining structures and operations similar to those of Mareus's PARSIFAL parser [Marcus 80] the grammar language incorporates the following changes. (1) The use of productions operating in parallel has essentially been eliminated and instead the productions are organized into sequences. Not only does this improve the understandability of the grammar, it is felt that, this organization corresponds more closely to the task of per- forming the sequence of buffer transformations and attachments required to parse the most common constituent types. (2) A general method for interfacing between the parser and a semavtic represen- tation system is introduced. This interface is independent of the particular semantic representation used and hides all details of the semantic processing from the grammar writer. (3) The interface also provides a general method for dealing with syntactic ambiguities which arise from the attachment of optional modifiers such as prepo- sitional phrases. This frees the grammar writer from determining each point at which such ambiguities can occur. 1. INTRODUCTION Marcus has effectively described the advantages of a deter- ministic parsing model as is embodied in his PARSIFAL system. Unfortunately a hindrance to the usability of PARSIFAL is the com- plexity of its grammar. The popularity of Woods' ATN parsing model [Woods 70] demonstrates that the ease with which a grammar can be written and understood is one of the greatest factors contri- buting to its usability. This paper describes DPARSER (Determinis- tic PARSER) which is an implementation of an alternate determinis- tic parsing model intended to reduce the complexity of deterministic grammars. DPARSER has been implemented and a small grammar writ- ten. In developing the grammar the focus has been on dealing with the syntactic ambiguities between the attachment of phrases and thus it can currently handle only simple noun and verb phrases. 2. CONSTITUENT BUFFER DPARSER maintains a constituent buffer which is manipu- lated by the grammar to derive the constituent structure of the input sentence. Each node of the buffer contains a constituent con- sisting of a set of feature-type, feature-value pairs, and a set of sub- constituents. When parsing begins the constituent buffer contains a single node with an associated subgrammar for parsing sentence con- stituents. As the subgrammar of the sentence node examines the buffer positions to its right, words are brought in from the input sen- tence to fill the empty positions. When the grammar discovers a subconstituent phrase to be parsed, it performs a PUSH operation specifying a subgrammar for parsing the constituent and the posi- tion of the rightmost word in the constituent phrase. The PUSIt operation inserts a new node into the buffer immediately preceding the constituent phrase and begins executing the …

Content truncated to 500 words