A new algorithm for parsing generalized phrase structure grammar
P.V. Harrison · University of Washington Press eBooks · 1988
This dissertation reports on the implementation of a grammar formalism and parser for English based on the Generalized Phrase Structure Grammar (GPSG) linguistic theory. The system currently consists of some 300 grammar rules and a lexicon of some 10,000 English words. It incorporates advances in the three areas: the grammar formalism, the parsing algorithm, and grammar evaluation techniques. The grammar formalism provides a means of specifying large context-free grammars with a relatively small number of grammar rules. Some unique features of the formalism include the method of representing syntactic features, a system of free categories for certain adverbial constructions, and an extension of the foot feature concept to handle certain constructions not previously treated in GPSG. The parser is based on the general context-free algorithm of Graham, Harrison and Ruzzo (1976) and includes several innovations that accommodate particular properties of the grammar formalism and promote efficiency, including parameterized rule triggering, constraints on gap node postulation, a specialized tree representation scheme that reduces memory, and a method of top-down filtering that utilizes syntactic features. In the area of system evaluation, two aspects are considered: parser efficiency and the accuracy of grammar coverage. The contributions of the parsing innovations are evaluated using a corpus of test sentences drawn from textbooks and newspaper articles. In the discussion of accuracy, two new evaluation techniques, designed to aid a linguist in assessing the correctness of the parser output, are proposed. The first technique involves extraction of the minimum-cost tree from the parse forest through the assignment of syntactic costs to the grammar rules. The second uses an unlabelled bracketing of the input sentence by the linguist and retrieves all trees that satisfy the bracketing.