Flow of Attributes in a Syntax Tree

Flow of Attributes in a Syntax Tree

1. Meaning

Flow = direction attributes travel over the tree. Synthesized flows up, inherited flows down/sideways. A correct evaluator follows the flow in one depth-first pass for L-attributed grammars.

2. Flow Patterns

synthesized:   child.val ──→ parent.val   (up)
inherited:     parent.inh ──→ child.inh   (down)
               left_sibling ──→ right_sibling (sideways, left-to-right only)

L-attributed restriction: inherited(X) may use only inherited(parent) + synthesized(left siblings) — guarantees left-to-right single pass.

3. Example — declarations int a, b

D → T L   { L.inh = T.type }        // type flows down to list
L → L1 , id { add(id,T=L.inh); L1.inh = L.inh }  // flows sideways
T → int   { T.type = integer }

Tree: T.type=integer flows down into L chain, each id gets type. Cannot flow right-to-left (would need multiple passes).

4. Implementation

• Inherited: procedure argument (recursive descent) or stack field set before pushing child.
• Synthesized: return value or stack field set on reduce.

5. Exam Points

• Draw attribute flow arrows on tree — 5 marks, very frequent.
• State L-attributed flow restriction — 3-5 marks, frequent.
• Declaration type-propagation example — 5 marks, frequent.