Today’s Lecture• Symbol Tables• Type CheckingComputer Science 320Prof. David Walker-1-Symbol TablesLexer Parser Back EndSourceStream ofTokensAbstractSyntax Tree TargetIR’’’SemanticAnalysis• 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 aug-mented with entries mapping identifiers to bindings.– When identifier subsequently used, symbol table consulted to find info aboutidentifier.– When identifier goes out of scope, entries are removed.Computer Science 320Prof. David Walker-2-Symbol Table Examplefunction f(b:int,c:int) =(print_int(b+c);letvar j := bvar a := "x"inprint(a)print(j)endprint_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 320Prof. 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. (oldtable 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 oldone, but old table remains intact.– When end-of-scope reached, retrieve old table.Computer Science 320Prof. David Walker-4-Imperative Symbol TablesSymbol tables must permit fast lookup of identifiers.• Hash Tables - an array of buckets• Bucket - linked list of entries (each entry maps identifier to binding)a->intb->intc->stringd->int0 1 2 ... n-1• 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 320Prof. David Walker-5-Imperative Symbol Tablesval size = 109 (* prime number *)type binding = ...type bucket = (string * binding) listtype table = bucket Array.arrayval t:table = Array.array(SIZE, nil)(* assume: fun hash(s:string) -> 0 <= j < SIZE *)exception notFoundfun lookup(s:string) =letval i = hash(s)fun search((s’, b)::rest) = if s = s’ then belse search rest| search([]) = raise notFoundinsearch(Array.sub(t,i))endComputer Science 320Prof. David Walker-6-Imperative Symbol Tablesfun insert(s:string, b:binding) =letval i = hash(s)inArray.update(t,i,(s,b)::Array.sub(t,i))endInserts new element at front of bucket.insert a → stringa -> inta -> inta -> stringiiComputer Science 320Prof. David Walker-7-Imperative Symbol TablesTo restore hash table, pop items off items at front of bucket.fun pop(s:string) =letval i = hash(s)val (s’, b)::rest = Array.sub(t,i)inassert(s = s’)Array.update(t,i,rest)endComputer Science 320Prof. David Walker-8-Functional Symbol TablesHash tables not efficient for functional symbol tables.Insert a → string ⇒ copy array, share buckets:a -> int a -> stringiiOld Symbol Table Array New Symbol Table ArrayNot feasible to copy array each time entry added to table.Computer Science 320Prof. David Walker-9-Functional Symbol TablesBetter 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)LRlComputer Science 320Prof. David Walker-10-Functional Symbol Table ExampleLookup:f->intc->intd->intt->ints->intComputer Science 320Prof. David Walker-11-Functional Symbol Table ExampleInsert:insert z → int, create node z, copy all ancestors of z:f->intc->intd->intt->ints->intf->intt->intz->intComputer Science 320Prof. David Walker-12-Issues With Table ImplementationsWhen 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 ontodifferent symbols)• key value = symbol ⇒ do cheap integer comparisons during lookupComputer Science 320Prof. David Walker-13-Issues With Table Implementationssignature SYMBOL = sigeqtype symbolval symbol:string -> symbolval name:symbol -> stringtype ’a tableval empty:’a tableval enter:’a table * symbol * ’a -> ’a tableval look:’a table * symbol -> ’a optionend• 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 320Prof. David Walker-14-Issues With Table Implementationsstructure Symbol:SYMBOL =structtype symbol = string * intval nextsym = ref 0fun symbol(name:string) =case HashTable.find hashtable name ofSOME(i) => (name, i)| NONE => letval i = !nextsyminnextsym := i + 1;HashTable.insert hashtable(name, i);(name, i)endComputer Science 320Prof. David Walker-15-Issues With Table Implementationsfun name((s,n)) = stype ’a table = ’a IntBinaryMap.mapval empty = IntBinaryMap.emptyfun 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)endComputer Science 320Prof. David Walker-16-Environments in Tiger CompilerTwo 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 320Prof. David Walker-17-Type Environmentstructure Types = structtype unique = unit refdatatype ty = INT| STRING| RECORD of (Symbol.symbol * ty) list * unique| ARRAY of ty * unique| NIL| UNIT| NAME of Symbol.symbol * ty option refend• In order to distinguish each record type, associate unit ref value with RECORD dataconstructor– Each ref is unique.– Can compare it with another unit ref for equality.• NAME: used when processing