The Earley parser is a type of chart parser mainly used for parsing in computational linguistics, named after its inventor, Jay Earley. The algorithm uses dynamic programming.
Earley parsers are appealing because they can parse all contextfree languages. The Earley parser executes in cubic time (O(n^{3}), where n is the length of the parsed string) in the general case, quadratic time (O(n^{2})) for unambiguous grammars, and linear time for almost all LR(k) grammars. It performs particularly well when the rules are written leftrecursively.
Contents
The algorithm
In the following descriptions, α, β, and γ represent any string of terminals/nonterminals (including the empty string), X and Y represent single nonterminals, and a represents a terminal symbol.
Earley's algorithm is a topdown dynamic programming algorithm. In the following, we use Earley's dot notation: given a production X → αβ, the notation X → α • β represents a condition in which α has already been parsed and β is expected.
For every input position (which represents a position between tokens), the parser generates an ordered state set. Each state is a tuple (X → α • β, i), consisting of
 the production currently being matched (X → α β)
 our current position in that production (represented by the dot)
 the position i in the input at which the matching of this production began: the origin position
(Earley's original algorithm included a lookahead in the state; later research showed this to have little practical effect on the parsing efficiency, and it has subsequently been dropped from most implementations.)
The state set at input position k is called S(k). The parser is seeded with S(0) consisting of only the toplevel rule. The parser then iteratively operates in three stages: prediction, scanning, and completion.
 Prediction: For every state in S(k) of the form (X → α • Y β, j) (where j is the origin position as above), add (Y → • γ, k) to S(k) for every production in the grammar with Y on the lefthand side (Y → γ).
Full article ▸
