Efficient Tabular LR Parsing

Efficient Tabular LR Parsing Mark-Jan Nederhof Faculty of Arts University of Groningen P.O. Box 716 9700 AS Groningen The Netherlands markj an@let, rug. nl Giorgio Satta Dipartimento di Elettronica ed Informatica Universit£ di Padova via Gradenigo, 6/A 1-35131 Padova Italy satt a@dei, unipd, it Abstract We give a new treatment of tabular LR parsing, which is an alternative to Tomita's generalized LR algorithm. The advantage is twofold. Firstly, our treatment is con- ceptually more attractive because it uses simpler concepts, such as grammar trans- formations and standard tabulation tech- niques also know as chart parsing. Second- ly, the static and dynamic complexity of parsing, both in space and time, is signifi- cantly reduced. 1 Introduction The efficiency of LR(k) parsing techniques (Sippu and Soisalon-Soininen, 1990) is very attractive from the perspective of natural language processing ap- plications. This has stimulated the computational linguistics community to develop extensions of these techniques to general context-free grammar parsing. The best-known example is generalized LR pars- ing, also known as Tomita's algorithm, described by Tomita (1986) and further investigated by, for ex- ample, Tomita (1991) and Nederhof (1994a). Des- pite appearances, the graph-structured stacks used to describe Tomita's algorithm differ very little from parse fables, or in other words, generalized LR pars- ing is one of the so called tabular parsing algorithms, among which also the CYK algorithm (Harrison, 1978) and Earley's algorithm (Earley, 1970) can be found. (Tabular parsing is also known as chart pars- ing.) In this paper we investigate the extension of LR parsing to general context-free grammars from a more general viewpoint: tabular algorithms can of- ten be described by the composition of two construc- tions. One example is given by Lang (1974) and Billot and Lang (1989): the construction of push- down automata from grammars and the simulation of these automata by means of tabulation yield dif- ferent tabular algorithms for different such construc- tions. Another example, on which our presentation is based, was first suggested by Leermakers (1989): a grammar is first transformed and then a standard tabular algorithm along with some filtering condi- tion is applied using the transformed grammar. In our case, the transformation and the subsequent ap- plication of the tabular algorithm result in a new form of tabular LR parsing. Our method is more efficient than Tomita's algo- rithm in two respects. First, reduce operations are implemented in an efficient way, by splitting them in- to several, more primitive, operations (a similar idea has been proposed by Kipps (1991) for Tomita's al- gorithm). Second, several paths in the computation that must be simulated separately by Tomita's algo- rithm are collapsed into a single computation path, using state minimization techniques. Experiments on practical grammars have indicated that there is a significant gain in efficiency, with regard to both space and time requirements. Our grammar transformation produces a so called cover for the input grammar, which together with the filtering condition fully captures the specifica- tion of the method, abstracting away from algorith- mic details such …

Content truncated to 500 words