Syntax-Directed Definitions (SDDs): S-Attributed vs L-Attributed Attribute Grammars

In compiler construction, a syntax-directed definition (often abbreviated SDD or called an attribute grammar ) specifies semantics by attaching attribute computation rules to a context-free grammar.

For each production of the form
$A \rightarrow X_1 X_2 \dots X_n$,
an SDD provides semantic rules that define how attributes of $A$ and/or $X_i$ are computed from other attributes. Attribute dependencies determine when each attribute can be evaluated, which leads to restricted classes like S-attributed and L-attributed.

Visual dependency intuition (attribute flow)

1) Define Syntax-Directed Definitions (SDDs)

Core idea

An SDD augments a context-free grammar with rules of the form:

• For each production $A \rightarrow X_1 X_2 \dots X_n$,
• you attach semantic equations that compute attributes.

An attribute grammar typically distinguishes:

• synthesized attributes: flow upward (bottom-up).
• inherited attributes: flow downward/sideways (top-down or left-to-right).

Canonical production form and semantic equations

For example, for $A \rightarrow X_1X_2$, an SDD might include semantic rules like:

• $A.\text{val} := f(X_1.\text{val}, X_2.\text{val})$ (synthesized)
• $X_1.\text{type} := A.\text{type}$ (inherited)
• $X_2.\text{type} := X_1.\text{type}$ (inherited from left sibling)

Why restrictions matter

Not every attribute grammar can be evaluated with a simple single traversal. Restrictions like S-attributed and L-attributed ensure there exists an evaluation order that avoids circular dependencies and supports linear-time parsing/translation strategies.

Key terms (quick map)

• attribute dependency
• evaluation order
• context-free grammar

2) S-Attributed vs L-Attributed: Differences

Both classes restrict which inherited attributes may depend on other attributes. The difference is how much sibling information is allowed.

S-attributed (stronger restriction)

Definition (informal but standard):
An attribute grammar is S-attributed if every inherited attribute of a child depends only on:

• attributes of the parent (and possibly synthesized attributes of nodes above it),
• not on attributes of siblings.

This means inherited information comes only from “above” (parent), not from “sideways” (other children).

L-attributed (weaker restriction → left-to-right evaluation)

An attribute grammar is L-attributed if every inherited attribute of a symbol $X_i$ (in $A \rightarrow X_1 \dots X_n$) depends only on:

• attributes of the parent $A$, and
• attributes of left siblings $X_1, \dots, X_{i-1}$ (specifically their synthesized attributes, since those can be computed left-to-right).

This enables an evaluation strategy consistent with left-to-right parsing (common with many practical parser/translator designs).

3) Example of an S-attributed definition (attribute evaluation)

We’ll use an SDD that computes expression type checking in a simple setting, using inherited attributes only from the parent.

Grammar

Let nonterminal E represent expressions. We use a context parameter Expected inherited from the parent to force checking a target type:

Productions:

1. $E \rightarrow \text{id}$
2. $E \rightarrow (E)$
3. $E \rightarrow E \;+\; E$

Assume each id has an intrinsic type known from the symbol table; we’ll represent it as id.type.
Let:

• $E.\text{type}$ be synthesized type of expression $E$.
• $E.\text{Expected}$ be inherited “expected type” passed from parent context.

S-attributed SDD (semantic rules)

For production 1: $E \rightarrow \text{id}$

• $E.\text{type} := \text{id.type}$
• (No inherited needed beyond what is already passed)

For production 2: $E \rightarrow (E_1)$

• $E_1.\text{Expected} := E.\text{Expected}$ (inherited from parent only)
• $E.\text{type} := E_1.\text{type}$ (synthesized from child)

For production 3: $E \rightarrow E_1 + E_2$

• $E_1.\text{Expected} := E.\text{Expected}$ (inherited from parent only)
• $E_2.\text{Expected} := E.\text{Expected}$ (inherited from parent only)
• $E.\text{type} := \text{numericComposedType}(E_1.\text{type}, E_2.\text{type})$ (synthesized)

Why it is S-attributed:
Each inherited attribute (the Expected passed to children) depends only on the parent’s Expected, not on sibling attributes.

Attribute evaluation explanation

Consider a parse tree node for E → E1 + E2.

1. When the evaluator visits node E, it already knows E.Expected (inherited from above).
2. It can compute:
   • E1.Expected := E.Expected
   • E2.Expected := E.Expected
3. Then it computes synthesized types from children:
   • first E1.type (bottom-up)
   • E2.type (bottom-up)
   • then E.type using E1.type and E2.type.

This schedule is consistent with bottom-up computation of synthesized attributes and top-down propagation of inherited attributes from the parent only—matching the S-attributed restriction.

Simple dependency diagram

4) Example of an L-attributed definition (left-to-right evaluation)

We’ll use a classic example: compute the type of an identifier and support a left-to-right symbol table context (or equivalently, a “prefix context” inherited to the right operand).

Grammar

Let Stmt be:

• $S \rightarrow \text{declare id} \; S$
• $S \rightarrow S_1 \; S_2$

Or simpler expression-like with sequencing:

• $P \rightarrow P_1 \; ; \; P_2$

But to keep it close to standard SDD examples, we’ll use:

• $A \rightarrow B \; C$ where B appears left of C.

Attribute idea

We maintain an inherited attribute Env (environment) flowing to the right, updated based on left part B.

Let:

• A.env be inherited environment from parent.
• B.env inherited from parent.
• C.env inherited from a combination of parent and left sibling synthesized info.

Production rules showing L-attributed behavior

For $A \rightarrow B\;C$:

Semantic rules:

• $B.\text{env} := A.\text{env}$ (inherited from parent)
• $C.\text{env} := \text{extend}(B.\text{defs}, A.\text{env})$
  where B.defs is synthesized information computed from B (definitions introduced by the left subtree).
• $A.\text{defs} := \text{merge}(B.\text{defs}, C.\text{defs})$ (synthesized)

Why it is L-attributed

For the inherited attribute of the second child C.env:

• it depends on the parent A.env, and
• it depends on the left sibling B.defs (synthesized).
• it does not depend on the right sibling (none exists yet) and does not depend on siblings to the right.

Thus it satisfies the L-attributed restriction.

Attribute evaluation (left-to-right)

Given the parse of $A \rightarrow B\;C$:

1. Evaluate/visit node A with known A.env.
2. Assign:
   • B.env := A.env
3. Compute synthesized attributes for B, especially B.defs.
4. Now assign:
   • C.env := extend(B.defs, A.env)
5. Compute synthesized attributes for C.
6. Finally compute synthesized attributes for A from B.defs and C.defs.

This works with a deterministic left-to-right traversal because C only needs synthesized results from B, the left sibling, before C’s inherited attributes can be evaluated.

Dependency diagram