Attributes and SDT Types Interview Questions and Answers: Trace and Explain

Practise explaining attribute dependencies, tracing 4 + 7 + 2, and passing a declaration type to two identifiers. These original rehearsal questions connect definitions to evaluation order and executable actions.

KnowledgeGate Team

Exam prep & CS education

Updated 13 Nov 20265 min read
Attributes and SDT Types Interview Questions and Answers: Trace and Explain

Interviewers often ask candidates to distinguish an SDD from an SDT, trace an attribute value, and explain when a semantic action runs. These compiler-specific grammars and computed traces are original practice prompts, not reported company questions or previous-year exam questions.

What are attributes, an SDD and an SDT?

An attribute is information attached to a particular grammar-symbol occurrence. A syntax-directed definition (SDD) adds semantic equations to grammar productions. A syntax-directed translation (SDT) scheme embeds executable actions at specified positions in production bodies.

Equations describe dependencies; action positions specify execution timing. For E → num, suppose the lexer supplies num.lexval = 9. The equation E.val = num.lexval gives E.val = 9. The corresponding scheme is:

Code
E → num { E.val = num.lexval; }

The action runs after recognising num. The parser does not invent its lexical value. Also, two occurrences of E can have different values: an attribute belongs to an occurrence, not to one global variable called E. This distinction connects compiler translation to .

How do synthesized, inherited, S-attributed and L-attributed differ?

Attribute

Dependency and example

Evaluation consequence

Synthesized

Children, or permitted information at the same node: E.val = E1.val + T.val

Compute prerequisites before the parent result.

Inherited

Context through the parent's production: in D → T L, L.in = T.type

Supply the left sibling's type before processing L.

An S-attributed SDD uses only synthesized attributes. Every S-attributed SDD is L-attributed, but inherited attributes can make an L-attributed SDD non-S-attributed.

For A → X1 ... Xn, an inherited attribute of Xj may depend on inherited attributes of A and attributes of preceding siblings. It cannot read a right sibling.

L-attributed supports evaluation through a left-to-right traversal. It does not mean left-recursive and does not make an arbitrary grammar LL(1). Use the Attributes and SDT Types in Compiler Design: Worked Trace for a full 3 * 5 + 4 L-attributed evaluation, and the Semantic Analysis and Syntax-Directed Translation: Worked Examples for binary, type-propagation, and broader GATE examples. For interview practice, trace 4 + 7 + 2, pass int from D to x and y, and test the right-sibling and cycle counterexamples.

Can you evaluate a synthesized expression without guessing the order?

Use this complete grammar and its actions:

Code
E → E1 + T { E.val = E1.val + T.val; }
E → T      { E.val = T.val; }
T → num    { T.val = num.lexval; }

For 4 + 7 + 2, label the root E2. Its left child is E1 and right child is T2; E1 has E0 and T1; E0 has T0. Subscripts distinguish tree occurrences.

Once the required token values are available, one legal order is:

Step

Evaluation

1

T0.val = 4

2

E0.val = T0.val = 4

3

T1.val = 7

4

E1.val = 4 + 7 = 11

5

T2.val = 2

6

E2.val = 11 + 2 = 13

Annotated parse tree for 4 + 7 + 2, with E0.val = 4, E1.val = 11, E2.val = 13, and orange dependency arrows.

Dependency arrows point from prerequisite to result. Independent values can use another legal order; the equations' textual order does not determine it.

Must you build the whole annotated tree? No. A suitable bottom-up parser computes these synthesized values on its semantic stack during reductions. Child values are ready before each parent sum; the tree explains that computation.

Can you pass a declaration type from left to right?

For input int x, y, use D → T L, T → int and L → id , L1 | id. These actions give the complete rules and their execution positions:

Code
T → int { T.type = int; }
D → T { L.in = T.type; } L
L → id { declare(id.lexeme,L.in); } , { L1.in=L.in; } L1
L → id { declare(id.lexeme,L.in); }

Start with an empty symbol table. Compute T.type=int, copy it into outer L.in, and insert (x,int). Copy L.in into inner L1.in, then insert (y,int). The final table contains exactly x:int and y:int; no sizes or offsets are implied.

Type propagation diagram showing int reaching x and y, with declaration steps and symbol-table snapshots before and after each insertion.

declare writes a type into the symbol table. This side effect is not a synthesized attribute. The definition is L-attributed but not S-attributed because it uses inherited in attributes. Moving L1.in=L.in after L1 returns is too late: its declaration action needs that value while processing L1.

Which counterexamples expose a memorised answer?

Right-sibling trap: for A → B C, consider C.s=5, B.i=C.s, B.s=2*B.i, and A.s=B.s.

The order C.s → B.i → B.s → A.s gives 5 → 5 → 10 → 10. It is acyclic and evaluable, but not L-attributed: B inherits from right sibling C. Check dependency direction separately from circularity.

Circularity trap: for A → B, let A.s=B.i+1 and B.i=A.s+1. Substitution gives A.s=(A.s+1)+1=A.s+2, implying 0=2. There is no consistent finite integer assignment and no topological evaluation order. Reordering the equations cannot repair them.

Terminology trap: S-attributed and L-attributed classify definitions; postfix and embedded actions describe translation-scheme placement. Consider this postfix emitter:

Code
E → E1 + T { emit('+'); }
E → T
T → num { emit(num.lexval); }

For 4+7+2, T actions emit the operands, and each addition action follows its operands. The output is 4 7 + 2 +, a token sequence, not the numeric value 13.

How do you rehearse interview follow-ups and exam-style checks?

In an interview, answer in 30 or 60 seconds depending on the prompt; the timings below are practice targets, not employer rules.

  • 30 seconds: Distinguish SDD from SDT. Expected answer: semantic equations express dependencies; positioned actions specify execution timing.

  • 60 seconds: Trace 4+7+2. Name the legal order T0, E0, T1, E1, T2, E2 and explain both sums producing 13.

  • 60 seconds: Classify the right-sibling example. Reject L-attributed, while acknowledging its acyclic evaluation order and result 10.

For an implementation follow-up, explain how a recursive-descent procedure can receive in as an argument and return a synthesized result, provided the grammar is suitable.

IIT Guwahati's GATE 2026 CS syllabus includes syntax-directed translation in Section 7, Compiler Design. Classification, tracing and action placement are useful practice formats; the syllabus inclusion establishes no question frequency.

What should your final answer and next practice step contain?

Use this oral-answer sequence: define the attribute, state its prerequisites, identify a legal order, compute the result, and justify the classification. Our outcomes are sum 13, declarations x:int and y:int, and a right-sibling dependency that fails the L-attributed restriction.

Now change the final token from 2 to 5. Only T2.val becomes 5 and E2.val becomes 11+5=16; E1.val stays 11. Explain why before checking your answer. For a structured next step, explore the Compiler Design course.