CPSC 411 - Lab Notes - 03-16 (Symbol Table)

We reviewed the functionality of the symbol table and what data structures would be required to implement it.

The four basic functions of the symbol table are:

st.newscope()
Prepares the symbol table to accept new entries at a new scope level. This is like a "push"
st.removescope()
Removes the latest scope and all definitions made at that scope level. A "pop"
st.insert(dec)
Inserts the information from a declaration into the symbol table. Random table insert.
st.lookup(id)
Finds an identifier in the symbol table and returns it's information. Random table lookup.

The first two functions describe a stack. This is done via lists in python. The next two functions describe a map in python. Therefore, in the initialization of the symbol table class we set up these two pieces of information.

class SymbolTable:
    def __init__(self):
        self.__symbol_table={}   # dict of ids -> [stentries]
        self.level=0
        self.identifiers_at_level_list=[[]]  # list of ids at this level

As the comments indicate, the list will have a list of ids at a scope level as its entries. The dictionary entries are a list of stenries. We don't go into the detail of these at this stage, just note that they contain the information we need about an identifier to create the ir.

Next we examine pushing and popping a scope.

   def newscope(self):
        self.level += 1
        self.identifiers_at_level_list.append([])

Because of our dictionary construction, the newscope function is simple. It simply increments the level and appends another list to hold the new variables at this scope.

    def removescope(self):
        if self.level == 0: return
        try:
            for id in self.identifiers_at_level_list[-1]:
                self.__symbol_table[id].pop()
            self.identifiers_at_level_list.pop()
            if 0 == self.identifiers_at_level_list.length():
                self.__symbol_table.remove(id)
            self.level -= 1
        except:
            print "Internal symbol table error"
            raise

Removing a scope is more complicated. We need to run through our dictionary, removing any entries added at this level. If we remove the last entry for an identifier, we need to actually remove it entirely from the dictionary.

Inserting entries into the scope is straightforward. We pass the details of creating the actual entries to a helper function, then add to the table. We either append it to the current entries, or create a new one.

def insert(self,declaration):
    (id, entry) = make_entry(declaration, level)
    if id in self.identifiers_at_level_list[-1]:
        raise semanticError("Duplicate id." + id)
    try:
        self.__symbol_table[d].append(newentry)
    except:
        self.__symbol_table[d] = [newentry]

Finally, lookup is very straightforward.

def lookup(self, lookup_id):
    try:
        sentry = self.__symbol_table[lookup_id][-1]
    except:
        raise semanticError("Identifier not found:"+lookup_id)
    return sentry
Last modified by Brett Giles

Last modified: Mon Mar 31 15:27:40 MST 2003 Valid XHTML 1.0!