LALR(1) Grammars
1. Idea
LALR(1) = Look-Ahead LR: build canonical LR(1) sets, then merge states with same core (LR(0) part), unioning lookaheads. Gets near-LR(1) power with LR(0)-size tables — what Yacc/Bison actually builds.
2. Construction
1. build LR(1) collection with lookaheads
2. group states with identical cores: {[A→α•β,_]} same ignoring lookahead
3. merged state lookahead = union of group
4. if merged table has conflicts → grammar not LALR (rare)
Example: expression grammar LR(1) has 14 states → LALR merges 2 pairs → 12 states, same as SLR count but with precise lookaheads.
3. LALR vs SLR vs LR(1)
| Table size | Power | Use | |
|---|---|---|---|
| SLR | small | weakest LR | teaching |
| LALR | small (=SLR) | almost LR(1) | Yacc, real compilers |
| LR(1) | large | strongest | reference |
Merging can introduce reduce-reduce conflicts absent in LR(1), but almost never for programming languages.
4. Why It Matters
C, Java, Pascal grammars are LALR(1) — deterministic, small tables, good errors. That is why Yacc defaults to LALR.
5. Exam Points
- Define LALR merging + core concept — 5 marks, very frequent.
- Compare SLR vs LALR vs LR(1) (size/power) — 5 marks, very frequent.
- Merge two LR(1) states example — 5 marks, frequent.