A Deterministic Parser With Broad Coverage

Abstract

'f11is paper is a progress report on a series of three significant extensions to the original parsing design of (Marcus 1980).* The extensions arc: The ran ge of syntJctic phenomena handled has been enlarged, encompassing sentences with Verb Phrase deletion gapping, and rightward movement, and an additional outpurepresentation of anaphor-antecedent relationships has been added (including pronoun and quantifier interpretation). A complete analysis of the parsing design has been carried out, clarifying the parser's relationship ro the extended LR(k , t) parsing method as originally defined by (Knuth 1965) and explored by (Szymanski and Williams 1976). The formal model has led directly to the desi gn of a "stripped down" parser that uses standard LR(k) technology and to results about the class of languages that can be handled by· Marcus-style parsers (briefly, the class of languages is defined by those that can be handled by a deterministic, two-stack push-down automaton with severe restrictions on the transfer of material between the two stacks, and includes some strictly context-sensitive languages).