GATE 2020 CS Q.33: solution and answer

GATE 2020 · CSQ.33 · 2 marks · MCQ

Consider the productions A → PQ and A → 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?

(A)
Both Rule 1 and Rule 2 are L-attributed.
(B)
Only Rule 1 is L-attributed.
(C)
Only Rule 2 is L-attributed.
(D)
Neither Rule 1 nor Rule 2 is L-attributed.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Only Rule 1 is L-attributed, which is option (B).

Official answer: BSource: Official answer key, GATE 2020 CS (IIT Delhi)

A definition is L-attributed if, for every production $A \to X_{1} X_{2} \dots X_{n}$ , each inherited attribute of $X_{j}$ depends only on (i) inherited attributes of $A$ and (ii) attributes (inherited or synthesized) of $X_{1}, \dots, X_{j - 1}$ , the symbols to its left. Synthesized attributes of $A$ may depend on any attribute in the body.
Rule 1, production $A \to P Q$ : $P . i = A . i + 2$ uses only the inherited attribute of the head, so it is allowed.
$Q . i = P . i + A . i$ uses $P$ , which is to the left of $Q$ , and the head's inherited attribute $A . i$ , so it is allowed.
$A . s = P . s + Q . s$ defines a synthesized attribute of the head, which may use any child. So Rule 1 is L-attributed.
Rule 2, production $A \to X Y$ : $X . i = A . i + Y . s$ makes the inherited attribute of $X$ depend on $Y . s$ , an attribute of $Y$ , which is to the right of $X$ . This violates the left-to-right condition, so Rule 2 is not L-attributed.
$Y . i = X . s + A . i$ alone would be allowed, because $X$ is to the left of $Y$ . One violation is enough to fail the definition. Together, $X . i$ needs $Y . s$ and $Y . i$ needs $X . s$ , so the dependencies are also circular.
Hence only Rule 1 is L-attributed: option (B).

KEY IDEA

In an L-attributed definition, an inherited attribute of a body symbol may use only the head's inherited attributes and attributes of symbols to its left. Never an attribute of a symbol to its right.

WATCH OUT FOR

Checking only $Y . i = X . s + A . i$ , which is legal, and ignoring that $X . i = A . i + Y . s$ looks to the right. Another slip is to think a synthesized attribute like $A . s$ is restricted in the same way.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 7 Syntax-directed translation questions, with notes

GATE 2020 CS Q.33: solution and answer

Answer and solution

More Syntax-directed translation questions