The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+33 votes
5.3k views

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
asked in Compiler Design by Veteran (59.4k points)
edited by | 5.3k views
+1
It should be B) because  if the underlying grammar is LL(1) and if it is L attributed then it can be converted to a translation  on a LR grammar.

so it can be evaluated. correct me if i am wrong?
0
@Sanket
Please explain
0
how to identify inherited attribute from SDT
0
confused...???
0
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 ??

5 Answers

+15 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 non-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

answered by Veteran (342k points)
edited by
+1
For L-attributed SDD's, there is a natural order in which to evaluate the attributes attached to a parse tree. traverse the tree in preorder, computing inherited attributes the rst time a node is reached and synthesized attributes the last time it is reached. Then why option B and not C ???
please explain
not able to understand??
+1
Not able to understand this statement "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." @Arjun sir, please explain this statement in more detail.
0
Can we also parse S-Attributed SDT with the top-down parser?

We know that L-attributed SDT can be parsed with both bottom-up and top-down traversal. is it also true for S-attributed?

I am thinking, for any S-attributed we must traverse through bottom-up only, it is not possible with a top-down parser.

Please correct me if I am wrong.
0

Some L-attributed grammars (including those with non-synthesized attributes)  can be evaluated by a bottom-up parser. 

@Arjun sir , Can you please provide some example.

+1

Similar question but different answer: https://gateoverflow.in/1328/gate2009-42

+1

A NOTE FROM WIKIPEDIA 

Inherited attributes, which must be passed down from parent nodes to children nodes of the abstract syntax tree during the semantic analysis of the parsing process, are a problem for bottom-up parsing because in bottom-up parsing, the parent nodes of the abstract syntax tree are created after creation of all of their children

0
@Arjun L attributed definition can be implemented by using bottom up parsers by mixing post order and preorder techniques right ? you mean to say only LL(1) grammars are guaranteed and if the grammar is LR(1) it may or may not be possible to bottom up parsing .
0

@Arjun Sir

option B: "be evaluated only if the definition is L-attributed"  , since only if means P->Q, here they are trying to say "If inherited attribute can be evaluated during bottom up parsing then SDD must be L-attributed".

but we can not use "if and only if" here , because there are L-attributed SDD which can not be evaluated by bottom up parsing(for example: A->CB,C->something , B->somethingelse,   if some inherited attribute of B depends upon A's inherited attribute then, during bottom up parsing when we reduce to B , we can not derive that  inherited attribute of B, So although this SDD is L-attributed but bottom up parsing will not work here. ).

Please let me know if my observations are correct.

 

+10 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 !

answered by Boss (42.4k points)
+2
Should be D
+4

We cant also say never,  if it would hv been Can not always be evaluated, then that would be correct.for some of sdds it can be done. 

+2

I've proved all other options wrong here. If there is any answer, then that is D.

Standard Defination of inherited attributes (In Ullman it is same)  ->

An inherited attribute at a node in parse tree is defined using the attribute values at the parent or siblings. Inherited attributes are convenient for expressing the dependence of a programming language construct on the context in which it appears. For example, we can use an inherited attribute to keep track of whether an identifier appears on the left or the right side of an assignment in order to decide whether the address or the value of the identifier is needed..
 

ref -> https://en.wikipedia.org/wiki/Attribute_grammar#Inherited_attributes

You can not evaluate use value of parent / sibling using Bottom up traversal. So D is false.

0
Can u plz elaborate your explanation  a bit more .
0

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 .

is it correct?

if bottom up evaluation and top down evaluation has huge difference in SDT? otherwise answer will be (B) , as inherited attribute can be evaluated only if definition is L attributed

@Arjun sir plz see it

+1

answer should be C ...Attribute evaluation in S-attribute grammars can be incorporated conveniently in both top-down parsing and bottom-up parsing since S-attributed grammars are not inherited...just that it should be is instead of has..

+1

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

 if the definition has only synthesized attributes.

am i right??

+1
Yes,if it has only synthesized then no chance of cycles.
+2 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.

answered by Loyal (8k points)
+3
Your explanation is correct, but C option says "has" not "is".
+2

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.

 

0

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.

+2
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
0
option C can not be answer because even if defination contains synthesized attributes bottom up  evaluation of inherited attributes is not possible.
0
'has only synthesized attributes'..then option C would be correct,right?
0 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
answered by (51 points)
–1 vote
Option b.
answered by Active (3.3k points)
edited by
0
explain it....
0
Acc. To my reasoning it should be b option but then in the book which which i am solving its given c and the reasoning theve given is that it is a fact.
0
same here,,i too think so it should b (b)
0
But in previous paper soln. Gk publishers it is given c things are getting real confusing at the last moment.
0
yes it is getting but at this moment dont get confused,,

sometimes these sources too have mistake in there answeres,,so u b confident
0
This tends to support b not d.
0
Inherited attributes can be evaluated by bottom up parsing of inherited attributes thats for sure
0
But in bottom up only Synthesized attribute is evaluated.... parents are created after all its children so is there any possibility to have inherited attribute?
0
L-r attributed grammar can evaluate inherited attributes using bottom up parsing.
0

It can be specification to ans B is..

A  S-attribute SDD can evaluate synthesized attributes only..

But a L-attribute SDD can evaluate both synthesized and inherited attribute..

 



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,528 questions
42,804 answers
121,627 comments
42,167 users