# Ullman (Compiler Design) Edition 2 Exercise 5.4 Question 2 (Page No. 336 - 337)

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.

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

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$.
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$.
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.
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.