Eliminate Left recursion in the following grammar (Remove Direct and Indirect recursion)

S->Aa l b $ \ \ \ \ $ A -> Ac | Sd | ɛ

Left Recursion

• Left Recursion. The production is left-recursive if the leftmost symbol on the right side is the same as the non-terminal on the left side.

• For example, expr → expr + term. If one were to code this production in a recursive-descent parser, the parser would go in an infinite loop.

Elimination of left Recursion

We eliminate left-recursion in three steps.

• eliminate ɛ -productions (impossible to generate ɛ!)
• eliminate cycles (A ⇒+ A)
• eliminate left-recursion

Algorithm

![enter image description here][1]

Step 1

1. Direct Recursion

For each rule which contains a left-recursive option,

A --> A | β

introduce a new nonterminal A' and rewrite the rule as

A --> β A'

A' --> | A'

• Thus the production:

  E --> E + T | T

  is left-recursive with "E" playing the role of "A","+ T" playing the role of , and "T" playing the role of β A'.

• Introducing the new nonterminal E', the production can be replaced by:

  E --> T E'

  E' --> | + T E'

• Of course, there may be more than one left-recursive part on the right-hand side. The general rule is to replace

  A --> A | | ... | β | β | ... | β

  by

  A --> β A' | β A'| ...| β A'

  A' --> | A' | A' | ...| A'

• Note that this may change the "structure". For the expression above, the original grammar is left-associative, while the non-left recursive one is now right-associative.

Step 2

Indirect Recursion

• Step one describes a rule to eliminate direct left recursion from a production. To eliminate left-recursion from an entire grammar may be more difficult because of indirect left-recursion.

• For example

  A --> B x y | x

  B --> C D

  C --> A | c

  D --> d

  is indirectly recursive because

  A ==> B x y ==> C D x y ==> A D x y.

  That is, A ==> ... ==> A where is D x y.

  The algorithm eliminates left-recursion entirely. It contains a "call" to a procedure which eliminates direct left-recursion (as described in step one).

EXAMPLE

Consider again the following grammar. S $\displaystyle \longmapsto$ Aa | b A $\displaystyle \longmapsto$ Ac | Sd | $\displaystyle \varepsilon$

We order the nonterminals: S < A.

There is no left recursive S-productions.

So the next step is to remove S from the right-hand side of the A-productions of the form

A $ \longmapsto$ S$ \alpha$.

Hence we obtain

S $\displaystyle \longmapsto$ Aa | b

A $\displaystyle \longmapsto$ Ac | Aad | bd | $\displaystyle \varepsilon$

Then we remove the left recursive A-productions.

S $\displaystyle \longmapsto$ Aa | b

A $\displaystyle \longmapsto$ bdA' | A'

A' $\displaystyle \longmapsto$ cA' | adA' | $\displaystyle \varepsilon$