一个简单的解释器（6）—— Pascal解释器

接下来的内容将更加硬核，我们距离创造自己的编程语言更近一步——实现一个初步的Pascal解释器。

Pascal

好吧这是一门古老的语言，在很久很久以前，我还是个初中生的时候稍微接触过一点，语法上跟同样古老的Basic差不多，不过因为它足够古老，不会有太多花里胡哨的特性，相对容易实现一些，一段简单的Pascal程序代码如下：

BEGIN
    BEGIN
        number := 2;
        a := number;
        b := 10 * a + 10 * number / 4;
        c := a - - b
    END;
    x := 11;
END.

从一个计算器解释器跳转到一个简单的编程语言解释器步子似乎有点大，我们一步一步来。

文法分析

可以看到，Pascal的语句都用"BEGIN ... END"对包裹起来，用"."号作为整个代码段的结尾，好，第一步，依旧是创建文法，第一条应该是一个program，它包含一个被BEGIN END对包裹的compound_statement和一个DOT：

program : compound_statement DOT

然后我们定义compound_statement：

compound_statement : BEGIN statement_list END

如上所述，一个compound_statement就是被BEGIN END对包裹的statement_list，然后我们再定义statement_list：

statement_list : statement | statement SEMI statement_list

请注意这里定义了一个terminal：SEMI，它代表一个分号，Pascal的分号不同于C/C++，分号只用来分隔语句，而不是作为语句的结束符号，如下Pascal代码是合法的：

BEGIN
  x := 1;
  y := 2
END.

所以对于我们的文法来说，只有statement后面又有statement_list时，才需要SEMI。
接下来我们定义具体的statement，在我们的示例代码中，一个statement只有三种可能：空语句、赋值语句、被BEGIN END包起来的compound_statement：

statement : empty |  assignment_statement | compound_statement

空语句比较简单，就是什么都没有：

empty :

compound_statement再前面已经定义过了，所以我们需要定义赋值语句assignment_statement：

assignment_statement : variable ASSIGN expr

对于变量名variable，我们定义一个terminal：ID，不用进一步展开：

variable : ID

然后定义了一个terminal操作符，，ASSIGN，代表:=，expr我们很熟悉了，它就是我们在前面的章节实现过的文法，这里不作赘述，需要注意的是factory需要对应的升级，因为variable也可能作为一个factor参与计算：

factor : (PLUS | MINUS) factor | INTEGER | LPAREN expr RPAREN | variable

完整的文法如下：

    program : compound_statement DOT

    compound_statement : BEGIN statement_list END

    statement_list : statement
                   | statement SEMI statement_list

    statement : compound_statement
              | assignment_statement
              | empty

    assignment_statement : variable ASSIGN expr

    empty :

    expr: term ((PLUS | MINUS) term)*

    term: factor ((MUL | DIV) factor)*

    factor : (PLUS | MINUS) factor
           | INTEGER
           | LPAREN expr RPAREN
           | variable

    variable: ID

其中，statement_list和statement可以合并成如下形式：

statement : ( compound_statement | assignment_statement | empty ) (SEMI ( compound_statement | assignment_statement | empty ))*

但是这显然过于啰嗦，而且将来当我们使用文法分析器如PLY时可能不支持*的语法，类似的，(PLUS | MINUS) factor，也可以拆分成PLUS factor | MINUS factor。

升级词法分析器

确认了文法以后，开干，第一步，升级词法分析器，我们需要完成：

  • 增加Token类型，识别BEGIN END DOT ID ASSIGN SEMI这些关键字；
  • 添加一个peek函数以解决歧义；
  • 添加一个id函数用来判断和获取变量名；
  • 升级getNextTokenPtr函数；
    扩展Token.h中的TokenType：
enum class TokenType {
    TT_INTEGER,
    TT_PLUS,
    TT_MINUS,
    TT_MULTI,
    TT_DIV,
    TT_LPAREN,
    TT_RPAREN,
    TT_BEGIN,
    TT_END,
    TT_SEMI,
    TT_DOT,
    TT_ASSIGN,
    TT_ID,
    TT_EOF
};

