Earley parser

related topics
{math, number, function}
{rate, high, increase}
{system, computer, user}
{mi², represent, 1st}

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 context-free languages. The Earley parser executes in cubic time (O(n3), where n is the length of the parsed string) in the general case, quadratic time (O(n2)) for unambiguous grammars, and linear time for almost all LR(k) grammars. It performs particularly well when the rules are written left-recursively.

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 top-down 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 look-ahead 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 top-level 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 left-hand side (Y → γ).

Full article ▸

related documents
Linear function
Elias gamma coding
Regular graph
Inner automorphism
Connectedness
Subring
Parse tree
Row and column spaces
Unitary matrix
Profinite group
Unit interval
Identity matrix
Specification language
Random sequence
Additive function
Euler's identity
Inequation
Kleene star
Sharp-P
Disjunctive normal form
Class (set theory)
Inverse functions and differentiation
Inverse transform sampling
Just another Perl hacker
Discrete probability distribution
Endomorphism
Urysohn's lemma
Sum rule in differentiation
Klein four-group
Column vector