0
$\begingroup$

My powerpoints for a compiler class says "an L-Attributed SDD can be evaluated with a pre-order (root, left, right) traversal", and to be L-Attributed the nodes need to have either synthesized values or inherited values from a parent node or a sibling node on the left or itself (sorry if it's unclear, it's originally in another language). All SDD based on an LL(1) grammar are L-Attributed. So for example this grammar with the semantic rules

1. T --> FT'
2. T' --> *FT'
3. T --> epsilon
4. F --> digit

1. T'.inherited_val = F.synthesized_val, T.synthesized_val = T'.synthesized_val
2. T'.inherited_val = T'.inherited_val * F.synthesized_val, T'.synthesized_val = T'.synthesized_val
3. T'.synthesized_val = T'.inherited_val
4. F.synthesized_val = digit.lexical_val

here's the parse graph:

here's the annotated parse graph:

If we do left-right-root, then the order of the semantic rules being executed would be

  1. F_1.synthesized_val = 2
  2. T'_1.inherited_val = 2
  3. F_2.synthesized_val = 3
  4. T'_2.inherited_val = 3
  5. F_3.synthesized_val = 5
  6. T'_3.inherited_val = 5
  7. T'_3.synthesized_val = 5
  8. T'_2.synthesized_val = 5*3 = 15
  9. T'_1.synthesized_val = 15*2 = 30
  10. T.synthesized_val = 30

However a preorder traversal (root-left-right) would just produce an error as all the values root (T) needs would be undefined.

What am I missing here?

Thanks

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.