Semantic Analysis

A valid parse tree can be built that is gramatically correct, but the program may still be wrong according to the semantics of the language.

Syntax Directed Definitions

Attach rules to a grammar to evaluate some other shit

  • Each nonterminal has a string-valued attribute that represents the expression generated by that nonterminal
    • Symbol used for string concat
    • Notation is attribute of
    • Attributes can be of any kind - numbers, types, table references, strings
  • It's a context free grammar with attributes and rules
    • Can be done in a parse tree - use semantic rules for each node and transform tree in-order
      • Gives annotated parse tree - has attribute values at each node
  • Synthesised attributes are those where the value at the node is determined from attribute values of children
    • Nonterminal at node is defined by semantic rule associated with production at
    • Production must have at it’s head
    • Has the desirable property that they can be evaluated during a single bottom-up traversal
  • SDD with only synthesised attributes is called S-attributed - each rule computes attribute for nonterminal at the head from attributes taken from body
  • Inherited attributes differ from synthesised attributes
    • A nonterminal at a parse tree node is defined by a semantic rule associated with the production at the parent of
      • Production must have as a symbol in it’s body
      • Inherited attributes defined in terms of ’s parents, itself and siblings
  • SDDs have issues - makes grammar large
    • Copy rules copy sets of info around the parse tree
      • Increase space and complexity
      • Can be avoided with a symbol table but that’s outside of this formalism

Dependency Graphs

Determines evaluation order for attribute instances in parse tree

  • Depict flow of information among attribute instances
  • Edge from one attribute instance to another means that value of first is needed to compute second
  • Gives order of evaluation - a topological sort of the graph
  • If there are any cycles there are no topological sorts and SDD cannot be evaluated
  • S-attributed grammars are those where every attributes are synthesised
    • Can be evaluated in any bottom-up order
    • Can evaluate using a post-order traversal
      • Corresponds to order in which LR parse reduces production to head
  • L-attributed grammars are those with synthesises and inherited attributes, but such that dependency graph edges can only go from left to right

Syntax Directed Translations

SDTs are based on SDDs - context free grammar augmented with program fragments called semantic actions

  • Semantic actions can appear anywhere within production body
  • SDTs more implementation oriented than SDDs - indicate order in which actions are evaluated
  • Implemented during parsing without building parse tree
  • Use a symbol table
  • Denoted with braces placed around actions
    • $$ refers to result location for current production
    • $1, $2, ..., $n refer to locations for symbols on the RHS of production
  • To build SDT:
    • Build parse tree ignoring actions
    • For each interior node add additional children for the actions of the productions, from left to right
      • Actions appear to right of productions in tree
      • This gives postfix SDTs
    • Do preorder traversal to evaluate
  • Typically SDTs are done without building a parse tree
    • Consider semantic actions as part of production body
    • During parsing, actions is executed as soon as grammar symbols to the left have been matched
    • Can have productions like
      • If parse bottom-up then is performed as soon as appears on top of stack
      • If parse top-down, is performed before we attempt to expand
  • Postfix SDTs are always LR-parsable, always S-attributed with semantic action at end of production
  • SDTs implementing L-attribute definitions are LL-parsable - pop and perform action when it comes to top of parse stack