LR(1) Grammars
1. Idea
LR(1) = canonical LR with 1 lookahead carried inside each item: [A → α • β, a] means reduce only if next token is a. Splits LR(0) states by context → most powerful deterministic parser, resolves SLR failures.
2. Closure with Lookaheads
closure adds [B → • γ, b] for every b in FIRST(β a) when [A → α • B β, a] present
goto(I,X) = closure({[A → α X • β, a] | [A → α • X β, a] in I})
Lookahead propagates precisely, not whole FOLLOW.
3. Example — assignment grammar (not SLR, but LR(1))
S → L = R | R | L → * R | id | R → L
LR(1) state: {[R → L •, $/=], [L → L • = R, $/=]}? lookaheads split:
on `=` only second item matters; on $ only first → no conflict
SLR merged them via FOLLOW(L)={$,=} → conflict; LR(1) keeps contexts separate
Tables are large (states × lookaheads) but handle all deterministic CFLs.
4. Table Size vs Power
- States: LR(1) >> LALR = SLR = LR(0) in count.
- Power: SLR ⊂ LALR ⊂ LR(1). Compilers use LALR (Yacc) to get near-LR(1) power with SLR-size tables.
5. Exam Points
- Define LR(1) item with lookahead + closure rule — 5 marks, very frequent.
- Build canonical LR(1) sets for small grammar — 7-10 marks, frequent (lengthy).
- Show grammar SLR-fails but LR(1)-passes — 5 marks, frequent.