Differentiate Between S-attributed SDT and L-attributed SDT (With Examples)

Syntax-directed translation (SDT) associates semantic actions with grammar productions, using attributes on grammar symbols. Two important restrictions on attribute dependencies are S-attributed and L-attributed forms, which determine whether translation can be performed in a single left-to-right pass with a parser.

In an S-attributed SDT, all inherited attributes (if any) of a production’s symbols may depend only on:

1. attributes of the production head (the left-hand side nonterminal), and
2. attributes of symbols to the left in the production’s right-hand side (including the case where a symbol’s inherited attribute depends on multiple earlier siblings).

In an L-attributed SDT, inherited attributes have an even stricter dependency: each inherited attribute of a symbol may depend only on:

1. attributes of the immediately preceding grammar symbols (through “left-to-right” accessibility), and
2. attributes of the production head, but still only in a way that enables left-to-right evaluation.

A key relationship (often stated in compiler-construction texts) is that every L-attributed SDT is S-attributed, but not every S-attributed SDT is L-attributed—because S-attributed allows some dependency patterns that break left-to-right evaluation.

Core Definitions and Dependency Rules

keyword

keyword

keyword

keyword

We consider a production like:

$$A \rightarrow X_1\,X_2\,\dots\,X_n$$

Let:

• $A$ be the head (left-hand side),
• $X_1,\dots,X_n$ be the body (right-hand side symbols).
• Each symbol may carry inherited attributes (typically written as $X_i.inh$) and synthesized attributes (typically $X_i.syn$).

S-attributed SDT

For any production $A \rightarrow X_1 \dots X_n$, the SDT is S-attributed if:

• Any inherited attribute of $X_i$ depends only on:
  • attributes of $A$ (the head), and
  • attributes of symbols $X_1,\dots,X_{i-1}$ (symbols to the left of $X_i$).
• Any synthesized attribute can depend on the children’s attributes in the usual upward way (there’s no special left-to-right restriction on synthesized attributes; the main restriction is about inherited dependencies).

L-attributed SDT

For the same production, the SDT is L-attributed if:

• The inherited attributes can be evaluated in a left-to-right manner such that when you reach $X_i$ you already know all values required to compute $X_i$’s inherited attributes.
• Formally, inherited dependencies are constrained so that $X_i$ can use information that has been computed by the parser so far (from the left side and the head), enabling a single-pass evaluation strategy (typical with LR/LL parsing variants under constraints).

Example 1: An L-attributed SDT (therefore also S-attributed)

Consider building the string representation with parentheses removal, or more standardly: computing type checking or constant folding with inherited context from the left.

A classic, simple L-attributed example is computing the prefix-based inherited context such as “the value of a variable’s scope to the left” in a left-to-right grammar. Here’s a compact SDT pattern for computing an expression’s value under operator precedence using synthesized attributes and a left-to-right inherited setup for something like an accumulated result.

Example grammar (toy)

Assume a grammar for left-associative addition:

$$E \rightarrow E + T \mid T$$

Use synthesized attributes for $E$ (common and doesn’t violate either restriction). To illustrate inheritance, consider:

$$E \rightarrow A\;B$$

where $A$ carries a starting inherited value and $B$ uses it.

SDT sketch (L-attributed)

Let:

• Each nonterminal $S$ carry synthesized attribute val.
• For an inherited attribute, let $A$ compute something that must be available for the next symbol.

For production:

$$S \rightarrow A\;B$$

Let:

• $A$ has no inherited attribute,
• $B.inh$ depends only on $S.syn$ (head) and attributes from $A$ (left sibling).

Because $B$’s inherited information depends only on values known after processing $A$ (left-to-right), this is consistent with L-attributed constraints.

Dependency reasoning

• Inherited for $B$ uses only: head $S$ and left symbol $A$.
• Therefore it is allowed for S-attributed, and importantly computable left-to-right ⇒ L-attributed.

Example 2: S-attributed but NOT L-attributed

To show S-attributed but not L-attributed, we need an SDT where:

• inherited attributes satisfy the “only head + left symbols” rule (so it is S-attributed),
• but the particular dependency requires an evaluation order that cannot be produced by left-to-right attribute evaluation.

Key idea

L-attributed SDTs require that when visiting $X_i$ left-to-right, all attributes needed for $X_i.inh$ are already known. If an inherited attribute of $X_i$ depends on a value that, although ultimately coming from the left side, is only computable using information that would require completing evaluation of later parts, then L-attributed fails but S-attributed might still hold structurally.

Concrete SDT pattern (conceptual)

Consider a grammar production:

$$A \rightarrow B\;C\;D$$

Define:

• $B$ has synthesized attribute $b$
• $C$ has inherited attribute $c_{inh}$
• $D$ provides some information needed to compute $b$ (but $b$ is synthesized of $B$ that depends on $D$ through its internal subtree evaluation).

Now impose:

• $c_{inh}$ depends on $b$ and $A.inh$ (head + left sibling)
  So it remains within S-attributed rules: $C.inh$ depends on head $A$ and left symbol $B$. But:
• if $b$ itself requires completion of $D$’s subtree (even though $B$ is left of $C$), then when parsing left-to-right you cannot compute $c_{inh}$ at the moment you reach $C$—because $b$ is not yet available.

This yields S-attributed (dependency graph respects head+left only) but violates the left-to-right evaluation requirement of L-attributed.

Why this breaks L-attributed evaluation

• In a left-to-right evaluation, by the time you reach $C$, you would need $b$.
• But $b$ cannot be computed until after evaluating $D$’s subtree, creating a “future dependency”.
• L-attributed SDTs are designed to prevent exactly this sort of computability issue for inherited attributes.

Summary of Differences (What to remember)

keyword

keyword

keyword

keyword