edited by
6,969 views

2 Answers

Best answer
38 votes
38 votes

(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^{\prime}$  

  • $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$
selected by
4 votes
4 votes
  • 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' | ϵ 

edited by

Related questions

12 votes
12 votes
4 answers
1
Kathleen asked Sep 26, 2014
4,326 views
Let $G_1 = (N, T, P, S_1)$ be a CFG where, $N=\{S_1, A, B\},T=\{a, b\}$ and $P$ is given by$$\begin{array}{l|l}S_1 \rightarrow a S_1 b &S_1 \rightarrow a B b \\S_1 \right...
28 votes
28 votes
1 answer
4
Kathleen asked Sep 25, 2014
8,678 views
Faster access to non-local variables is achieved using an array of pointers to activation records called a stackheapdisplayactivation tree