Check Whether the Given Grammar Is CLR(1)

In compiler courses, “CLR” almost always refers to CLR(1) grammars (a.k.a. LR(1) grammars). A grammar is CLR(1) iff it can be parsed by a deterministic LR parser built from LR(1) items without conflicts. Concretely: construct the LR(1) canonical collection of items, build ACTION/GOTO, and verify there are no shift/reduce or reduce/reduce conflicts.

This section checks the given grammar:

• $S \rightarrow Aa \mid bBa \mid Ba \mid bAc$
• $A \rightarrow c$
• $B \rightarrow d$

We will determine whether it is CLR(1) by examining the LR(1) parsing behavior around the points where the parser must choose between actions.

Key terms you’ll use:

• LR parsing
• LR(1) item
• ACTION/GOTO table
• Shift/reduce conflict
• Canonical collection of LR(1) items

Step 1: Augment the grammar and identify productions

To build LR(1), we augment:

• $S' \rightarrow S$

So the productions are:

1. $S' \rightarrow S$
2. $S \rightarrow Aa$
3. $S \rightarrow bBa$
4. $S \rightarrow Ba$
5. $S \rightarrow bAc$
6. $A \rightarrow c$
7. $B \rightarrow d$

Terminals: $\{a,b,c,d\}$ (and end-marker $$$).

We will look for a state where the parser’s choice depends on lookahead in a conflicting way.

Step 2: Compute the LR(1) lookahead distinctions for the key ambiguity (after reading $b d$)

The potentially confusing part of the grammar is:

• $S \rightarrow Ba$
• $S \rightarrow bBa$

Both contain the substring $Ba$ after possibly consuming an extra leading $b$.

Now examine what strings these generate:

• From $S \rightarrow Ba$: since $B \rightarrow d$, we get $S \Rightarrow da$
• From $S \rightarrow bBa$: we get $S \Rightarrow b d a$

So:

• The parser should reduce by $S \rightarrow Ba$ only when the derivation corresponds to having already completed a $B$ in the correct context.
• If the input contains a leading $b$, then the correct derivation must match $S \rightarrow bBa$, not $S \rightarrow Ba$ (because $S \rightarrow Ba$ cannot produce a leading $b$).

In LR(1), the lookahead helps the parser decide at the exact reduction time.

Concretely:

• $B \rightarrow d$ is a complete production when the dot reaches the end: items like $[B \rightarrow d •, a]$ tell the parser to reduce $B \rightarrow d$ with lookahead $a$ if $a$ is the expected following terminal.
• In $S \rightarrow Ba$, $a$ is required immediately after $B$.
• In $S \rightarrow bBa$, $a$ is also required immediately after $B$ (still $Ba$).

Thus, after reading $b d$, the next symbol must be $a$ for those productions to be valid. That means the parser’s action at the state where $B \rightarrow d •$ items exist will consistently be “reduce $B \rightarrow d$”, and then “reduce $S \rightarrow bBa$” or “reduce $S \rightarrow Ba$” depending on how much of the prefix was consumed—without needing to guess between two different continuations on the same lookahead.

Step 3: Check the other alternative containing $A$

The other “almost-overlapping” structure is:

• $S \rightarrow Aa$ where $A \rightarrow c$ gives $S \Rightarrow c a$
• $S \rightarrow bAc$ where $A \rightarrow c$ gives $S \Rightarrow b c c$

Again, the symbols immediately following $A$ are different:

• In $Aa$, the symbol after $A$ must be $a$.
• In $bAc$, the symbol after $A$ must be $c$ (and there is also the leading $b$ already).

So LR(1) lookahead will disambiguate reductions involving $A \rightarrow c$ in the same way.