一个简单的解释器（5）—— 抽象语法树

这一章，我们要接触一些稍微硬核点的知识，理解一个概念——抽象语法树。

抽象语法树和语法解析树

对于文法：

expr : term((PLUS | MINUS)term)*
term : factory((MULTI | DIV)factory)*
factory : INTEGER | LPAREN expr RPAREN

当输入2*7+3时，可以构造成如下语法解析树：

lsbasi_part7_parsetree_01.png

很容易理解吧，但是这还不够，我们需要把这个树写成数据结构，树的每个节点存储一个terminal，将它写成如下形式：

AST.png

这样的树被称作抽象语法树(Abstract Syntax Tree, AST)。
如此，当获得一个输入string的时候，我们需要先根据文法，将它转换成一棵AST，它的根节点的值就是我们的输出值，那么转换的过程是怎么样的呢，我们需要利用之前几章的全部知识：

实现词法分析器将输入的string转换成tokens
根据文法，实现一个语法分析器
使用语法分析器解析tokens，并构造出AST
实现不同AST node的访问函数
其中，词法分析器在前面的章节已经实现过了，可以直接复用，这一章，我们将实现一个语法分析器，将它的功能从之前章节的Interperter中剥离出来。

ASTNode

首先，我们需要实现AST的node结构，写一个抽象类，方便多态调用：

#pragma once
#include <memory>
#include <string>
#include "Token.h"

class AbstractSyntaxTreeNodeBase
{
public:
    virtual std::string getClassName() = 0;
};

typedef std::shared_ptr<AbstractSyntaxTreeNodeBase> ASTNodePtr;

由于C++不支持反射，这里手动声明一个getClassName函数，为了多态实现稍微增加一点代码量。
对于我们的计算器，AST只有两种node：整数、二元运算符，首先实现整数node：

#pragma once
#include "AbstractSyntaxTreeNodeBase.h"
#include "Token.h"

class NumNode : public AbstractSyntaxTreeNodeBase
{
private:
    TokenPtr tokenPtr;
public:
    NumNode(TokenPtr p);
    TokenPtr getTokenPtr();
    std::string getClassName();
};

它只需要存储token就行，实现上很简单，然后重载一下className：

#include "NumNode.h"
#include <iostream>
#include <variant>
using namespace std;

NumNode::NumNode(TokenPtr p)
{
    tokenPtr = p;
}

TokenPtr NumNode::getTokenPtr()
{
    return tokenPtr;
}

std::string NumNode::getClassName()
{
    return "NumNode";
}

直接把tokenPtr放在public域当然更省事，不过我还是选择更安全的做法。
对于操作符的node，它会有两个子节点，所以它的声明如下：

#pragma once
#include "AbstractSyntaxTreeNodeBase.h"
#include "Token.h"

class BinOpNode : public AbstractSyntaxTreeNodeBase
{
private:
    ASTNodePtr leftNodePtr;
    ASTNodePtr rightNodePtr;
    TokenPtr opTokenPtr;
public:
    BinOpNode(ASTNodePtr l,TokenPtr ptr, ASTNodePtr r);
    TokenPtr getOpTokenPtr();
    ASTNodePtr left();
    ASTNodePtr right();
    std::string getClassName();
};

同样非常简单，只需要重载getClassName就行了，其余就是私有成员变量的get函数，它跟NumNode的区别在于BinOpNode拥有两个子节点。

AST Parser

OK，数据结构实现了，接下来我们需要实现语法解析的算法，实现一个AST Parser类，参考之前章节的文法分析，对于AST Parser，我们同样需要实现expr、term、factory：

#pragma once
#include <string>
#include "BinOpNode.h"
#include "NumNode.h"
#include "Lexer.h"

class ASTParser
{
private:
    LexerPtr lexerPtr;
    TokenPtr currentTokenPtr;
private:
    void raiseError();
    void eat(TokenType type);
    ASTNodePtr expr();
    ASTNodePtr term();
    ASTNodePtr factory();
public:
    ASTParser(std::string txt);
    ASTNodePtr parse();
};

typedef std::shared_ptr<ASTParser> ASTParserPtr;

不同之处在于，上一章中，我们在这三个函数的最后会直接返回计算出的值，这一章，我们将这个行为进一步抽象化，ASTParser只负责语法分析，生成抽象语法树，而计算的行为还是交给解释器Interpreter。
具体实现如下：

#include "ASTParser.h"
#include "ASTException.h"
#include <memory>
using namespace std;

void ASTParser::raiseError()
{
    throw ASTException();
}

