in Compiler Design edited by
36,302 views
75 votes
75 votes

In a bottom-up evaluation of a syntax directed definition, inherited attributes can

  1. always be evaluated
  2. be evaluated only if the definition is L-attributed
  3. be evaluated only if the definition has synthesized attributes
  4. never be evaluated
in Compiler Design edited by
36.3k views

4 Comments

Read all the available solutions and still confused ?

Doubt :- for inherited attribute , defination must be L attributed. and if defination is L attributed then evaluation is done using depth first traversal (Left to right ).

and if it is S attributed then evaluation is done using Bottom Up parsing .

I know only these two points .

Can somebody plz explain this que in simple word ??
2
2
Please correct me if I am wrong I am completely confused by all the answers here is what I think,S-attributed SDT attributes are evaluated during Bottom Up parsing but since there is inheritance no chance of S-attribute and L-attributed is used for depth first,left to right making option D as the correct answer.Please Help
0
0

@sripo

check my comment on the answer of arjun sir

0
0

10 Answers

43 votes
43 votes
Best answer
  1. is false. If the grammar is not L-attributed; we cannot evaluate the inherited attributes in a bottom-up parse. In fact even for some L-attributed grammar, bottom-up parse is not possible for inherited attributes. 
    http://infolab.stanford.edu/~ullman/dragon/slides2.pdf
    https://gateoverflow.in/?qa=blob&qa_blobid=14587629398289520039
     
  2. is true. Is there any non L-attributed grammar which can be parsed by a bottom-up parser? No, as shown in the above link. In fact only for the L-attributed grammar made from a LL(1) grammar, we can always guarantee a bottom-up parsing. Even for LR(1) grammar, bottom-up parsing is not a guarantee for all inherited attributes.
     
  3. is false. Some L-attributed grammars (including those with no synthesized attributes)  can be evaluated by a bottom-up parser. 
     
  4. is false for above-told reasons. 


A nice PDF for the same :- https://acm.sjtu.edu.cn/w/images/a/a1/Compiler2013-lec07.pdf

edited by
by

4 Comments

sir the evaluation which you showed in the parse tree is depth first traversal only then how is it bottom up parsing. @Shaik Masthan

2
2

Reason given for $C$ conflicts with the reason of III in https://gateoverflow.in/1328/gate2009-42

1
1

There it is S-attributed,although it contains synthesized attributes only but see this Answer,

https://gateoverflow.in/908/gate-cse-2003-question-18?show=16807#a16807

the first example has synthesized attribute, but cannot be evaluated from BUP.

that’s what option C is ,

  1. be evaluated only if the definition has synthesized attributes 

so that example was a counter for this.

and also it is not the case that it can never be evaluated by BUP,

so the most suitable answer here is B.

 

0
0
14 votes
14 votes

Ans D

Why ?

A) inherited attributes can have cyclic dependencis. Due to which we can not be sure whether they can be evaluated in First Place.

So A is wrong.

B) This is wrong because even defination is is L-attributed, we need to go top down, left to right. We can not do standard bottom up Traversal.

example :-

T' -> *FT1' | T1'.inh = T'.inh * F.val -> This move is allowed in L attributed, which can not be computed using bottom up traversal. We need to go from left to right, top down. So B is out of question.

reference :- https://en.wikipedia.org/wiki/L-attributed_grammar

L-attributed grammars are a special type of attribute grammars. They allow the attributes to be evaluated in one depth-first left-to-right traversal of the abstract syntax tree. As a result, attribute evaluation in L-attributed grammars can be incorporated conveniently in top-down parsing.

A syntax-directed definition is L-attributed if each inherited attribute of Xj on the right side of

A → X1 X2 … Xn

depends only on

1.the attributes of the symbols X1, X2, …, Xj-1

2.the inherited attributes of A // This is why B is false.

C) This is wrong because it says " definition has synthesized attributes". So along with Synthesized attributes, I can even have cycles. Which makes this wrong..

So answer is One and only D. Never !

4 Comments

@Kapil Option C would correct if it would like below:-

 if the definition has only synthesized attributes.

am i right??

1
1
Yes,if it has only synthesized then no chance of cycles.
1
1
0
0
6 votes
6 votes
Ans:C

lets see how ,consider following SDD:

A->BC   B.i =A.i 

B->b  B.s=b.val 

C->c  C.s=c.val

if u draw parse tree

  A

B  C

b   c

now ur traversing bottom up

first you 'll evaluate B.s then you want to evaluate B.i    but as we can see as i is an inherited attribute and it is dependent on A.i , but we have'nt evaluated A.i yet coz we are doing a bottom up traversal and we havent seen A yet . so it cannot be evaluated due to Inherited attribute i.

 

now if  A=BC  A.s=B.s+C.s

B->b  B.s=b.val 

C->c  C.s=c.val

see that

  A

B  C

b   c

you 'll traverse bottom up ,first eval B.s=b then C.s=c

then when you are at A ,you have already evaluated all the attributes on which A.s is dependent..so Only in this case where SDD has Synthesized attributes ,then only Bottom up Evaluation can be used.

 for Inherited attributes  we will need  a depth first evaluation.

6 Comments

Your explanation is correct, but C option says "has" not "is".
5
5

A->BC       C.i=B.s 

B->id         B.s=id.val  

   A

B    C

id     

now when we can evaluate inherited attribute C.i , becoz sdd has synthesized attributes present.

3
3

But Anurag_s , attribute values can also be taken from parent , which will be problematic if Bottom up evaluation is used, so C should be False.

0
0
yes, its not true for every case, but its not false for all cases.

I think in c option he wanted to say can be evaluated sometimes

c seems to be most appropriate if i have to mark any one
3
3
option C can not be answer because even if defination contains synthesized attributes bottom up  evaluation of inherited attributes is not possible.
0
0
'has only synthesized attributes'..then option C would be correct,right?
0
0
2 votes
2 votes
Ans: B

In bottom-up parser inherited from the parent isn't possible.but inherited from the left child is possible in L-attributed
Answer:

Related questions