High yield ●●●

🧮 Syntax-Directed Translation

Why it matters: Evaluating attributes on a parse tree and classifying S/L-attributed definitions are regular marks.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 5 done.

Formulas

S-attributed ⊂ L-attributed
every S-attributed SDD is also L-attributed
L-attributed rule
for A → X1 … Xn, inherited Xi.a may use only A.inherited and attributes of X1 … X(i−1)
Synthesized rule
A.s = f(attributes of the children of A and A.inherited)
Evaluation order
topological order of the dependency graph (acyclic required)

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Evaluate an attributed parse tree
Compute the final value at the root for a given SDD and input; or the output printed by a translation scheme.
★★★
Classify S-attributed / L-attributed
Decide whether given semantic rules are S-attributed, L-attributed, or neither.
★★★
Postfix / output of translation scheme
Order of print statements for an expression.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

9 real questions from the official GATE CSE papers (2016 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

9 questions · 0 correct of 0 attempted · marks 0 / 16

Year:
GATE 2025 CS2 · Q22MCQ1 mark
Given the following syntax directed translation rules: Rule 1: R → A B {B.i = R.i − 1; A.i = B.i; R.i = A.i + 1}. Rule 2: P → C D {P.i = C.i + D.i; D.i = C.i + 2}. Rule 3: Q → E F {Q.i = E.i + F.i}. Which ONE is the CORRECT option?
GATE 2024 CS2 · Q29MSQ1 mark
Which of the following statements is/are FALSE?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS1 · Q37MCQ2 marks
Consider the syntax-directed definition:
S → D H T U {S.val = D.val + H.val + T.val + U.val}
D → "M" D₁ {D.val = 5 + D₁.val}
D → ε {D.val = −5}
H → "L" H₁ {H.val = 5*10 + H₁.val}
H → ε {H.val = −10}
T → "C" T₁ {T.val = 5*100 + T₁.val}
T → ε {T.val = −5}
U → "K" {U.val = 5}
Given "MMLK" as input, the value computed by the SDD in S.val is
GATE 2023 · Q60NAT2 marks
Consider the syntax directed translation:
N → I # F {N.val = I.val + F.val}
I → I₁ B {I.val = 2·I₁.val + B.val}
I → B {I.val = B.val}
F → B F₁ {F.val = ½(B.val + F₁.val)}
F → B {F.val = ½·B.val}
B → 0 {B.val = 0}
B → 1 {B.val = 1}
N is the start symbol, and #, 0, 1 are tokens. The value computed by the translation scheme for the input string 10#011 is ______ (rounded off to three decimal places).
GATE 2022 · Q65NAT2 marks
Consider the grammar with translation rules:
S → S₁ # T {S.val = S₁.val * T.val}
S → T {S.val = T.val}
T → T₁ % R {T.val = T₁.val ÷ R.val}
T → R {T.val = R.val}
R → id {R.val = id.val}
Here # and % are operators and id is a token representing an integer. The computed value of S.val for the root of the parse tree for the expression 20#10%5#8%2%2 is ______.
GATE 2021 Set 1 · Q26MCQ2 marks
Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pseudo-code:
P → D* E*
D → int ID {record that ID.lexeme is of type int}
D → bool ID {record that ID.lexeme is of type bool}
E → E₁ + E₂ {check that E₁.type = E₂.type = int; set E.type := int}
E → !E₁ {check that E₁.type = bool; set E.type := bool}
E → ID {set E.type := int}
With respect to the above grammar, which one of the following choices is correct?
GATE 2020 · Q33MCQ2 marks
Consider the productions A → PQ and A → XY. 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, Q.i = P.i + A.i, and A.s = P.s + Q.s. Rule 2: X.i = A.i + Y.s and Y.i = X.s + A.i. Which one of the following is TRUE?
GATE 2019 Set 2 · Q36MCQ2 marks
Consider the following grammar and semantic actions to support inherited type declaration attributes. Let X1, X2, X3, X4, X5 and X6 be the placeholders for the non-terminals D, T, L or L1 in the following table. D → T L: X1.type = X2.type. T → int: T.type = int. T → float: T.type = float. L → L1 , id: X3.type = X4.type; addType(id.entry, X5.type). L → id: addType(id.entry, X6.type). Which one of the following are the appropriate choices for X1, X2, X3 and X4?
GATE 2016 Set 1 · Q46MCQ2 marks
Consider the following Syntax Directed Translation Scheme (SDTS), with non-terminals {S, A} and terminals {a, b}:
S → aA {print 1}
S → a {print 2}
A → Sb {print 3}
Using the above SDTS, the output printed by a bottom-up parser, for the input aab is:

Common traps

An inherited attribute that uses a right sibling breaks L-attribution.
Terminals only have synthesized attributes (from the lexer).
Actions in a bottom-up parser run at reduce time.