× Close
Join the Ques10 Community
Ques10 is a community of thousands of students, teachers, and academic experts, just like you.
Join them; it only takes a minute
Sign up
Question: Eliminate Left recursion in the following grammar (Remove Direct and Indirect recursion)
0

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

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

Mumbai University > Computer Engineering > Sem6 > System Programming and Compiler Construction

Marks: 5M

Year: Dec 2015

ADD COMMENTlink
modified 28 days ago by gravatar for SAGAR NARKAR SAGAR NARKAR1.0k written 10 months ago by gravatar for Ramnath Ramnath1.9k
0

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

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

ADD COMMENTlink
written 10 months ago by gravatar for Ramnath Ramnath1.9k
0

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$

ADD COMMENTlink
written 28 days ago by gravatar for SAGAR NARKAR SAGAR NARKAR1.0k
Please log in to add an answer.


Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Traffic: 1 users visited in the last hour