Polynomial time and space shift-reduce parsing of arbitrary context-free grammars

ABSTRACT

We introduce an algorithm for designing a predictive left to right shift-reduce non-determinisic push-down machine corresponding to an arbitrary unrestricted context-free grammar and an algorithm for efficiently driving this machine in pseudo-parallel. The performance 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 behavior has been compiled out. At run time, the machine is driven in pseudo-parallel with the help of a chart.The recognizer behaves in the worst case in O(|G|²n³)-time and O(|G|n²)-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 variants of the basic parser can be obtained by determinizing portions of the basic non-deterministic push-down machine while still using the same pseudo-parallel driver.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 2: Jay Clark Earley, An efficient context-free parsing algorithm, 1968
• 3: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 4: Susan L. Graham , Michael Harrison and Walter L. Ruzzo, An Improved Context-Free Recognizer, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.3, p.415-462, July 1980 [doi>10.1145/357103.357112]
• 5: Mark Johnson. 1989. The computational complexity of Tomita's algorithm. In Proceedings of the International Workshop on Parsing Technologies, Pittsburgh, August.
• 6: T. Kasami. 1965. An efficient recognition and syntax algorithm for context-free languages. Technical Report AF-CRL-65-758, Air Force Cambridge Research Laboratory, Bedford, MA.
• 7: James R. Kipps. 1989. Analysis of Tomita's algorithm for general context-free parsing. In Proceedings of the International Workshop on Parsing Technologies, Pittsburgh, August.
• 8: D. E. Knuth. 1965. On the translation of languages from left to right. Information and Control, 8:607--639.
• 9: Bernard Lang, Deterministic Techniques for Efficient Non-Deterministic Parsers, Proceedings of the 2nd Colloquium on Automata, Languages and Programming, p.255-269, July 29-August 02, 1974
• 10: Hans Leiss, On Kilbury's modification of Earley's algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.4, p.610-640, Oct. 1990 [doi>10.1145/88616.88637]
• 11: Yves Schabes. 1991. Polynomial time and space shift-reduce parsing of context-free grammars and of tree-adjoining grammars. In preparation.
• 12: Stuart M. Shieber, Using restriction to extend parsing algorithms for complex-feature-based formalisms, Proceedings of the 23rd annual meeting on Association for Computational Linguistics, p.145-152, July 08-12, 1985, Chicago, Illinois [doi>10.3115/981210.981228]
• 13: Masaru Tomita, Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems, Kluwer Academic Publishers, Norwell, MA, 1985
• 14: Masaru Tomita, An efficient augmented-context-free parsing algorithm, Computational Linguistics, v.13 n.1-2, p.31-46, January-June 1987
• 15: D. H. Younger. 1967. Recognition and parsing of context-free languages in time n3. Information and Control, 10(2):189--208.