Syntax-directed translation and attribute evaluation
Goal and notation
Attach meaning to a parse tree without confusing grammar symbols with attributes. A syntax-directed definition (SDD) associates attributes and semantic rules with productions. A translation scheme places executable actions at specific positions in a production. The grammar determines syntactic structure; the attribute dependencies determine a valid evaluation order. An action is not free to use an attribute before it has been computed.
1. Synthesized and inherited attributes
A synthesized attribute at a node is computed from attributes of its children (and permitted local information). An inherited attribute is supplied using the parent and/or relevant siblings. Subscripts distinguish occurrences: in E→E₁+T, E and E₁ are different parse-tree nodes even though they have the same grammar symbol.
For arithmetic, use E→E₁+T {E.val=E₁.val+T.val}; E→T {E.val=T.val}; T→T₁F {T.val=T₁.valF.val}; T→F {T.val=F.val}; F→num {F.val=num.lexval}. All val attributes are synthesized. A postorder traversal can evaluate them after the children; the left-recursive grammar is acceptable for this attribute example and bottom-up parsing. It is not an LL(1) grammar.
Worked evaluation of 2+34: the three num leaves supply 2,3,4. The multiplication subtree computes 34=12. The root addition computes 2+12=14. Evaluating the addition before its right child is ready violates the dependency order. The grammar gives multiplication the tighter grouping; the attribute rule does not invent precedence.
2. Dependency graph and scheduling
Create one vertex for every attribute occurrence. If a rule computes x from y and z, draw y→x and z→x. Any topological order is a valid evaluation order for an acyclic dependency graph. Syntactic left-to-right order alone is insufficient. If a particular tree's dependency graph has a directed cycle, this direct one-pass dependency evaluation has no topological order; general attribute grammar questions require checking possible trees rather than just one diagram.
An S-attributed definition uses only synthesized attributes and fits bottom-up evaluation. In a reduction A→XYZ, the parser can retrieve X,Y,Z attributes from the semantic stack, compute A's values, and replace the RHS entries by A. An ε production may synthesize a constant even though it has no children.
3. Inherited accumulator for a left-factored expression
Use E→T R; R→+T R₁ | ε; T→num. To compute a left-to-right sum, define T.val=num.lexval. On E→TR set R.inh=T.val and E.val=R.syn. On R→+TR₁ set R₁.inh=R.inh+T.val and R.syn=R₁.syn. On R→ε set R.syn=R.inh. The right-recursive grammar carries the running result in an inherited attribute.
For 2+3+4, the first T gives 2 and the first R.inh=2. The next T gives 3, so the next R.inh=5. The last T gives 4, so the final R.inh=9. At ε, R.syn=9; that value returns through each R to E.val=9. The same accumulator idea is important for left-associative subtraction: use a minus rule and update inh−T.val, rather than turning subtraction into right-associated 2−(3−4).
An L-attributed definition allows an inherited attribute of RHS symbol Xᵢ to depend on inherited attributes of the parent and attributes of symbols to its left, with any permitted same-symbol dependencies required not to create cycles. The rules above satisfy the usual left-to-right evaluation restriction: R₁.inh uses R.inh and the earlier T.val. A rule requiring an unevaluated right sibling is not justified by this property.
4. Action placement and postfix output
For postfix translation use E→E₁+T {print('+')}, T→T₁F {print('')}, F→num {print(num.lexeme)}, plus copy productions E→T, T→F. Actions at the right end execute after the children. Input 2+3*4 prints 2 3 4 * +. An action placed before T in E→E₁+{print('+')}T would print + before T's output and would not implement the same postfix scheme.
Pitfalls
S-attributed is a subset of L-attributed, not the reverse. Synthesized does not mean evaluated before children. A symbol-table pointer and a numeric val are different possible attributes. Do not count an attribute name once globally: repeated nonterminal occurrences have separate values. Parse-tree construction, attribute evaluation, and output side effects must each respect their own ordering requirements.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. The rules computing each parent val only from child vals form:
A. An S-attributed definition B. An inherently cyclic definition C. A definition with only inherited attributes D. An LL(1) grammar automatically
Answer: A
A: All attributes are synthesized.
B: Child-to-parent dependencies need not cycle.
C: These values flow upward, not downward.
D: Attribute classes do not establish LL(1) parsing.
P02. For 2+3*4 under the lesson grammar, E.val is:
A. 20 B. 14 C. 24 D. 9
Answer: B
A: Twenty would group the addition first.
B: Multiplication yields 12, then addition yields 14.
C: This ignores the operators and grouping.
D: Nine would add all three operands.
P03. If x=f(y,z), the dependency edges are:
A. x→y and x→z B. y→z only C. y→x and z→x D. No edges
Answer: C
A: These reverse the prerequisite direction.
B: No y-to-z dependency was stated.
C: Prerequisites point to the value they enable.
D: x cannot be scheduled independently of y,z.
P04. In the accumulator evaluation of 2+3+4, the final R.inh is:
A. 2 B. 3 C. 5 D. 9
Answer: D
A: Two is the first inherited value.
B: Three is a later operand, not the total.
C: Five is the intermediate sum.
D: The accumulator progresses 2,5,9.
P05. Right-end actions for postfix output on 2+3*4 print:
A. 2 3 + 4 * B. + 2 * 3 4 C. 2 3 4 * + D. 2 + 3 * 4
Answer: C
A: This groups addition before multiplication.
B: This is prefix ordering.
C: Children print before each operator.
D: This retains infix notation.
P06. A directed cycle in a tree attribute dependency graph means:
A. Any order works B. There is no topological evaluation order C. The input must have a lexical error D. Removing left recursion always fixes it
Answer: B
A: Cycle dependencies prevent a prerequisite-first order.
B: A directed cycle rules out a topological ordering.
C: Attribute dependencies do not establish lexical invalidity.
D: Grammar rewriting does not automatically remove semantic cycles.
Sources and scope
Aligned to the official 2026 course. This lesson covers a bounded topic slice; no claim of 2027 completeness. All examples and exercises are original.
Sign in to keep your progress. Sign in