在编程语言中，我们需要分辨同样起始字符的不同符号如:=和::，==和=>，Pascal的保留字和变量名等等，为此在Lexer中实现一个peek函数，区别于advance，它返回当前字符的下一个字符，但不使pos+1：

char Lexer::peek()
{
    if (currentPos + 1 >= strlen(text.c_str()))
    {
        return NULL;
    }
    return text.c_str()[currentPos + 1];
}

实现一个id函数，在读取到字母时判断它是保留字还是变量名，并返回相应的Token：

static const std::map<std::string, TokenPtr> REVERSED_WORDS =
{
    {"BEGIN",make_shared<Token>(TokenType::TT_BEGIN,"BEGIN")},
    {"END",make_shared<Token>(TokenType::TT_END,"END") },
};
TokenPtr Lexer::id()
{
    std::string result = "";
    while (isalnum(currentChar)) 
    {
        result += currentChar;
        advance();
    }
    if (REVERSED_WORDS.find(result) == REVERSED_WORDS.end()) 
    {
        return make_shared<Token>(TokenType::TT_ID,result);
    }
    else 
    {
        return REVERSED_WORDS.at(result);
    }
}

最后，升级一下getNextTokenPtr，加入新的Tokens的判断：

TokenPtr Lexer::getNextTokenPtr()
{
    while (currentChar != '\0' && currentPos < strlen(text.c_str()))
    {
        if (isSpace(currentChar))
        {
            skipWhiteSpaces();
        }

        TokenType tokenType;
        TokenValue tokenValue;

        if (isDigit(currentChar))
        {
            return make_shared<Token>(TokenType::TT_INTEGER, integer());
        }

        if (isalpha(currentChar)) 
        {
            return id();
        }

        switch (currentChar)
        {
        case '.':
            tokenType = TokenType::TT_DOT;
            tokenValue = ".";
            break;
        case ':':
            if (peek() == '=') 
            {
                advance();
                tokenType = TokenType::TT_ASSIGN;
                tokenValue = ":=";
            }
            else 
            {
                raiseError();
            }
            break;
        case ';':
            tokenType = TokenType::TT_SEMI;
            tokenValue = ";";
            break;
        case '+':
            tokenType = TokenType::TT_PLUS;
            tokenValue = "+";
            break;
        case '-':
            tokenType = TokenType::TT_MINUS;
            tokenValue = "-";
            break;
        case '*':
            tokenType = TokenType::TT_MULTI;
            tokenValue = "*";
            break;
        case '/':
            tokenType = TokenType::TT_DIV;
            tokenValue = "/";
            break;
        case '(':
            tokenType = TokenType::TT_LPAREN;
            tokenValue = "(";
            break;
        case ')':
            tokenType = TokenType::TT_RPAREN;
            tokenValue = ")";
            break;
        default:
            raiseError();
            break;
        }

        advance();
        return make_shared<Token>(tokenType, tokenValue);
    }
    return make_shared<Token>(TokenType::TT_EOF, NULL);
}

OK，至此，词法分析器升级完成，我们写一段代码来测试：

int main()
{
    std::string text = "BEGIN x:=1 END.";
    Lexer lexer(text);
    TokenPtr tokenPtr = lexer.getNextTokenPtr();
    while (tokenPtr->getType() != TokenType::TT_EOF) 
    {
        std::visit([](auto&& arg) { std::cout << arg << std::endl; }, tokenPtr->getValue());
        tokenPtr = lexer.getNextTokenPtr();
    }
    return 0;
}

这里利用std::visit来更快捷地访问TokenValue的值，顺利的话，输出内容应该如下：

BEGIN
x
:=
1
END
.

可以看到原始string已经被顺利解析成Tokens了。

升级语法分析器

往上一层，对于ASTParser来说，我们需要升级以下功能：

  • 定义新的ASTNodes；
  • 完成所有那些新的文法对应的函数实现；
  • 升级parse和factor函数；
    同样的，我们对文法的所需要的AST节点进行定义，首先，定义CompoundNode：
