in Compiler Design edited by
36,299 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

24 Comments

edited by
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??
3
3
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.
3
3
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
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
1

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

4
4
edited by

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

8
8
@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
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.

1
1
C is correct
0
0
This is one of those answer which broke my many wrong concept and helped me build correct concept
1
1
@mehul vaidya can u explain the solution clearly . solution posted here is not correct according to me.
0
0

from the reference you have given ::

Five Styles of Translation 1. Construct parse tree and perform a SDD.

2. Recursive procedures associated with non terminals (like recursive-descent parser).

3. Recursive procedures that spit out code as a side-effect.

4. SDT on an LL grammar; top-down parse.

5. SDT on an LR grammar; bottom-up parse.

 (1) is completely general.

(2) through (5) require an "L-attributed SDD."

here it is written LL grammar; top down parse requires L-attributed but you have written bottom up .

so answer will be C explained well by below answer.

0
0
don't just down vote my comment i have used the reference given in the answer

 .  if possible explain with just one example  . just one example whoever has given down vote that why option c is wrong and option b is correct with an example.

because in L-attributed if it has  an inherited attribute then no way using bottom up parsing we can evaluate .

but there is a possibility that if all attributes are synthesized then it can be evaluated.
1
1

Option B is correct answer !

Let

D means Declaration, T means Type, L means List and Add means add identifier into symbol table table.

 

D → T L; { L.type = T.type }

$ \color{red}L → \color{blue}L,id  \;\{ \color{blue}L.type = \color{red}L.type, Add(id,\color{blue}L.type) \}\;| \;id \;\{  \;Add(id,\color{red}L.type) \} $

T → int { T.type = int } | char { T.type = int }

 

Which are semantic rules ( L-attributed ) for adding variables into the symbol table. ( But not exact. )

let we define the variables like int a,b,c; in our languages, you can parse it by Bottom-Up parser

 

2
2

@Shaik Masthan

In option B it is saying in Bottom up evaluation , inherited attribute evaluated only if SDD definition is L attributed

that means If SDD is not L attributed then inherited attributes are not evaulated

Can we see it like this ...if SDD definition is not L attributed meas it will be not S nor L attributed ..if defn is not S nor L attributed does that means in such SDD also inherited attributed not evaluated in BUP the SDD may be not S nor L because of inheritence from right sibling??

4
4
yes
4
4
still having some doubts

1) that means there do not exits any SDD which is not L attributed and can be evaluated by BUP evaluation even if it is build on LL(1) grammar ..

2) What evaluation order is used for L-attrbuted SDDs built on LR(1) grammar ?

3) In BUP evaulation ..synthesized attributes are always evaluated in S attributed and L attributed def as well..
3
3

What evaluation order is used for L-attrbuted SDDs built on LR(1) grammar ?

DFS from Left to right

 

In BUP evaulation ..synthesized attributes are always evaluated in S attributed and L attributed def as well..

yes

 

that means there do not exits any SDD which is not L attributed and can be evaluated by BUP evaluation even if it is build on LL(1) grammar ..

i hope so, but not sure due such LL(1) grammar exist or not ?

0
0

@Shaik Masthan @jatin khachane 1 L attribute use both Synthesize as well as inherited attribute,

For Synthesize, value of a node is evaluated  after evaluating all child 

in INherited attribute, a node inherits value either from left sibling or from parent

But " If the L attribute contains only inherited attributes not synthesize attribute, then can it will evaluate with bottom up parsing?"

the doubt is silly but i got confused, please guide

 

0
0

 @jatin khachane 1 one more conclusion:

Using Top down, we can implement any L attribute definition based on LL(1) grammar.

Using Top down, we can also implement any L attribute definition based on LL(1) grammar.(each LL(1) is also a subset of LR(1).

In addition to the  L -attributed definitions based on LL(1)  grammars, we can implement some of the L-attributed definitions based on LR(1) g ( )grammars (not all of them ) using the bottom-up translation scheme.

 

1
1

@Shaik Masthan @jatin khachane 1

i understood ur diagram. But here also we are evaluating the inherited attributes from left to right and from top to bottom. Then how can we say that inherited attributes can be evaluated during bottom up parsing

0
0

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.

4 Comments

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