Synthesized vs Inherited Attributes in Attribute Grammars (with Examples)

In compiler construction, attribute grammars extend a context-free grammar by attaching attributes to grammar symbols and defining rules that compute those attributes. Two common categories are synthesized attributes and inherited attributes.

A helpful mental model is the parse tree direction of information flow:

• Synthesized attributes: children compute first; parent “collects” results.
• Inherited attributes: parent (or left sibling) supplies context to children before they compute.

A classic example is type checking: bottom-up computation can synthesize an expression’s type, while context-sensitive information (e.g., “expected type” or symbol table scope) is often inherited.

Visualizing information flow

⚠️ Note: Although attribute grammars can mix both kinds, the key distinction is direction: synthesized values flow upward; inherited values flow downward (often top-down).

Core definitions (what to remember)

• Synthesized attributes are typically evaluated after children, because they depend on child values.
• Inherited attributes are evaluated before the dependent child, because the child depends on context from above.

In notation used in compiler textbooks, attributes are associated with symbols in productions, and semantic rules are written to compute them. A production like:

may have:

• a synthesized attribute on $A$ computed from attributes of $B$ and $C$, e.g., $A.type = combine(B.type, C.type)$
• inherited attributes on $B$ or $C$ computed from $A$ or from each other, e.g., $B.env = A.env$

Example 1: Synthesized attribute for expression type (bottom-up)

Assume a simple language fragment with expressions:

• integer literals
• addition: $E \\rightarrow E + E$
• multiplication: $E \\rightarrow E * E$

We want an attribute $E.type$ that synthesizes the type of each expression node.

Grammar sketch

Synthesized attribute semantic rules

• For an integer literal:
  • $E.type = \\text{Int}$
• For addition:
  • $E.type = \\text{Int}$ if both children types are Int; otherwise error.
  • Formally: if $E_1.type = \\text{Int}$ and $E_2.type = \\text{Int}$ then $E.type = \\text{Int}$.
• For multiplication similarly.

This is synthesized because the parent’s type depends on child types: $E.type = f(E_1.type, E_2.type)$.

Mini parse-tree walkthrough

For input: 3 + 4 * 5, the parse tree (simplified) nests multiplications inside additions. Bottom-up:

1. 3 synthesizes $type=Int$
2. 4 synthesizes $type=Int$, 5 synthesizes $type=Int$, so 4*5 synthesizes $type=Int$
3. Now 3 + (4*5) synthesizes $type=Int$

No external context is needed if the symbol table for id is also available via a synthesized lookup (or via a separate attribute approach).

Example 2: Inherited attribute for scope/environment (top-down)

Consider identifiers and scoping rules, like blocks:

Suppose we attach an environment attribute env to expressions and statements so that id can be resolved.

We model env as inherited: the enclosing block provides it to its contents.

• Let Block.env be built at the block level.
• Then each child statement receives Stmt.env = Block.env.

Inherited semantic rules (conceptual)

• If a block creates a new scope, it extends the parent environment:
  • $\\text{Block.env} = extend(\\text{Parent.env}, \\text{Block.locals})$
• Then for child statements:
  • $Stmt.env = Block.env$
• Finally, inside an expression with an identifier:
  • $Expr.type = lookup(Expr.id, Expr.env)$

Because Expr.type depends on Expr.env provided from above, env is inherited.

Example 3: Mixed attributes (both synthesized and inherited)

Type checking with operator typing often uses both:

• Inherited attribute: expected type passed from context (e.g., assignment).
• Synthesized attribute: computed actual type of expressions.

For assignment:

• Let Stmt.expected be inherited from assignment context (or be the type of id).
• Alternatively, you can treat the LHS type as inherited into RHS.

One consistent design

• Use an inherited attribute for the expected type:
  • $Expr.expected = Stmt.lhsType$
• Use a synthesized attribute for the actual type:
  • $Expr.type = typeOf(Expr...)$
• Then check compatibility:
  • If $Expr.type$ is compatible with $Expr.expected$, accept; else error.

This pattern is common in semantic analysis because it naturally separates:

• what information the context provides (inherited)
• what the subtree computes (synthesized)