#pragma once
#include "AbstractSyntaxTreeNodeBase.h"
#include <vector>

class CompoundNode : public AbstractSyntaxTreeNodeBase
{
private:
    std::vector<ASTNodePtr> children;
public:

    GET_CLASS_NAME(CompoundNode)
};

AssginNode：

#pragma once
#include "AbstractSyntaxTreeNodeBase.h"

class AssignNode : public AbstractSyntaxTreeNodeBase
{
private:
    ASTNodePtr left;
    ASTNodePtr right;
    TokenPtr opTokenPtr;
public:
    AssignNode(ASTNodePtr l, TokenPtr op, ASTNodePtr r);

    GET_CLASS_NAME(AssignNode)
};

VarNode：

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

class VarNode : public AbstractSyntaxTreeNodeBase
{
private:
    TokenPtr tokenPtr;
    TokenValue varValue;
public:
    VarNode(TokenPtr ptr);

    GET_CLASS_NAME(VarNode)
};

varNode需要一个额外的varValue成员来存储它的值。
以及特殊的NoOpNode：

#pragma once
#include "AbstractSyntaxTreeNodeBase.h"

class NoOpNode : public AbstractSyntaxTreeNodeBase
{
public:
    GET_CLASS_NAME(NoOpNode)
};

对应文法中的empty，是一个空的节点。
OK，完成了新的nodes，我们开始升级Parser，每有一条文法都有一个对应的函数，所以我们先在ASTParser.h中添加如下声明

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

class ASTParser
{
private:
    LexerPtr lexerPtr;
    TokenPtr currentTokenPtr;
private:
    void raiseError();
    void eat(TokenType type);

    ASTNodePtr program();
    ASTNodePtr compoundStatement();
    std::vector<ASTNodePtr> statementList();
    ASTNodePtr statement();
    ASTNodePtr assignStatement();
    ASTNodePtr variable();
    ASTNodePtr empty();

    ASTNodePtr expr();
    ASTNodePtr term();
    ASTNodePtr factory();
public:
    ASTParser(std::string txt);
    ASTNodePtr parse();
};

typedef std::shared_ptr<ASTParser> ASTParserPtr;

然后实现这些新增的函数：

ASTNodePtr ASTParser::program()
{
    ASTNodePtr node = compoundStatement();
    eat(TokenType::TT_DOT);
    return node;
}

ASTNodePtr ASTParser::compoundStatement()
{
    eat(TokenType::TT_BEGIN);
    ASTNodePtr root = make_shared<CompoundNode>(statementList());
    eat(TokenType::TT_END);
    return root;
}

std::vector<ASTNodePtr> ASTParser::statementList()
{
    ASTNodePtr node = statement();
    std::vector<ASTNodePtr> result = { node };
    while (currentTokenPtr->getType() == TokenType::TT_SEMI)
    {
        eat(TokenType::TT_SEMI);
        result.push_back(statement());
    }
    if (currentTokenPtr->getType() != TokenType::TT_END)
    {
        raiseError();
    }
    return result;
}

ASTNodePtr ASTParser::statement()
{
    if (currentTokenPtr->getType() == TokenType::TT_BEGIN)
    {
        return compoundStatement();
    }

    if (currentTokenPtr->getType() == TokenType::TT_ID)
    {
        return variable();
    }

    return empty();
}

ASTNodePtr ASTParser::assignStatement()
{
    ASTNodePtr left = variable();
    TokenPtr opToken = currentTokenPtr;
    eat(TokenType::TT_ASSIGN);
    ASTNodePtr right = expr();
    return make_shared<AssignNode>(left,opToken,right);
}

ASTNodePtr ASTParser::variable()
{
    ASTNodePtr varNode = make_shared<VarNode>(currentTokenPtr);
    eat(TokenType::TT_ID);
    return varNode;
}

ASTNodePtr ASTParser::empty()
{
    return make_shared<NoOpNode>();
}

factor函数新增了一种可能：

