This is an implementation of an earley parser written in Rust.

The parser first reads the grammar specification from a string. Take, for example:

EXP
EXP -> EXP + EXP
EXP -> EXP * EXP
EXP -> EXP - EXP
EXP -> EXP / EXP
EXP -> ( EXP ) 
EXP -> n

Then it will parse any given input and will return a list of parse trees.

For example, given n+n*n the parser will output the following trees:

Our method of constructing the parse trees is simple but slow. We effectively embed all the derivation trees in the construction of the Earley sets.

The paper SPPF-Style Parsing From Earley Recognisers describes this method as a fix to the original method of constructing the parse trees (which is incorrect).

It is shown that this method does not result in a cubic parser, so I would advise you to search for a better solution if speed is what you want.

• As mentioned above, this parser is slow
• It does not support cyclic grammars (which are bogus anyway). It will forever loop in the scan/predict/complete cycle because there is an infinite set of parse trees.

You will need cargo to build this project. Also, you need to install dot, the graph visualization tool.

After you install these dependencies, you can build the project:

cargo build

Then run the program:

cargo run