Practical Earley Parsing

Abstract

Earley's parsing algorithm is a general algorithm, able to handle any context-free grammar. As with most parsing algorithms, however, the presence of grammar rules having empty right-hand sides complicates matters. By analyzing why Earley's algorithm struggles with these grammar rules, we have devised a simple solution to the problem. Our empty-rule solution leads to a new type of finite automaton expressly suited for use in Earley parsers, and to a new statement of Earley's algorithm. We show that this new form of Earley parser is much more time-efficient in practice than the original.