国产青青草原视频,91精品视频你懂的

這一章，我們要接觸一些稍微硬核點(diǎn)的知識(shí)，理解一個(gè)概念——抽象語(yǔ)法樹。

抽象語(yǔ)法樹和語(yǔ)法解析樹

對(duì)于文法：

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

當(dāng)輸入2*7+3時(shí)，可以構(gòu)造成如下語(yǔ)法解析樹：

lsbasi_part7_parsetree_01.png

很容易理解吧，但是這還不夠，我們需要把這個(gè)樹寫成數(shù)據(jù)結(jié)構(gòu)，樹的每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)terminal，將它寫成如下形式：

AST.png

這樣的樹被稱作抽象語(yǔ)法樹(Abstract Syntax Tree, AST)。
如此，當(dāng)獲得一個(gè)輸入string的時(shí)候，我們需要先根據(jù)文法，將它轉(zhuǎn)換成一棵AST，它的根節(jié)點(diǎn)的值就是我們的輸出值，那么轉(zhuǎn)換的過程是怎么樣的呢，我們需要利用之前幾章的全部知識(shí)：

實(shí)現(xiàn)詞法分析器將輸入的string轉(zhuǎn)換成tokens
根據(jù)文法，實(shí)現(xiàn)一個(gè)語(yǔ)法分析器
使用語(yǔ)法分析器解析tokens，并構(gòu)造出AST
實(shí)現(xiàn)不同AST node的訪問函數(shù)
其中，詞法分析器在前面的章節(jié)已經(jīng)實(shí)現(xiàn)過了，可以直接復(fù)用，這一章，我們將實(shí)現(xiàn)一個(gè)語(yǔ)法分析器，將它的功能從之前章節(jié)的Interperter中剝離出來。

ASTNode

首先，我們需要實(shí)現(xiàn)AST的node結(jié)構(gòu)，寫一個(gè)抽象類，方便多態(tài)調(diào)用：

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

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

typedef std::shared_ptr<AbstractSyntaxTreeNodeBase> ASTNodePtr;

由于C++不支持反射，這里手動(dòng)聲明一個(gè)getClassName函數(shù)，為了多態(tài)實(shí)現(xiàn)稍微增加一點(diǎn)代碼量。
對(duì)于我們的計(jì)算器，AST只有兩種node：整數(shù)、二元運(yùn)算符，首先實(shí)現(xiàn)整數(shù)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();
};

它只需要存儲(chǔ)token就行，實(shí)現(xiàn)上很簡(jiǎn)單，然后重載一下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域當(dāng)然更省事，不過我還是選擇更安全的做法。
對(duì)于操作符的node，它會(huì)有兩個(gè)子節(jié)點(diǎn)，所以它的聲明如下：

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

同樣非常簡(jiǎn)單，只需要重載getClassName就行了，其余就是私有成員變量的get函數(shù)，它跟NumNode的區(qū)別在于BinOpNode擁有兩個(gè)子節(jié)點(diǎn)。

AST Parser

OK，數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了，接下來我們需要實(shí)現(xiàn)語(yǔ)法解析的算法，實(shí)現(xiàn)一個(gè)AST Parser類，參考之前章節(jié)的文法分析，對(duì)于AST Parser，我們同樣需要實(shí)現(xiàn)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;

不同之處在于，上一章中，我們?cè)谶@三個(gè)函數(shù)的最后會(huì)直接返回計(jì)算出的值，這一章，我們將這個(gè)行為進(jìn)一步抽象化，ASTParser只負(fù)責(zé)語(yǔ)法分析，生成抽象語(yǔ)法樹，而計(jì)算的行為還是交給解釋器Interpreter。
具體實(shí)現(xiàn)如下：

#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都依照各自的邏輯生成一個(gè)node，而對(duì)于我們的語(yǔ)法來說，根節(jié)點(diǎn)就是expr生成的node，所以在parse函數(shù)中直接返回expr()。

解釋器

OK，在將語(yǔ)法分析的邏輯剝離出去以后，我們的解釋器的工作就更加簡(jiǎn)明了，這里我們使用訪問者模式（visitor pattern），Interpreter作為訪問者去訪問各個(gè)node，為此，首先實(shí)現(xiàn)一個(gè)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，相當(dāng)于更高級(jí)的函數(shù)指針，將class name映射到對(duì)應(yīng)的函數(shù)中去，然后visit時(shí)再根據(jù)node的class name調(diào)用相應(yīng)的函數(shù)即可：

#include "NodeVisitor.h"

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

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

接下來，我們的Interpreter繼承NodeVisitor，并實(shí)現(xiàn)一個(gè)interpret函數(shù)：

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

