接下來(lái)的內(nèi)容將更加硬核，我們距離創(chuàng)造自己的編程語(yǔ)言更近一步——實(shí)現(xiàn)一個(gè)初步的Pascal解釋器。

Pascal

好吧這是一門古老的語(yǔ)言，在很久很久以前，我還是個(gè)初中生的時(shí)候稍微接觸過(guò)一點(diǎn)，語(yǔ)法上跟同樣古老的Basic差不多，不過(guò)因?yàn)樗銐蚬爬?，不?huì)有太多花里胡哨的特性，相對(duì)容易實(shí)現(xiàn)一些，一段簡(jiǎn)單的Pascal程序代碼如下：

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

從一個(gè)計(jì)算器解釋器跳轉(zhuǎn)到一個(gè)簡(jiǎn)單的編程語(yǔ)言解釋器步子似乎有點(diǎn)大，我們一步一步來(lái)。

文法分析

可以看到，Pascal的語(yǔ)句都用"BEGIN ... END"對(duì)包裹起來(lái)，用"."號(hào)作為整個(gè)代碼段的結(jié)尾，好，第一步，依舊是創(chuàng)建文法，第一條應(yīng)該是一個(gè)program，它包含一個(gè)被BEGIN END對(duì)包裹的compound_statement和一個(gè)DOT：

program : compound_statement DOT

然后我們定義compound_statement：

compound_statement : BEGIN statement_list END

如上所述，一個(gè)compound_statement就是被BEGIN END對(duì)包裹的statement_list，然后我們?cè)俣xstatement_list：

statement_list : statement | statement SEMI statement_list

請(qǐng)注意這里定義了一個(gè)terminal：SEMI，它代表一個(gè)分號(hào)，Pascal的分號(hào)不同于C/C++，分號(hào)只用來(lái)分隔語(yǔ)句，而不是作為語(yǔ)句的結(jié)束符號(hào)，如下Pascal代碼是合法的：

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

所以對(duì)于我們的文法來(lái)說(shuō)，只有statement后面又有statement_list時(shí)，才需要SEMI。
接下來(lái)我們定義具體的statement，在我們的示例代碼中，一個(gè)statement只有三種可能：空語(yǔ)句、賦值語(yǔ)句、被BEGIN END包起來(lái)的compound_statement：

statement : empty |  assignment_statement | compound_statement

空語(yǔ)句比較簡(jiǎn)單，就是什么都沒(méi)有：

empty : 

compound_statement再前面已經(jīng)定義過(guò)了，所以我們需要定義賦值語(yǔ)句assignment_statement：

assignment_statement : variable ASSIGN expr

對(duì)于變量名variable，我們定義一個(gè)terminal：ID，不用進(jìn)一步展開：

variable : ID

然后定義了一個(gè)terminal操作符，，ASSIGN，代表:=，expr我們很熟悉了，它就是我們?cè)谇懊娴恼鹿?jié)實(shí)現(xiàn)過(guò)的文法，這里不作贅述，需要注意的是factory需要對(duì)應(yīng)的升級(jí)，因?yàn)関ariable也可能作為一個(gè)factor參與計(jì)算：

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 ))*

但是這顯然過(guò)于啰嗦，而且將來(lái)當(dāng)我們使用文法分析器如PLY時(shí)可能不支持*的語(yǔ)法，類似的，(PLUS | MINUS) factor，也可以拆分成PLUS factor | MINUS factor。

升級(jí)詞法分析器

確認(rèn)了文法以后，開干，第一步，升級(jí)詞法分析器，我們需要完成：

• 增加Token類型，識(shí)別BEGIN END DOT ID ASSIGN SEMI這些關(guān)鍵字；
• 添加一個(gè)peek函數(shù)以解決歧義；
• 添加一個(gè)id函數(shù)用來(lái)判斷和獲取變量名；
• 升級(jí)getNextTokenPtr函數(shù)；
  擴(kuò)展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
};

在編程語(yǔ)言中，我們需要分辨同樣起始字符的不同符號(hào)如:=和::，==和=>，Pascal的保留字和變量名等等，為此在Lexer中實(shí)現(xiàn)一個(gè)peek函數(shù)，區(qū)別于advance，它返回當(dāng)前字符的下一個(gè)字符，但不使pos+1：

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

實(shí)現(xiàn)一個(gè)id函數(shù)，在讀取到字母時(shí)判斷它是保留字還是變量名，并返回相應(yīng)的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);
    }
}

最后，升級(jí)一下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，至此，詞法分析器升級(jí)完成，我們寫一段代碼來(lái)測(cè)試：

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來(lái)更快捷地訪問(wèn)TokenValue的值，順利的話，輸出內(nèi)容應(yīng)該如下：

BEGIN
x
:=
1
END
.

可以看到原始string已經(jīng)被順利解析成Tokens了。

升級(jí)語(yǔ)法分析器

往上一層，對(duì)于ASTParser來(lái)說(shuō)，我們需要升級(jí)以下功能：

• 定義新的ASTNodes；
• 完成所有那些新的文法對(duì)應(yīng)的函數(shù)實(shí)現(xiàn)；
• 升級(jí)parse和factor函數(shù)；
  同樣的，我們對(duì)文法的所需要的AST節(jié)點(diǎn)進(jìn)行定義，首先，定義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需要一個(gè)額外的varValue成員來(lái)存儲(chǔ)它的值。
以及特殊的NoOpNode：

#pragma once
#include "AbstractSyntaxTreeNodeBase.h"

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

對(duì)應(yīng)文法中的empty，是一個(gè)空的節(jié)點(diǎn)。
OK，完成了新的nodes，我們開始升級(jí)Parser，每有一條文法都有一個(gè)對(duì)應(yīng)的函數(shù)，所以我們先在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;

然后實(shí)現(xiàn)這些新增的函數(shù)：

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函數(shù)新增了一種可能：

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

更新parse函數(shù)，這次我們parse的輸出是一個(gè)program了：

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

至此，語(yǔ)法分析器更新完畢，下一步，我們需要更新解釋器的visitor，另外，為了variable實(shí)現(xiàn)一張變量表。

更新解釋器

首先，我們添加新增的node的visitor函數(shù)聲明：

#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();
};

注意這里新增了一個(gè)globalVariables成員變量，用來(lái)儲(chǔ)存我們要解釋的代碼段的變量名和值。
然后，實(shí)現(xiàn)相應(yīng)的visitor函數(shù)：

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放進(jìn)globalVariables。
然后，在構(gòu)造函數(shù)中添加一下函數(shù)指針的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，就這么簡(jiǎn)單，我們完成了Pascal語(yǔ)言的初步解釋，現(xiàn)在解釋器可以識(shí)別賦值語(yǔ)句并存儲(chǔ)到變量表中了。
寫一段測(cè)試代碼：

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！試試隨意修改這段代碼看看吧！