2.4.5 LALR(1): merging states and which conflicts merging can create

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

How is the lookahead of a new item computed in LR(1) CLOSURE? from Lesson 2.4.4
What is CLOSURE({S → A•B}) when B → b | cB (LR(0))? from Lesson 2.4.2
Remove left recursion from A → A c | d. from Lesson 2.2

1 · The Story

📖

Too many bundles

The wall of bundles-with-notes is now huge. Mrs. Desai notices that many bundles hold exactly the same cards, differing only in the notes. “Pin those together,” she says, “and put both notes on each card.”

The wall shrinks back to the size of the original LR(0) wall. Most of the time nothing goes wrong: a card that says “fold if next is c or d” and its twin that says “fold if next is $” simply become one card that says “fold if next is c, d or $”.

Kabir finds one rulebook where merging hurts. Two bundles each held two complete cards, “fold as A” and “fold as B”, with opposite notes. After pinning them together, both cards say “fold if next is d or e”. Now, when d arrives, Kabir cannot tell which fold to make.

2 · Predict First

🤔

Can merging two CLR states that have no shift/reduce conflict ever produce a shift/reduce conflict? Write your guess down. The answer is in the vault.

3 · Core Concept

Merging cores

The core of an LR(1) state is its set of LR(0) items (lookaheads dropped). LALR(1) (lookahead LR) merges all CLR states with the same core, taking the union of the lookaheads. GOTO is well defined after merging, because states with the same core have GOTOs with the same cores.

The result has exactly as many states as the LR(0) automaton. In practice LALR tables are built more efficiently (for example by propagating lookaheads on the LR(0) automaton), but the result is the same.

The LALR(1) table

Same rules as CLR, using the merged states and merged lookaheads. A grammar is LALR(1) if the table has no multiple entries. Most programming-language grammars are LALR(1), which is why parser generators use it.

Which conflicts merging can create

Shift/reduce: never new. A shift on a in the merged state comes from a core item, present in every original state; if a merged reduce had lookahead a, the original state with that lookahead already had the S/R conflict.
Reduce/reduce: possible. Two states with complete items [A → c•, d], [B → c•, e] and [A → c•, e], [B → c•, d] are each fine, but merged they give A and B both on d and e.

An LALR conflict that is not in CLR is therefore always R/R.

Power ordering

LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ LR(1) as classes of grammars. LALR also detects errors a little later than CLR (it may perform a few extra reductions before reporting), but never shifts an erroneous token.

Story → compiler term

In the story	In the compiler
bundles with the same cards, different notes	CLR states with the same core
pinning them together, notes combined	merging into an LALR state (union of lookaheads)
wall back to LR(0) size	LALR states = LR(0) states
“fold as A or as B?” after pinning	reduce/reduce conflict created by merging

4 · Visual

Diagram: S · A · a · b · A · a · b · A · a · b · I0 · S' → • S, $ · S → • A A, $ · A → • a A, a/b · A → • b, a/b · I1 · S' → S •, $ · I2 · S → A • A, $ · A → • a A, $ · A → • b, $ · I3 · A → a • A, a/b/$ · A → • a A, a/b/$ · A → • b, a/b/$ · I4 · A → b •, a/b/$ · I5 · S → A A •, $ · I6 · A → a A •, a/b/$

LALR(1) automaton of S → A A, A → a A | b: the 10 CLR states merge into 7 (pairs merged: I3+I6, I4+I7, I8+I9).

State	`a`	`b`	`$`	S	A
I0	s3	s4		1	2
I1			acc
I2	s3	s4			5
I3	s3	s4			6
I4	r3	r3	r3
I5			r1
I6	r2	r2	r2

5 · Worked Examples

Example 1 Easy

Merge the CLR states of S → A A, A → a A | b.

Solution

The CLR collection has 10 states. Three pairs share a core (the states after a, after b, and after A in A → aA•): CLR states 3 and 6; 4 and 7; 8 and 9. Merging gives 7 states with lookaheads a/b/$ on the merged complete items, no conflicts. Mrs. Desai’s wall shrinks back to the LR(0) size.

