CLR(1) and LALR(1) Parsing: short notes (Compiler Design)

Introduction

SLR places a reduction $A \to \alpha$ on every token in FOLLOW( $A$ ). FOLLOW is a global set: it collects every token that can follow $A$ anywhere in the grammar, even when, in the particular state the parser is in, only a few of those tokens can actually come next. The false conflicts that result (the L = R grammar is the standard example) disappear if each item carries the exact tokens that may follow it in that context.

That is the idea of canonical LR(1) parsing (CLR, or simply LR(1)): items with a lookahead terminal. CLR is the most powerful of the one-token LR methods but can have many more states. LALR(1) (lookahead LR) merges CLR states that have the same items apart from the lookaheads. It has exactly as many states as SLR and LR(0), is almost as powerful as CLR, and is the method used by Yacc and Bison. This note builds both, compares all four LR methods, and explains what merging can and cannot break.

Prerequisites

LR(0) and SLR(1) Parsing: items, CLOSURE, GOTO, the LR driver and the conflict tests.
FIRST sets of strings (see the note FIRST and FOLLOW Sets), used to compute lookaheads.

Core concepts

Term	Definition
LR(1) item	$[A \to \alpha \cdot \beta,\; a]$ : an LR(0) item (the core) plus a lookahead terminal $a$ (or $\text{\textdollar}$ )
Meaning of the lookahead	Reduce by $A \to \alpha$ in a state containing $[A \to \alpha \cdot,\; a]$ only when the next token is $a$
Canonical LR(1) collection	All LR(1) item sets reachable from CLOSURE( $\{[S' \to \cdot S, \text{\textdollar}]\}$ )
Core of a state	The set of LR(0) items obtained by dropping all lookaheads
LALR(1) states	The CLR states with identical cores merged into one, lookaheads united

Lookahead restricts reduce actions only in completed items. In a noncomplete item it also propagates during closure through $\operatorname{FIRST}(\beta a)$ ; it is not merely carried unchanged until completion.

Algorithms

CLOSURE and GOTO with lookaheads

Text

CLOSURE1(I)
    repeat
        for each item [A -> alpha . B beta, a] in I, B a nonterminal
            for each production B -> gamma
                for each terminal b in FIRST(beta a)
                    add [B -> . gamma, b] to I
    until no item is added
    return I

GOTO1(I, X)
    return CLOSURE1({ [A -> alpha X . beta, a] : [A -> alpha . X beta, a] in I })

The lookahead of a new item is FIRST of what follows $B$ in the item, followed by the item's own lookahead. If $\beta$ is nullable, the lookahead $a$ itself is inherited; otherwise only FIRST( $\beta$ ) is used.

The collection is built from CLOSURE1( $\{[S' \to \cdot S, \text{\textdollar}]\}$ ) with GOTO1, exactly as in the LR(0) case. Table filling: shift entries as in SLR; for $[A \to \alpha \cdot, a]$ with $A \ne S'$ , ACTION[ $i, a$ ] $=$ reduce $A \to \alpha$ , and only on $a$ ; accept on $[S' \to S \cdot, \text{\textdollar}]$ .

LALR by merging

Text

LALR-FROM-CLR(C)
    group the CLR states by core
    for each group, form one state: the union of its LR(1) items
    GOTO of a merged state on X = the merged state containing GOTO of any member
    build the table as for CLR; conflicts in the merged table mean "not LALR(1)"

GOTO is well defined after merging, because states with the same core have successors with the same core. Building every CLR state first can be expensive; practical generators compute LALR lookaheads directly on the LR(0) automaton by propagating them, with the same result.

Worked examples

The grammar $S \to C C$ , $C \to c C \mid d$

The canonical LR(1) collection has 10 states:

State	Items	Transitions
$I_0$	$[S' \to \cdot S, \text{\textdollar}]$ , $[S \to \cdot C C, \text{\textdollar}]$ , $[C \to \cdot c C, c/d]$ , $[C \to \cdot d, c/d]$	$S$ : 1, $C$ : 2, $c$ : 3, $d$ : 4
$I_1$	$[S' \to S \cdot, \text{\textdollar}]$	none
$I_2$	$[S \to C \cdot C, \text{\textdollar}]$ , $[C \to \cdot c C, \text{\textdollar}]$ , $[C \to \cdot d, \text{\textdollar}]$	$C$ : 5, $c$ : 6, $d$ : 7
$I_3$	$[C \to c \cdot C, c/d]$ , $[C \to \cdot c C, c/d]$ , $[C \to \cdot d, c/d]$	$C$ : 8, $c$ : 3, $d$ : 4
$I_4$	$[C \to d \cdot, c/d]$	none
$I_5$	$[S \to C C \cdot, \text{\textdollar}]$	none
$I_6$	$[C \to c \cdot C, \text{\textdollar}]$ , $[C \to \cdot c C, \text{\textdollar}]$ , $[C \to \cdot d, \text{\textdollar}]$	$C$ : 9, $c$ : 6, $d$ : 7
$I_7$	$[C \to d \cdot, \text{\textdollar}]$	none
$I_8$	$[C \to c C \cdot, c/d]$	none
$I_9$	$[C \to c C \cdot, \text{\textdollar}]$	none

( $c/d$ abbreviates two items, one with each lookahead.) Why two copies: a $C$ derived for the first $C$ of $S \to C C$ is followed by the second $C$ , which begins with c or d; a $C$ derived for the second one is followed by the end of input. States 3, 4, 8 serve the first $C$ ; states 6, 7, 9 serve the second.

LALR merge. The pairs $\{I_3, I_6\}$ , $\{I_4, I_7\}$ , $\{I_8, I_9\}$ have the same cores. Merging them gives 7 states, the same number as the LR(0) automaton, with lookaheads $c/d/\text{\textdollar}$ in the merged complete items. No conflict arises, so the grammar is LALR(1); it is in fact LR(0).

Parsing c d d with the CLR table: shift 3, shift 4, reduce $C \to d$ , reduce $C \to c C$ , shift 7, reduce $C \to d$ , reduce $S \to C C$ , accept. The LALR parser does the same moves with state 4 in place of 7.

Error detection. On the invalid input c d (a single $C$ ), the CLR parser stops in $I_4$ on $\text{\textdollar}$ : $\text{\textdollar}$ is not a lookahead there, so it reports the error before any reduction. The LALR parser, in the merged state with lookaheads $c/d/\text{\textdollar}$ , first reduces $C \to d$ and $C \to c C$ and only then reports the error. LALR and SLR may perform extra reductions before detecting an error, but never shift an erroneous token.

Classes of grammars LR(0), SLR(1), LALR(1), LR(1) and LL(1) with example grammars — Figure 1. Strict inclusion LR(0) $\subset$ SLR(1) $\subset$ LALR(1) $\subset$ LR(1) of grammar classes, with LL(1) inside LR(1) but cutting across the other three, and one example grammar placed in each region.

Computing lookaheads: $I_0$ of the `L = R` grammar

Start from $[S' \to \cdot S, \text{\textdollar}]$ and close:

$S$ follows the dot with nothing after it, so the lookahead is FIRST( $\text{\textdollar}$ ): add $[S \to \cdot L = R, \text{\textdollar}]$ and $[S \to \cdot R, \text{\textdollar}]$ .
In $[S \to \cdot L = R, \text{\textdollar}]$ , $L$ is followed by = R, so the new $L$ -items get FIRST( $= R\, \text{\textdollar}$ ) $= \{=\}$ : $[L \to \cdot * R, =]$ , $[L \to \cdot \textbf{id}, =]$ .
In $[S \to \cdot R, \text{\textdollar}]$ , nothing follows $R$ : add $[R \to \cdot L, \text{\textdollar}]$ .
In $[R \to \cdot L, \text{\textdollar}]$ , nothing follows $L$ : add $[L \to \cdot * R, \text{\textdollar}]$ , $[L \to \cdot \textbf{id}, \text{\textdollar}]$ .

I_0 = \{[S' \to \cdot S, \text{\textdollar}],\ [S \to \cdot L = R, \text{\textdollar}],\ [S \to \cdot R, \text{\textdollar}],\ [L \to \cdot * R, =/\text{\textdollar}],\ [L \to \cdot \textbf{id}, =/\text{\textdollar}],\ [R \to \cdot L, \text{\textdollar}]\}.

The item $[R \to \cdot L, \text{\textdollar}]$ has lookahead $\text{\textdollar}$ only. After reading $L$ , the state holds $[S \to L \cdot = R, \text{\textdollar}]$ and $[R \to L \cdot, \text{\textdollar}]$ , so $R \to L$ is reduced on $\text{\textdollar}$ only, and = is free for the shift. SLR used FOLLOW( $R$ ) $= \{=, \text{\textdollar}\}$ instead, and conflicted.

Where SLR fails but LALR succeeds

For $S \to L = R \mid R$ , $L \to * R \mid \textbf{id}$ , $R \to L$ , the CLR collection has 14 states and LALR merges them to 10, the LR(0) count. The state that caused the SLR conflict now has items $[S \to L \cdot = R, \text{\textdollar}]$ and $[R \to L \cdot, \text{\textdollar}]$ : reduce only on $\text{\textdollar}$ , shift on =, no conflict. The grammar is LALR(1) and LR(1), but not SLR(1).

Where LALR fails but CLR succeeds

Text

S -> a A d | b B d | a B e | b A e
A -> c
B -> c

The CLR collection has 14 states, including

$\{[A \to c \cdot, d],\; [B \to c \cdot, e]\}$ , reached on a c, and
$\{[B \to c \cdot, d],\; [A \to c \cdot, e]\}$ , reached on b c.

Each is conflict-free, so the grammar is LR(1). They have the same core $\{A \to c \cdot, B \to c \cdot\}$ , so LALR merges them into $\{[A \to c \cdot, d/e],\; [B \to c \cdot, d/e]\}$ : on d and on e it can reduce by either production. LALR has 13 states and two reduce-reduce conflicts, so the grammar is not LALR(1). It is not SLR(1) either, since FOLLOW( $A$ ) $=$ FOLLOW( $B$ ) $= \{d, e\}$ .

Lookaheads separating two $\varepsilon$ -reductions

For S -> A a A b | B b B a, A -> eps, B -> eps, the initial LR(1) state contains $[A \to \cdot, a]$ and $[B \to \cdot, b]$ : the lookahead of each is the terminal that follows the first $A$ or $B$ in its body. The four tables all have 10 states.

Method	Conflicts in state 0
LR(0)	reduce-reduce on `a`, `b` and $\text{\textdollar}$ (complete non-augmented production items reduce on every token; the completed augmented start accepts only on the endmarker)
SLR(1)	reduce-reduce on `a` and `b`, since FOLLOW( $A$ ) $=$ FOLLOW( $B$ ) $= \{a, b\}$
LALR(1), CLR(1)	none: $A \to \varepsilon$ on `a` only, $B \to \varepsilon$ on `b` only

Why merging never creates a shift-reduce conflict

Suppose the merged state has a shift-reduce conflict on $a$ : it contains a complete item $[A \to \alpha \cdot, a]$ and an item $[B \to \beta \cdot a \gamma, b]$ . The complete item came from some CLR state $I$ in the group. All states in the group have the same core, so $I$ also contains $B \to \beta \cdot a \gamma$ (with some lookahead), and $I$ shifts on $a$ . Then $I$ itself already had the conflict, and the grammar was not LR(1). Hence: if a grammar is LR(1), its LALR table can have reduce-reduce conflicts but never shift-reduce conflicts.

Comparison of the LR methods

Property	LR(0)	SLR(1)	LALR(1)	CLR(1)
Items	LR(0)	LR(0)	LR(1), merged by core	LR(1)
Ordinary reduction $A\to\alpha$ , $A\ne S'$ , on	every token	FOLLOW( $A$ )	merged lookaheads	exact lookaheads
Number of states	$n$	$n$	$n$	$\ge n$ , often much more
Grammar class	smallest	larger	larger	largest of the four
Error detection	may reduce first	may reduce first	may reduce first	before any reduction on the bad token

Here $n$ is the number of LR(0) states. The LALR lookahead set of a complete item is always a subset of FOLLOW of its head, which is why every SLR(1) grammar is LALR(1).

Grammar classes and languages

Grammars: LR(0) $\subset$ SLR(1) $\subset$ LALR(1) $\subset$ LR(1), every inclusion strict, with the examples above as witnesses: the expression grammar (SLR, not LR(0)), the L = R grammar (LALR, not SLR), the a A d grammar (LR(1), not LALR).
LL(1) grammars are all LR(1). They are not all LALR(1): for example, S -> ( X | E ] | F ), X -> E ) | F ], E -> A, F -> A, A -> eps is LL(1) and LR(1), but its LALR table has reduce-reduce conflicts. S -> A a A b | B b B a, A -> eps, B -> eps is LL(1) and LALR(1) but not SLR(1).
Ambiguous grammars belong to none of these classes.
Languages: a language has an SLR(1) grammar if and only if it has an LALR(1) grammar, if and only if it has an LR(1) grammar, if and only if it is a deterministic context-free language (see Deterministic PDAs and DCFLs). The displayed ACTION-table convention uses an end marker to detect acceptance; do not transfer a prefix-property characterization from formal zero-lookahead models without end detection to this convention. So the methods differ in which grammars they accept, not in which languages they can describe with some grammar.

Important properties and observations

State counts. For the same grammar: LR(0) $=$ SLR $=$ LALR $\le$ CLR. Examples: 7, 7, 7, 10 for $S \to C C$ ; 10, 10, 10, 14 for the L = R grammar.
The expression grammar $E \to E + T \mid T$ , $T \to T * F \mid F$ , $F \to ( E ) \mid \textbf{id}$ has 12 states for LR(0), SLR and LALR, and 22 for CLR: 10 of the 12 cores occur in two CLR states that differ only in their lookaheads. In each pair, exactly one copy has $\text{\textdollar}$ among its lookaheads; the other is reached only inside parentheses, where ) plays the role of $\text{\textdollar}$ . Its only LR(0) conflicts are the shift-reduce entries of $I_2$ and $I_9$ on *; SLR, LALR and CLR have none.
What merging can do. Merge an LR(1) grammar's states and you may get new reduce-reduce conflicts, never new shift-reduce conflicts, and possibly later error detection.
Lookahead propagation. In CLOSURE1, the lookahead of $[B \to \cdot\gamma, b]$ is FIRST( $\beta a$ ). Taking FOLLOW( $B$ ) instead turns CLR into something close to SLR and loses its power.
Yacc and Bison build LALR(1) tables and resolve remaining conflicts by default rules (shift over reduce; the earlier production for reduce-reduce) or by declared precedence and associativity.

Common misconceptions.

"LALR has fewer states than SLR." It has the same number.
"LALR merging can introduce shift-reduce conflicts." Not for an LR(1) grammar.
"CLR parsers accept more languages than SLR parsers." They accept more grammars; the languages are the same, the deterministic context-free languages.
"Every LL(1) grammar is LALR(1)." No; it is LR(1), but some LL(1) grammars are not LALR(1).

GATE examination perspective

Containment questions. LR(0) $\subset$ SLR $\subset$ LALR $\subset$ CLR for grammars; LL(1) $\subset$ LR(1). Watch for options claiming LL(1) $\subset$ LALR(1) or LL(1) $\subset$ SLR(1): both are false.
State counts. " $n_1$ states for SLR, $n_2$ for LALR, $n_3$ for CLR": the true relation is $n_1 = n_2 \le n_3$ .
Merging conflicts. "If a CLR(1) table has no conflict, the LALR(1) table may have": reduce-reduce conflicts only.
Lookahead computation. Compute FIRST( $\beta a$ ) for the items added by closure; a nullable $\beta$ passes the parent's lookahead down.
One core, several lookaheads. In $I_0$ of the L = R grammar, $L \to \cdot \textbf{id}$ appears with = (through $S \to \cdot L = R$ ) and with $\text{\textdollar}$ (through $R \to \cdot L$ ). Options that list only one lookahead are wrong.
$\varepsilon$ -productions in LR(1) items. $[A \to \cdot, a]$ is a complete item from the start; its lookahead decides where the empty reduction goes.
Which grammar is which. Locate the states with complete items and check lookaheads; for an LALR question, merge same-core states and recheck.

Summary

LR(1) items carry a lookahead; reduce only on that lookahead.
CLOSURE1 adds $[B \to \cdot\gamma, b]$ for every $b \in \text{FIRST}(\beta a)$ .
LALR merges CLR states with equal cores: as many states as LR(0) and SLR.
$S \to C C$ , $C \to c C \mid d$ : CLR 10 states, LALR 7, merged pairs $(3,6), (4,7), (8,9)$ .
Merging can create reduce-reduce conflicts (the a A d grammar) but never shift-reduce conflicts.
LR(0) $\subset$ SLR(1) $\subset$ LALR(1) $\subset$ LR(1) for grammars; all one-token LR methods describe exactly the deterministic context-free languages.
CLR detects errors before reducing; LALR and SLR may reduce first, but never shift a wrong token.
Expression grammar: 12 states for LR(0), SLR and LALR, 22 for CLR.
L = R grammar: $[R \to \cdot L, \text{\textdollar}]$ in $I_0$ has lookahead $\text{\textdollar}$ only, which removes the SLR conflict on =.

LR(0) and SLR(1) Parsing: prerequisite. Items, automaton and table construction.
Deterministic PDAs and DCFLs: related. The language class that the LR methods describe.

CLR(1) and LALR(1) Parsing

Introduction

Prerequisites

Core concepts

Algorithms

CLOSURE and GOTO with lookaheads

LALR by merging

Worked examples

The grammar $S \to C C$ , $C \to c C \mid d$

Computing lookaheads: $I_0$ of the `L = R` grammar

Where SLR fails but LALR succeeds

Where LALR fails but CLR succeeds

Lookaheads separating two $\varepsilon$ -reductions

Why merging never creates a shift-reduce conflict

Comparison of the LR methods

Grammar classes and languages

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Algorithms

CLOSURE and GOTO with lookaheads

LALR by merging

Worked examples

The grammar S→CCS \to C CS→CC, C→cC∣dC \to c C \mid dC→cC∣d

Computing lookaheads: I0I_0I0​ of the L = R grammar

Where SLR fails but LALR succeeds

Where LALR fails but CLR succeeds

Lookaheads separating two ε\varepsilonε-reductions

Why merging never creates a shift-reduce conflict

Comparison of the LR methods

Grammar classes and languages

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps

The grammar $S \to C C$ , $C \to c C \mid d$

Computing lookaheads: $I_0$ of the `L = R` grammar

Lookaheads separating two $\varepsilon$ -reductions