Syntax-Directed Translation

Definition

Syntax-Directed Translation (SDT) attaches semantic rules/actions to grammar productions, so that as a parse tree is built (or traversed), useful computations — type checking, code generation, value evaluation — happen alongside parsing.

Key Points

• Synthesized attributes: value at a node computed from its children's attribute values (flows bottom-up the parse tree). E.g., the value of an expression computed from its sub-expressions.
• Inherited attributes: value at a node computed from its parent/siblings (flows top-down or left-to-right). E.g., passing a declared type down to each variable in a declaration list.
• Syntax tree construction: an abstract, compact version of the parse tree — omits redundant grammar detail (e.g., collapses unary productions), keeping only operationally significant nodes.
• Top-down translation: attribute evaluation combined with a top-down (LL) parse — works well when all attributes are synthesized, or when inherited attributes only depend on already-computed values (L-attributed definitions).
• S-attributed vs L-attributed grammars: S-attributed uses only synthesized attributes (evaluable in a single bottom-up pass); L-attributed allows inherited attributes evaluated left-to-right (compatible with top-down parsing).

Example

For E → E1 + T { E.val = E1.val + T.val }, E.val is a synthesized attribute computed from its children E1.val and T.val.

For declarations D → T L { L.type = T.type }, L.type is inherited from the parent's T.type.

📌 CSS Frequency: High — "differentiate synthesized vs inherited attributes with an example" is a repeated question.

Model Answer (short)

"In syntax-directed translation, synthesized attributes are computed from a node's children and flow bottom-up (e.g., an expression's value from its operands), while inherited attributes are computed from a node's parent or siblings and flow top-down or left-to-right (e.g., a declared type passed down to each identifier in a list). S-attributed grammars use only synthesized attributes and suit bottom-up parsing, while L-attributed grammars allow restricted inherited attributes and suit top-down parsing."

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2023 · Paper-I · Q8(a) · 8 marks

Q. Discuss the role of a syntax tree in representing formal text structure. Develop a syntax tree for: while b ≠ 0: if a > b then a = a − b else b = b − a; return a.

Ans.

• Role of a syntax tree (abstract syntax tree): it shows the structure of the program with only the meaningful parts. Operators and statements are internal nodes, and operands are leaves. Brackets and punctuation are left out. The compiler uses it for semantic checking, optimisation and code generation.
• Syntax tree for the code:

          SEQUENCE
         /        \
     WHILE        RETURN
    /     \          |
 (≠)      IF         a
 / \     / | \
b   0  (>) (=) (=)
       /\   /\   /\
      a  b a (−) b (−)
              /\      /\
             a  b    b  a

• Reading it: WHILE has two children, the condition (b ≠ 0) and the body. The body is an IF with the condition (a > b), a "then" assignment a = a − b and an "else" assignment b = b − a. After the loop, return a is executed.