An LALR parser is a type of parser defined in computer science as a Look-Ahead LR parser.
LALR parsers are based on a finite-state-automata concept, from which they derive their speed. The data structure used by an LALR parser is a pushdown automaton (PDA). A deterministic PDA is a deterministic-finite automaton (DFA) that uses a stack for a memory, indicating which states the parser has passed through to arrive at the current state. Because of the stack, a PDA can recognize grammars that would be impossible with a DFA; for example, a PDA can determine whether an expression has any unmatched parentheses, whereas an automaton with no stack would require an infinite number of states due to unlimited nesting of parentheses.
LALR parsers are driven by a parser table in a finite-state machine (FSM) format. An FSM is very difficult for humans to construct and therefore an LALR parser generator is used to create the parser table automatically from a grammar in Backus–Naur Form which defines the syntax of the computer language the parser will process. The parser table is often generated in source code format in a computer language (such as C++ or Java). When the parser (with parser table) is compiled and/or executed, it will recognize text files written in the language defined by the BNF grammar.
LALR parsers are generated from LALR grammars, which are capable of defining a larger class of languages than SLR grammars, but not as large a class as LR grammars. Real computer languages can often be expressed as LALR(1) grammars, and in cases where a LALR(1) grammar is insufficient, usually an LALR(2) grammar is adequate. If the parser generator handles only LALR(1) grammars, then the LALR parser will have to interface with some hand-written code when it encounters the special LALR(2) situation in the input language.
LR parsing was invented by Donald Knuth in 1965 in a paper, "On the Translation of Languages from Left to Right". LR parsers have the potential of providing the fastest parsing speed of all parsing algorithms. However, LR parsers are considered impractical because of their huge size.
LALR parsing was invented by Frank DeRemer in 1969 in a paper, "Practical LR(k) Translators". LALR parsers offer the same high performance of LR parsers, but are much smaller in size. For this reason, it is LALR parsers that are most often generated by compiler-compilers such as yacc and GNU bison.
Generating LALR Parsers
Full article ▸