8.6k 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

edited | 8.6k 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
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 ??
0
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

@sripo

check my comment on the answer of arjun sir

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

by Veteran (425k 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 ???
not able to understand??
+2
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.

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

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.

+1
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

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

@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??

+2
yes
+2
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..
0

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

@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

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

0

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

sir the evaluation which you showed in the parse tree is depth first traversal only then how is it bottom up parsing. @Shaik Masthan

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.

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 !

by Boss (41.5k 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..

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

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

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

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.

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

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?
Ans: B

In bottom-up parser inherited from the parent isn't possible.but inherited from the left child is possible in L-attributed
by (93 points)

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.

ago by Active (5.2k points)
–1 vote
Option b.
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..