Graph-structured Stack and Natural Language Parsing

Graph-structured Stack and Natural Language Parsing Masaru Tomlta Center for Machine Translation and Computer Science Department Camegie-MeUon University Pittsburgh, PA 15213 Abstract 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. 1. Introduction A stack plays an important role in natural language parsing. It is the stack which gives a parser context- free (rather than regular) power by permitting recursions. Most parsing systems make explicit use of the stack. Augmented Transition Network (ATN) [10] employs a stack for keeping track of retum addresses when it visits a sub-network. Shift-reduce parsing uses a stack as a pdmary device; sentences are parsed only by pushing an element onto the stack or by reducing the stack in accordance with grammatical rules. Implementation of pdnciple-based parsing [9, 1, 4] and categodal grammar [2] also often requires a stack for stodng partial parses already builL Those parsing systems usually introduce backtracking or pseudo parallelism to handle nondeterminism, taking exponential time in the worst case. This paper describes a general device, a graph-structured stack. The graph-structured stack was originally introduced in Tomita's generalized LR parsing algorithm [7, 8]. This paper applies the graph- structured stack to various other parsing methods. Using the graph-structured stack, a system is guaranteed not to replicate the same work and can run in polynomial time. This is true for all of the parsing systems mentioned above; ATN, shift-reduce parsing, principle-based parsing, and perhaps any other parsing systems which employ a stack. The next section describes the graph-structure stack itself. Sections 3, 4, 5 and 6 then describe the use of the graph-structured stack in shift-reduce LR parsing, ATN, Categorlal Grammars, and principle- based parsing, respectively. Section 7 discusses the relationship between the graph-structured stack and chart [5], demonstrating that chart parsing may be viewed as a special case of shift-reduce parsing with a graph-structured stack. 2. The Graph-structured Stack In this section, we describe three key notions of the graph-structured stack: splitting, combining and local ambiguity packing. • 2.1. SpUttlng When a stack must be reduced (or popped) in more than one way, the top of the stack is split. Suppose that the stack is in the following state. The left-most element, A, is the bottom of the stack, and the right- most element, E, is the top of the stack. In a graph- structured stack, there can be more than one top, whereas there can be only one bottom. #,--- n --- C --- D --- Z Suppose that the stack must be reduced in the following three different ways. F <-- D ]~ G <-- D IB H<-- C D 1 Then after the three reduce actions, the stack looks 249 like: A …

Content truncated to 500 words