Attribute Grammars and Syntax-Directed Definitions

45 mins

Understand how compilers attach semantic meaning to grammar rules. Learn to evaluate synthesized and inherited attributes, differentiate between S-Attributed and L-Attributed SDDs, and trace dependency graphs.

Learning Goals

Define Syntax-Directed Definitions (SDDs) as a CFG paired with semantic rules, and Syntax-Directed Translation Schemes (SDTs) as implementations with embedded actions.
Differentiate between synthesized attributes and inherited attributes with concrete examples (type computation, expression evaluation).
Differentiate between S-Attributed and L-Attributed definitions, prove that S-Attributed is a subset of L-Attributed, and understand parser compatibility (A highly tested exam topic).
Construct an annotated parse tree step-by-step and evaluate attribute values at each node.
Construct a dependency graph on a syntax tree, perform topological sort, and detect cyclic dependencies.
Design an SDT for mathematical expressions and trace its execution to produce output.
Trace the execution of embedded semantic action symbols (e.g., print statements) during bottom-up parsing to predict output sequences.
Apply SDT action placement rules: synthesized attributes at end of production, inherited attributes in the middle.

Syntax-Directed Definitions (SDD) & Translation (SDT)

Syntax-Directed Translation is the process of attaching semantic rules to the grammatical productions of a Context-Free Grammar. This allows the compiler to evaluate expressions, check types, or generate intermediate code exactly at the moment a syntax rule is applied.

Formal Definition of SDD: An SDD is a Context-Free Grammar together with semantic rules associated with each production. For every production $A \to \alpha$ , the SDD associates a set of semantic rules of the form $b = f(c_1, c_2, \dots, c_k)$ where $b$ is an attribute of a grammar symbol in the production and $f$ is a function on attributes $c_1, \dots, c_k$ of grammar symbols in the production.

SDD vs SDT — Specification vs Implementation:

An SDD is a specification — it tells you what value each attribute should have, but not when or how to compute it during parsing.
An SDT is an implementation — it embeds semantic actions (program fragments) within the right side of productions, telling the parser exactly when to execute each action.

Why is SDT Important? SDT bridges the gap between purely structural parsing and actual code meaning. It is crucial because it allows the compiler to perform Semantic Analysis (type checking), evaluate mathematical expressions, and generate Intermediate Code all simultaneously while the parser is building the syntax tree, making the compilation process highly efficient.

An SDD is a Context-Free Grammar paired with semantic rules. Each rule specifies an attribute's value as a function of other attributes, but does not dictate when the rule is evaluated.

Example SDD:

Production	Semantic Rule
$E \to E_1 + T$	$E.val = E_1.val + T.val$
$E \to T$	$E.val = T.val$
$T \to T_1 * F$	$T.val = T_1.val * F.val$
$T \to F$	$T.val = F.val$
$F \to \text{num}$	$F.val = \text{num.lexval}$

The rules are declarative — they state relationships between attributes, not execution order.

SDT Action Placement Rules

When constructing an SDT from an SDD, follow these placement rules:

Synthesized attributes: Place the action at the end of the production (after all grammar symbols have been recognized).
Inherited attributes: Place the action just before the grammar symbol that receives the inherited value (in the middle of the production).
For L-Attributed SDDs: These placement rules guarantee that all needed attributes are available when the action executes during a left-to-right parse.

Attributes

There are two fundamental types of attributes:

Synthesized Attributes: The value of the attribute at a node is computed from the values of attributes at its children. Information flows bottom-up.
Inherited Attributes: The value of the attribute at a node is computed from the attributes of its parent and/or its siblings. Information flows top-down or left-to-right.

Concrete Examples:

Expression Evaluation (Synthesized): In $E \to E_1 + T$ , the attribute $E.val = E_1.val + T.val$ is synthesized — it is computed from children $E_1$ and $T$ .
Type Computation (Inherited): In $D \to T L$ , the attribute $L.type = T.type$ is inherited — $L$ receives its type from its sibling/parent $T$ . This allows the type declared at the beginning of a declaration to propagate to each identifier in the list.

Comparison: Synthesized vs Inherited Attributes

Feature	Synthesized Attribute	Inherited Attribute
Value Source	Children nodes	Parent and/or left siblings
Information Flow	Bottom-up	Top-down / left-to-right
Evaluation During	Bottom-up (LR) parsing	Top-down (LL) parsing
Typical Use	Expression values, type of expressions	Type declarations, symbol table info
Example	$E.val = E_1.val + T.val$	$L.type = T.type$
Start Symbol	Can have synthesized attributes on start symbol	Cannot have inherited attributes on start symbol (no parent)
S-Attributed SDD	Allowed (only these are used)	Forbidden
L-Attributed SDD	Allowed	Allowed (with left-sibling restriction)

S-Attributed vs L-Attributed Definitions

