Editing LALR parser (section)

{{Short description|Type of parser in computer science}}
{{Use dmy dates|date=October 2020}}
In [[computer science]], an '''LALR parser'''{{efn|"LALR" is pronounced as the [[initialism]] "el-ay-el-arr"}} ('''look-ahead, left-to-right, rightmost derivation parser''') is part of the compiling process where human readable text is converted into a structured representation to be read by computers. An LALR parser is a software tool to process ([[parse]]) text into a very specific internal representation that other programs, such as compilers, can work with. This process happens according to a set of [[production (computer science)|production rules]] specified by a [[formal grammar]] for a [[computer language]]. 

An LALR parser 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'',{{sfn|DeRemer|1969}} 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,<ref name=chapman>''LR Parsing: Theory and Practice,'' Nigel P. Chapman, [https://books.google.com/books?id=nEA9AAAAIAAJ&pg=PA87 p. 86–87]</ref> including [[Java technology|Java]],<ref>{{cite web|title=Generate the Parser
|url=http://www.eclipse.org/jdt/core/howto/generate%20parser/generateParser.html|publisher=Eclipse JDT Project|access-date=29 June 2012}}</ref> though the reference grammars for many languages fail to be LALR due to being [[ambiguous grammar|ambiguous]].<ref name=chapman />

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.<ref>{{cite journal| first1=T.| last1=Anderson| first2=J.| last2=Eve| first3=J.| last3=Horning| title=Efficient LR(1) parsers| journal=Acta Informatica| issue=2| year=1973| pages= 2–39}}</ref> In 1982, DeRemer and Tom Pennello published an algorithm that generated highly memory-efficient LALR parsers.<ref name="DeRemer82">{{cite journal |first1=Frank |last1=DeRemer |first2=Thomas |last2=Pennello |date=October 1982 |title=Efficient Computation of LALR(1) Look-Ahead Sets |url=http://3e8.org/pub/scheme/doc/parsing/Efficient%20Computation%20of%20LALR%281%29%20Look-Ahead%20Sets.pdf |journal=ACM Transactions on Programming Languages and Systems |volume=4 |issue=4 |pages=615–649|doi=10.1145/69622.357187}}</ref> 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.