On Kilbury's Modification of Earley's Algorithm

Abstract

We improve on J. Kilbury's proposal to interchange “predictor” and “scanner” in Earley's parser. This modification of Earley's parser can trivially be combined with those suggested by S. Graham, M. Harrison, and W. Ruzzo, leading to smaller parse tables and almost the power of lookahead 1. Along these lines we can also obtain Earley-parsers having partial lookahead r ≥ 1, without storing right contexts. Parse trees with shared structure can be stored in the parse tables directly, rather than constructing the trees from “dotted rules."