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