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

1 votes
1 votes

I’ll try to answer this. Let me know if there are any conflicts in this answer.

As every S attributed is L attributed, so if L attributed is not possible, then even S attributed is not possible. S -attributed definitions use synthesized attributes. L-attributed definitions use both inherited and synthesized attributes. S-attributed can be parsed by BUP, post order traversal, traversal of the parse-tree as S-attributes are computed from child nodes. Therefore, if the grammar is L attributed then there are possibilities that we can solve using BUP (provided it is S attributed too), while not all L attributed are solvable using BUP (as not all L attributed are S attributed). 

S-attributed uses synthesized attributes that can be traversed by BUP (True) and some L attributed definitions uses inherited (which cannot be traversed by BUP) and synthesized attributes (which can be traversed by BUP). So, option B seems to be the correct answer.

Some more info : 

  1. Inherited attributes cannot be always evaluated by a Pre-Order traversal of the parse-tree. 
  2. Inherited attributes that do not depend on the right children can be evaluated by a Pre-Order traversal.

Ref. http://cse.iitkgp.ac.in/~bivasm/notes/SDD.pdf

edited by
0 votes
0 votes
Option b.
edited by
0 votes
0 votes

 A Syntax Directed Definition (SDD) is called S Attributed if it has only synthesized attributes.

L-Attributed Definitions contain both synthesized and inherited attributes but do not need to build a dependency graph to evaluate them.

References:
http://cse.iitkgp.ac.in/~bivasm/notes/SDD.pdf

0 votes
0 votes

I think the solution can be reached using the following logic.

(1) No, it can’t be evaluated if inherits from the parent.

(3) No, because it can be evaluated if it depends upon the attributes of a left sibling which make it non-synthesized attribute.

(4) 3rd point’s logic makes this option wrong too.

Now coming to 2nd point. If it is not L-attributed then it is not even S-attributed. And we saw that there are only 2 possibilities to be able to parse in a BOTTOM-UP fashion (first is when attributes depend on the child’s attributes or when depends on a left sibling). Hence there are possibilities to be able to solve when grammar is L-attributed but not all L-attributed grammars can be solved using BUP.

Please correct me if my answer is wrong.

Answer:

Related questions

32 votes
32 votes
4 answers
2
Kathleen asked Sep 17, 2014
8,455 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,883 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)