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 $X.a$ is attribute $a$ of $X$
  • 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 $A$ at node $N$ is defined by semantic rule associated with production at $N$
  • Production must have $A$ 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 $B$ at a parse tree node $N$ is defined by a semantic rule associated with the production at the parent of $N$
    • Production must have $B$ as a symbol in it’s body
    • Inherited attributes defined in terms of $N$’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 $B\to X\{a\}Y$
    • If parse bottom-up then $a$ is performed as soon as $X$ appears on top of stack
    • If parse top-down, $a$ is performed before we attempt to expand $Y$
• 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