UPPCL AE 2018:64

Question

The following grammar $\text{G}$ is left recursive.

• $\text{E} \rightarrow \text{E + T}\; \mid \; \text{T} $
• $\text{T} \rightarrow \text{T * F} \; \mid \; \text{F} $
• $\text{F} \rightarrow \text{(E)} \mid \textbf{id} $

Which of the following is a correct left-recursive variant of $\text{G}$?

• A. $\text{E} \rightarrow \text{E}’\text{T} \\ \text{E}' \rightarrow \text{+TE}’ \mid  \epsilon \\ \text{T} \rightarrow \text{T}’\text{F} \\ \text{T}' \rightarrow \text{*FT}’ \mid \epsilon \\ \text{F} \rightarrow \text{(E)} \mid \textbf{id} $

 

• A. $\\ \text{E} \rightarrow \text{TE}' \\ \text{E}' \rightarrow \text{+TE}’ \mid  \epsilon  \\ \text{T} \rightarrow \text{FT}' \\ \text{T}' \rightarrow \text{FT}’* \mid \epsilon \\ \text{F} \rightarrow \text{(E)} \mid \textbf{id} $

 

100. $\text{E} \rightarrow \text{TE}' \\ \text{E}' \rightarrow \epsilon \mid \text{TE}' \\ \text{T} \rightarrow \text{FT}' \\ \text{T}' \rightarrow \text{*FT}’ \mid \epsilon \\ \text{F} \rightarrow \text{(E)} \mid \textbf{id} $

 

500. $\text{E} \rightarrow \text{TE}' \\ \text{E}' \rightarrow \text{T + E}' \\ \text{T} \rightarrow \text{FT}' \\ \text{T}' \rightarrow \text{F* + T}' \\ \text{F} \rightarrow \text{(E)} \mid \textbf{id} $

Answer 1

T--->FT`

T`-->*FT`|{

F-->(E)|id

E-->TE`

E`-->+TE`|{

would be right as E-->T+E` would run infinitely