Evaluation of Attributes in a Syntax Tree
1. Problem
Given a parse tree + SDD rules, in what order do we compute attributes so every dependency is ready? Answer: topological order of the dependency graph; in practice one DFS / single pass for S- and L-attributed grammars.
2. Dependency Graph Method
for each node N with production P: edge from each used attribute to defined attribute
if graph has cycle → SDD is circular (unevaluable); else topological sort gives order
Example E → E+T with E.val = E1.val + T.val: edges E1.val → E.val, T.val → E.val → evaluate children first.
3. Practical Evaluators
| Grammar | Method |
|---|---|
| S-attributed | bottom-up on LR stack: keep val alongside symbols; reduce computes parent |
| L-attributed | depth-first left-to-right: pass inherited on entry, return synthesized on exit (recursive descent / LL) |
| General | multiple passes or graph + topological sort |
4. Worked — 3+4*2 (val)
leaves: 3,4,2 → T(4*2)=8 (reduce *) → E(3+8)=11 (reduce +)
stack evaluator: shift 3 → reduce T → ... → on E→E+T pop 3 vals, push sum
5. Exam Points
- Explain dependency graph + topological order — 5 marks, very frequent.
- S-attributed on LR stack vs L-attributed DFS — 5 marks, frequent.
- Detect circular SDD — 3 marks, frequent.