Attributes and SDT Types in Compiler Design: S-Attributed, L-Attributed and a Worked Trace

Parse-tree arrows, inherited values, synthesized values, S-attributed definitions, L-attributed definitions, SDDs and SDTs are often memorised separately. Then one small dependency question becomes confusing. You need one clear method for deciding what is computed, where, and when. With the input 3 * 5 + 4, the grammar rules produce an attribute value of 19 and the postfix output 35*4+.

Attribute grammars add meaning to a parse tree

Take E -> T R. A context-free grammar decides which parse tree is legal. A syntax-directed definition, or SDD, adds attributes and semantic rules that calculate facts on it.

The specification names num.lexval, F.val, R.in and E.val. Each tree occurrence is a separate attribute instance. F0.val and F1.val share a name but belong to different nodes.

An intrinsic attribute comes from outside the SDD, such as the lexer's num.lexval=3. A synthesized attribute uses child attributes. An inherited attribute may use its parent and, in an L-attributed definition, symbols to its left. Inherited does not mean copied unchanged from the parent.

S-attributed and L-attributed are SDD classes. An SDT, or syntax-directed translation scheme, places executable actions inside productions. An SDD describes dependencies; an SDT supplies their execution schedule. For the broader path from semantic checks through three-address code, Semantic Analysis and SDT in Compiler Design: Attributes, Worked Examples, and How GATE Tests It is the canonical guide. Its shared 3 * 5 + 4 input maps the whole pipeline; the trace below exposes every inherited accumulator, dependency edge, and SDT action time.

Synthesized and inherited attributes are directions of dependency

In F -> num { F.val = num.lexval }, F.val is synthesized because parent F receives its child's value. In D -> T L { L.in = T.type }, L.in is inherited because child L receives a value from left sibling T.

Create one dependency-graph node per attribute instance. Draw x -> y when y reads x, then choose a topological order. The second rule gives T.type -> L.in. A cycle means no valid evaluation order exists for that tree under those rules. Visual position cannot break it.

Synthesized arrows usually travel upward; inherited arrows usually travel down or sideways. Classify from the rule's inputs, not an illustrator's arrow direction.

S-attributed versus L-attributed definitions

An S-attributed SDD has only synthesized non-intrinsic attributes. Postorder evaluation after children are known fits bottom-up reductions. Examples are F -> num { F.val=num.lexval } and E -> E1 + T { E.val=E1.val+T.val }.

For A -> X1 X2 ... Xn, an inherited attribute of Xi may depend on inherited attributes of A, attributes of X1 ... X(i-1), and permitted attributes of Xi. It cannot use a right sibling. Every S-attributed SDD is L-attributed, but an L-attributed SDD using in attributes is not S-attributed.

For A -> X Y, X.in = Y.val looks rightward, so it is not L-attributed. Y.in = X.val supports left-to-right evaluation. An SDD outside this class may still be evaluated with another schedule or multiple passes.

Worked example: evaluate 3 * 5 + 4 with an L-attributed SDD

Use these rules. Subscripts distinguish occurrences of the same non-terminal.

E  -> T R          { R.in = T.val; E.val = R.out }
R  -> + T R1       { R1.in = R.in + T.val; R.out = R1.out }
R  -> epsilon      { R.out = R.in }
T  -> F Q          { Q.in = F.val; T.val = Q.out }
Q  -> * F Q1       { Q1.in = Q.in * F.val; Q.out = Q1.out }
Q  -> epsilon      { Q.out = Q.in }
F  -> num          { F.val = num.lexval }

Q carries multiplication within a term; R carries addition between terms, so * binds more tightly than +. Q.in and R.in are inherited accumulators. F.val, Q.out, T.val, R.out and E.val are synthesized.

For the first term, token 3 gives F0.val=3, hence Q0.in=3. Token 5 gives F1.val=5, so Q1.in=Q0.in * F1.val=3*5=15. Q1 -> epsilon gives Q1.out=15. It returns as Q0.out=15, so T0.val=15.

Now R0.in=T0.val=15. In R0 -> + T1 R1, token 4 gives F2.val=4. Then Q2.in=4, Q2 -> epsilon gives Q2.out=4, and T1.val=4. Therefore R1.in=R0.in+T1.val=15+4=19. The epsilon rule gives R1.out=19, returning as R0.out=19; finally, E.val=19.

This SDD is L-attributed but not S-attributed because R.in and Q.in are inherited. Every inherited dependency uses only the parent or an already evaluated left sibling.

Turn the same input into an SDT and trace action timing

This postfix SDT translates the expression rather than evaluating it:

E -> E + T  { emit('+') }
E -> T
T -> T * F  { emit('*') }
T -> F
F -> num    { emit(num.lexeme) }

Right-end actions run after that production's symbols are recognised. Recognising 3 emits 3; recognising 5 emits 5; completing T -> T * F emits *, giving 35*. Recognising 4 emits 4, giving 35*4. Completing E -> E + T emits +, giving 35*4+.

The order is emit(3), emit(5), emit(*), emit(4), emit(+). This string is not the earlier numeric value 19. Moving emit('*') before the right-hand F puts the operator before its second operand, so this scheme would not produce postfix. Do not generalise that observation to every parser implementation. After action timing, Syntax-directed translation and code optimization in compilers explained carries semantic actions into three-address code and machine-independent optimization.

How practice questions test attributes and SDTs, and where errors enter

Practice questions ask you to classify attributes or an SDD, draw edges, order evaluation, detect a cycle or right-sibling violation, calculate a root value, or execute actions.

The short version and the next concrete step

Recall five links: grammar builds the tree and attributes attach facts; dependency edges set evaluation order; S-attributed means synthesized only; L-attributed permits restricted left-to-right inherited flow; SDT actions run where written. Self-check: 3*5+4 has attribute value 19 and postfix translation 35*4+.

Now change only the final token and solve 3 * 5 + 2 without notes. Your checkable answer is T0.val=15, R1.in=17, E.val=17, with postfix 35*2+.

Use Compiler Design MCQs to practise these distinctions. Choose GATE Guidance by Sanchit Sir for a structured GATE route, or CS Fundamentals for Exams & Placements as the neutral subject hub.