ASTNodePtr ASTParser::factory()
{
    TokenPtr tokenPtr = currentTokenPtr;
    ...
    if (tokenPtr->getType() == TokenType::TT_ID) 
    {
        return variable();
    }
    ...

更新parse函数，这次我们parse的输出是一个program了：

ASTNodePtr ASTParser::parse()
{
    ASTNodePtr programNode = program();
    if (currentTokenPtr->getType() != TokenType::TT_EOF) 
    {
        raiseError();
    }
    return programNode;
}

至此，语法分析器更新完毕，下一步，我们需要更新解释器的visitor，另外，为了variable实现一张变量表。

更新解释器

首先，我们添加新增的node的visitor函数声明：

#pragma once
#include "NodeVisitor.h"
#include "Parser/ASTParser.h"
#include "ASTNodes/CompoundNode.h"
#include "ASTNodes/NoOpNode.h"
#include "ASTNodes/AssignNode.h"
#include "ASTNodes/VarNode.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:
    std::map<std::string,TokenValue> globalVariables;
public:
    DECLARE_VISITOR(NumNode);
    DECLARE_VISITOR(BinOpNode);
    DECLARE_VISITOR(UnaryOpNode);
    DECLARE_VISITOR(CompoundNode);
    DECLARE_VISITOR(NoOpNode);
    DECLARE_VISITOR(AssignNode);
    DECLARE_VISITOR(VarNode);
    Interpreter(std::string text);
    TokenValue interpret();
};

注意这里新增了一个globalVariables成员变量，用来储存我们要解释的代码段的变量名和值。
然后，实现相应的visitor函数：

DEFINE_VISITOR(CompoundNode)
{
    auto children = dynamic_pointer_cast<CompoundNode>(nodePtr)->getChildren();
    for (ASTNodePtr child : children)
    {
        this->visit(child);
    }
    return NULL;
}

DEFINE_VISITOR(NoOpNode)
{
    return NULL;
}

DEFINE_VISITOR(AssignNode)
{
    auto node = dynamic_pointer_cast<AssignNode>(nodePtr);
    auto varNode = dynamic_pointer_cast<VarNode>(node->getLeftPtr());
    globalVariables[get<std::string>(varNode->getTokenPtr()->getValue())] = this->visit(node->getRightPtr());
    return NULL;
}

DEFINE_VISITOR(VarNode)
{
    auto varNode = dynamic_pointer_cast<VarNode>(nodePtr);
    auto varName = get<string>(varNode->getTokenPtr()->getValue());
    if (globalVariables.find(varName) == globalVariables.end())
    {
        raiseError("Name error");
    }
    return globalVariables[varName];
}

在AssignNode的visitor中，我们将它的left的值作为key，right的值作为value放进globalVariables。
然后，在构造函数中添加一下函数指针的map：

Interpreter::Interpreter(std::string text)
{
    ADD_TO_VISIT_MAP(NumNode);
    ADD_TO_VISIT_MAP(BinOpNode);
    ADD_TO_VISIT_MAP(UnaryOpNode);
    ADD_TO_VISIT_MAP(CompoundNode);
    ADD_TO_VISIT_MAP(AssignNode);
    ADD_TO_VISIT_MAP(NoOpNode);
    ADD_TO_VISIT_MAP(VarNode);

    astParserPtr = make_shared<ASTParser>(text);
}

OK，就这么简单，我们完成了Pascal语言的初步解释，现在解释器可以识别赋值语句并存储到变量表中了。
写一段测试代码：

int main()
{
    std::string text = R"(
                    BEGIN 
                        x:=1;
                        BEGIN
                            y:=2*(2+3)
                            z:=x+y
                        END;
                    END.
    )";
    Interpreter inter(text);
    inter.interpret();
    for (const auto& pair : inter.globalVariables)
    {
        cout << pair.first << "=" << std::get<int>(pair.second) << endl;
    }
    return 0;
}

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

x=1
y=10
z=11

Cool！试试随意修改这段代码看看吧！

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

推荐阅读更多精彩内容