GATE 2025 CS2 Q.22: solution and answer

GATE 2025 · CS2Q.22 · 1 mark · MCQ

Given the following syntax directed translation rules:

Rule 1: $R \to A B$ { $B . i = R . i - 1$ ; $A . i = B . i$ ; $R . i = A . i + 1$ ; }
Rule 2: $P \to C D$ { $P . i = C . i + D . i$ ; $D . i = C . i + 2$ ; }
Rule 3: $Q \to E F$ { $Q . i = E . i + F . i$ ; }

Which ONE is the CORRECT option among the following?

(A)
Rule 1 is S-attributed and L-attributed; Rule 2 is S-attributed and not L-attributed; Rule 3 is neither S-attributed nor L-attributed
(B)
Rule 1 is neither S-attributed nor L-attributed; Rule 2 is S-attributed and L-attributed; Rule 3 is S-attributed and L-attributed
(C)
Rule 1 is neither S-attributed nor L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed
(D)
Rule 1 is S-attributed and not L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Option (C): Rule 1 is neither S-attributed nor L-attributed; Rule 2 is not S-attributed but is L-attributed; Rule 3 is both S-attributed and L-attributed.

Official answer: CSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

An SDD is S-attributed if every attribute is synthesized, so each value depends only on attributes of the node's children. It is L-attributed if each inherited attribute of a right-hand-side symbol depends only on the inherited attributes of the parent and on attributes of symbols to its left in the production.
Rule 1, $R \to A B$ : $B . i = R . i - 1$ defines an attribute of the right-hand-side symbol $B$ , so $B . i$ is inherited and the rule is not S-attributed. Also $A . i = B . i$ defines the inherited $A . i$ from $B . i$ , and $B$ lies to the right of $A$ . This violates the L-attributed condition. So Rule 1 is neither S-attributed nor L-attributed.
Rule 2, $P \to C D$ : $P . i = C . i + D . i$ defines an attribute of the left-hand side from its children, so it is synthesized. $D . i = C . i + 2$ defines an attribute of the right-hand-side symbol $D$ , so it is inherited. It depends only on $C$ , which lies to the left of $D$ , so the L-attributed condition holds. The rule is L-attributed but not S-attributed, because it has an inherited attribute.
Rule 3, $Q \to E F$ : the only definition is $Q . i = E . i + F . i$ , which is synthesized from the children. So Rule 3 is S-attributed. Every S-attributed definition is also L-attributed, because it has no inherited attributes to constrain. So Rule 3 is both.
Summary: Rule 1 is neither, Rule 2 is not S-attributed but is L-attributed, and Rule 3 is both S-attributed and L-attributed. This is option (C). Option (A) is wrong about Rule 1 and Rule 3. Option (B) is wrong about Rule 2. Option (D) is wrong about Rule 1.

KEY IDEA

Classify each attribute by where it is defined. If it sits on the left-hand side and is computed from the children, it is synthesized. If it sits on a right-hand-side symbol, it is inherited. S-attributed means no inherited attributes. L-attributed means every inherited attribute uses only the parent's inherited attributes and attributes of symbols to its left. S-attributed implies L-attributed.

WATCH OUT FOR

Treating $A . i = B . i$ as harmless because it looks like a simple copy. $A . i$ is inherited, and $B$ is to the right of $A$ , so the rule breaks the left-to-right dependency condition. Another slip is forgetting that a rule with any inherited attribute cannot be S-attributed, which wrongly makes Rule 2 S-attributed.

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

GATE 2025 CS2 Q.22: solution and answer

Answer and solution

More Syntax-directed translation questions