Earley parser: Encyclopedia II - Earley parser - Performing the Algorithm

Earley parser - Performing the Algorithm

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 of this production began: the origin state.

The state set at input position k is called S(k). The parser is seeded with S(0) being the top-level rule. The parser then iteratively operates in three stages: prediction, scanning, and completion. In the following descriptions, α, β, and γ represent any sequence of terminals/nonterminals (including the null sequence), X, Y, and Z represent single nonterminals, and a represents a terminal symbol.

• Prediction: For every state in S(k) of the form (X → α • Y β, j) (where j is the origin state as above), add (Y → • γ, k) to S(k) for every production with Y on the left-hand side.

• Scanning: If a is the next symbol in the input stream, for every state in S(k) of the form (X → α • a β, j), add (X → α a • β, j) to S(k+1).

• Completion: For every state in S(k) of the form (X → γ •, j), find states in S(j) of the form (Y → α • X β, i) and add (Y → α X • β, i) to S(k).

These steps are repeated until no more states can be added to the set. This is generally realized by making a queue of states to process, and performing the corresponding operation depending on what kind of state it is. For the implementor, it is important to note that this is a set of states, and that you not add two identical states to the same set.

Adapted from the Wikipedia article "Performing the Algorithm", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki