Syntax-directed translation

Attributes and syntax-directed definitions

Definition. An attribute attaches a value to a grammar symbol occurrence, such as a type, value, location, or generated code. A syntax-directed definition (SDD) associates semantic rules with productions; a syntax-directed translation scheme (SDT) embeds actions at specific positions in production bodies.

Example. For E→E1+T, a synthesized attribute can set E.val=E1.val+T.val.

Exam point. Attribute dependencies determine evaluation order; production order alone may not be sufficient.

Solved examples

Example 1 — evaluate an expression. Grammar E→E1+T | T, T→digit. Each digit carries its numeric value. Evaluate 7+4.

1. The leaf digit 7 has attribute 7; the leaf 4 has attribute 4.
2. T nodes copy the digit value upward.
3. The addition production computes E.val=7+4.
4. Root synthesized value is 11.

Example 2 — postfix translation. For production E→E1+T, emit code for E1, then T, then +. Translate 3+5.

1. The left child emits 3.
2. The right child emits 5.
3. The parent appends +.
4. Postfix string is 3 5 +.

Synthesized and inherited attributes

Definition. A synthesized attribute at a node is computed from attributes of its children and the node's production. An inherited attribute is computed from the parent and/or siblings and passed downward or sideways. S-attributed definitions use only synthesized attributes; L-attributed definitions restrict inherited dependencies to the parent and left siblings.

Example. A declaration's base type can be inherited by each identifier in a list.

Exam point. Every S-attributed definition is L-attributed, but an L-attributed definition may use inherited attributes.

Solved examples

Example 1 — synthesized value. For E→E1*T, set E.val=E1.val*T.val. Evaluate 2*6.

1. Leaves synthesize 2 and 6.
2. Child expressions pass values upward.
3. The parent multiplies 2·6.
4. E.val=12.

Example 2 — inherited type. Grammar D→T L, T→int, L→L1,id | id. Pass type int to every listed identifier.

1. T synthesizes type=int.
2. D passes this value as inherited L.in.
3. For L→L1,id, pass L.in to L1 and attach it to id.
4. For L→id, attach L.in to the identifier.
5. In int x,y, both x and y receive type int.

Example 3 — classify an SDD. A rule sets a parent's value from child values only.

1. No inherited values are referenced.
2. The definition is S-attributed.
3. S-attributed implies L-attributed.
4. Both classifications apply.

Dependency graphs and evaluation order

Definition. Attribute instances are nodes in a dependency graph. An edge X→Y means Y's semantic rule needs X. A topological order evaluates attributes when all dependencies are ready; a cycle indicates circular attribute equations for that parse tree.

Example. If E.val depends on E1.val and T.val, edges from both child values lead to the parent value.

Exam point. An SDD may be valid for one parse tree and circular for another if dependencies depend on productions.

Solved examples

Example 1 — topological evaluation. Rules are A.x=B.y+1, B.y=C.z*2, and C.z=4.

1. C.z has no dependency, so evaluate it first: 4.
2. B.y=4·2=8.
3. A.x=8+1=9.
4. Valid order: C.z, B.y, A.x; final value 9.

Example 2 — detect a cycle. Equations are A.x=B.y+1 and B.y=A.x−1.

1. A.x depends on B.y.
2. B.y depends on A.x.
3. The dependency graph contains a directed cycle.
4. No topological evaluation order exists; the definition is circular.

Type checking as attribute evaluation

Definition. Type attributes represent the type assigned to an expression. Semantic rules check operator constraints and synthesize result types; a type error occurs when an operator receives operands outside its permitted types. Symbol-table lookup supplies identifier types.

Example. If + accepts integers, the type of E1+E2 is int only when both operands are int.

Exam point. Syntax can be valid while semantic type rules reject the program.

Solved examples

Example 1 — arithmetic type. Assume + requires two integers and returns integer. Classify x+3 when x has type int.

1. Lookup gives type(x)=int.
2. The literal 3 has type int.
3. The rule's precondition holds.
4. Expression type is int.

Example 2 — mismatch. Under the same rule, classify x+3 when x has type string.

1. Left operand type is string; right operand type is int.
2. The integer-addition rule requires both operands int.
3. Report a type error; no valid synthesized result type follows from this rule.