GATE CS 2025 Set 2 Q.22: Syntax-Directed Translation

Given the following syntax directed translation rules:

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

Which ONE is the CORRECT option among the following?

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

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

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

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

Official answer and solution

Official answer: C
From: Official GATE 2025 answer key

Solution

Check each rule against the definitions of S-attributed (only synthesized attributes) and L-attributed (inherited attributes depend only on parent or left siblings).

Rule 1: Computes attributes of RHS symbols $A.i$ and $B.i$ (so it is not S-attributed), and $A.i = B.i$ depends on $B$ , which is to the right of $A$ in $R \rightarrow AB$ (so it is not L-attributed).
Rule 2: Computes $D.i = C.i + 2$ , which is an inherited attribute of RHS symbol $D$ (so it is not S-attributed). Since $D.i$ depends only on its left sibling $C.i$ , and $P.i$ is a synthesized attribute of the LHS symbol $P$ , Rule 2 is L-attributed.
Rule 3: Computes only the synthesized attribute $Q.i$ of the LHS symbol from the attributes of its children $E$ and $F$ . Hence Rule 3 is both S-attributed and L-attributed.

Final answer

Option (C)

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

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 22 of 65
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