5,359 views

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?

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

Ref: Taken from Ullman.

@arjun sir, @

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

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

In L-attributed definitions,

1.  A parent can take its attribute values from any child (which is $S-$attributed and Every $S-$attributed is also $L-$Attributed).
2.  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?

@jiminpark

what is the significance of $X.i$ and $X.s$ ( difference between  $X.i$ and $X.s$)

$X.i$ is inherited attribute  and $X.s$ is synthesized attribute.

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)

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.

Yeah...you're right...when used to L-attributed definition...then inheriting from right sibling is not allowed