Overview
As with other types of LR parser, 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 doesn't need to use backtracking. Being a lookahead parser by definition, it always uses a lookahead, with LALR(1) being the most common case.
The LALR(1) parser uses production rules of the form
A → B, C, a
as is the case with any parser based on the LR(1) parser. The simplification that the LALR parser introduces consists in merging rules that differ only in the lookahead. This reduces the power of the parser because, as the following example depicts, dropping the lookahead info can confuse the parser as to which grammar rule to pick next, resulting in a reduce/reduce conflict.
- State sequence : A, B, C
- Current lookahead: a
- Rules (LALR merge rules in brackets):
-
- (A10)A1 → B, C, a
- (A10)A2 → B, C, b
- A3 → A, A1(A10)
- A4 → A, A2(A10)
In a LR(1) parser the state sequence is correctly resolved to A3, because the lookahead information has been preserved through the detailed rule system. In a LALR parser the state sequence cannot be resolved because the parser encounters a duplicate rule, which is an error. The above grammar will be declared ambiguous by a LALR parser generator.
Read more about this topic: LALR Parser