Ullman (Compiler Design) Edition 2 Exercise 5.2 Question 3 (Page No. 317)

Question

Suppose that we have a production $A\rightarrow BCD$. Each of the four nonterminals $A, B, C,$ and $D$ have two attributes: $s$ is a synthesized attribute, and $i$ is an inherited attribute. For each of the sets of rules below, tell whether

1. the rules are consistent with an S-attributed definition
2. the rules are consistent with an L-attributed definition, and
3. whether the rules are consistent with any evaluation order at all?

 

1. $A.s=B.i+C.s.$
2. $A.s=B.i+C.s$ and $D.i=A.i+B.s.$
3. $A.s=B.s+D.s$
4. $A.s=D.i,B.i=A.s+C.s,C.i=B.s,$ and $D.i=B.i+C.i.$ 

Answer 1

$A\rightarrow BCD$
a. $A.s=B.i+C.s$

    This is L attributed SDD. Attributes of parent node can take values from their children

b. $A.s=B.i+C.s,$ $D.i=A.i+B.s$

    A cannot have inherited attribute. Since, there is nothing present on the LHS of A. So this SDD is neither S attributed nor L attributed

c. $A.s=B.s+D.s$

    A's synthesized attribute is a function of synthesized attributes of its children. This confirms to S attributed definition. Every S attributed SDD is also L attributed SDD

d. $A.s=D.i,$ $B.i=A.s+C.s,$ $C.i=B.s,$ $D.i=B.i+C.i$

   In the rule B.i=A.s+C.s. Here B's inherited attributed is taking values from its right sibling C. This violates L-attributed definition which says that inherited attributes are limited to take values from its parents or left siblings only. Hence, this SDD is not L-attributed

Comments

Please explain b little more in detail>

---

which part u didn't get?

---

aditi19 i'm not convinced with explanation of b 

A cannot have inherited attribute. Since, there is nothing present on the LHS of A. So this SDD is neither S attributed nor L attributed

The third condition of L-attributed SDD is 

Inherited or synthesized attributes associated with this occurrence of Xi itself, but only in such a way that there are no cycles in a dependency graph formed by the attributes of this Xi

Is it neccessary that some non-terminal to be at the LHS of A? Cannot $A_i$ take value from $A_s$? 

---

watch this 

https://www.youtube.com/watch?v=YvyxWf8fwh4&list=PLXR_CjemKJsCDcByt2DN-c81SNw-TDgvn&index=36 

and

https://www.youtube.com/watch?v=t0yAGEx03TM&list=PLXR_CjemKJsCDcByt2DN-c81SNw-TDgvn&index=37

---

aditi19 are these questions solved? or just concepts?

---

questions from ullman?

---

I'm talking about that video

---

mostly concepts

---

b is L-attributed but not S-attributed.

---

Ques b is L attributed because it is possible that A.i is already initialised.This can be seen in the fig 5.25 of the ullmann book.So no point in saying that A doesnt have any parent or left sibling.

Answer 2

a. A.s = B.i + C.s

This would have been S-attributed had it been synthesized attribute for B too. But it is L-attributed for sure.

b. A.s = B.i + C.s,   D.i = A.i + B.s

since in the question, it says that each non-terminal has both synthesized as well as an inherited attribute, therefore we can consider A to have inherited attribute. And since D’s attribute is associated with its parent and left sibling, therefore L-attributed.

c. A.s = B.s + D.s

obviously both S-attributed and L-attributed.

d. A.s = D.i;   B.i = A.s + C.s;  C.i = B.s, and D.i = B.i + C.i

Because in the second semantic rule, B’s attribute is associated with a non-terminal which lies on its right side in the production A → BCD, therefore neither S-attributed not L-attributed.

Comments

This is the correct answer. Thanks.

http://dragon-book.jcf94.com/book/ch05/5.2/5.2.html