Paper: Polynomial Time And Space Shift-Reduce Parsing Of Arbitrary Context-Free Grammars

ACL ID P91-1014
Title Polynomial Time And Space Shift-Reduce Parsing Of Arbitrary Context-Free Grammars
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1991
Authors
  • Yves Schabes (University of Pennsylvania, Philadelphia PA)

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 ...