Gate2017 ss Q43

43Consider the following expression grammar G.
E -> E - T | T
T -> T + F | F
F -> (E) | id
Which of the following grammars are not left recursive, but equivalent to G.

Option : C
Explanation :
The rule for removal of left recursion is
A →Aα |β will be
A →β A’
A’ → αA’|ϵ
The given grammar is:
E → E – T | T; in this α is “– T” and β is T
T →T + F | F, In this α is “+ F” and β is F
F → (E) | id
Hence after removal of the left recursion:
E → TX
X → - TX|ϵ
T → FY
Y → +FY|ϵ
F → (E) | id

Forgot your password?

I agree with the Terms.