Question

The grammar which is equivalent to - a -> a+a/a-a/b b -> b*b/a after eliminating the left factoring is -

Answer 1

Answer:

Left Recursion

Right Recursion

General Recursion

1. Left Recursion-

A production of grammar is said to have left recursion if the leftmost variable of its RHS is same as variable of its LHS.

A grammar containing a production having left recursion is called as Left Recursive Grammar.

Example-

S → Sa / ∈

(Left Recursive Grammar)

Left recursion is considered to be a problematic situation for Top down parsers.

Therefore, left recursion has to be eliminated from the grammar.

Elimination of Left Recursion

Left recursion is eliminated by converting the grammar into a right recursive grammar.

If we have the left-recursive pair of productions-

A → Aα / β

(Left Recursive Grammar)

where β does not begin with an A.

Then, we can eliminate left recursion by replacing the pair of productions with-

A → βA’

A’ → αA’ / ∈

(Right Recursive Grammar)

This right recursive grammar functions same as left recursive grammar.

2. Right Recursion-

A production of grammar is said to have right recursion if the rightmost variable of its RHS is same as variable of its LHS.

A grammar containing a production having right recursion is called as Right Recursive Grammar.

Example-

S → aS / ∈

(Right Recursive Grammar)

Right recursion does not create any problem for the Top down parsers.

Therefore, there is no need of eliminating right recursion from the grammar.

Also Read- Types of Recursive Grammar

3. General Recursion-

The recursion which is neither left recursion nor right recursion is called as general recursion.

Example-

S → aSb / ∈

PRACTICE PROBLEMS BASED ON LEFT RECURSION ELIMINATION-

Problem-01:

Consider the following grammar and eliminate left recursion-

A → ABd / Aa / a

B → Be / b

Solution-

The grammar after eliminating left recursion is-

A → aA’

A’ → BdA’ / aA’ / ∈

B → bB’

B’ → eB’ / ∈

Problem-02:

Consider the following grammar and eliminate left recursion-

E → E + E / E x E / a

Solution-

The grammar after eliminating left recursion is-

E → aA

A → +EA / xEA / ∈

Problem-03: