Differentiate between S-attribute SDT and L-attribute SDT (with Examples)

Syntax-directed translation (SDT) associates semantic rules with productions of a grammar, using attributes to compute semantic information (e.g., types, intermediate code). In attribute grammars, attributes are typically synthesized from children upward or inherited from a parent or left siblings downward. Two important classes—S-attributed SDT and L-attributed SDT—impose restrictions that make evaluation efficient and often compatible with parsing strategies.

Below, we formalize the constraints, then contrast them with concrete examples (expression attributes, type checking, and code generation), including a “why it works” evaluation order view using the parse tree.

[VideoBlock] requires a direct URL from tool results; however, web search is currently unavailable in this environment.

Key learning terms

• Attribute grammar: SDT framework with attribute rules.
• Synthesized attribute: flows upward.
• Inherited attribute: flows sideways/downward.
• Evaluation order: required by dependency constraints.

---

S-attribute SDT (S-attributed): what it means

In an S-attributed (syntax-directed) translation / attribute grammar, the semantic rules attached to each production are restricted so that all values needed to compute attributes for a node come only from its children (i.e., you do not use inherited attributes in a way that depends on parent or left-context).

Practical consequence

• The translation can be done bottom-up (post-order style on the parse tree).
• You typically compute synthesized results like expression type, numeric value, or generated code for a subtree once all children are known.

Typical examples suited for S-attributed SDT

• Type synthesis:
  • For production $E \to E\ +\ T$, synthesize $E.type$ from $E.left.type$ and $T.type$.
• Constant folding:
  • $E.value$ computed from child numeric values.

[CalloutBlock]
type: "tip" title: "Pro Tip (S-attributed mindset)" content: "If your semantic needs only “bottom-up info” (children determine everything), you can usually model it as S-attributed."

---

L-attribute SDT (L-attributed): what it means

An L-attributed attribute grammar is more general: it allows inherited attributes, but still enforces a disciplined dependency structure.

Constraint (the essential rule)

For a production

$$A \to X_1\ X_2\ \dots\ X_n$$

• Each semantic rule may assign attributes for any $X_i$.
• Inherited attributes of $X_i$ can depend on:
  1. attributes of the parent $A$, and
  2. attributes of symbols to the left: $X_1, \dots, X_{i-1}$.
• Crucially, inherited attributes cannot depend on information from $X_{i+1}, \dots, X_n$ (right siblings).

Practical consequence

• The translation can be evaluated in a left-to-right order across the right-hand side of productions, while still allowing inherited flow needed for context-sensitive decisions.

[CalloutBlock]
type: "warning" title: "Common pitfall (L-attributed dependency)" content: "If an inherited attribute for $X_i$ needs data from a right sibling (some $X_j$ with $j>i$), then the grammar is not L-attributed."

---

Direct differentiation: S-attribute vs L-attribute

Comparison table

Mermaid: dependency arrows

---

Worked examples

Example 1: Expression type synthesis (S-attributed friendly)

Consider:

$$E \to E + T \quad\quad E \to T \quad\quad T \to id$$

Goal: synthesize $E.type$ from children.

• Attach rules like:
  • $E.type = \text{numeric\_type\_join}(E_1.type, T.type)$
  • $T.type = \text{lookup}(id.lexeme)$

All used values come from children; no inherited context is needed. This fits S-attributed SDT.

---

Example 2: Type checking with inherited environment (L-attributed)

Now add declarations and scoping-like context in a simplified way, e.g.:

$$Stmt \to \text{begin } L \text{ end}$$

where $L$ is a list of statements, and an inherited environment $Env$ must flow into each statement as it is parsed/evaluated left-to-right.

• Production: $$L \to L_1\ ;\ S$$
• Inherited idea: $L.Env$ carries the symbol table / type environment accumulated from earlier declarations.
• Rule shape (conceptual):
  • $S.Env := L.Env$ (inherits from left structure)
  • If $S$ introduces declarations, then update for the next list element.

This requires inherited information that depends on left context (earlier items in the list), which matches L-attributed SDT.

Why not S-attributed?
Because $S$ may need environment built from left siblings (earlier declarations), which is not available if you restrict to children-only synthesized computation.

---

Example 3: Code generation needing left context (L-attributed)

For infix expressions you often need left-to-right evaluation to manage:

• stack layout,
• temporaries,
• or concatenation of instruction sequences.

Suppose you generate code while respecting operand order:

• $E \to E_1\ +\ E_2$
• Let synthesized pieces $code(E_1)$ and $code(E_2)$ exist, but let inherited attribute $nextTemp$ or $outputMode$ depend on what was emitted for the left subtree.

If $nextTemp$ (or similar) depends on emitted instructions from $E_1$ (left sibling context on the RHS), then L-attributed fits; S-attributed generally does not model it without additional structure.

---