一个简单的解释器（8）—— symbol table

OK，接下来我们需要面对更加严肃的问题：如何构建一个真正的解释器？
前几章的内容已经足够的有趣，但是仅仅是添加grammar，然后一步一步实现Lexer，AST nodes，Syntax analysis等内容是不够的，我们还要管理代码中的全局变量、局部变量、函数、函数嵌套等等问题，为此，我们需要打下一个足够好的地基，然后才能真正地实现一个解释器，并且不至于让代码变成屎山。

Symbol table

首先，我们引入一个新的概念：符号表（Symbol table），符号表需要完成这样一个功能：存储代码中的所有符号和它对应的类型。
比如：

PROGRAM part8;
VAR:
    a: INTEGER;
BEGIN
END;

这段代码里，有两个符号：a和INTEGER，INTEGER是内置类型，a是INTEGER类型的变量。
为此，我们先写一个Symbol类：

#pragma once
#include <string>
#include <memory>

class Symbol;
typedef std::shared_ptr<Symbol> SymbolPtr;
typedef Symbol* const SymbolRawPtr;

class Symbol
{
protected:
    std::string symbolName;
    SymbolPtr symbolType;
public:
    virtual SymbolRawPtr getType() = 0;
    std::string getName();
};

它负责存储符号的名字跟类型，并且类型本身又指向一个Symbol类，然后写一个继承了Symbol类的BuiltinTypeSymbol类来表示内置类型：

#pragma once
#include "Symbol/Symbol.h"

class BuiltinTypeSymbol : public Symbol
{
public:
    BuiltinTypeSymbol(std::string sName);
    SymbolRawPtr getType();
};

它不需要做任何事，只需要在getType时返回自身即可：

#include "Symbol/BuiltinTypeSymbol.h"

BuiltinTypeSymbol::BuiltinTypeSymbol(std::string sName)
{
    symbolName = sName;
}

SymbolRawPtr BuiltinTypeSymbol::getType()
{
    return this;
}

对于变量，定义一个VarSymbol：

#pragma once
#include "Symbol/Symbol.h"

class VarSymbol : public Symbol
{
public:
    VarSymbol(std::string varName, SymbolPtr varType);
    SymbolRawPtr getType();
};

它需要记录两个成员：变量名和变量类型，并且getType时返回varType所指向的Symbol，这里，varType会指向一个BultinTypeSymbol。
接下来，我们需要一张符号表，它负责记录代码中所有的符号：

#pragma once
#include <map>
#include <string>
#include "Symbol/Symbol.h"

class SymbolTable
{
private:
    std::map<std::string, SymbolPtr> symbols;
public:
    SymbolTable();
    void define(SymbolPtr symbolPtr);
    SymbolPtr lookup(std::string symbolName);
    std::map<std::string, SymbolPtr> getAll() const;
};

这里主要需要实现两个函数：define和lookup，以便通过符号名找到对应的符号：

#include "Symbol/SymbolTable.h"
#include "Symbol/BuiltinTypeSymbol.h"

SymbolTable::SymbolTable()
{
    define(std::make_shared<BuiltinTypeSymbol>("INTEGER"));
    define(std::make_shared<BuiltinTypeSymbol>("REAL"));
}

void SymbolTable::define(SymbolPtr symbolPtr)
{
    symbols[symbolPtr->getName()] = symbolPtr;
}

SymbolPtr SymbolTable::lookup(std::string symbolName)
{
    if (symbols.find(symbolName) == symbols.end()) 
    {
        throw "symbol error";
    }
    return symbols[symbolName];
}

std::map<std::string, SymbolPtr> SymbolTable::getAll() const
{
    return symbols;
}

注意这里将INTEGER和REAL两个符号作为内置类型，在构造时调用define函数。
下一步，实现一个SymbolTableBuilder，它继承自NodeVisitor，但是不同于Interpreter，它不用解释代码，它要做的只是访问node时记录代码中的符号，声明如下：

#pragma once
#include "NodeVisitor/NodeVisitor.h"
#include "ASTNodes/ProgramNode.h"
#include "ASTNodes/BlockNode.h"
#include "ASTNodes/BinOpNode.h"
#include "ASTNodes/NumNode.h"
#include "ASTNodes/UnaryOpNode.h"
#include "ASTNodes/CompoundNode.h"
#include "ASTNodes/NoOpNode.h"
#include "ASTNodes/VarDeclNode.h"
#include "ASTNodes/VarNode.h"
#include "ASTNodes/AssignNode.h"
#include "Symbol/SymbolTable.h"

class SymbolTableBuilder : public NodeVisitor
{
private:
    SymbolTable symTable;
private:
    DECLARE_VISITOR(ProgramNode);
    DECLARE_VISITOR(BlockNode);
    DECLARE_VISITOR(BinOpNode);
    DECLARE_VISITOR(NumNode);
    DECLARE_VISITOR(UnaryOpNode);
    DECLARE_VISITOR(CompoundNode);
    DECLARE_VISITOR(NoOpNode);
    DECLARE_VISITOR(VarDeclNode);
    DECLARE_VISITOR(VarNode);
    DECLARE_VISITOR(AssignNode);
public:
    SymbolTableBuilder();
    SymbolTable getSymbolTable() const;
};

类似Interpreter，SymbolTableBuilder需要对每一种node实现一个visit函数，其中最关键的是VarDeclNode和AssignNode，他们分别实现变量的声明和赋值（这里暂时不实现赋值的逻辑，只是调用lookup）：

SYM_TABLE_BUILDER_VISITOR(VarDeclNode) 
{
    auto node = std::dynamic_pointer_cast<VarDeclNode>(nodePtr);
    auto typeName = std::get<std::string>(node->getType()->getTokenPtr()->getValue());
    auto typeSymbol = symTable.lookup(typeName);
    std::string varName = std::get<std::string>(node->getVar()->getTokenPtr()->getValue());
    symTable.define(std::make_shared<VarSymbol>(varName,typeSymbol));
    return NULL;
}

SYM_TABLE_BUILDER_VISITOR(AssignNode)
{
    auto node = std::dynamic_pointer_cast<AssignNode>(nodePtr);
    auto varNode = std::dynamic_pointer_cast<VarNode>(node->getLeftPtr());
    std::string varName = std::get<std::string>(varNode->getTokenPtr()->getValue());
    symTable.lookup(varName);
    this->visit(node->getRightPtr());
    return NULL;
}

最后，写一段代码验证一下：

int main()
{
    std::string text = R"(
PROGRAM Part8;
VAR
   number : INTEGER;
   a, b   : INTEGER;
   y      : REAL;

BEGIN {Part8}
   number := 2;
   a := number ;
   b := 10 * a + 10 * number DIV 4;
   y := 20 / 7 + 3.14
END.  {Part8}
)";
    ASTParser parser(text);
    SymbolTableBuilder symtableBuilder;
    symtableBuilder.visit(parser->parse());
    for (const auto pair : symtableBuilder.getSymbolTable().getAll())
    {
        cout << pair.first << " : " << pair.second->getType()->getName() << endl;
    }
    cout << endl;
    return 0;
}

顺利的话，可以看到输出结果如下：

INTEGER : INTEGER
REAL : REAL
a : INTEGER
b : INTEGER
number : INTEGER
y : REAL

当然这里还有一个问题：没有实现变量作用域，这个问题我们将来再说。