Paper: Graph-Structured Stack And Natural Language Parsing

ACL ID P88-1031
Title Graph-Structured Stack And Natural Language Parsing
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1988
Authors

A general device for handling nondeterminism in stack operations is described. The device, called a Graph-structured Stack, can eliminate duplication of operations throughout the nondeterministic processes. This paper then applies the graph-structured stack to various natural language parsing methods, including ATN, LR parsing, categodal grammar and principle- based parsing. The relationship between the graph- structured stack and a chart in chart parsing is also discussed.