S-attribute SDT vs L-attribute SDT

S-Attribute (Synthesized) SDTs

• An SDT is S-attributed ("synthesized") if every attribute is a synthesized attribute — computed from the children of a nonterminal.
• All the evaluation is bottom-up.
• An S-attributed SDT can be evaluated during a bottom-up parse — the semantic action is placed at the right end of the production: A → α { do action }.
• Supported: only bottom-up based LL/LR? Precisely: LR parser can implement any S-attributed SDD without changing the parsing stack (just attach the attributes value with each stack symbol).

L-Attributed SDTs

• An SDT is L-attributed when:
  1. each attribute is either synthesized, or inherited, and
  2. inherited attributes depend only on: attributes of the left siblings, the parent, and attributes of the symbols themselves (i.e. dependencies can flow from left to right, and from parent → children).
• Condition: In the production $A \to X_1 X_2 \dots X_n$, an inherited attribute of $X_i$ can only depend on:
  • attributes of $X_1,X_2,\dots, X_{i-1}$ (the symbols to its left), and
  • inherited attributes of $A$ (the parent).
• Evaluation is basically top-down / left-to-right — works with LL / predictive parsers too, and can be implemented in a top-down or LR parser with suitable actions.

Key differences:

Point	S-attributed	L-attributed
Attributes	All synthesized	synthesized + inherited (with L- constraint)
Evaluation pass	bottom–up	depth-first left-to-right following structure
Parser suitable	any LR / bottom-up	LL / top-down (recursive-descent; LR also if aug.)
Action placement	can move to the end of RHS	must keep in position (actions constrained)
Which is larger	—	L is a superset of S

Every S-attributed definition is also L-attributed, but not vice versa.

Example

S-attribute example: grammar with val
$$E \to E_1+T \quad E.val=E_1.val+T.val$$
All attributes synthesized ⇒ S-attributed (also L).

L-attribute (non-S) example: an inherited attribute such as in a C float conversion
$$Y \to X_1 X_2 \quad Y.inh=...\,;\ X_1.inh=..., X_2.inh=f(Y.inh, X_1.att)$$
For instance, declaring arrays:
D → T L, L → id , L_1; L.inh = T.type; L1.inh = L.inh. The inherited attribute inh must always be computed before the symbol is parsed — that's the left-to-right constraint.

Summary: an S-SDT = simply synthesized attributes; evaluate bottom-up. L-SDT = a wider class, allows inherited attributes under the restriction that they use only attributes from the left (or inherited from context above) — evaluated in a depth-first left-first traversal. Since L is a superset of S, any S-scheme is a special case of L.