Polynomial Time and Space Shift-Reduce Parsing of Arbitrary Context-free Grammars.

Polynomial Time and Space Shift-Reduce Parsing of Arbitrary Context-free Grammars.* Yves Schabes Dept. of Computer & Information Science University of Pennsylvania Philadelphia, PA 19104-6389, USA e-mail: schabes~linc.cis.upenn.edu Abstract We introduce an algorithm for designing a predictive left to right shift-reduce non-deterministic push-down machine corresponding to an arbitrary unrestricted context-free grammar and an algorithm for efficiently driving this machine in pseudo-parallel. The perfor- mance of the resulting parser is formally proven to be superior to Earley's parser (1970). The technique employed consists in constructing before run-time a parsing table that encodes a non- deterministic machine in the which the predictive be- havior has been compiled out. At run time, the ma- chine is driven in pseudo-parallel with the help of a chart. The recognizer behaves in the worst case in O(IGI2n3)-time and O(IGIn2)-space. However in practice it is always superior to Earley's parser since the prediction steps have been compiled before run- time. Finally, we explain how other more efficient vari- ants of the basic parser can be obtained by deter- minizing portionsof the basic non-deterministic push- down machine while still using the same pseudo- parallel driver. 1 Introduction Predictive bottom-up parsers (Earley, 1968; Earley, 1970; Graham et al., 1980) are often used for natural language processing because of their superior average performance compared to purely bottom-up parsers *We are extremely indebted to Fernando Pereira and Stuart Shleber for providing valuable technical comments during dis- cussions about earlier versio/m of this algorithm. We are also grateful to Aravind Joehi for his support of this research. We also thank Robert Frank. All remaining errors are the author's responsibility alone. This research wa~ partially funded by ARO grant DAAL03-89-C0031PRI and DARPA grant N00014- 90-J-1863. such as CKY-style parsers (Kasami, 1965; Younger, 1967). Their practical superiority is mainly obtained because of the top-down filtering accomplished by the predictive component of the parser. Compiling out as much as possible this predictive component before run-time will result in a more efficient parser so long as the worst case behavior is not deteriorated. Approaches in this direction have been investigated (Earley, 1968; Lang, 1974; Tomita, 1985; Tomita, 1987), however none of them is satisfying, either be- cause the worst case complexity is deteriorated (worse than Earley's parser) or because the technique is not general. Furthermore, none of these approaches have been formally proven to have a behavior superior to well known parsers such as Earley's parser. Earley himself ([1968] pages 69-89) proposed to pre- compile the state sets generated by his algorithm to make it as efficient as LR(k) parsers (Knuth, 1965) when used on LR(k) grammars by precomputing all possible states sets that the parser could create. How- ever, some context-free grammars, including most likely most natural language grammars, cannot be compiled using his technique and the problem of knowing if a grammar can be compiled with this tech- nique is undecidable (Earley [1968], page 99). Lang (1974) proposed a technique for evaluating in pseudo-parallel non-deterministic push down au- tomata. Although this technique achieves a worst …

Content truncated to 500 words