{
  "id": "enwiki-001371759853",
  "slug": "earley-parser",
  "title": "Earley parser",
  "qid": "",
  "lead": "In computer science, the Earley parser is an algorithm for parsing strings that belong to a given context-free language. Named after its inventor Jay Earley, it was first introduced in his dissertation in 1968 (and later appeared in abbreviated, more legible form in a journal). It is a chart parser that uses dynamic programming. Earley parsers are appealing because they can parse all context-free languages, unlike LR parsers and LL parsers, which are more typically used in compilers but which can only handle restricted classes of languages. However, the original Earley algorithm contained a bug, and its run time and memory use were high for the computers available at the time it was published. Earley parsing has since become a viable solution, as corrections and optimizations of the algorithm have been found and computers have become far more powerful. Earley parsers perform particularly well when the rules are written left-recursively. Some grammars can be automatically rewritten so that the Earley algorithm parses the language they describe more efficiently. The worst-case costs of the original Earley algorithm are: O(n) linear time and space for non-right recursive LR(k) grammars, O(n^2) quadratic time and space for unambiguous grammars, O(n^3) cubic time and O(n^2) quadratic space for all other context-free grammars, where n is the length of the parsed string.",
  "body": "In computer science, the Earley parser is an algorithm for parsing strings that belong to a given context-free language. Named after its inventor Jay Earley, it was first introduced in his dissertation in 1968 (and later appeared in abbreviated, more legible form in a journal). It is a chart parser that uses dynamic programming. Earley parsers are appealing because they can parse all context-free languages, unlike LR parsers and LL parsers, which are more typically used in compilers but which can only handle restricted classes of languages. However, the original Earley algorithm contained a bug, and its run time and memory use were high for the computers available at the time it was published. Earley parsing has since become a viable solution, as corrections and optimizations of the algorithm have been found and computers have become far more powerful. Earley parsers perform particularly well when the rules are written left-recursively. Some grammars can be automatically rewritten so that the Earley algorithm parses the language they describe more efficiently. The worst-case costs of the original Earley algorithm are: O(n) linear time and space for non-right recursive LR(k) grammars, O(n^2) quadratic time and space for unambiguous grammars, O(n^3) cubic time and O(n^2) quadratic space for all other context-free grammars, where n is the length of the parsed string. DECLARE ARRAY S; function INIT(words) S ← CREATE_ARRAY(LENGTH(words) + 1) for k ← from 0 to LENGTH(words) do S[k] ← EMPTY_ORDERED_SET function EARLEY_PARSE(words, grammar) INIT(words) ADD_TO_SET((γ → •S, 0), S[0]) for k ← from 0 to LENGTH(words) do for each state in S[k] do // S[k] can expand during this loop if not FINISHED(state) then if NEXT_ELEMENT_OF(state) is a nonterminal then PREDICTOR(state, k, grammar) // non_terminal else do SCANNER(state, k, words) // terminal else do COMPLETER(state, k) end end return chart procedure PREDICTOR((A → α•Bβ, j), k, grammar) for each (B → γ) in GRAMMAR_RULES_FOR(B, grammar) do ADD_TO_SET((B → •γ, k), S[k]) end procedure SCANNER((A → α•aβ, j), k, words) if k ::= # the start rule ::= \"+\" | ::= \"*\" | ::= \"1\" | \"2\" | \"3\" | \"4\" With the input: 2 + 3 * 4 This is the sequence of state sets: The state (P → S •, 0) represents a completed parse. This state also appears in S(3) and S(1), which are complete sentences.",
  "categories": [
    "23118434",
    "23603337",
    "26709286",
    "27954162",
    "7692542"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1371759853",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1787896498.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001371759853",
    "type": "webpage",
    "title": "Earley parser",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/earley-parser",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001371759853",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1371759853",
    "note": "Immutable snapshot enwiki-001371759853"
  }
}