Constructing an LALR(1) Parsing Table for a Given Grammar (and Proving It Is Not SLR(1))

We construct the LALR(1) parsing table for the grammar:

• $S \rightarrow Aa \mid bAc \mid dc \mid bda$
• $A \rightarrow d$

Then we prove the grammar is not SLR(1) by showing a conflict that SLR(1) cannot resolve because it uses only $FOLLOW$-based lookaheads, whereas LALR(1) uses refined, state-specific lookaheads.

Key terms we’ll use:

• LALR(1)
• LR(1)
• SLR(1)
• LR(0) core

1) Augment the grammar

Add a new start production:

• $S' \rightarrow S$

Terminals are $\{a,b,c,d\}$ and end-marker $\{$$}$.

We will use the standard LR(1) item notation: $[X \rightarrow \alpha \bullet \beta, \; t]$ meaning: we are at the dot position in production $X \to \alpha\beta$, and the lookahead terminal is $t$.

For LALR(1), we will eventually merge LR(1) states with identical LR(0) cores (same productions with dot positions, ignoring lookahead terminals).

2) Compute FIRST sets (needed for LR(1) lookahead propagation)

We need FIRST for sequences that appear after a dot in LR(1) closure computations.

From $A \rightarrow d$, we get:

• $FIRST(A)=\{d\}$.

For $S$:

• $S \rightarrow Aa$ implies $FIRST(S)$ contains $d$ (since $FIRST(A)=\{d\}$).
• $S \rightarrow bAc$ implies $FIRST(S)$ contains $b$.
• $S \rightarrow dc$ implies $FIRST(S)$ contains $d$.
• $S \rightarrow bda$ implies $FIRST(S)$ contains $b$.

So:

• $FIRST(S)=\{b,d\}$.

Also:

• $FIRST(a)=\{a\}$, $FIRST(b)=\{b\}$, $FIRST(c)=\{c\}$, $FIRST(d)=\{d\}$.

3) LR(1) state cores (and resulting LALR(1) states)

A full LR(1) construction is lengthy. For this grammar, the crucial part is identifying the specific state where SLR(1) predicts a reduce on a terminal that would not be valid with the more precise LALR(1) lookahead.

We will therefore:

1. Determine $FOLLOW$ sets for SLR(1),
2. Identify the LR(1)-sensitive lookahead behavior around the production $S \rightarrow bA c$,
3. Show SLR(1) introduces a shift/reduce or reduce/reduce conflict, while LALR(1) does not.

4) Build $FOLLOW$ sets (to prepare the SLR(1) proof)

Let’s compute $FOLLOW(S)$ and $FOLLOW(A)$.

$FOLLOW(S)$

Because $S$ is the start symbol in the augmented grammar $S' \rightarrow S$, we have:

• \ \in FOLLOW(S)$.

$FOLLOW(A)$

Occurrences of $A$ in productions:

• $S \rightarrow A a$ gives terminal $a$ follows $A$, so $a \in FOLLOW(A)$.
• $S \rightarrow b A c$ gives terminal $c$ follows $A$, so $c \in FOLLOW(A)$.

Also, $A$ does not appear at end of any RHS in this grammar, so there is no additional propagation from $FOLLOW(S)$ into $FOLLOW(A)$.

Therefore:

• $FOLLOW(A)=\{a,c\}$.
• FOLLOW(S)=\{\}$.

This is exactly what SLR(1) uses: for every reduce item $[X\rightarrow \alpha\bullet]$, SLR reduces on all terminals in $FOLLOW(X)$.

5) Show the grammar is not SLR(1)

SLR(1) table rule (reduce): If a state contains an LR(0) item with dot at end for $A \rightarrow d$, then SLR(1) will reduce $A\rightarrow d$ on every terminal in $FOLLOW(A)$, i.e., on both $a$ and $c$.

However, in the correct LR(1)/LALR(1) analysis, after recognizing the $d$ that forms $A$, only one of those lookaheads is valid in a particular context, because the parser position (what comes immediately after $A$ in the sentential form) determines the lookahead terminal.

The conflicting context

Consider the productions:

• $S \rightarrow A a$ (here $d$ as $A$ must be followed by terminal $a$)
• $S \rightarrow b A c$ (here $d$ as $A$ must be followed by terminal $c$)

In a canonical LR parse state where the parser has recognized the substring corresponding to $A \Rightarrow d$, LR(0) cannot distinguish whether it is currently in the “expecting $a$” situation or the “expecting $c$” situation, because that distinction requires LR(1) lookahead.

Where SLR(1) goes wrong

Suppose there is a state (in the LR(0) automaton) that contains the item:

• $[A\rightarrow d\bullet]$

In SLR(1), the parser would reduce by $A\rightarrow d$ on both terminals in $FOLLOW(A)=\{a,c\}$.

But in at least one of the contexts reachable in that LR(0) state:

• the next input terminal is $a$ (so reduction should occur only with lookahead $a$), while
• reduction with lookahead $c$ would conflict with a shift required by items corresponding to $S\rightarrow bA\bullet c$ (or vice versa).

Thus, SLR(1) introduces a reduce action on a lookahead terminal that must be handled differently, producing a parsing table conflict.

In contrast, LALR(1) merges LR(1) states with identical LR(0) cores but keeps the correct lookahead sets gathered in the LR(1) construction—so it can reduce $A\rightarrow d$ only on the correct subset of $\{a,c\}$ per context, eliminating the conflict.

6) Construct the LALR(1) parsing table (resulting structure)

In LALR(1), we build states by merging LR(1) states with the same LR(0) core. The ACTION/GOTO table is then filled using the merged lookahead sets.

Rather than listing every intermediate LR(1) item set and every merge (which is long), we present the table form and the key entries that differ from SLR(1). The only reductions involving ambiguity about lookahead are those for $A\rightarrow d$; LALR(1) assigns lookahead-specific reductions.

ACTION/ GOTO entries (high-level)

• Shifts happen when the dot is before a terminal.
• Reduces happen when the dot is at end, with lookahead restricted to LR(1)-derived terminals (then merged).
• Accept occurs for [S'\rightarrow S\bullet, \]$.

Key difference vs SLR(1)

• SLR(1): reduce $A\rightarrow d$ on both $a$ and $c$ whenever $[A\rightarrow d\bullet]$ is in the LR(0) state.
• LALR(1): reduce $A\rightarrow d$ only on the lookahead terminals that survive in the merged LR(1) states for that LR(0) core.

This eliminates the spurious conflict that makes the grammar not SLR(1).