void ASTParser::eat(TokenType type)
{
    if (currentTokenPtr->getType() != type)
    {
        raiseError();
        return;
    }
    currentTokenPtr = lexerPtr->getNextTokenPtr();
}

ASTParser::ASTParser(std::string txt)
{
    lexerPtr = make_shared<Lexer>(txt);
    currentTokenPtr = lexerPtr->getNextTokenPtr();
}

ASTNodePtr ASTParser::parse()
{
    return expr();
}

ASTNodePtr ASTParser::expr()
{
    ASTNodePtr node = term();
    while (currentTokenPtr->getType() == TokenType::TT_PLUS ||
        currentTokenPtr->getType() == TokenType::TT_MINUS)
    {
        TokenPtr tokenPtr = currentTokenPtr;
        eat(tokenPtr->getType());
        node = make_shared<BinOpNode>(node, tokenPtr, term());
    }
    return node;
}

ASTNodePtr ASTParser::term()
{
    ASTNodePtr node = factory();
    while (currentTokenPtr->getType() == TokenType::TT_MULTI ||
        currentTokenPtr->getType() == TokenType::TT_DIV)
    {
        TokenPtr tokenPtr = currentTokenPtr;
        eat(currentTokenPtr->getType());
        node = make_shared<BinOpNode>(node, tokenPtr, factory());
    }
    return node;
}

ASTNodePtr ASTParser::factory()
{
    TokenPtr tokenPtr = currentTokenPtr;
    if (tokenPtr->getType() == TokenType::TT_INTEGER) 
    {
        eat(TokenType::TT_INTEGER);
        return make_shared<NumNode>(tokenPtr);
    }

    if(tokenPtr->getType() == TokenType::TT_LPAREN)
    {
        eat(TokenType::TT_LPAREN);
        ASTNodePtr result = expr();
        eat(TokenType::TT_RPAREN);
        return result;
    }

    raiseError();
    return NULL;
}

可以看到expr、term、factory都依照各自的逻辑生成一个node，而对于我们的语法来说，根节点就是expr生成的node，所以在parse函数中直接返回expr()。

解释器

OK，在将语法分析的逻辑剥离出去以后，我们的解释器的工作就更加简明了，这里我们使用访问者模式（visitor pattern），Interpreter作为访问者去访问各个node，为此，首先实现一个NodeVisitor基类：

#pragma once
#include <map>
#include <string>
#include "AbstractSyntaxTreeNodeBase.h"
#include "Token.h"
#include <functional>

class NodeVisitor
{
protected:
    std::map<std::string, std::function<TokenValue(ASTNodePtr)>> visitMap;
public:
    TokenValue visit(ASTNodePtr nodePtr);
};

这里利用C++11的std::function，相当于更高级的函数指针，将class name映射到对应的函数中去，然后visit时再根据node的class name调用相应的函数即可：

#include "NodeVisitor.h"

TokenValue NodeVisitor::visit(ASTNodePtr nodePtr)
{
    if (visitMap.find(nodePtr->getClassName()) == visitMap.end())
    {
        throw "";
    }

    return visitMap[nodePtr->getClassName()](nodePtr);
}

接下来，我们的Interpreter继承NodeVisitor，并实现一个interpret函数：

#pragma once
#include "NodeVisitor.h"
#include "ASTParser.h"
#include <string>

class Interpreter : public NodeVisitor
{
private:
    ASTParserPtr astParserPtr;
private:
    void raiseError(std::string content);
public:
    TokenValue visitNumNode(ASTNodePtr nodePtr);
    TokenValue visitBinOpNode(ASTNodePtr nodePtr);
    Interpreter(std::string text);
    TokenValue interpret();
};

在构造函数中，将visit的具体实现放进visitMap：

Interpreter::Interpreter(std::string text)
{
    visitMap["NumNode"] = [this](ASTNodePtr nodePtr) -> TokenValue
    {
        return this->visitNumNode(nodePtr);
    };
    visitMap["BinOpNode"] = [this](ASTNodePtr nodePtr) -> TokenValue 
    {
        return this->visitBinOpNode(nodePtr);
    };

    astParserPtr = make_shared<ASTParser>(text);
}

使用lambda表达式去调用相应的具体visit实现，注意为了避免跟std::visit的歧义，这里用了this来调用visit，或者你也可以去掉using namespace std;一行。
对于NumNode，visit函数只需要返回它的TokenValue，对于BinOpNode，visit函数需要根据运算符的类型分别返回不同的结果，而它的左右子节点的值则同样通过visit函数获取，形成一个后序遍历的递归算法：

