GATE CS Syntax Directed Translation Previous Year Questions

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?

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

Explanation

Answer: (C)

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

GATE CS 2024 Set 1 | Question 37

MCQ · 2 marks · −0.66

Consider the following syntax-directed definition (SDD).

\({S \to DHTU}\)	\(\{\ S.\mathit{val} = D.\mathit{val} + H.\mathit{val} + T.\mathit{val} + U.\mathit{val};\ \}\)
\({D \to \text{``M''}D_{1}}\)	\(\{\ D.\mathit{val} = 5 + D_{1}.\mathit{val};\ \}\)
\({D \to \epsilon}\)	\(\{\ D.\mathit{val} = -5;\ \}\)
\({H \to \text{``L''}H_{1}}\)	\(\{\ H.\mathit{val} = 5 * 10 + H_{1}.\mathit{val};\ \}\)
\({H \to \epsilon}\)	\(\{\ H.\mathit{val} = -10;\ \}\)
\({T \to \text{``C''}T_{1}}\)	\(\{\ T.\mathit{val} = 5 * 100 + T_{1}.\mathit{val};\ \}\)
\({T \to \epsilon}\)	\(\{\ T.\mathit{val} = -5;\ \}\)
\({U \to \text{``K''}}\)	\(\{\ U.\mathit{val} = 5;\ \}\)

Given "MMLK" as the input, which one of the following options is the CORRECT value computed by the SDD (in the attribute \(S.\mathit{val}\))?

45 50 55 65

Explanation

Answer: (A)

For "MMLK", the rule \(S \to DHTU\) uses \(D\) for "MM", \(H\) for "L", \(T\) for the empty string and \(U\) for "K". Evaluating the attributes bottom-up:

\(D\): the innermost \(D \to \epsilon\) gives \(-5\), then \(5 + (-5) = 0\), then \(5 + 0 = 5\).
\(H\): \(H \to \epsilon\) gives \(-10\), then \(5 * 10 + (-10) = 40\).
\(T \to \epsilon\) gives \(-5\), and \(U\) gives 5.

So \(S.\mathit{val} = 5 + 40 + (-5) + 5 = 45\). Ignoring the negative values of some of the \(\epsilon\)-productions leads to the other options, 50, 55 or 65.

Answer: A

GATE CS 2024 Set 2 | Question 29

MSQ · 1 mark

Which of the following statements is/are FALSE?

An attribute grammar is a syntax-directed definition (SDD) in which the functions in the semantic rules have no side effects The attributes in a L-attributed definition cannot always be evaluated in a depth-first order Synthesized attributes can be evaluated by a bottom-up parser as the input is parsed All L-attributed definitions based on LR(1) grammar can be evaluated using a bottom-up parsing strategy

Explanation

Answer: (B), (D)

The question asks for the false statements.

A is true. That is the usual definition: the semantic rules of an attribute grammar just compute attribute values, without printing, updating tables or other side effects.
B is false. In an L-attributed definition an inherited attribute depends only on the parent and on siblings to its left, so a single left-to-right depth-first traversal always works, computing inherited attributes on the way down and synthesized ones on the way up.
C is true. An LR parser computes a synthesized attribute when it reduces by a production, keeping the values on its stack.
D is false. Inserting marker nonterminals to compute inherited attributes is guaranteed to work for LL grammars, but in an LR(1) grammar the markers can create parsing conflicts, so not every such definition can be evaluated bottom-up.

Answer: B, D