Proving That a Grammar Is LL(1) but Not SLR(1)

Consider the grammar

$$\begin{aligned} S &\rightarrow AaAb \mid BbBa\\ A &\rightarrow \epsilon\\ B &\rightarrow \epsilon \end{aligned}$$

where $a$ and $b$ are terminals, $S$ is the start symbol, and $\epsilon$ denotes the empty string.

This section proves two different properties:

1. The grammar is LL(1) because one input symbol is sufficient to choose every production in a predictive top-down parser.
2. The grammar is not SLR(1) because its SLR parsing table contains a reduce–reduce conflict.

An LL(1) table is constructed using FIRST and FOLLOW sets. A grammar is LL(1) when no table cell receives more than one production. SLR(1), in contrast, constructs LR(0) item sets and places reductions according to FOLLOW sets; overlapping reductions create conflicts.

Footnotes

1. Top-Down Parsing - Describes FIRST/FOLLOW-based predictive parsing tables and LL(1) conditions. ↩

2. LR Parsing and SLR(1) Parsing - Defines LR(0) items, SLR reductions using FOLLOW sets, and shift–reduce/reduce–reduce conflict conditions. ↩

Language generated by the grammar

Because both $A$ and $B$ derive $\epsilon$,

$$A \Rightarrow \epsilon \qquad\text{and}\qquad B \Rightarrow \epsilon.$$

Therefore,

$$S \Rightarrow AaAb \Rightarrow ab$$

and

$$S \Rightarrow BbBa \Rightarrow ba.$$

Thus,

$$L(G)=\{ab,ba\}.$$

The two alternatives begin with different terminals:

• $AaAb$ begins with $a$, because $A$ disappears and the next symbol is $a$.
• $BbBa$ begins with $b$, because $B$ disappears and the next symbol is $b$.

This separation is the central reason the grammar is LL(1).

FIRST and FOLLOW summary

The two alternatives for $S$ satisfy

$$FIRST(AaAb)\cap FIRST(BbBa) = \{a\}\cap\{b\} = \varnothing.$$

Although both alternatives contain nullable nonterminals, neither alternative itself derives $\epsilon$:

$$\epsilon\notin FIRST(AaAb), \qquad \epsilon\notin FIRST(BbBa).$$

Consequently, there is no FIRST/FIRST conflict and no FIRST/FOLLOW conflict for $S$.

Constructing the LL(1) parsing table

For a production $X\rightarrow\alpha$, place the production in $M[X,t]$ for each $t\in FIRST(\alpha)$. If $\epsilon\in FIRST(\alpha)$, place it under every symbol in $FOLLOW(X)$.

The terminals are $a$, $b$, and $$$.

Every populated table cell contains exactly one production. Therefore, the grammar is LL(1).

Formally,

$$FIRST(AaAb)\cap FIRST(BbBa)=\varnothing,$$

and the nullable productions for $A$ and $B$ are selected uniquely using their FOLLOW sets. Hence,

$$\boxed{G\text{ is LL(1)}}.$$

Footnotes

1. Top-Down Parsing - Describes FIRST/FOLLOW-based predictive parsing tables and LL(1) conditions. ↩

LL(1) derivation traces

For input $ab$:

$$\begin{aligned} S &\Rightarrow AaAb\\ &\Rightarrow \epsilon a\epsilon b\\ &\Rightarrow ab. \end{aligned}$$

For input $ba$:

$$\begin{aligned} S &\Rightarrow BbBa\\ &\Rightarrow \epsilon b\epsilon a\\ &\Rightarrow ba. \end{aligned}$$

The first lookahead symbol determines the production for $S$:

This is exactly the one-symbol prediction required by LL(1).

Why the SLR(1) analysis is different

To test SLR(1), augment the grammar with a new start production:

$$S'\rightarrow S.$$

An LR(0) item places a dot at every possible position in a production. For example,

$$S\rightarrow AaAb$$

produces