Exam Tip — Most Tested Topic

"The distinction between S-Attributed and L-Attributed SDDs is the #1 most frequently tested question in Module 3. You will almost certainly be asked to identify whether a given SDD is S-Attributed, L-Attributed, or neither. Remember: S-Attributed ⊂ L-Attributed, so if an SDD is S-Attributed, it is automatically L-Attributed too."

Feature	S-Attributed SDD	L-Attributed SDD
Attribute Types Allowed	Uses ONLY Synthesized attributes.	Can use Both Synthesized and Inherited attributes.
Inheritance Restriction	N/A (Inherited attributes are forbidden).	Inherited attributes can only depend on parents or left siblings (never right siblings).
Evaluation Order	Strictly Bottom-Up.	Left-to-Right, Depth-First (Top-Down or Top-Down with Bottom-Up evaluation).
Parsing Compatibility	Easily evaluated during Bottom-Up parsing (e.g., LR parsers).	Easily evaluated during Top-Down parsing (e.g., LL parsers). Also works with LR parsers if no inherited attrs.
Subset Relationship	S-Attributed is a strict subset of L-Attributed.	L-Attributed is a superset of S-Attributed.

Proof that S-Attributed ⊂ L-Attributed: An S-Attributed SDD uses only synthesized attributes. Synthesized attributes depend only on children — they never depend on right siblings or parents. Therefore, they trivially satisfy the L-Attributed restriction (which only restricts inherited attributes to depend on parent/left siblings). Since S-Attributed SDDs have no inherited attributes at all, they automatically satisfy all L-Attributed constraints. Hence, every S-Attributed SDD is also L-Attributed.

Suitable Examples:

S-Attributed Example: $E \to E_1 + T \quad \{ E.val = E_1.val + T.val \}$ (Notice $E.val$ is calculated entirely from its children $E_1$ and $T$ . No inherited attributes exist.)
L-Attributed Example: $A \to L M \quad \{ M.inherited = L.synthesized \}$ (Notice $M$ inherits a value from its left sibling $L$ . This is strictly allowed in L-Attributed, but forbidden in S-Attributed).
Neither Example: $A \to B C \quad \{ B.inherited = C.synthesized \}$ (Notice $B$ inherits from its right sibling $C$ . This violates the L-Attributed restriction — inherited attributes may NOT depend on right siblings.)

Constructing an Annotated Parse Tree for $3 * 5 + 4$

1
Step 1
Grammar:

$E \to E_1 + T$

$E \to T$

$T \to T_1 * F$

$T \to F$

$F \to \text{num}$

SDD (all synthesized attributes):

$E \to E_1 + T$ : $E.val = E_1.val + T.val$

$E \to T$ : $E.val = T.val$

$T \to T_1 * F$ : $T.val = T_1.val * F.val$

$T \to F$ : $T.val = F.val$

$F \to \text{num}$ : $F.val = \text{num.lexval}$
2
Step 2
Parse tree for input 3 * 5 + 4:
3
Step 3
Assign $F.val$ from the lexval of each number:

$F_1.val = 3$ (from 3)

$F_2.val = 5$ (from 5)

$F_3.val = 4$ (from 4)
4
Step 4
Evaluate $T$ nodes from their children:

$T_{1a}.val = F_1.val = 3$ (rule $T \to F$ )

$T_1.val = T_{1a}.val * F_2.val = 3 * 5 = 15$ (rule $T \to T * F$ )

$T_2.val = F_3.val = 4$ (rule $T \to F$ )
5
Step 5
Evaluate $E$ nodes from their children:

$E_1.val = T_1.val = 15$ (rule $E \to T$ )

$E_{root}.val = E_1.val + T_2.val = 15 + 4 = 19$ (rule $E \to E + T$ )

Final Result: $E_{root}.val = 19$
6
Step 6
The evaluation proceeds in post-order (bottom-up, left-to-right):

$F_1$ → $T_{1a}$ → $F_2$ → $T_1$ → $E_1$ (left subtree complete)

$F_3$ → $T_2$ (right subtree base)

$E_{root}$ (root)

This is the natural order for bottom-up (LR) parsing and works perfectly for S-Attributed SDDs.

Annotated Parse Trees (Infix to Prefix)

An annotated parse tree is a regular parse tree where every node is annotated with the final, computed values of its attributes.

Example: Infix to Prefix Translation Consider a grammar that translates $E \to E_1 + T$ into Prefix notation (e.g., translating 3 + 4 into + 3 4). Semantic Rule: E.val = "+" || E1.val || T.val

If the input is A + B, the annotated parse tree evaluating bottom-up looks like this:

Constructing a Dependency Graph

Step 1

Consider a simplified grammar for expression evaluation with type checking:

