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.
ARTICLES RELATED TO 'early' An Earley parser C -library.
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 ...
