Today s Lecture Symbol Tables Type Checking Computer Science 320 Prof David Walker 1 Symbol Tables Source Lexer Stream of Tokens Parser Abstract Syntax Tree Semantic Analysis IR Back End Target Semantic Analysis Phase Type check AST to make sure each expression has correct type Translate AST into IR trees Main data structure used by semantic analysis symbol table Contains entries mapping identifiers to their bindings e g type As new type variable function declarations encountered symbol table augmented with entries mapping identifiers to bindings When identifier subsequently used symbol table consulted to find info about identifier When identifier goes out of scope entries are removed Computer Science 320 Prof David Walker 2 Symbol Table Example function f b int c int print int b c let var j b var a x in print a print j end print int a 0 a int 1 b int c int a int 2 j int b int c int a int 3 a string j int b int c int a int 1 b int c int a int 0 a int Computer Science 320 Prof David Walker 3 Symbol Table Implementation Imperative Style side effects Global symbol table When beginning of scope entered entries added to table using side effects old table destroyed When end of scope reached auxiliary info used to remove previous additions old table reconstructed Functional Style no side effects When beginning of scope entered new environment created by adding to old one but old table remains intact When end of scope reached retrieve old table Computer Science 320 Prof David Walker 4 Imperative Symbol Tables Symbol tables must permit fast lookup of identifiers Hash Tables an array of buckets Bucket linked list of entries each entry maps identifier to binding 0 1 2 n 1 a int c string b int d int Suppose we with to lookup entry for id i in symbol table 1 Apply hash function to key i to get array element j 0 n 1 2 Traverse bucket in table j in order to find binding b table x all entries whose keys hash to x Computer Science 320 Prof David Walker 5 Imperative Symbol Tables val size 109 prime number type binding type bucket string binding list type table bucket Array array val t table Array array SIZE nil assume fun hash s string 0 j SIZE exception notFound fun lookup s string let val i hash s fun search s b rest if s s then b else search rest search raise notFound in search Array sub t i end Computer Science 320 Prof David Walker 6 Imperative Symbol Tables fun insert s string b binding let val i hash s in Array update t i s b Array sub t i end Inserts new element at front of bucket insert a string i i a int a string a int Computer Science 320 Prof David Walker 7 Imperative Symbol Tables To restore hash table pop items off items at front of bucket fun pop s string let val i hash s val s b rest Array sub t i in assert s s Array update t i rest end Computer Science 320 Prof David Walker 8 Functional Symbol Tables Hash tables not efficient for functional symbol tables Insert a string copy array share buckets Old Symbol Table Array i New Symbol Table Array i a int a string Not feasible to copy array each time entry added to table Computer Science 320 Prof David Walker 9 Functional Symbol Tables Better method use binary search trees BSTs Functional additions easy Need less than ordering to build tree Each node contains mapping from identifier key to binding Use string comparison for less than ordering For all nodes n L key n key l For all nodes n R key n key l l L Computer Science 320 Prof David Walker R 10 Functional Symbol Table Example Lookup f int c int t int d int Computer Science 320 Prof David Walker s int 11 Functional Symbol Table Example Insert insert z int create node z copy all ancestors of z f int f int c int d int Computer Science 320 Prof David Walker t int t int z int s int 12 Issues With Table Implementations When key value string need to do expensive string compares when doing lookup operation Solution use symbol data structure instead Each symbol object associated with integer value All occurrences of same string map onto same symbol 2 different strings map onto different symbols key value symbol do cheap integer comparisons during lookup Computer Science 320 Prof David Walker 13 Issues With Table Implementations signature SYMBOL sig eqtype symbol val symbol string symbol val name symbol string type a table val empty a table val enter a table symbol a a table val look a table symbol a option end Implements symbol tables function using BSTs Table is polymorphic each entry maps symbol to binding of type a Need type bindings for type symbols Need value bindings for variable and function symbols Computer Science 320 Prof David Walker 14 Issues With Table Implementations structure Symbol SYMBOL struct type symbol string int val nextsym ref 0 fun symbol name string case HashTable find hashtable name of SOME i name i NONE let val i nextsym in nextsym i 1 HashTable insert hashtable name i name i end Computer Science 320 Prof David Walker 15 Issues With Table Implementations fun name s n s type a table a IntBinaryMap map val empty IntBinaryMap empty fun enter t a table s n symbol a a IntBinaryMap insert t n a fun look t a table s n symbol IntBinaryMap look t n end Computer Science 320 Prof David Walker 16 Environments in Tiger Compiler Two name spaces types variables functions two environments type environment maps types symbols to type that it stands for value environment Maps variable symbols to their types Maps function symbols to parameter and result types Computer Science 320 Prof David Walker 17 Type Environment structure Types struct type unique unit ref datatype ty INT STRING RECORD of Symbol symbol ty list unique ARRAY of ty unique NIL UNIT NAME of Symbol symbol ty option ref end In order to distinguish each record type associate unit ref value with RECORD data constructor Each ref is unique Can compare it with another unit ref for equality NAME used when processing mutually recursive types placeholder for types whose name is known but whose definition has yet to be seen Computer Science 320 Prof David Walker 18 Value Environment signature ENV sig type access type ty datatype enventry VarEntry of ty ty FunEntry of formals ty list result ty val base tenv ty Symbol table val base venv enventry Symbol table end base tenv contains int INT string STRING base venv contains predefined functions in appendix Computer Science 320 Prof David Walker 19 Type Checking Symbol structure implements functional symbol tables using BSTs type a table environment contains mappings from symbol to a