What are common examiner traps in Syntax-Directed Translation?

Right-to-left attribute dependency: Overlooking that an inherited attribute of an RHS symbol depends on an attribute from a symbol to its right (invalidating L-attributed property). Parent synthesized attribute misuse: Mistaking an inherited attribute dependent on parent's synthesized attribute as L-attributed. Left vs. Right recursion evaluation order: In computing numerical values, confusing left-recursive accumulation (e.g. integer building: 2 I1.val + B.val) with right-recursive fraction accumulation (e.g. (B.val + F1.val)/2). Execution order of actions in bottom-up parsers: Forgetting that actions inside or at the end of productions execute strictly upon reduction, not upon shifting tokens. Bypassing symbol table lookup: Assuming an SDT correctly type-checks identifiers when base productions hardcode attributes rather than querying the symbol table.

Syntax-Directed Translation

9 Qs · since 2016 · 16 marks · 0.6 marks/paperStandard yield

Take topic test

Syntax-Directed Translation (SDT/SDD) in GATE CS is consistently tested through two primary angles: theoretical classification (identifying S-attributed vs. L-attributed definition… Guide

Type

GATE CSE 2026 Set 1Q53MSQ2 marksMediumDiagramConsider the following two syntax-directed definitions SDD1 and SDD2 for type declarations. $D$ is the start symbol, and $int$ , $float$ and $id$ are the three terminals. The non-terminal $V_1$ is the same as $V$ and the non-terminal $D_1$ is the same as $D$ . Here, the subscript is used to…
GATE CSE 2025 Set 2Q22MCQ1 markMediumGiven the following syntax directed translation rules: Rule 1: $R \to AB \{B.i = R.i - 1; A.i = B.i; R.i = A.i + 1;\}$ Rule 2: $P \to CD \{P.i = C.i + D.i; D.i = C.i + 2;\}$ Rule 3: $Q \to EF \{Q.i = E.i + F.i;\}$ Which ONE is the CORRECT option among the following?
GATE CSE 2024 Set 1Q37MCQ2 marksMediumDiagramConsider the following syntax-directed definition (SDD). Given "MMLK" as the input, which one of the following options is the CORRECT value computed by the SDD (in the attribute $S.val$ )?
GATE CSE 2024 Set 2Q29MSQ1 markMediumWhich of the following statements is/are FALSE?
GATE CSE 2023Q60NAT2 marksMediumConsider the syntax directed translation given by the following grammar and semantic rules. Here $N, I, F$ and $B$ are non-terminals. $N$ is the starting non-terminal, and $\#$ , $\mathbf{0}$ and $\mathbf{1}$ are lexical tokens corresponding to input letters “#”, “0” and “1”, respectively. $X.val$ denotes…
GATE CSE 2022Q65NAT2 marksMediumConsider the following grammar along with translation rules. $\begin{array}{ll} S \rightarrow S_1 \text{ \# } T & \{S_{\bullet val} = S_{1\bullet val} * T_{\bullet val}\} S \rightarrow T & \{S_{\bullet val} = T_{\bullet val}\} T \rightarrow T_1 \% R & \{T_{\bullet val} = T_{1\bullet val} \div R_{\bullet val}\} T \rightarrow R & \{T_{\bullet val} = R_{\bullet val}\} R \rightarrow id & \{R_{\bullet val} = id_{\bullet val}\} \end{array}$ …
GATE CSE 2021 Set 1Q26MCQ2 marksMediumConsider 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 \rightarrow D^* E^*$ $D \rightarrow \text{int } \text{ID } \{\text{record that } \text{ID.lexeme} \text{ is of type int}\}$ $D \rightarrow \text{bool } \text{ID } \{\text{record that } \text{ID.lexeme} \text{ is of type bool}\}$ …
GATE CSE 2020Q33MCQ2 marksMediumConsider the productions $\text{A} \rightarrow \text{PQ}$ and $\text{A} \rightarrow \text{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$ …
GATE CSE 2016 Set 1Q46MCQ2 marksMediumConsider the following Syntax Directed Translation Scheme (SDTS), with non-terminals $\{S, A\}$ and terminals $\{a, b\}$ . $\begin{aligned} S & \longrightarrow aA & \{\text{ print } 1 \} S & \longrightarrow a & \{\text{ print } 2 \} A & \longrightarrow Sb & \{\text{ print } 3 \} \end{aligned}$ Using the above…

Topic guide

What does GATE test in Syntax-Directed Translation?

Syntax-Directed Translation (SDT/SDD) in GATE CS is consistently tested through two primary angles: theoretical classification (identifying S-attributed vs. L-attributed definitions and parser traversal compatibility) and concrete evaluation (tracing attribute evaluation or action execution for a given input string). Questions routinely evaluate precedence, associativity, base conversions (e.g., binary fractions), type checking, or parse-reduction action sequences.

Core concepts

Synthesized vs. Inherited attributes
S-attributed SDDs (purely synthesized, bottom-up evaluable during parsing)
L-attributed SDDs (dependency on parent inherited attributes and left-sibling attributes)
Bottom-up reduction order and semantic action firing
Operator precedence and associativity encoded in recursive grammar structures
Type synthesis and inherited type distribution across declaration lists into symbol tables
Depth-first / Left-to-right evaluation traversals and dependency graphs

Recurring question patterns

Attribute Classification (S-attributed vs. L-attributed)
common · MCQ · 1.5 marks · 2026, 2025, 2020
Given a set of production rules paired with attribute assignment equations, determine whether each rule or the overall SDD is S-attributed, L-attributed, or neither based on attribute dependencies.
Input String Evaluation / Attribute Value Computation
common · NAT · 2 marks · 2024, 2023, 2022
Given an SDD defining synthesized (and optionally inherited) numerical or structural values, construct the parse tree for a specific input string and compute the final synthesized attribute at the root.
Side-Effect / Bottom-Up Parsing Action Sequence
occasional · MCQ · 2 marks · 2016
Given an SDTS with inline print statements or symbol table updates, trace the execution sequence triggered during shift-reduce parsing (post-order reductions) of an input token stream.
Semantic Analysis & Type Checking Correctness
occasional · MSQ · 2 marks · 2026, 2021
Evaluate multi-rule SDTs for language equivalence, type declarations, or semantic actions to identify logic bugs (e.g., missing symbol-table lookup vs. hardcoded types) or compare equivalent semantic schemes.
Theoretical SDD Properties & Traversal MSQ
occasional · MSQ · 1 marks · 2024
Multi-statement questions testing foundational definitions: evaluation order (depth-first/left-to-right), LR(1) bottom-up evaluation capabilities, and side effects in attribute grammars.

Formulas GATE uses

S-Attributed Definition Condition

$A.s = f(X_1.a, X_2.a, \dots, X_n.a)$ for production $A \to X_1 X_2 \dots X_n$

Used when verifying that an SDD contains only synthesized attributes computed exclusively from children nodes.

L-Attributed Dependency Rule

$X_j.i = f(A.i, X_1.a, X_2.a, \dots, X_{j-1}.a)$ for production $A \to X_1 X_2 \dots X_n$

Used when checking whether inherited attributes of an RHS symbol $X_j$ depend strictly on parent inherited attributes or attributes of symbols strictly to its left ( $X_1 \dots X_{j-1}$ ).

Binary Fractional Synthesis Recurrence

F.val = \frac{1}{2}(B.val + F_1.val)

Used during bottom-up synthesized evaluation of right-recursive fractional bit strings.

Examiner traps in Syntax-Directed Translation

Right-to-left attribute dependency: Overlooking that an inherited attribute of an RHS symbol depends on an attribute from a symbol to its right (invalidating L-attributed property).
Parent synthesized attribute misuse: Mistaking an inherited attribute dependent on parent's synthesized attribute as L-attributed.
Left vs. Right recursion evaluation order: In computing numerical values, confusing left-recursive accumulation (e.g. integer building: 2 I1.val + B.val) with right-recursive fraction accumulation (e.g. (B.val + F1.val)/2).
Execution order of actions in bottom-up parsers: Forgetting that actions inside or at the end of productions execute strictly upon reduction, not upon shifting tokens.
Bypassing symbol table lookup: Assuming an SDT correctly type-checks identifiers when base productions hardcode attributes rather than querying the symbol table.

How questions are asked

Classify grammar rules as S-attributed, L-attributed, or neither
Compute root attribute value (NAT) for a given arithmetic/binary token stream
Trace print action output sequence during bottom-up parsing
Identify true/false theoretical statements about SDDs and traversals (MSQ)
Compare two translation schemes for language and symbol-table equivalence

Paper trends

Shift from pure single-answer bottom-up print tracing to deep attribute computations (custom arithmetic, fractional conversions) formatted as numerical answer type (NAT).
2023, 2022, 2016
Rise of multi-select questions (MSQ) testing conceptual nuance (e.g., L-attributed traversals, grammar equivalence, symbol table operations).
2026, 2024
Formalization of classification questions into multi-rule dependency checks assessing LHS-to-RHS and RHS-sibling dependency directions.
2025, 2020

Difficulty notes

Easy: Direct syntactic check of single-rule attribute dependencies (S vs. L-attributed). Medium: Tracing numerical value computations with operator precedence/associativity or fractional recursions; tracing reduction-action sequences. Hard: Multi-grammar comparisons evaluating symbol table side effects alongside formal attribute classifications in an MSQ format.