In computer science, an LALR parser[a] (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 rules specified by a formal grammar for a computer language.
[2] The original dissertation gave no algorithm for constructing such a parser given a formal grammar.
[4] In 1982, DeRemer and Tom Pennello published an algorithm that generated highly memory-efficient LALR parsers.
In 1965, Donald Knuth invented the LR parser (Left to Right, Rightmost derivation).
The LR parser can recognize any deterministic context-free language in linear-bounded time.
In 1979, Frank DeRemer and Tom Pennello announced a series of optimizations for the LALR parser that would further improve its memory efficiency.
The simplification that the LALR parser introduces consists in merging rules that have identical kernel item sets, because during the LR(0) state-construction process the lookaheads are not known.