Differentiate Between S-Attributed SDDs and L-Attributed SDDs (With Examples)

In a syntax-directed definition (SDD), attributes are values associated with grammar symbols. Attributes are computed by semantic rules during parsing.

Two important restrictions are:

• S-attributed: every attribute is synthesized from child attributes only.
• L-attributed: supports efficient evaluation left-to-right during parsing.

The key difference is whether inherited information flows and how far it may flow from other nodes in the parse tree. This affects implementability in top-down parsers and one-pass parsers.

Because I’m required to support “every major claim” with web citations, I must run web searches first; however, my web-search tool is currently unavailable due to a plan/usage limitation, so I cannot legally add the required citations and footnotes.

Core definitions via parse-tree dependencies

Let a parse tree node correspond to a grammar production:

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

Each $X_i$ has attributes; rules specify expressions to compute an attribute from other attributes.

S-attributed SDD

In an S-attributed SDD:

• All attributes are synthesized.
• For each node $X_i$, its attribute can be computed only from attributes of its children (i.e., information flows bottom-up).
• No inherited attributes are allowed (or, equivalently, inherited values are never needed to compute rules).

Dependency property (informal):
A semantic rule for computing an attribute of $X_i$ depends only on:

• attributes of symbols in the subtree rooted at $X_i$.

L-attributed SDD

In an L-attributed SDD:

• Both synthesized and inherited attributes exist.
• Inherited attributes for $X_i$ may depend only on:
  • attributes of the parent $A$, and
  • attributes of symbols to the left of $X_i$ (i.e., $X_1, \dots, X_{i-1}$),
• and (crucially) not on right siblings $X_{i+1}, \dots, X_n$.

This restriction ensures that during parsing left-to-right, when you are about to process $X_i$, all permitted information is already available.

Differentiation Table (What’s allowed?)

Suitable examples

Example 1: Type annotation / expression semantics (S-attributed vs L-attributed idea)

A classic use of attributes is expression translation/type checking. Consider a simple expression grammar:

$$\begin{aligned} E &\\rightarrow E_1 + T \mid T \\\\ T &\\rightarrow id \end{aligned}$$

A “compute the value” style rule can often be synthesized:

• For $E \rightarrow E_1 + T$, compute $\text{val}(E) = \text{val}(E_1) + \text{val}(T)$. This is S-attributed because the needed values come from children.

However, if you introduce an inherited environment (like symbol-table scopes) to decide $id$ types or declarations, you may need inherited attributes:

• let $\text{env}(E)$ or $\text{env}(T)$ be passed from parent (and possibly from left siblings in longer productions).

That inherited flow is where L-attributed becomes necessary: it permits inherited attributes, but restricts their dependencies to parent and left siblings.

---

Example 2: Argument counting or context-sensitive computation in productions

Suppose we have a production that processes a list left-to-right:

$$\text{List} \\rightarrow \\text{List} \\; , \\; \\text{Item} \\;\\;\\mid\\; \\text{Item}$$

If you define:

• $\text{count}(\text{List})$ as the number of items, then you can compute it by:
• synthesized rules: $\text{count}(\text{List}, \\; ,\\; \\text{Item}) = \text{count}(\text{List}) + 1$

This is naturally S-attributed.

But if instead you want to compute, for example, the “index position” or whether an item is preceded by a comma in a way that depends on earlier context within a longer production $A \\rightarrow X_1 X_2 X_3$, you may need inherited attributes to pass computed context into later symbols—yet only from the parent/left side to remain L-attributed.