Example 2 Medium

Why can merging never create a shift/reduce conflict?

Solution

Suppose the merged state has [A → α•, a] and [B → β•aγ, b]. The second item’s core is in every state being merged, so in particular in the original state that contributed [A → α•, a]. That original state already had the S/R conflict on a. So a grammar that is CLR without S/R conflicts is LALR without S/R conflicts.

Example 3 GATE

Show that S → a A d | b B d | a B e | b A e, A → c, B → c is LR(1) but not LALR(1).

Solution

After a c, the CLR state is { [A → c•, d], [B → c•, e] }; after b c it is { [A → c•, e], [B → c•, d] }. Each is fine (the lookaheads differ). They have the same core, so LALR merges them into { [A → c•, d/e], [B → c•, d/e] }: reduce/reduce conflicts on d and e. Computed: CLR 14 states, no conflicts; LALR 13 states, conflicts R/R.

6 · Shortcuts

⚡

States: LALR = SLR = LR(0) ≤ CLR. For S → CC: 7, 7, 7, 10. Valid when: any state-count comparison.

⚡

LALR conflict not in CLR ⇒ it is R/R. Valid when: MCQs asking which conflict merging can introduce.

7 · GATE Traps

⚠️

Merging can introduce reduce/reduce conflicts, never shift/reduce conflicts.
LALR has the same number of states as LR(0)/SLR, not as CLR.
LALR is strictly more powerful than SLR (it fixes L = R) and strictly less than CLR.
An LALR parser may make extra reductions before detecting an error, but never shifts an erroneous token.
If CLR has an S/R conflict, LALR has it too.

8 · Memory Hook

🧠

LALR = CLR states pinned by core. Same size as LR(0); merging may add R/R, never S/R.

9 · Connect the Dots

You now know four LR methods and one LL method. The next lesson puts them side by side: how powerful each is, how big its tables are, and how to classify a grammar quickly in the exam.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markStates

How many states does the LALR(1) automaton of S → C C, C → c C | d have?

Numerical answer: ________

Q2MCQ1 markMerging

Merging LR(1) states with identical cores can introduce:

(A) shift/reduce conflicts only
(B) reduce/reduce conflicts only
(C) both kinds
(D) no conflicts ever

Q3MCQ2 marksClassification

S → a A d | b B d | a B e | b A e, A → c, B → c is:

(A) LALR(1) but not LR(1)
(B) LR(1) but not LALR(1)
(C) SLR(1)
(D) ambiguous

Q4MSQ1 markFacts

Which are true?

(A) Number of LALR(1) states = number of LR(0) states.
(B) Every SLR(1) grammar is LALR(1).
(C) Every LALR(1) grammar is SLR(1).
(D) S → L = R | R, L → * R | id, R → L is LALR(1).

Q5NAT2 marksMerging

In the canonical LR(1) collection of S → L = R | R, L → * R | id, R → L, how many states disappear when LALR merging is applied?

Numerical answer: ________

11 · Rule Card

Core = LR(0) part of an LR(1) state.
LALR(1): merge CLR states with equal cores; union lookaheads.
LALR states = LR(0) states ≤ CLR states.
Merging can create R/R conflicts, never S/R.
LR(0) ⊂ SLR ⊂ LALR ⊂ LR(1).

12 · Concept Ledger

core of an LR(1) stateLALR(1)lookahead mergingmerge-induced reduce/reduce conflict

13 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Warm-up

From FIRST(βa) for the item [A → α•Bβ, a].
{ S → A•B, B → •b, B → •cB }.
A → d A′; A′ → c A′ | ε.

Predict First

No. Shift entries depend only on the item cores, which are the same in both states. If a merged state had a complete item with lookahead a and an item with a after the dot, one of the original states already had both. Merging can only create reduce/reduce conflicts.