2015-02-26
Code Generation (Ch. 5-6)

Chapter 5: Syntax-Directed Translation (SDT)

basic concept: associate attributes with syntax tree nodes,
               then use them for translation

cartoon on the front cover

inherited (top-down) vs. synthesized (bottom-up) attributes
  - inherited: defined in terms of the node, its parent, and its siblings
  - synthesized: defined in terms of the node and its children

SDD: Syntax-Directed Definition

S-attributed SDDs ("synthesized")
  - only synthesized (bottom-up) attributes
  - more restrictive
  - most suitable for LR parsing (more permissive grammar)
      "every S-attributed SDD can be implemented in an LR parse"

L-attributed SDDs ("left-to-right")
  - synthesized attributes
      OR
  - inherited (top-down) attributes with a left-to-right dependency graph
  - less restrictive
  - most suitable for LL parsing (stricter grammar)
      "every L-attributed SDD can be implemented in an LL parse"

trick: use "markers" to implement L-attributed SDDs in an LR parse
  - replace embedded actions with fake "marker" non-terminals
  - attributes needed by the markers willall always be available on the stack

overall goal of SDT: perform translation WHILE parsing
  - embed translation commands (side effects) into grammar