Production	Semantic Rules
$E \to E_1 + T$	$E.val = E_1.val + T.val$ ; $E.type = \text{max}(E_1.type, T.type)$
$E \to T$	$E.val = T.val$ ; $E.type = T.type$
$T \to \text{num}$	$T.val = \text{num.lexval}$ ; $T.type = \text{integer}$

Input: 5 + 3

2
Step 2
3
Step 3
For each grammar symbol node, create attribute nodes:

$T_1.val$ , $T_1.type$

$T_2.val$ , $T_2.type$

$E_1.val$ , $E_1.type$

$E_{root}.val$ , $E_{root}.type$
4
Step 4
Based on semantic rules, draw edges from source to dependent attribute:
5
Step 5
Topological sort yields a valid evaluation order (no attribute is evaluated before its dependencies):

$T_1.val$ , $T_1.type$ (base — no incoming edges)

$T_2.val$ , $T_2.type$ (base — no incoming edges)

$E_1.val = T_1.val$ , $E_1.type = T_1.type$ (depend only on $T_1$ )

$E_{root}.val = E_1.val + T_2.val$ , $E_{root}.type = \text{max}(E_1.type, T_2.type)$ (depend on $E_1$ and $T_2$ )

This order is valid — the graph has no cycles.
6
Step 6
If a dependency graph contains a cycle, topological sort is impossible and the SDD is invalid — no evaluation order exists.

Example of a cyclic (invalid) SDD: $A \to B \quad \{ B.inherited = A.synthesized \}$ $A \to B \quad \{ A.synthesized = B.inherited \}$

Here $A.synthesized$ depends on $B.inherited$ , and $B.inherited$ depends on $A.synthesized$ — a cycle! This SDD cannot be evaluated.

Dependency Graphs & Evaluation Order

A Dependency Graph is a directed graph that shows the interdependencies between attributes in a parse tree. It is specifically used to determine the exact evaluation order of attributes.

How to construct and use it:

Draw the parse tree.
For every node, draw a point representing its attributes.
If an attribute $X$ depends on an attribute $Y$ to be calculated, draw a directed edge from $Y$ to $X$ .
Evaluation Order: The compiler performs a Topological Sort on this graph. A topological sort guarantees that an attribute is evaluated only after all the attributes it depends on have been evaluated. (Note: If the dependency graph contains a cycle, the attributes cannot be evaluated, and the SDD is invalid).

Example of a Dependency Graph (Topological Order): For the rule $E \to E_1 + T$ , evaluating types:

Semantic Action Tracing

1
Step 1
Examiners frequently ask you to trace the output of a grammar with embedded semantic actions (like {print()}). You must simulate a bottom-up parser (or post-order traversal) and determine the exact sequence of printed output.
2
Step 2
Consider the rules:

$S \to A S \{ \text{print}(1) \}$

$S \to A \{ \text{print}(2) \}$

$A \to a \{ \text{print}(3) \}$ Input string: aa
3
Step 3
For input aa, the tree is:
4
Step 4
We evaluate the actions as the nodes are reduced (from bottom-left to top-right):

Reduce the first a to $A$ . Action: print(3).

Reduce the second a to $A$ . Action: print(3).

Reduce the second $A$ to $S$ . Action: print(2).

Reduce the first $A$ and the second $S$ to the root $S$ . Action: print(1). Final Printed Output: 3321

Second Tracing Example — Expression with Infix to Postfix

Step 1

Consider an SDT that converts infix expressions to postfix:

Production	Semantic Action
$E \to E_1 + T$	$\{ \text{print}(E_1.post) \} + \{ \text{print}(T.post) \} \{ \text{print}(\text{"+"}) \}$
$E \to T$	$\{ \text{print}(T.post) \}$
$T \to \text{num}$	$\{ \text{print}(\text{num.lexval}) \}$

Input: 5 + 3

2
Step 2
3
Step 3
Actions execute during reductions:

Reduce 5 to $T$ : print(5)

Reduce $T$ to $E$ : (no additional print, just propagation)

Reduce 3 to $T$ : print(3)

Reduce $E + T$ to root $E$ : **print("+")

Final Output: 5 3 + (postfix notation)

Why SDT is Preferred Over SDD in Practice

In real compiler implementations, SDTs are preferred because they embed actions at specific positions in productions, allowing the parser to execute semantic actions on-the-fly during parsing. This eliminates the need to build a separate dependency graph and perform topological sort — the parser's natural traversal order guarantees correct evaluation for well-designed SDTs. SDDs, being declarative, require post-processing to determine evaluation order.

Common Questions on SDDs and SDTs

Knowledge Check

Question 1 of 7

Q1Single choice

Which type of SDD allows ONLY synthesized attributes? [PYQ 2022]

L-Attributed

S-Attributed

Both

Neither

Compilers: Principles, Techniques, and Tools (Dragon Book) — Chapter 5: Syntax-Directed Translation

web

PYQ Analysis and Exam Preparation

Symbol Table Management