Earley parser, Earley parser - Example, Earley parser - Performing the Algorithm, CYK algorithm, Context-free grammar, Parsing Algorithms, Parse::Earley An Earley parser Perl module., 'early' An Earley parser C -library., Spark an Object Oriented "little language framework" for Python that implements an earley parser.
The algorithm is hard to see from the abstract description above. It becomes much clearer how it operates once you see it in action. The output is a little verbose, but you should be able to follow it.
Let's say you have the following simple arithmetic grammar:
P → S # the start rule
S → S + M
| M
M → M * T
| T
T → number
And you have the input:
2 + 3 * 4
...
To understand how Earley's algorithm executes, you have to understand dot notation. Given a production A → BCD (where B, C, and D are symbols in the grammar, terminals or nonterminals), the notation A → B • C D represents a condition in which B has already been parsed and the sequence C D is expected.
For every input position (which represents a position between tokens), the parser generates a state set. Each state is the cartesian product (that is, just the combination) of:
A dot condition for a particular production.
The position at which the matching ...
