GATE CS 2017 Set 2 Q32 — Parsing (LL, LR)

To eliminate immediate left recursion from a grammar, we use the standard transformation rule:

If we have productions of the form: $$A \rightarrow A\alpha \mid \beta$$ where $\beta$ does not begin with $A$, we can replace them with: $$\begin{aligned} A &\rightarrow \beta A' \\ A' &\rightarrow \alpha A' \mid \epsilon \end{aligned}$$

Let's apply this rule step-by-step to the given grammar $G$:

1. For the non-terminal $E$:

   The production is $E \rightarrow E-T \mid T$. Here, $A = E$, $\alpha = -T$, and $\beta = T$.

   Applying the transformation (using $X$ as the new non-terminal instead of $E'$):

   $$\begin{aligned} E &\rightarrow TX \\ X &\rightarrow -TX \mid \epsilon \end{aligned}$$
2. For the non-terminal $T$:

   The production is $T \rightarrow T + F \mid F$. Here, $A = T$, $\alpha = +F$, and $\beta = F$.

   Applying the transformation (using $Y$ as the new non-terminal instead of $T'$):

   $$\begin{aligned} T &\rightarrow FY \\ Y &\rightarrow +FY \mid \epsilon \end{aligned}$$
3. For the non-terminal $F$:

   The production is $F \rightarrow (E) \mid id$. Since it is not left-recursive, it remains unchanged:

   $$F \rightarrow (E) \mid id$$

Combining all the transformed productions, we get:

This matches Option C.

Elimination of other options:

• Option A: This is the original grammar, which contains left recursion in both $E$ and $T$.
• Option B: Left recursion is eliminated only for $E$, but $T \rightarrow T + F \mid F$ is still left-recursive.
• Option D: This grammar is not equivalent to $G$ (e.g., it cannot generate the same set of strings, and the operator precedence/associativity is lost).