在構(gòu)造函數(shù)中，將visit的具體實(shí)現(xiàn)放進(jìn)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表達(dá)式去調(diào)用相應(yīng)的具體visit實(shí)現(xiàn)，注意為了避免跟std::visit的歧義，這里用了this來調(diào)用visit，或者你也可以去掉using namespace std;一行。
對(duì)于NumNode，visit函數(shù)只需要返回它的TokenValue，對(duì)于BinOpNode，visit函數(shù)需要根據(jù)運(yùn)算符的類型分別返回不同的結(jié)果，而它的左右子節(jié)點(diǎn)的值則同樣通過visit函數(shù)獲取，形成一個(gè)后序遍歷的遞歸算法：

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

對(duì)于Interpreter來說，根節(jié)點(diǎn)的值就是我們想要的結(jié)果，所以interpret直接返回visit(rootNode)即可，然后我們寫一個(gè)main來測(cè)試：

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

大功告成！

利用宏定義優(yōu)化反射機(jī)制

利用宏定義，將visitMap相關(guān)的代碼優(yōu)化一下，首先，在AbstractSyntaxTreeNodeBase.h中添加以下宏定義：

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

如此，它的子類們（NumNode, BinOpNode）只需要一條宏命令即可返回相應(yīng)的類名：

#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中，聲明一個(gè)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();
};

這樣就可以方便地生成對(duì)應(yīng)node類型的函數(shù)名，之后在Interpreter.cpp中聲明對(duì)應(yīng)的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); \
}

這樣，構(gòu)造函數(shù)就可以更簡(jiǎn)潔地添加函數(shù)指針：

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

    astParserPtr = make_shared<ASTParser>(text);
}

題外話：礙于本人水平，本章中的多態(tài)實(shí)現(xiàn)還是有點(diǎn)丑陋，精通C++的路程還是很漫長(zhǎng)，如果你有興趣的話，使用python之類的動(dòng)態(tài)類型語(yǔ)言則可以方便很多（比如不需要考慮函數(shù)指針的參數(shù)、返回值匹不匹配的問題，聲明上更加自由，自帶反射等等等），但是畢竟我們是要做一個(gè)解釋器，還是在native語(yǔ)言的基礎(chǔ)上實(shí)現(xiàn)更加合理。

嘗試添加一點(diǎn)額外特性

在完成上面的工作以后，我們可以很輕松地添加我們想要的特性，接下來我們向解釋器添加一個(gè)一元運(yùn)算符——Unary Operator。
首先，構(gòu)造文法：

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

這樣，在文法上，我們就添加了一個(gè)一元運(yùn)算符（+/-），實(shí)現(xiàn)類似-1+3--2++3*-3這樣的語(yǔ)法，一元運(yùn)算符的優(yōu)先級(jí)高于其它運(yùn)算符，也就是說2*-3這樣的語(yǔ)法是合法的會(huì)輸出-6，所以我們將它添加在最底層的factor中，還記得嗎，越下層的文法越早展開，優(yōu)先級(jí)越高。
下一步，添加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)
};

同樣不需要實(shí)現(xiàn)任何邏輯，只要保存Token和它右側(cè)的節(jié)點(diǎn)，以及一個(gè)class name用于反射。
詞法方面我們沒有添加任何新詞，所以Lexer無需修改，然后修改語(yǔ)法分析器ASTParser，在factory函數(shù)中添加邏輯：

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;
}

這一步也非常簡(jiǎn)單，對(duì)于factory來說，如果第一個(gè)Token是加號(hào)或者減號(hào)，那么它就是UnaryOpNode，記錄該Token和它后面的值，由文法分析，它后面的值就是一個(gè)factory，遞歸調(diào)用即可。
最后，修改Interpreter，實(shí)現(xiàn)visitUnaryOpNode，并在構(gòu)造時(shí)添加到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);
}

好了，運(yùn)行一下，我們驚喜地發(fā)現(xiàn)，解釋器的工作方式已經(jīng)可以很接近普通計(jì)算器了。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一個(gè)簡(jiǎn)單的解釋器（5）—— 抽象語(yǔ)法樹

一個(gè)簡(jiǎn)單的解釋器（5）—— 抽象語(yǔ)法樹

抽象語(yǔ)法樹和語(yǔ)法解析樹

ASTNode

AST Parser

解釋器

利用宏定義優(yōu)化反射機(jī)制

嘗試添加一點(diǎn)額外特性

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

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

一個(gè)簡(jiǎn)單的解釋器（5）—— 抽象語(yǔ)法樹

抽象語(yǔ)法樹和語(yǔ)法解析樹

ASTNode

AST Parser

解釋器

利用宏定義優(yōu)化反射機(jī)制

嘗試添加一點(diǎn)額外特性

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

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av