Ref: Taken from Ullman.

Dark Mode

5,359 views

10 votes

Consider the productions $A \rightarrow PQ$ and $A \rightarrow XY$. Each of the five non-terminals $A, P, Q, X,$ and $Y$ has two attributes: $s$ is a synthesized attribute, and $i$ is an inherited attribute. Consider the following rules.

- Rule $1: P . i = A.i + 2, \: Q.i = P. i + A.i,$ and $A.s = P.s +Q. s$
- Rule $2: X.i = A.i + Y.s$ and $Y. i = X. s +A .i$

Which one of the following is TRUE?

- Both Rule $1$ and Rule $2$ are $L$-attributed.
- Only Rule $1$ is $L$-attributed.
- Only Rule $2$ is $L$-attributed.
- Neither Rule $1$ nor Rule $2$ is $L$-attributed.

@arjun sir, @Tuhin Dutta

If rule number 1’s 2^{nd} rule would have been modified to $Q.i = P. i + A.s$ then option D would have been correct. Right?

0

edited
Nov 13, 2021
by ankit3009

Yes, @reboot. Because then for production A → PQ , the rule :

Q.i = P.i+A.s

Here, when assigning to Q, A and P must be of attribute type → inherited attribute.

Also, if for production A → XY , Rule 2 : 1] X.i = A.i + Y.s and 2] Y.i = X.s + A.i ,

Here, if 1] would be :- X.i = A.i , it won’t work even if it’s X.i = A.i + Y.i because especially in L attributed … the inherited attributes consider only left siblings, so here Y is present to the right of X in the given production, so Y would be ignored by X;

and

2] would be :- Y.i = X.i + A.i then option A would have been correct. Please correct if I am wrong.

Q.i = P.i+A.s

Here, when assigning to Q, A and P must be of attribute type → inherited attribute.

Also, if for production A → XY , Rule 2 : 1] X.i = A.i + Y.s and 2] Y.i = X.s + A.i ,

Here, if 1] would be :- X.i = A.i , it won’t work even if it’s X.i = A.i + Y.i because especially in L attributed … the inherited attributes consider only left siblings, so here Y is present to the right of X in the given production, so Y would be ignored by X;

and

2] would be :- Y.i = X.i + A.i then option A would have been correct. Please correct if I am wrong.

0

14 votes

Best answer

Answer : B.

**In L-attributed definitions,**

- A parent can take its attribute values from any child (which is $S-$attributed and Every $S-$attributed is also $L-$Attributed).
- A child can take its attribute values from the parent as well as from any left sibling but not from any right sibling.

Based on these properties, only Rule-1 is $L-$attributed.

**Rule-2 is failed** for the production $A \to XY,$ and defintion $X.i =A.i +Y.s$ since $X$ take value from its sibling $Y,$ which is present in its right in the production.

@Anshul999 Sir, what is the significance of X.i and X.s ( difference between any X.i and X.s) or can we just consider it similar while finding Attributed definitions as in this question?

Please tell !

1

1 vote

L-attributed definition: it can synthesized or inherited type.

Synthesized: An attribute can take values from its children.

Inherited: an attribute can take values from its siblings.

But, the condition is inherited attribute can take values only from the parent or left sibling. Strictly not from right sibling

In Rule1: all are following conditions of L-attributed grammer.

In Rule2: X.i = A.i + Y.s ( given production is A-->XY )

An attriubte is taking values from its right sibling. Therefore not L-attributed.

Therefore Ans : (B)

Synthesized: An attribute can take values from its children.

Inherited: an attribute can take values from its siblings.

But, the condition is inherited attribute can take values only from the parent or left sibling. Strictly not from right sibling

In Rule1: all are following conditions of L-attributed grammer.

In Rule2: X.i = A.i + Y.s ( given production is A-->XY )

An attriubte is taking values from its right sibling. Therefore not L-attributed.

Therefore Ans : (B)

But, the condition is inherited attribute can take values only from the parent or left sibling. Strictly not from right sibling

No, there is a twist. Inherited attribute can take value from it's parent and all siblings(left or right). But when this inherited attribute is used in L-attributed definition then, it can take value only from it's left siblings, not from the right siblings.

2