Today in CS362: Symbol Tables

Admin
* Candy
* No lab tomorrow!  We all need a week off.
* How are the parsers going?
  + Our target is now mid-level assembly and not x86
  + /home/rebelsky/Web/Courses/CS362/2002F/Examples/
    rebelsky/compiler/pascal
    rebelsky/compiler/lexer
    rebelsky/compiler/parser
* Get ready to start your type checkers:
  + Minimally: Reals, Integers, Booleans, and expressions
  + Preferably: Records, Arrays, Procedure Calls, Function Calls, 
    etc.
* Side note: How a bad compiler can bring down a system.
case (x) of
  1..100: S
end case
...
if (x = 1) then S;
if (x = 2) then S;
if (x = 3) then S;
if (x = 4) then S;

* Daren's talk

Overview
* What is a symbol table?
* Nesting and scoping, revisited
* Implementation options
* Translation strategies

Goal: Translation from a nice-ly pruned parse tree to 
PAL.  

Tools that help:
* Stack frame (helps us think about procedure calls)
* Pretend you have an infinite number of registers
  (temporaries)
* You need a helper procedure to allocate those temporaries

How will the translation process work?
Walk through the parse tree, generating code as we go.
Attach a "translation" attribute to each node in the
parse tree.

When we refer to variables, procedures, and other named
things, we often need to look up "attributes" somewhere.
The part of the compiler that associates attributes with
names is called the "SYMBOL TABLE"

At the basic form, a symbol table is simply a kind of map

program xxx(input,output)
  type:
    count = integer;
  var
    x,i: integer;
    y: real;
    c: count;
  function foo(aardvark: integer): real;
    var
      q,r: real;
    begin
     ...
    end;
begin
  x := i;
end.

What are the keys in our map?
What are the associated values?
* x: type:integer variable; 
     memory-location: offset of N from stack-frame for program
     initialized: false
* y: type: real;
* foo: type: function from integer to real;
       location of code: address
       size of stack frame: xxx
* baz: type: function from (integer,real,string) to real
* q,r: type: real
* aardvark: 
* input,output: type: stream (predefined)
* c: type: count
* xxx: type: program
* count: type: type

Observation: We have to deal with scope
Techniques:
(1) Create a new symbol table when you enter a scope,
    delete that symbol table when you exit the scope
(1a) Need a stack of symbol tables <- BETTER
(1b) Copy all values from previous symbol table into
  new symbol table (may need to replace)
(2) Keep a stack of information about each symbol in
  the symbol table

Side Observation: Defined and Declared are different words

Question: How do you deal with the infinite number of
function types:

Answer:

class Function
  implements Type
{
  Type[] parameters;
  Type resultType;
  ...
}

symbols.addType("foo", new Function(new Type[1]{Integer}, Integer);

Practicum:

<block> ::= 
  { create a new symbol table and push it on the symtab stack }
  <constant-declarations> // updates symbol table
  <type-declarations> // updates symbol table
  <variable-declarations> // updates symbol table
  <function-and-procedure-declarations> // updates symbol table
  begin
  <statement-list> // uses symbol table
  end
  { pop the symbol table off of the symtab stack }