$$\begin{aligned} S&\rightarrow \bullet AaAb\\ S&\rightarrow A\bullet aAb\\ S&\rightarrow Aa\bullet Ab\\ S&\rightarrow AaA\bullet b\\ S&\rightarrow AaAb\bullet. \end{aligned}$$

An item with the dot at the end is a completed item and proposes a reduction.

For SLR(1), a completed item $X\rightarrow\alpha\bullet$ produces a reduce action only on terminals in $FOLLOW(X)$.

Footnotes

1. LR Parsing and SLR(1) Parsing - Defines LR(0) items, SLR reductions using FOLLOW sets, and shift–reduce/reduce–reduce conflict conditions. ↩

Initial LR(0) item set

The closure of the initial item is

$$\begin{aligned} I_0=\{& S'\rightarrow\bullet S,\\ &S\rightarrow\bullet AaAb,\\ &S\rightarrow\bullet BbBa,\\ &A\rightarrow\epsilon\bullet,\\ &B\rightarrow\epsilon\bullet \}. \end{aligned}$$

The two completed items are especially important:

$$A\rightarrow\epsilon\bullet \qquad\text{and}\qquad B\rightarrow\epsilon\bullet.$$

They both occur in the same LR(0) state.

The SLR reduction rule is:

• reduce $A\rightarrow\epsilon$ on every terminal in $FOLLOW(A)$;
• reduce $B\rightarrow\epsilon$ on every terminal in $FOLLOW(B)$.

Since

$$FOLLOW(A)=FOLLOW(B)=\{a,b\},$$

the actions are:

Each cell contains a reduce–reduce conflict.

Why this is a reduce–reduce conflict

On lookahead $a$, the SLR parser sees two valid reductions:

$$A\rightarrow\epsilon \qquad\text{or}\qquad B\rightarrow\epsilon.$$

On lookahead $b$, it again sees two valid reductions:

$$A\rightarrow\epsilon \qquad\text{or}\qquad B\rightarrow\epsilon.$$

Therefore,

$$FOLLOW(A)\cap FOLLOW(B) = \{a,b\} \neq\varnothing.$$

Because the completed items occur in the same LR(0) item set, SLR places both reductions in the same ACTION-table cells. This is precisely the SLR reduce–reduce conflict condition.

Thus,

$$\boxed{G\text{ is not SLR(1)}}.$$

Footnotes

1. LR Parsing and SLR(1) Parsing - Defines LR(0) items, SLR reductions using FOLLOW sets, and shift–reduce/reduce–reduce conflict conditions. ↩

Visual comparison of the two analyses

The apparent contrast is not contradictory:

• Top-down parsing sees the first terminal of the complete $S$ alternative.
• SLR parsing sees two completed nullable reductions in the same LR(0) state.
• SLR uses the coarse FOLLOW approximation for reductions, so both reductions are enabled on both terminals.

Final proof

For LL(1):

$$FIRST(AaAb)=\{a\}, \qquad FIRST(BbBa)=\{b\}.$$

Therefore,

$$FIRST(AaAb)\cap FIRST(BbBa)=\varnothing.$$

Also,

$$FOLLOW(A)=FOLLOW(B)=\{a,b\},$$

so the epsilon productions are selected unambiguously. The LL(1) parsing table has no multiply defined entries. Hence,

$$\boxed{G\text{ is LL(1)}}.$$

For SLR(1), the initial LR(0) state contains

$$A\rightarrow\epsilon\bullet \qquad\text{and}\qquad B\rightarrow\epsilon\bullet.$$

SLR places the reductions on their FOLLOW sets. Since

$$FOLLOW(A)\cap FOLLOW(B)=\{a,b\}\neq\varnothing,$$

both reductions are entered under both $a$ and $b$, producing reduce–reduce conflicts. Hence,

$$\boxed{G\text{ is not SLR(1)}}.$$

Therefore, the required result is

$$\boxed{\text{The grammar is LL(1) but not SLR(1).}}$$