GATE CS - COMPILER DESIGN:Syntax-Directed Translation

Syntax-Directed Translation for GATE CS

GATE Compiler Design loves asking whether a rule set is S-attributed, L-attributed, both, or neither — and sometimes to emit three-address code for a short expression. This chapter is that skill.

SDD vs SDT

• SDD (syntax-directed definition): attributes + semantic rules attached to productions (order of evaluation is logical, not necessarily textual).
• SDT (translation scheme): actions written in curly braces inside the production, executed when the parser reaches that point.

Example SDT fragment:

E → E₁ + T { print('+') }
T → num { print(num.lexval) }

Attributes

Expression value E.val from children is synthesized. Passing a type or offset into a child is inherited.

S-attributed vs L-attributed

S-attributed: only synthesized attributes. Fits bottom-up (LR) parsing naturally.

L-attributed: each inherited attribute of a symbol depends only on:

• inherited attributes of the parent, and
• attributes of symbols to its left in the same production

(plus synthesized attributes as usual). L-attributed grammars work with left-to-right (LL) evaluation; every S-attributed grammar is L-attributed.

Worked: classify three rules

Suppose attributes i on nonterminals:

1. R → A B { B.i = R.i − 1; A.i = B.i; R.i = A.i + 1 }

Uses R.i on the right while also defining it from children — dependency order is not a clean S- or L-pattern as written (inherited flowing the wrong way). Treat as neither in the usual GATE reading when parents depend on children incorrectly mixed with inherited use.

1. P → C D { P.i = C.i + D.i; D.i = C.i + 2 }

D.i inherited from left sibling C → OK for L. P.i synthesized from children → OK. Not S-only if D.i is inherited. → L-attributed, not S-attributed.

1. Q → E F { Q.i = E.i + F.i }

Only synthesized → S-attributed and L-attributed.

(Exact GATE options use this style of classification — match each production carefully.)

Three-address code

At most three operands per instruction. For x = y + z * 2:

t1 = z * 2
t2 = y + t1
x = t2

Representations: quadruples (op, arg1, arg2, result), triples (op, arg1, arg2 with implicit result index), indirect triples.

What to drill

1. Mark each attribute synthesized vs inherited
2. Check L-attributed constraints on inherited attrs
3. Generate TAC for a 3–4 operator expression

Then: Code Generation. Quizzes: GATE hub.