一個簡單的解釋器（6）—— Pascal解釋器

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

Pascal

好吧這是一門古老的語言，在很久很久以前，我還是個初中生的時候稍微接觸過一點，語法上跟同樣古老的Basic差不多，不過因為它足夠古老，不會有太多花里胡哨的特性，相對容易實現(xiàn)一些，一段簡單的Pascal程序代碼如下：

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

從一個計算器解釋器跳轉(zhuǎn)到一個簡單的編程語言解釋器步子似乎有點大，我們一步一步來。

文法分析

可以看到，Pascal的語句都用"BEGIN ... END"對包裹起來，用"."號作為整個代碼段的結(jié)尾，好，第一步，依舊是創(chuàng)建文法，第一條應(yīng)該是一個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++，分號只用來分隔語句，而不是作為語句的結(jié)束符號，如下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再前面已經(jīng)定義過了，所以我們需要定義賦值語句assignment_statement：

assignment_statement : variable ASSIGN expr

對于變量名variable，我們定義一個terminal：ID，不用進一步展開：

variable : ID

然后定義了一個terminal操作符，，ASSIGN，代表:=，expr我們很熟悉了，它就是我們在前面的章節(jié)實現(xiàn)過的文法，這里不作贅述，需要注意的是factory需要對應(yīng)的升級，因為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這些關(guān)鍵字；
  • 添加一個peek函數(shù)以解決歧義；
  • 添加一個id函數(shù)用來判斷和獲取變量名；
  • 升級getNextTokenPtr函數(shù)；
    擴展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中實現(xiàn)一個peek函數(shù)，區(qū)別于advance，它返回當前字符的下一個字符，但不使pos+1：

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

實現(xiàn)一個id函數(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);
    }
}

最后，升級一下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的值，順利的話，輸出內(nèi)容應(yīng)該如下：

BEGIN
x
:=
1
END
.

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

升級語法分析器

往上一層，對于ASTParser來說，我們需要升級以下功能：

  • 定義新的ASTNodes；
  • 完成所有那些新的文法對應(yīng)的函數(shù)實現(xiàn)；
  • 升級parse和factor函數(shù)；
    同樣的，我們對文法的所需要的AST節(jié)點進行定義，首先，定義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)
};

對應(yīng)文法中的empty，是一個空的節(jié)點。
OK，完成了新的nodes，我們開始升級Parser，每有一條文法都有一個對應(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;

然后實現(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的輸出是一個program了：

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

至此，語法分析器更新完畢，下一步，我們需要更新解釋器的visitor，另外，為了variable實現(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();
};

注意這里新增了一個globalVariables成員變量，用來儲存我們要解釋的代碼段的變量名和值。
然后，實現(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放進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，就這么簡單，我們完成了Pascal語言的初步解釋，現(xiàn)在解釋器可以識別賦值語句并存儲到變量表中了。
寫一段測試代碼：

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

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容