edited by
36,489 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
edited by

10 Answers

Best answer
43 votes
43 votes
  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
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 !

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.

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

32 votes
32 votes
4 answers
2
Kathleen asked Sep 17, 2014
8,458 views
Consider the syntax directed definition shown below.$$\begin{array}{ll}S \rightarrow \mathbf{ id :=} E&\qquad \{gen(\mathbf{ id}.place = E.place;);\}\\E \rightarrow E_1 +...
40 votes
40 votes
3 answers
4
Kathleen asked Sep 17, 2014
19,884 views
Consider the grammar shown below. $S \rightarrow C \ C$$C \rightarrow c \ C \mid d$This grammar isLL(1)SLR(1) but not LL(1)LALR(1) but not SLR(1)LR(I) but not LALR(1)