The following grammar G is left recursive. E → E + T | T T → T * F | F F → (E) | id Which of the following is a correct left-recursive variant of G? E → TE' E' → T + E' 

The following grammar G is left recursive. E → E + T | T T → T * F | F F → (E) | id Which of the following is a correct left-recursive variant of G? E → TE' E' → T + E'  Correct Answer <p>T → FT'</p> <p>T' → *FT' | ε</p> <p>F → (E) | id</p>

The correct answer is option 4.

Concept:

Left Recursion:

When the right-hand side's leftmost variable is the same as the left-hand sides variable then the grammatical production is have left recursion. Left Recursive Grammar refers to a grammar that contains a production with left recursion.

We know for left recursion :

A -> Aα/β

After removing the left recursion it can be written as

A -> βA’

A’ -> αA’/ε

Solution:

E → E + T | T (here right-hand side's leftmost variable E is the same as the left-hand sides variable E)

T → T * F | F  (here right-hand side's leftmost variable T is the same as the left-hand sides variable T)

F → (E) | id  (no left recursive)

E → E + T | T

E → TE'

E' → + TE’ /ε

T → T * F | F 

T → FT'

T' → *FT’ /ε

Hence the correct answer is 

T → FT'

T' → *FT' | ε

F → (E) | id