**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**

**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**

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

**Eliminating ɛ production**

S->Aa |b |a

A -> AC |Sd | c

**Production**

A --> β A'

A' --> | A'

A -> SdA’ | cA’

A’ -> cA’| ɛ

S -> Aa | b| a

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$