GATE CS 2016 Set 2 Q45 — Parsing (LL, LR)

A grammar has left recursion if there exists a non-terminal $X$ such that $X \Rightarrow^+ X\alpha$ for some string of grammar symbols $\alpha$. Left recursion can be either immediate (e.g., $X \rightarrow X\alpha$) or indirect/mutual (e.g., $X \rightarrow Y\beta \Rightarrow X\alpha\beta$).

Let's analyze each option:

• Option A: $$\begin{aligned} S &\rightarrow AB \\ A &\rightarrow Aa \mid b \\ B &\rightarrow c \end{aligned}$$ The production $A \rightarrow Aa$ is an immediate left recursion. Thus, this grammar is not free from left recursion.
• Option B: $$\begin{aligned} S &\rightarrow Ab \mid Bb \mid c \\ A &\rightarrow Bd \mid \epsilon \\ B &\rightarrow e \end{aligned}$$ Let's trace all possible derivations starting with each non-terminal:
  • From $S$: $S \rightarrow Ab \rightarrow Bdb \rightarrow edb$, or $S \rightarrow Bb \rightarrow eb$, or $S \rightarrow c$. No derivation starts with $S$.
  • From $A$: $A \rightarrow Bd \rightarrow ed$, or $A \rightarrow \epsilon$. No derivation starts with $A$.
  • From $B$: $B \rightarrow e$. No derivation starts with $B$.
  Since there is no sequence of derivations where $X \Rightarrow^+ X\alpha$ for any non-terminal $X$, this grammar is free from left recursion.
• Option C: $$\begin{aligned} S &\rightarrow Aa \mid B \\ A &\rightarrow Bb \mid Sc \mid \epsilon \\ B &\rightarrow d \end{aligned}$$ We can derive: $$S \rightarrow Aa \rightarrow Sca$$ Since $S \Rightarrow^+ Sca$, this grammar has indirect left recursion.
• Option D: $$\begin{aligned} S &\rightarrow Aa \mid Bb \mid c \\ A &\rightarrow Bd \mid \epsilon \\ B &\rightarrow Ae \mid \epsilon \end{aligned}$$ We can derive: $$A \rightarrow Bd \rightarrow Aed$$ Since $A \Rightarrow^+ Aed$, this grammar has indirect left recursion.

Therefore, only the grammar in Option B is free from left recursion.