Home → Magazine Archive → February 1970 (Vol. 13, No. 2) → An efficient context-free parsing algorithm → Abstract

An efficient context-free parsing algorithm

By Jay Earley

Communications of the ACM, Vol. 13 No. 2, Pages 94-102
10.1145/362007.362035


Save PDF
A parsing algorithm which seems to be the most efficient general context-free algorithm known is described. It is similar to both Knuth's LR(k) algorithm and the familiar top-down algorithm. It has a time bound proportional to n3 (where n is the length of the string being parsed) in general; it has an n2 bound for unambiguous grammars; and it runs in linear time on a large class of grammars, which seems to include most practical context-free programming language grammars. In an empirical comparison it appears to be superior to the top-down and bottom-up algorithms studied by Griffiths and Petrick.

The full text of this article is premium content

0 Comments

No entries found