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

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

0
705views

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]

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$