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]).

Compiler Stages

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.

[1] Compilers : Principles, Techniques, and Tools
[2] Wikipedia : Symbol Table


2 thoughts on “Adding a Symbol Table (Compiler Series Part VI)

  1. Pingback: Writing A Compiler In Haskell (Compiler Series Part I) « A blog on math

  2. Pingback: Cleaning up NewL and Adding a Symbol Table Part II (Compiler Series Part VII) « A blog on math

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s