GATE CS 2025 Set 2 | Question 22

MCQ · 1 mark · −0.33

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?

  1. Option 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
  2. Option 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
  3. Option 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 (correct)
  4. Option 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

Answer

(C)

Explanation

A definition is S-attributed if it uses only synthesized attributes. It is L-attributed if each inherited attribute of a body symbol depends only on inherited attributes of the head and on attributes of symbols to its left. Every S-attributed definition is also L-attributed.

  • Rule 1: \(A.i\) and \(B.i\) are inherited, so it is not S-attributed. \(A.i = B.i\) takes its value from \(B\), which lies to the right of \(A\), so it is not L-attributed either. The rules are even circular: \(R.i\) needs \(A.i\), which needs \(B.i\), which needs \(R.i\).
  • Rule 2: \(D.i = C.i + 2\) is inherited, so it is not S-attributed, but it uses only the left sibling \(C\), so it is L-attributed.
  • Rule 3: only the synthesized \(Q.i\) is computed, so it is S-attributed and therefore L-attributed.

Answer: C