Adding a Symbol Table (Compiler Series Part VI)

Now that we have a lexer and parser it’s time to add a symbol table for doing type checking. Type checking/Semantic analysis is a huge subject so I’ll be splitting it into several posts.

Our compiler so far consists of the lexer and parser. For a complete compiler we need the following stages (the diagram is taken from figure 1.6 of the second edition of the Dragon Book [1]).

We need the beginnings of a symbol table to start the semantic analysis. The symbol table is what it says it is, a table of symbols. For example the following fragment of pseudo code would have the associated symbol tables

                               symbol_table1 = {}
int x;                         symbol_table1 = {"x" : int_type }
int y;                         symbol_table1 = {"x" : int_type, "y" : int_type}
{
    int z                      symbol_table2 = {"z": int_type}, symbol_table1 = {"x" : int_type, "y" : int_type
}

The above symbol tables only track the type of the variables. The code reveals two things, (1) it is necessary to have a stack of symbol tables to track the scope of a variable’s declaration and (2) to get the type of a variable a search of the symbol table stack must be done with the type determined by the first symbol table in the stack to contain a declaration of that variable (this is so that if a variable is shadowed the correct type is returned). Wikipedia has a good article on symbol tables here [2].

For the NewL compiler the construction of the symbol table and the type checking are very entwined. I determined what to put in the symbol table via what was required for type checking. I ended up with the following definition for two symbol types, one for methods and one for classes.

data ClassSymbol 
    = ClassSymbol 
      {
          className       :: String -- class name
        , publicVariables :: [(String, String)] -- (variable name, variable type name) list of variable
        , methods         :: [(String, MethodSymbol)] -- (method name, method symbol) list of methods
      }
      deriving (Eq)

instance Show ClassSymbol where 
    show (ClassSymbol cName vars methods) = show cName
    
data MethodSymbol = MethodSymbol {
      returnType :: String
    , name       :: String
    , args       :: [(String, String)] -- list of arguments
    } 
    deriving (Show, Eq)

The symbol table itself is an association list of variable names and their type names, for instance the following would be the symbol table upon entering the type checking for a class.

[("this", className)]

In my next post I’ll go into how to use the symbol table for some basic type checking.

References
[1] Compilers : Principles, Techniques, and Tools http://dragonbook.stanford.edu/
[2] Wikipedia : Symbol Table