c++compiler-constructionsymbol-tablesemantic-analysis

How to avoid ambiguity within symbol table lookups?


I have a rather rudimentary symbol table to map a identifier to a symbol, storing VariableSymbols, MethodSymbols, BuiltInTypeSymbols etc. This has worked fine for my simple interpreter. However now I want to implement more advanced symbol types such as tuples (say - TupleSymbol) which stores an array of BuiltInTypes.

I can easily implement a TupleSymbol and store it in the table, but I have realised that continuing the use of my current map-to-symbol approach for storing types will eventually lead to a lot of ambiguous symbol types upon symbol table lookups. For example, if I want to assign a tuple to a tuple variable named "test", within an assign operation I will have to check if the Symbol stored in the table for the identifier "test" is a TupleSymbol or a BuiltInTypeSymbol, and I will have to do the same for the value I want to assign to it.

Is there a better way of implementing a symbol table? For example is it best to have multiple areas in a symbol table scope storing each type of symbol separately, i.e. std::map<std::string, MethodSymbol> for methods and std::map<std::string, VarSymbol> for variables?

Edit

Here's some code to help visualise my current design. Note how the symbol table map symbolTable uses the base Symbol class.

class BuiltInTypeSymbol;
class Symbol {
    public:
       BuiltInTypeSymbol* type;
       std::string name;
       Symbol(std::string inname, BuiltInTypeSymbol* intype) : name(inname), type(intype){}
};

class BuiltInTypeSymbol : public Symbol {
    public:
       BuiltInTypeSymbol(std::string inname) : Symbol(inname, this) {}
}

class VarSymbol : public Symbol {
    public:
       VarSymbol(std::string inname, BuiltInTypeSymbol* typesymbol) : Symbol(inname, typesymbol) {}
}

BuiltInTypeSymbol* intType = new BuiltInTypeSymbol("int");
BuiltInTypeSymbol* floatType = new BuiltInTypeSymbol("float");

std::map<std::string, Symbol*> symbolTable = {
     {intType->name, intType}, // registering int type
     {floatType->name, floatType}, // registering float type
     {"a", new VarSymbol("a", intType)} // registering test variable "a" of type int
};

Solution

  • If you allow duplicate symbol names for different types, as most languages allow, for example the same name for a variable and a function you need to go with different maps for each type.

    Also you probably need to iterate over some symbol type, for example built-in symbols - it's a good idea to create a map for them as well.