CSC362 2004S, Class 24: Semantic Actions

Admin:
* Train data: 1:11
* Mea Culpa (or why never to ask SamR to write letters of recc.)
* Break
* Yay Jonathan!  Yay Grinnell Putnam team

Overview
* Adding attributes to parse trees
* Example: Evaluating expressions
* Computing the values of attributes
* Example: Typing expressions
* Example: Sequences of assignments

Reminder: Status
* Front end: From source code to "intermediate code"
  * Lexical analysis (done)
  * Syntactic analysis (mostly done)
  * Type checking (now)
  * Intermediate code generation (soon)
* Back end: From "intermediate code" to target code
  * Optimize
  * Translate
  * Optimize

Attribute generation: Traverse the parse tree and compute "values" based
on the structure of and values in the parse tree.
* Traditionally, we attach these computed values to nodes in the treeq
* Values are computed based on neighboring values
* The value of the root is the "endpoint" of the process

Traditional computer science method: add rules to the grammar that specify
how values are computed

E.g.,

Production:
  exp0 ::= exp1 PLUS exp2
Associated rule:
  exp0.value = exp1.value + exp2.value

BUT THIS PRODUCTION IS NOT IN THE NORMAL UNAMBIGUOUS EXPRESSION GRAMMAR
that uses term, factor, and such.

exp0 ::= exp1 PLUS term
  exp0.value = exp1.value + term.value
exp0 ::= exp1 MINUS term
  exp0.value = exp1.value - term.value
exp ::= term
  exp.value = term.value
term0 ::= term1 TIMES factor
  term0.value = term1.value * factor.value
term0 ::= term1 DIVIDE factor
  term0.value = term1.value / factor.value
term ::= factor
  term.value = factor.value
factor ::= OPEN exp CLOSE
  factor.value = exp.value
factor ::= NUM
  factor.value = NUM.value

[Example on board]

Observation: In this exampel, all the attributes are computed from attributes of children
Question: Are there ever times we want the attributes to be computed from attributes of parents or neighbors?
* One possibility: 
  <variable-decl> ::= <type-id> <id-list>
* Symbol table: For each variable, give type of variable (and perhaps its memory location)
  * One way to compute a table
    <variable-decl>.table ::= map(lambda (id) <type-id>.type) <id-list>.ids
    "The table assigns each id in id-list to the type given by type-id"
  * Another way to compute the table
  <variable-decl> ::= <type-id> <id-list>
    <id-list>.type = <type-id>.type
    <id-list>.in-table = empty-table
  <id-list> ::= <id>
    <id-list>.out-table = <id-list>.in-table + (<id>.id -> <id-list>.type)
  <id-list>0 ::= <id> COMMA <id-list>1
    <id-list>1.in-table = <id-list>0.in-table + (<id>.id -> <id-list>.type)
    <id-list>1.type = <id-list>0.type
    <id-list>0.out-table = <id-list>1.out-table
* ObservatioN: The first way is all "bottom up"; the second way is both top-down and bottom-up

Suppose you want to be general about this: Allow both top-down and bottom-up dependencies of values.  How do you decide what order in which to compute the attributes?
* The theory response: Build a directed graph of dependencies and topologically sort it
  * Topological sort: Given a directed graph, put the nodes in order such that: No node appears before any of its predecessors
* The practice response (1): Limit your rules (e.g. to only bottom-up)
* Another practice response: Write programs that know how to navigate

Almost everything you want to compute from here on (types, symbol tables, code) are done by walking the tree either using these kinds of rules or by writing "navigation programs"
* next class: "Navigation programs" that type check