{
  "id": "enwiki-001363023383",
  "slug": "lalr-parser",
  "title": "LALR parser",
  "qid": "",
  "lead": "An LALR parser (look-ahead, left-to-right, rightmost derivation parser) is a type of parser for computer languages. It is a simplified version of a canonical LR parser. The LALR parser was invented by Frank DeRemer in his 1969 PhD dissertation, Practical Translators for LR(k) languages, in his treatment of the practical difficulties at that time of implementing LR(1) parsers. He showed that the LALR parser has more language recognition power than the LR(0) parser, while requiring the same number of states as the LR(0) parser for a language that can be recognized by both parsers. This makes the LALR parser a memory-efficient alternative to the LR(1) parser for languages that are LALR. It was also proven that there exist LR(1) languages that are not LALR. Despite this weakness, the power of the LALR parser is sufficient for many mainstream computer languages, including Java, though the reference grammars for many languages fail to be LALR due to being ambiguous. The original dissertation gave no algorithm for constructing such a parser given a formal grammar. The first algorithms for LALR parser generation were published in 1973. In 1982, DeRemer and Tom Pennello published an algorithm that generated highly memory-efficient LALR parsers. LALR parsers can be automatically generated from a grammar by an LALR parser generator such as Yacc or GNU Bison.…",
  "body": "An LALR parser (look-ahead, left-to-right, rightmost derivation parser) is a type of parser for computer languages. It is a simplified version of a canonical LR parser. The LALR parser was invented by Frank DeRemer in his 1969 PhD dissertation, Practical Translators for LR(k) languages, in his treatment of the practical difficulties at that time of implementing LR(1) parsers. He showed that the LALR parser has more language recognition power than the LR(0) parser, while requiring the same number of states as the LR(0) parser for a language that can be recognized by both parsers. This makes the LALR parser a memory-efficient alternative to the LR(1) parser for languages that are LALR. It was also proven that there exist LR(1) languages that are not LALR. Despite this weakness, the power of the LALR parser is sufficient for many mainstream computer languages, including Java, though the reference grammars for many languages fail to be LALR due to being ambiguous. The original dissertation gave no algorithm for constructing such a parser given a formal grammar. The first algorithms for LALR parser generation were published in 1973. In 1982, DeRemer and Tom Pennello published an algorithm that generated highly memory-efficient LALR parsers. LALR parsers can be automatically generated from a grammar by an LALR parser generator such as Yacc or GNU Bison. The automatically generated code may be augmented by hand-written code to augment the power of the resulting parser. Generally, the LALR parser refers to the LALR(1) parser, just as the LR parser generally refers to the LR(1) parser. The \"(1)\" denotes one-token lookahead, to resolve differences between rule patterns during parsing. Similarly, there is an LALR(2) parser with two-token lookahead, and LALR(k) parsers with k-token lookup, but these are rare in actual use. The LALR parser is based on the LR(0) parser, so it can also be denoted LALR(1)&nbsp;=&nbsp;LA(1)LR(0) (1 token of lookahead, LR(0)) or more generally LALR(k)&nbsp;=&nbsp;LA(k)LR(0) (k tokens of lookahead, LR(0)). There is in fact a two-parameter family of LA(k)LR(j) parsers for all combinations of j and k, which can be derived from the LR(j&nbsp;+&nbsp;k) parser, but these do not see practical use. As with other types of LR parsers, an LALR parser is quite efficient at finding the single correct bottom-up parse in a single left-to-right scan over the input stream, because it does not need to use backtracking. Being a lookahead parser by definition, it always uses a lookahead, with being the most-common case.",
  "categories": [
    "22906663",
    "23118434",
    "23603337",
    "24623845",
    "27954162"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1363023383",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1783434446.0,
  "claims": [
    {
      "id": 29390000,
      "subject_qid": "",
      "subject_slug": "lalr-parser",
      "predicate": "publication date",
      "object_text": "1973",
      "object_num": 19730000.0,
      "object_unit": null,
      "polarity": 1,
      "qualifier": "",
      "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1363023383",
      "source_name": "Wikipedia",
      "source_tier": 3,
      "retrieved_at": 1792482424.750751,
      "confidence": 0.95,
      "article_slug": "lalr-parser",
      "span_start": 53,
      "span_end": 71
    }
  ],
  "contradictions": [],
  "confidence": 0.95,
  "csl": {
    "id": "enwiki-001363023383",
    "type": "webpage",
    "title": "LALR 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/lalr-parser",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          21
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001363023383",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1363023383",
    "note": "Immutable snapshot enwiki-001363023383"
  }
}