search
Log In
1 vote
132 views

 Rewrite the following SDT:

  • $A\rightarrow A\{a\}B\mid AB\{b\}\mid 0$
  • $B\rightarrow B\{c\}A\mid BA\{d\}\mid 1$ 

so that the underlying grammar becomes non-left-recursive. Here, $a, b, c$, and $d$ are actions, and $0$ and $1$ are terminals. 

in Compiler Design 132 views

1 Answer

0 votes
Let {a} = M1, {b} = M2, {c} = M3 and {d} = M4
 

A → 0A`

A`→ M1 B A` / B M2 A` / ε

B → 1B`

B` → M3 A B` / A M4 B` / ε

M1 → ε {a}

M2 → ε {b}

M3 → ε {c}

M4 → ε {d}

 

This way it has no left recursion and also it is now a postfix SDT
0
Why u including in final statement M1 ,M2,M3,M4 is €.

U intinally let {a} = M1

.....so on
0
That step is to make SDT S-Attributed. You can omit that step to get the desired answer also. Left recursion can still be removed without doing that step.

Related questions

0 votes
0 answers
1
109 views
Modify the SDD of Fig. $5.25$ to include superscripts denoted by operator sup between boxes. If box $B_{2}$ is a superscript of box $B_{1}$, then position the baseline of $B_{2}\:0.6$ times the point size of $B_{1}$ above the baseline of $B_{1}.\text{Add}$ the new production and rules to the SDT of Fig. $5.26$.
asked Sep 7, 2019 in Compiler Design Lakshman Patel RJIT 109 views
0 votes
0 answers
2
96 views
Modify the SDD of Fig. $5.25$ to include a synthesized attribute $B.le$, the length of a box. The length of the concatenation of two boxes is the sum of the lengths of each. Then add your new rules to the proper positions in the SDT of Fig. $5.26$.
asked Sep 7, 2019 in Compiler Design Lakshman Patel RJIT 96 views
0 votes
0 answers
3
52 views
Write L-attributed SDT's analogous to that of Example $5.19$ for the following productions, each of which represents a familiar flow-of-control construct, as in the programming language C. You may need to generate a three address statement to jump to a particular ... have a jump from its middle to the next statement, so it is not sufficient simply to generate code for each statement in order.
asked Sep 7, 2019 in Compiler Design Lakshman Patel RJIT 52 views
0 votes
0 answers
4
34 views
Write L-attributed SDD's analogous to that of Example $5.19$ for the following productions, each of which represents a familiar flow-of-control construct, as in the programming language C. You may need to generate a three address statement to jump to a particular ... have a jump from its middle to the next statement, so it is not sufficient simply to generate code for each statement in order.
asked Sep 6, 2019 in Compiler Design Lakshman Patel RJIT 34 views
...