The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+13 votes

Consider the grammar

  • S $\rightarrow  Aa \mid b$
  • A $\rightarrow Ac \mid Sd \mid \epsilon$

Construct an equivalent grammar with no left recursion and with minimum number of production rules.

asked in Compiler Design by Veteran (59.5k points)
edited by | 1k views

2 Answers

+15 votes
Best answer

(b) As it is the case of indirect recursion so let first make it as direct recursion then apply rules of removal of left recursion.

to make it as direct recursion first production remain unchanged while in second production substitute the right hand side of first production wherever it comes.In the question $S$ comes in middle of $A$ so substitute the right hand side of production $S$.Now after substituting it looks like..

$A \rightarrow  Ac\mid Aad \mid bd \mid \epsilon$

Now remove direct recursion from it

For removal of direct recursion rule--

A \rightarrow A\alpha_1 \mid \ldots \mid A\alpha_n \mid \beta_1 \mid \ldots \mid \beta_m

Replace these with two sets of productions, one set for A:

A \rightarrow \beta_1A^\prime \mid \ldots \mid \beta_mA^\prime

and another set for the fresh nonterminal A' 

A^\prime \rightarrow \alpha_1A^\prime \mid \ldots \mid \alpha_nA^\prime \mid \epsilon

After applying these rule we'll get..

$A \rightarrow  bdA'\mid A'$

$A' \rightarrow cA'\mid adA' \mid \epsilon$

Now complete production without left recursion is...

$S \rightarrow Aa \mid b$

$A \rightarrow  bdA'\mid A'$

$A' \rightarrow cA'\mid adA' \mid \epsilon$

answered by Junior (569 points)
selected by

i have a doubt that in the production for S, if on rhs A is replaced by A'S that is also an indirect recursion??

  • S →Aa∣b
  • A →Ac∣Sd∣ϵ


  • S →Aca|Sda∣b
  • A →Ac∣|Aad|bd∣ϵ

on removing left rec





they are asking for minimum production rules
+1 vote
  • S →Aa∣b
  • A →Ac∣Sd∣ϵ

Remove indirect recursion first:-

A-> Ac | Aad | bd |ϵ

I have replace S production with RHS in above . Now we have got the grammer with direct left recursion.

Now let us remove left recursion

S →Aa∣b

A -> bd A' | A'

A' -> cA' | ad A' | ϵ 

answered by Boss (24.5k points)
edited by
Why are we not replacing the A in S production... Isn't it indirect recursion??

And also from the above grammar we are not able to generate some strings Eg 'b'.

Please help.
its not generating b. This is not correc.Please refer above answer.I will update this answer in some time
In above answer also the same confusion is there. Please update soon.
You can not leave S, the we will miss out S --- > b , Moreover keeping S---> Aa is necessary to reach A. And what we did is,after reaching A,we never go back to S, i.e. we eliminated the indirect recursion. We handle that with help of A' .
Yes it was incorrect. I have update it now.

@Garry:- I saw your above comment where you generated byu replacing A in S.I think you are getting 4 productions but with other way only 3 are possible.So,we will prefer 3

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,079 questions
45,572 answers
49,040 users