TokenValue Interpreter::visitNumNode(ASTNodePtr nodePtr)
{
    auto numNodePtr = dynamic_pointer_cast<NumNode>(nodePtr);
    return numNodePtr->getTokenPtr()->getValue();
}

TokenValue Interpreter::visitBinOpNode(ASTNodePtr nodePtr)
{
    auto binOpNodePtr = dynamic_pointer_cast<BinOpNode>(nodePtr);
    ASTNodePtr leftNodePtr = binOpNodePtr->left();
    ASTNodePtr rightNodePtr = binOpNodePtr->right();
    switch (binOpNodePtr->getOpTokenPtr()->getType())
    {
    case TokenType::TT_PLUS:
        return get<int>(this->visit(leftNodePtr)) + get<int>(this->visit(rightNodePtr));
    case TokenType::TT_MINUS:
        return get<int>(this->visit(leftNodePtr)) - get<int>(this->visit(rightNodePtr));
    case TokenType::TT_DIV:
        return get<int>(this->visit(leftNodePtr)) / get<int>(this->visit(rightNodePtr));
    case TokenType::TT_MULTI:
        return get<int>(this->visit(leftNodePtr)) * get<int>(this->visit(rightNodePtr));
    default:
        raiseError("Syntax error");
        break;
    }
    return NULL;
}

TokenValue Interpreter::interpret()
{
    ASTNodePtr rootNode = astParserPtr->parse();
    return this->visit(rootNode);
}

对于Interpreter来说，根节点的值就是我们想要的结果，所以interpret直接返回visit(rootNode)即可，然后我们写一个main来测试：

#include<iostream>
#include<sstream>
#include "Interpreter.h"
#include "InterpreterException.h"
#include "LexerException.h"
#include "ASTParser.h"
#include "ASTException.h"
#include <memory>
using namespace std;

int main() 
{
    try 
    {
        while (true) 
        {
            std::string text;
            getline(cin, text);
            Interpreter interpreter(text);
            cout << get<int>(interpreter.interpret()) << endl;
        }
    }
    catch  (InterpreterException e)
    {
        return -1;
    }
    catch (LexerException e) 
    {
        return 0;
    }
    catch (ASTException e) 
    {
        return 0;
    }
}

大功告成！

利用宏定义优化反射机制

利用宏定义，将visitMap相关的代码优化一下，首先，在AbstractSyntaxTreeNodeBase.h中添加以下宏定义：

#define GET_CLASS_NAME(CLASS_NAME) std::string getClassName(){ return #CLASS_NAME; }

如此，它的子类们（NumNode, BinOpNode）只需要一条宏命令即可返回相应的类名：

#pragma once
#include "AbstractSyntaxTreeNodeBase.h"
#include "Token.h"

class NumNode : public AbstractSyntaxTreeNodeBase
{
private:
    TokenPtr tokenPtr;
public:
    NumNode(TokenPtr p);
    TokenPtr getTokenPtr();

    GET_CLASS_NAME(NumNode)
};

然后在Interpreter.h中，声明一个DECLARE_VISITOR宏：

#pragma once
#include "NodeVisitor.h"
#include "ASTParser.h"
#include <string>

#define DECLARE_VISITOR(NODE_NAME) TokenValue visit##NODE_NAME(ASTNodePtr nodePtr)

class Interpreter : public NodeVisitor
{
private:
    ASTParserPtr astParserPtr;
private:
    void raiseError(std::string content);
public:
    DECLARE_VISITOR(NumNode);
    DECLARE_VISITOR(BinOpNode);
    Interpreter(std::string text);
    TokenValue interpret();
};

这样就可以方便地生成对应node类型的函数名，之后在Interpreter.cpp中声明对应的DEFINE_VISITOR宏和ADD_TO_VISIT_MAP宏：

#define DEFINE_VISITOR(NODE_NAME) TokenValue Interpreter::visit##NODE_NAME(ASTNodePtr nodePtr)

#define ADD_TO_VISIT_MAP(NODE_NAME) visitMap[#NODE_NAME] = \
[this](ASTNodePtr nodePtr) -> TokenValue \
{ \
    return this->visit##NODE_NAME(nodePtr); \
}

这样，构造函数就可以更简洁地添加函数指针：

Interpreter::Interpreter(std::string text)
{
    ADD_TO_VISIT_MAP(NumNode);
    ADD_TO_VISIT_MAP(BinOpNode);

    astParserPtr = make_shared<ASTParser>(text);
}

