Earley parser

An Earley (from a person's name) parser is a parser that is capable of parsing a language defined by an arbitrary context-free grammar in at most cubic time. For a large class of more common grammars (unambiguous) its complexity is even better (quadratic) and for most practically useful grammars, it is linear.

What exists now

We have some documentation that contains both a description of the protocols and of the implementation.

We also have some preliminary code. which is currently only capable of recognizing whether the input is in the language defined by the grammar. We are working on a version that will also return the parse tree (defined by grammar actions).