GATE CS 2020 Q.43 (CS Q.33): Syntax-Directed Translation

Consider the productions $A \to P Q$ and $A \to X Y$ . 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,\quad Q.i = P.i + A.i,\quad A.s = P.s + Q.s$
Rule 2: $X.i = A.i + Y.s,\quad 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.

Official answer and solution

Official answer: B
From: Official GATE 2020 answer key

Solution

Check attribute dependencies against the definition of L-attributed definition.

Definition of L-attributed syntax-directed definition (SDD):

In every production $A \to X_1 X_2 \dots X_n$ $A \to X_{1} X_{2} \dots X_{n}$ , each inherited attribute of $X_j$ $X_{j}$ may depend only on:
1. Inherited attributes of the parent $A$ .
2. Any attributes of symbols to the left of $X_j$ (i.e., $X_1, \dots, X_{j-1}$ ).
Synthesized attributes of $A$ may depend on any attributes of $A$ and its children.

Analysis of Rule 1:

$P.i = A.i + 2$ : Inherited attribute $P.i$ depends on parent's inherited attribute $A.i$ . (Valid)
$Q.i = P.i + A.i$ : Inherited attribute $Q.i$ depends on left sibling's attribute $P.i$ and parent's $A.i$ . (Valid)
$A.s = P.s + Q.s$ : Synthesized attribute $A.s$ depends on children's synthesized attributes. (Valid)
Thus, Rule 1 is L-attributed.

Analysis of Rule 2:

Production $A \to X Y$ .
$X.i = A.i + Y.s$ : Inherited attribute $X.i$ of symbol $X$ depends on $Y.s$ , an attribute of symbol $Y$ which appears to the right of $X$ .
Dependencies on right siblings are strictly prohibited in L-attributed grammars.
Thus, Rule 2 is NOT L-attributed.

Therefore, only Rule 1 is L-attributed.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2020 Computer Science and Information Technology (CS)
Question: 43 of 65, printed as CS Q.33
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source