Generalized Left-Corner Parsing

Generalized Left-Corner Parsing Mark-Jan Nederhof * University of Nijmegen, Department of Computer Science Toernooiveld, 65125 ED Nijmegen, The Netherlands markjan@cs.kun.nl Abstract We show how techniques known from gen- erMized LR parsing can be applied to left- corner parsing. The ~esulting parsing algo- rithm for context-free grammars has some advantages over generalized LR parsing: the sizes and generation times of the parsers are smaller, the produced output is more compact, and the basic parsing technique can more easily be adapted to arbitrary context-free grammars. The algorithm can be seen as an optimiza- tion of algorithms known from existing lit- erature. A strong advantage of our presen- tation is that it makes explicit the role of left-corner parsing in these algorithms. Keywords: Generalized LR parsing, left- corner parsing, chart parsing, hidden left recursion. 1 Introduction Generalized LR parsing was first described by Tomita [Tomita, 1986; Tomita, 1987]. It has been regarded as the most efficient parsing technique for context-free grammars. The technique has been adapted to other formalisms than context-free gram- mars in [Tomita, 1988]. A useful property of generalized LR parsing (henceforth abbreviated to GLR parsing) is that in- put is parsed in polynomial time. To be exact, if the length of the right side of the longest rule is p, and if the length of the input is n, then the time com- plexity is O(nP+l). Theoretically, this may be worse *Supported by the Dutch Organization for Scientific Research (NWO), under grant 00-62-518 than the time complexity of Earley's algorithm [Ear- ley, 1970], which is O(n3). For practical cases in natural language processing however, GLR parsing seems to give the best results. The polynomial time complexity is established by using a graph-structured stack, which is a generaliza- tion of the notion of parse stack, in which pointers are used to connect stack elements. If nondeterminism occurs, then the search paths are investigated simul- taneously, where the initial part of the parse stack which is common to all search paths is represented only once. If two search paths share the state of the top elements of their imaginary individual parse stacks, then the top element is represented only once, so that any computation which thereupon pushes el- ements onto the stack is performed only once. Another useful property of GLR parsing is that the output is a concise representation of all possi- ble parses, the so called parse forest, which can be seen as a generalization of the notion of parse tree. (By some authors, parse forests are more specifically called shared, shared-packed, or packed shared (parse) forests.) The parse forests produced by the Mgorithm can be represented using O(n p+I) space. Efficient decoration of parse forests with attribute values has been investigated in [Dekkers et al., 1992]. There are however some drawbacks to GLR pars- ing. In order of decreasing importance, these are: • The parsing technique is based on the use of LR tables, which may be very large for grammars describing natural languages. 1 Related to this is …

Content truncated to 500 words