GATE CS 2017 Set 2 Q.32 (CS Q.32): Parsing and Syntax Analysis (LL and LR)

Consider the following expression grammar $G$ :

\begin{aligned} E &\to E - T \mid T \\ T &\to T + F \mid F \\ F &\to (E) \mid \text{id} \end{aligned}

Which of the following grammars is not left recursive, but is equivalent to $G$ ?

E \to E - T \mid T \\ T \to T + F \mid F \\ F \to (E) \mid \text{id}

E \to T E' \\ E' \to -T E' \mid \epsilon \\ T \to T + F \mid F \\ F \to (E) \mid \text{id}

E \to T X \\ X \to -T X \mid \epsilon \\ T \to F Y \\ Y \to +F Y \mid \epsilon \\ F \to (E) \mid \text{id}

E \to T X \mid (TX) \\ X \to -T X \mid +T X \mid \epsilon \\ T \to \text{id}

Official answer and solution

Solution

Eliminate immediate left recursion from each non-terminal in grammar $G$ using the standard transformation rule.

The standard rule to eliminate immediate left recursion $A \to A\alpha_1 \mid \dots \mid A\alpha_m \mid \beta_1 \mid \dots \mid \beta_n$ is:

A \to \beta_1 A' \mid \dots \mid \beta_n A'

A' \to \alpha_1 A' \mid \dots \mid \alpha_m A' \mid \epsilon

Apply this to the given grammar $G$ :

For production $E \to E - T \mid T$ :
Here $A = E$ , $\alpha = -T$ , $\beta = T$ . Replacing $E'$ with variable name $X$ : $E \to T X$ $X \to -T X \mid \epsilon$
For production $T \to T + F \mid F$ :
Here $A = T$ , $\alpha = +F$ , $\beta = F$ . Replacing $T'$ with variable name $Y$ : $T \to F Y$ $Y \to +F Y \mid \epsilon$
For production $F \to (E) \mid \text{id}$ :
This rule contains no left recursion and remains unchanged.

The resulting grammar without left recursion is:

E \to T X

X \to -T X \mid \epsilon

T \to F Y

Y \to +F Y \mid \epsilon

F \to (E) \mid \text{id}

This is completely equivalent to $G$ and identical to option C.

Final answer

Common trap

Option B eliminates left recursion only from $E$ , leaving $T \to T + F \mid F$ still left-recursive.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.