Earley parser


Earley parser

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.

The algorithm

In the following descriptions, α, β, and γ represent any string of terminals/nonterminals (including the empty string), X, Y, and Z 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 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. The set is generally implemented as a queue of states to process (though a given state must appear in one place only), and performing the corresponding operation depending on what kind of state it is.

Example

Consider the following simple grammar for arithmetic expressions:

P → S # the start rule S → S + M
M M → M * T
T T → number

With the input:

2 + 3 * 4

This is the sequence of state sets:

(state no.) Production (Origin) # Comment --------------------------------- = S(0): • 2 + 3 * 4 =

(1) P → • S (0) # start rule (2) S → • S + M (0) # predict from (1) (3) S → • M (0) # predict from (1) (4) M → • M * T (0) # predict from (3) (5) M → • T (0) # predict from (3) (6) T → • number (0) # predict from (5) = S(1): 2 • + 3 * 4 =

(1) T → number • (0) # scan from S(0)(6) (2) M → T • (0) # complete from S(0)(5) (3) M → M • * T (0) # complete from S(0)(4) (4) S → M • (0) # complete from S(0)(3) (5) S → S • + M (0) # complete from S(0)(2) (6) P → S • (0) # complete from S(0)(1) = S(2): 2 + • 3 * 4 =

(1) S → S + • M (0) # scan from S(1)(5) (2) M → • M * T (2) # predict from (1) (3) M → • T (2) # predict from (1) (4) T → • number (2) # predict from (3) = S(3): 2 + 3 • * 4 =

(1) T → number • (2) # scan from S(2)(4) (2) M → T • (2) # complete from S(2)(3) (3) M → M • * T (2) # complete from S(2)(2) (4) S → S + M • (0) # complete from S(2)(1) (5) S → S • + M (0) # complete from S(0)(2) (6) P → S • (0) # complete from S(0)(1) = S(4): 2 + 3 * • 4 =

(1) M → M * • T (2) # scan from S(3)(3) (2) T → • number (4) # predict from (1) = S(5): 2 + 3 * 4 • =

(1) T → number • (4) # scan from S(4)(2) (2) M → M * T • (2) # complete from S(4)(1) (3) M → M • * T (2) # complete from S(2)(2) (4) S → S + M • (0) # complete from S(2)(1) (5) S → S • + M (0) # complete from S(0)(2) (6) P → S • (0) # complete from S(0)(1)

The state (P → S •, 0) represents a completed parse. This state also appears in S(3) and S(1), which are complete sentences.

See also

* CYK algorithm
* Context-free grammar
* Parsing Algorithms

References

*J. Earley, [http://portal.acm.org/citation.cfm?doid=362007.362035 "An efficient context-free parsing algorithm"] , "Communications of the Association for Computing Machinery", 13:2:94-102, 1970.

*J. Aycock and R.N. Horspool. [http://www.cs.uvic.ca/~nigelh/Publications/PracticalEarleyParsing.pdf Practical Earley Parsing] . "The Computer Journal", 45:6:620-630, 2002.

External links

* [http://search.cpan.org/~lpalmer/Parse-Earley-0.15/Earley.pm Parse::Earley] An Earley parser Perl module.
* [http://cocom.sourceforge.net/ammunition-13.html 'early'] An Earley parser C -library.
* [http://pages.cpsc.ucalgary.ca/~aycock/spark/ Spark] an Object Oriented "little language framework" for Python that implements an Earley parser.
* [http://nltk.sourceforge.net/ NLTK] a Python toolkit that has an Earley parser.
* [http://www.ling.ohio-state.edu/~scott/#projects-pep Pep] A Java library that implements the Earley algorithm and provides charts and parse trees as parsing artifacts.
* [http://linguateca.dei.uc.pt/index.php?sep=recursos PEN] A Java library that implements the Earley.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Earley-Algorithmus — Der Earley Algorithmus oder Earley Parser ist in der Informatik ein Algorithmus, der entscheidet, ob ein Wort von einer kontextfreien Grammatik erzeugt werden kann. Er wurde 1970 von Jay Earley entwickelt. Er ähnelt dem Cocke Younger Kasami… …   Deutsch Wikipedia

  • Earley — For the parsing algorithm, see Earley parser. Coordinates: 51°25′59″N 0°55′59″W / 51.433°N 0.933°W / 51.433; 0.933 …   Wikipedia

  • Parser — Analyse syntaxique Pour les articles homonymes, voir Analyseur. L analyse syntaxique consiste à mettre en évidence la structure d un texte, généralement un programme informatique ou du texte écrit dans une langue naturelle. Un analyseur… …   Wikipédia en Français

  • Chart-Parser — Ein Chart Parser, auch Chartparser geschrieben, ist ein Parser für kontextfreie Grammatiken, der sich Teilanalysen (Teilkonstituenten) in einer Tabelle (Chart) merkt. Diese Zwischenspeicherung und Wiederverwendung von Teilanalysen verbessert die… …   Deutsch Wikipedia

  • Chart parser — A chart parser is a type of parser suitable for ambiguous grammars (including grammars of natural languages). It uses the dynamic programming approach partial hypothesized results are stored in a structure called a chart and can be re used. This… …   Wikipedia

  • Jay Earley — invented the Earley parser in his early career in computer science. Later he became a transformational psychologist.External links* [http://www.earley.org Jay Earley s website] ** [http://www.earley.org/bio.htm Biography of Jay Earley] …   Wikipedia

  • GLR parser — In computer science, a GLR parser ( Generalized Left to right Rightmost derivation parser ) is an extension of an LR parser algorithm to handle nondeterministic and ambiguous grammars. First described in a 1986 paper by Masaru Tomita, it has also …   Wikipedia

  • Comparison of parser generators — This is a list of notable lexer generators and parser generators for various language classes. Contents 1 Regular languages 2 Deterministic context free languages 3 Parsing expression grammars, deterministic boolean grammars …   Wikipedia

  • Chart Parsing — Ein Chartparser ist ein Parser für kontextfreie Grammatiken, der sich Teilanalysen (Teilkonstituenten) in einer Tabelle (Chart) merkt. Diese Zwischenspeicherung und Wiederverwendung von Teilanalysen verbessert die Effizienz erheblich und macht… …   Deutsch Wikipedia

  • Context-free grammar — In formal language theory, a context free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty). The… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.