3.2 S-attributed and L-attributed definitions; which parsers can evaluate which

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

Synthesized or inherited: in A → B C, the rule A.s = B.s + C.s? from Lesson 3.1
Which grammar classes contain LL(1) grammars? from Lesson 2.4.6
What is on the LL(1) parser stack at the start, and how does it expand a nonterminal? from Lesson 2.3.3

1 · The Story

📖

No second pass

Mrs. Desai wants Anaya’s notes filled while Kabir works, not in a second pass over a finished chart.

With Kabir’s pile method (folding from the words up), Anaya can write a note on a category card at the moment Kabir folds it, using the notes on the cards he just removed. That works only if every note is filled from below.

With Chetan’s top-down method, Anaya walks with him: before he starts a part, she can hand it notes from the parent and from parts already finished to its left; when the part is finished, its own notes come back up. That works as long as no note needs something from the right, which has not been read yet.

2 · Predict First

🤔

Can an LR (bottom-up) parser evaluate the declaration SDD for “float a, b” during parsing without any trick? Write your guess down. The answer is in the vault.

3 · Core Concept

S-attributed definitions

An SDD is S-attributed if every attribute is synthesized. Evaluation: any bottom-up (postorder) walk of the parse tree.

An LR parser evaluates it during parsing: keep a value stack in parallel with the state stack. When reducing A → X₁ … Xₖ, the values of X₁ … Xₖ are the top k entries; compute A’s value, pop k, push it. (Example 2.)

L-attributed definitions

An SDD is L-attributed if every attribute is either synthesized, or an inherited attribute of Xⱼ in a production A → X₁ X₂ … Xₙ that depends only on

inherited attributes of A (the parent), and/or
attributes (inherited or synthesized) of X₁ … Xⱼ₋₁ (siblings to the left), and/or
other attributes of Xⱼ itself, without forming a cycle.

Information never comes from the right or from the parent’s synthesized attributes. Every S-attributed SDD is L-attributed.

Evaluating L-attributed SDDs

One depth-first, left-to-right traversal: on entering a child, compute its inherited attributes; on leaving a node, compute its synthesized attributes. A recursive-descent parser does this naturally: inherited attributes are parameters, synthesized attributes are return values.

int Rest(int inh) {            // R → + T R₁  with R₁.inh = R.inh + T.val ; R.syn = R₁.syn
  if (look == '+') { match('+'); int t = T(); return Rest(inh + t); }
  return inh;                   // R → ε     with R.syn = R.inh
}

LL parsers can also do it; LR parsers need extra marker nonterminals (M → ε) to hold inherited values, which works for many but not all L-attributed SDDs.

Summary

SDD class	Allowed dependencies	Evaluated naturally by
S-attributed	synthesized only	bottom-up (LR) during parsing; any postorder walk
L-attributed	synthesized + inherited from parent and left siblings	top-down (LL, recursive descent) during parsing; one left-to-right depth-first walk
neither	e.g. inherited from a right sibling	needs the whole tree and a dependency graph

Story → compiler term

In the story	In the compiler
notes written when Kabir folds a card	S-attributed evaluation at reductions (LR)
handing notes to a part before Chetan starts it	inherited attributes as parameters (top-down)
notes coming back when a part is finished	synthesized attributes as return values
“no note may need something from the right”	the L-attributed restriction
filling notes while working, not afterwards	evaluation during parsing (one pass)

4 · Visual

Stack	Values	Input	Action
`·`	`·`	`n * n + n $`	shift n
`n`	`3`	`* n + n $`	reduce F → n → 3
`F`	`3`	`* n + n $`	reduce T → F → 3
`T`	`3`	`* n + n $`	shift *
`T *`	`3 ·`	`n + n $`	shift n
`T * n`	`3 · 5`	`+ n $`	reduce F → n → 5
`T * F`	`3 · 5`	`+ n $`	reduce T → T * F → 15
`T`	`15`	`+ n $`	reduce E → T → 15
`E`	`15`	`+ n $`	shift +
`E +`	`15 ·`	`n $`	shift n
`E + n`	`15 · 4`	`$`	reduce F → n → 4
`E + F`	`15 · 4`	`$`	reduce T → F → 4
`E + T`	`15 · 4`	`$`	reduce E → E + T → 19
`E`	`19`	`$`	reduce L → E → 19
`L`	`19`	`$`	accept

LR parse of 3 * 5 + 4 with a value stack (desk calculator): 15 rows, final value 19. Each reduce computes the new value from the top of the value stack.

5 · Worked Examples

Example 1 Easy

Classify: (a) the desk calculator; (b) the declaration SDD; (c) A → B C with B.i = C.s; (d) A → B C with C.i = A.s.

