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

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

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

1 Answer

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


![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 | | ... | β | β | ... | β


    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).


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$

Please log in to add an answer.

Continue reading...

The best way to discover useful content is by searching it.