题外话：碍于本人水平，本章中的多态实现还是有点丑陋，精通C++的路程还是很漫长，如果你有兴趣的话，使用python之类的动态类型语言则可以方便很多（比如不需要考虑函数指针的参数、返回值匹不匹配的问题，声明上更加自由，自带反射等等等），但是毕竟我们是要做一个解释器，还是在native语言的基础上实现更加合理。

尝试添加一点额外特性

在完成上面的工作以后，我们可以很轻松地添加我们想要的特性，接下来我们向解释器添加一个一元运算符——Unary Operator。
首先，构造文法：

expr : term((PLUS | MINUS)term)*
term : factor((MULTI | DIV)factor)*
factor : (PLUS | MINUS)factor | INTEGER | LPAREN expr RPAREN

这样，在文法上，我们就添加了一个一元运算符（+/-），实现类似-1+3--2++3*-3这样的语法，一元运算符的优先级高于其它运算符，也就是说2*-3这样的语法是合法的会输出-6，所以我们将它添加在最底层的factor中，还记得吗，越下层的文法越早展开，优先级越高。
下一步，添加UnaryOpNode类：

#pragma once
#include "AbstractSyntaxTreeNodeBase.h"

class UnaryOpNode :public AbstractSyntaxTreeNodeBase
{
private:
    TokenPtr tokenPtr;
    ASTNodePtr rightNode;
public:
    UnaryOpNode(TokenPtr op,ASTNodePtr r);
    TokenPtr getOpTokenPtr();
    ASTNodePtr getRightNodePtr();

    GET_CLASS_NAME(UnaryOpNode)
};

同样不需要实现任何逻辑，只要保存Token和它右侧的节点，以及一个class name用于反射。
词法方面我们没有添加任何新词，所以Lexer无需修改，然后修改语法分析器ASTParser，在factory函数中添加逻辑：

ASTNodePtr ASTParser::factory()
{
    TokenPtr tokenPtr = currentTokenPtr;
    if (tokenPtr->getType() == TokenType::TT_PLUS || 
        tokenPtr->getType() == TokenType::TT_MINUS) 
    {
        eat(tokenPtr->getType());
        return make_shared<UnaryOpNode>(tokenPtr, factory());
    }

    if (tokenPtr->getType() == TokenType::TT_INTEGER) 
    {
        eat(TokenType::TT_INTEGER);
        return make_shared<NumNode>(tokenPtr);
    }

    if(tokenPtr->getType() == TokenType::TT_LPAREN)
    {
        eat(TokenType::TT_LPAREN);
        ASTNodePtr result = expr();
        eat(TokenType::TT_RPAREN);
        return result;
    }

    raiseError();
    return NULL;
}

这一步也非常简单，对于factory来说，如果第一个Token是加号或者减号，那么它就是UnaryOpNode，记录该Token和它后面的值，由文法分析，它后面的值就是一个factory，递归调用即可。
最后，修改Interpreter，实现visitUnaryOpNode，并在构造时添加到visitMap中：

DEFINE_VISITOR(UnaryOpNode)
{
    auto unaryOpNode = dynamic_pointer_cast<UnaryOpNode>(nodePtr);
    if (unaryOpNode->getOpTokenPtr()->getType() == TokenType::TT_PLUS) 
    {
        return +get<int>(this->visit(unaryOpNode->getRightNodePtr()));
    }

    if (unaryOpNode->getOpTokenPtr()->getType() == TokenType::TT_MINUS)
    {
        return -get<int>(this->visit(unaryOpNode->getRightNodePtr()));
    }

    raiseError("Syntax error");
    return NULL;
}

Interpreter::Interpreter(std::string text)
{
    ADD_TO_VISIT_MAP(NumNode);
    ADD_TO_VISIT_MAP(BinOpNode);
    ADD_TO_VISIT_MAP(UnaryOpNode);

    astParserPtr = make_shared<ASTParser>(text);
}

好了，运行一下，我们惊喜地发现，解释器的工作方式已经可以很接近普通计算器了。

最后编辑于：2024.04.01 11:00:42

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 216,402评论 6赞 499
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,377评论 3赞 392
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 162,483评论 0赞 353
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,165评论 1赞 292
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,176评论 6赞 388
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,146评论 1赞 297
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,032评论 3赞 417
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,896评论 0赞 274
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,311评论 1赞 310
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,536评论 2赞 332
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,696评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,413评论 5赞 343
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,008评论 3赞 325
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,659评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,815评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,698评论 2赞 368
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,592评论 2赞 353