Solution

(a) S-attributed (hence also L-attributed). (b) L-attributed: L.inh comes from the left sibling T or from the parent L. (c) Neither: B’s inherited attribute uses its right sibling. (d) Not L-attributed: an inherited attribute may use the parent’s inherited attributes only, not its synthesized ones (A.s is computed after C, a cycle risk). Anaya’s rule: nothing from the right, nothing from the parent’s result.

Example 2 Medium

Trace the value stack while an LR parser evaluates 3 * 5 + 4.

Solution

See the trace above. When T → T * F is reduced, the values 3, ·, 5 are on top; the new value 15 replaces them. When E → E + T is reduced, 15 and 4 give 19. Anaya writes each note exactly when Kabir folds.

Example 3 GATE

Which parser can evaluate each SDD during parsing? S1: S-attributed. S2: L-attributed with inherited attributes. S3: an SDD where an inherited attribute depends on a right sibling.

Solution

S1: a bottom-up (LR) parser, directly; also a top-down parser. S2: a top-down (LL / recursive-descent) parser, directly; an LR parser only with marker nonterminals. S3: neither during parsing; it needs the full tree and a dependency graph.

6 · Shortcuts

⚡

L-attributed test: for every inherited attribute in a rule, check that it uses only the parent’s inherited attributes and left siblings. One right sibling or one parent-synthesized attribute breaks it. Valid when: classifying an SDD from its rules.

⚡

S ⊂ L: if every attribute is synthesized, answer “both”. Valid when: MSQs listing both classes.

7 · GATE Traps

⚠️

Every S-attributed SDD is L-attributed, not the reverse.
Using the parent’s synthesized attribute in a child’s inherited rule breaks L-attributedness.
LR parsers evaluate S-attributed SDDs directly; L-attributed ones need markers.
Recursive descent passes inherited attributes as parameters and returns synthesized ones.
An SDD can be neither: then a single pass during parsing cannot evaluate it.

8 · Memory Hook

🧠

S = Synthesized only = fold time (bottom-up). L = Left-to-right = walk time (top-down).

9 · Connect the Dots

So far rules were attached to whole productions. The next lesson puts small actions between the symbols of a production, which fixes exactly when each one runs, and asks the classic GATE question: what does this scheme print?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markS-attributed

An SDD with only synthesized attributes is:

(A) S-attributed only
(B) L-attributed only
(C) both S-attributed and L-attributed
(D) neither

Q2MCQ2 marksL-attributed

Which rule makes an SDD not L-attributed (production A → B C D)?

(A) C.i = A.i + B.s
(B) D.i = B.s + C.s
(C) B.i = D.s
(D) A.s = B.s + D.s

Q3MCQ1 markParser

An L-attributed SDD (with inherited attributes) is evaluated most naturally during parsing by:

(A) an LR parser with no changes
(B) a recursive-descent (top-down) parser
(C) the lexer
(D) an operator-precedence parser

Q4NAT1 markValue stack

An LR parser evaluates the desk calculator on 2 + 3 * 4. What value is on the value stack when E → E + T is reduced (the value it pushes)?

Numerical answer: ________

Q5MSQ2 marksFacts

Which are true?

(A) An S-attributed SDD can be evaluated in any postorder walk.
(B) An L-attributed SDD can be evaluated in one depth-first, left-to-right walk.
(C) L-attributed rules may use the parent’s synthesized attributes in a child’s inherited attribute.
(D) Recursive descent returns synthesized attributes as function results.

11 · Rule Card

S-attributed: synthesized only → postorder; LR evaluates on reductions with a value stack.
L-attributed: inherited attrs of Xⱼ depend only on A’s inherited and X₁…Xⱼ₋₁ (and Xⱼ, acyclically).
S-attributed ⊂ L-attributed.
L-attributed: one depth-first left-to-right walk; recursive descent: inherited = parameters, synthesized = return values.
LR + inherited attributes: needs marker nonterminals M → ε.

12 · Concept Ledger

S-attributed definitionL-attributed definitionvalue stackevaluation during parsingmarker nonterminal (M → ε)

13 · Answer Vault

Answer Vault

Try the questions first. Open when you are ready to check.

Warm-up

Synthesized (it computes the left side from children).
LL(1) ⊂ LR(1); LL(1) is not contained in SLR or LALR.
$ S; it replaces the nonterminal on top by the right side of M[A, a], pushed in reverse.

Predict First

Not directly. L.inh is inherited and the LR parser builds L before reducing D → T L, so it has no node for L’s parent yet. (Markers or a value-stack trick fix it; a plain postorder walk does not.) The synthesized desk calculator works directly.