GATE CSE 2003 | Question: 18

Question

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

• A. always be evaluated
• B. be evaluated only if the definition is L-attributed
• C. be evaluated only if the definition has synthesized attributes
• D. never be evaluated

Comments

@Shaik Masthan @Arjun 
@Deepak Poonia
Sir, plz clear some doubts:

 
1. Can we say, L-Attributed SDD is parsed by BUP only if there is Synthesized attribute? 

2. What parsing is used for L-attributed SDD if it only contains restricted Inherited attribute?

3. Since, Inherited attribute can't be parsed by BUP, then What parsing is used for L-attributed SDD if it contains both restricted Inherited attribute and Synthesized attribute?

4. Can we use LL parser for Bottom up Evaluation? 
5. S-attributed is always Parsed by BUP?

 

PS: BUP = Bottom up Parser

---

The options are not consistent with the options in practice paper website.

be evaluated only if the definition is L-attributed

This option should be  "be evaluated only if the definition is L-attributed"

Even Ullman distinguishes between "single bottom up parse" and "bottom up parse" and it's mentioned in the book.
This question is only about dependency graphs, and any attribute grammar having no dependency cycle can be evaluated using a bottom-up parser in atmost 2 parses.

And even if we suppose that the questionnaire is asking about "single bottom up parse" then also option B is false.
Because L-Attributed SDD's on LR grammars cannot be computer in a single bottom up parse. (Ullman second edition, section 5.5.3, page 348 has a simple proof)

Only if we remove parent - child inherited attributes, then we can parse L-attributed grammar in single parse. But this too can't be parsed in a single parse if translation schemes are introduced. An example of this is in Ullman section 5.4.3 page 327 Figure 5.21

Further readings in Ullman section 5.4 and 5.5

The original question paper is not available on IIT Madras page and other websites also have the same misprint of "only"
Practicepaper.in had the correct option.

Please update the option B @gatecse

---

All questions related to Syntax Directed Definitions(SDD):

Compiler Design: GATE CSE 1992 | Question: 11a

Compiler Design: GATE CSE 2003 | Question: 18

Compiler Design: GATE CSE 2003 | Question: 59

Compiler Design: GATE CSE 2019 | Question: 36

Compiler Design: GATE CSE 2020 | Question: 33

Compiler Design: GATE CSE 2024 | Set 1 | Question: 27

Compiler Design: GATE CSE 2024 | Set 2 | Question: 19

Compiler Design: GATE CSE 2025 | Set 2 | Question: 12

Answer 1

In the context of syntax-directed definitions (SDDs) and their evaluation during parsing, the question revolves around the evaluation of inherited attributes in a bottom-up parsing approach. Let's delve into the specifics:

Syntax-Directed Definitions (SDDs)

1. Synthesized Attributes: These are attributes of a non-terminal that are computed from the attributes of its children in the parse tree. They naturally fit the bottom-up parsing model since they are evaluated after the children are processed.

1. Inherited Attributes: These are attributes of a non-terminal that are computed from the attributes of its parent or siblings. Evaluating these in a bottom-up manner can be challenging because they often rely on information that is not available until after the non-terminal is processed.

L-Attributed Definitions

An SDD is termed L-attributed if each inherited attribute of a non-terminal can be computed using the attributes of its siblings to the left and its parent. This structure allows for a left-to-right evaluation that aligns with top-down parsing strategies, such as LL parsing.

Bottom-Up Parsing

In bottom-up parsing, such as LR parsing, the parse tree is constructed from the leaves (tokens) to the root. This approach is inherently suitable for evaluating synthesized attributes, as each node's attributes can be computed from its children as they are reduced.

Evaluation of Inherited Attributes in Bottom-Up Parsing

• Always Be Evaluated: This is incorrect because inherited attributes depend on context that may not be available in a bottom-up approach unless specific conditions are met.

• Evaluated Only If the Definition is L-Attributed: This is the correct answer. L-attributed definitions allow inherited attributes to be evaluated in a way that can be adapted to bottom-up parsing, provided that the dependencies are such that they can be resolved during the reduction process.

• Evaluated Only If the Definition Has Synthesized Attributes: This is incorrect because synthesized attributes do not directly affect the evaluation of inherited attributes. They are evaluated independently in a bottom-up manner.

• Never Be Evaluated: This is incorrect because there are cases, specifically with L-attributed grammars, where inherited attributes can indeed be evaluated in a bottom-up parser.

Conclusion

In a bottom-up evaluation, inherited attributes can be evaluated only if the syntax-directed definition is L-attributed. This is because L-attributed grammars ensure that the dependencies needed for computing inherited attributes can be resolved in a manner compatible with the bottom-up parsing process. However, it is important to note that not all L-attributed grammars can be efficiently parsed bottom-up, but if an SDD allows for such parsing, it is necessarily L-attributed.

 

Ref: http://infolab.stanford.edu/~ullman/dragon/slides2.pdf
https://gateoverflow.in/?qa=blob&qa_blobid=14587629398289520039

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

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

---

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

---

Gupta731

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.

 

Answer 2

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' -> *FT₁' | T₁'.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 !

Comments

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

 if the definition has only synthesized attributes.

am i right??

---

Yes,if it has only synthesized then no chance of cycles.

---

We can evaluate l-attributed sdt using bottom up parsing..

https://cs.stackexchange.com/questions/67956/bottom-up-evaluation-of-inherited-attributes

Answer 3

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.

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

---

option C can not be answer because even if defination contains synthesized attributes bottom up  evaluation of inherited attributes is not possible.

---

'has only synthesized attributes'..then option C would be correct,right?

Answer 4

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

Comments

Nice :)

Answer 5

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 6

Option b.

Comments

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?

---

L-r attributed grammar can evaluate inherited attributes using bottom up parsing.

---

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