Question

Give the grammar following:

E --> E + T | T

T --> T* F | F

F --> (E) | id

Eliminating the left recursion rules and getting a non-left recursive equivalent grammar.

Answer 1

Solution:

Given grammar,

E -> E + T | T

T -> T * F | F

F -> (E) | id

Explanation:

=>E, T and F are non terminals and (. ) and id are terminals in the given grammar.

=>Production rules E -> E + T and T -> T * F are left recursive because same non terminal exist on the left side of production rule and exactly left of the right side of production rule.

Removing left recursion:

=>If there is left recursive production rule A -> A | where A is non terminal, and are set of terminals and non terminals so we can write above production rule in non-left recursive form as A -> A', A' -> | A'

So the non-left recursive form of the given grammar is.

E -> TE'

E' -> | +TE'

T -> FT'

T' -> | *FT'

F -> (E) | id

I have explained each and every part with the help of statements attached to the answer above.