Question

A → A a b | B d

B → b d | b e

(upper cases are nonterminals; lower cases are terminals)

Remove the left recursion in the grammar?

Perform left factoring if there exists some common prefix among choices?

Answer 1

1. To remove left recursion,

A Aa | b (Left recursive grammar)

After removing left recursion,

A bA'

A' aA' |

Apply this on above grammar,

A A a b | B d

B b d | b e

here A Aab has left recusrion, we can write it as a

A B d A'

A' a b A' |

Now no any production rule has left recursion.

The grammar will be,

A B d A' | B d

A' a b A' |

B b d | b e

2. In given grammar there exists left factoring as we have a production rule,

B b d | b e

Here, parser can't decide which production rule must be chosen to parse string in hand.

process to remove left factoring,

A a1 | a2 | a3

will change to

A aA'

A' 1 | 2 | 3

Apply this in above grammar,

A B d A' | B d

A' a b A' |

B b d | b e

Consider A B d A' | B d

After removing left factoring,

A B d X

X A' |

Consider B b d | b e

After removing left factoring,

B b B'

B' d | e

Combining all production rules,we get

A B d X

X A' |

A' a b A' |

B b B'

B' d | e

the grammar withoot left ecursion and left factoring