快捷導(dǎo)航

C++設(shè)計(jì)模式之解釋器模式

更新時(shí)間：2014年10月08日 11:31:04 作者：果凍想

這篇文章主要介紹了C++設(shè)計(jì)模式之解釋器模式,本文講解了什么是解釋器模式、文法規(guī)則和抽象語(yǔ)法樹(shù)、解釋器模式的使用場(chǎng)合等內(nèi)容,需要的朋友可以參考下

前言

那日，閑的無(wú)聊，上了一個(gè)在線編程學(xué)習(xí)網(wǎng)站；最近那個(gè)在線編程學(xué)習(xí)網(wǎng)站很火??；之前，蓋茨、扎克伯格等大人物都來(lái)宣傳了，思想是人人都應(yīng)該學(xué)習(xí)編程；我一想就這算怎么回事??？這要是在中國(guó)，還讓人活不？話題不扯開(kāi)了，還是說(shuō)我上了那個(gè)在線編程網(wǎng)站吧，首先是給你玩一個(gè)小游戲，激發(fā)你對(duì)編程的興趣。游戲是這樣的，網(wǎng)頁(yè)上有一個(gè)編輯框，屏幕上有一只小狗，比如你在編輯框中輸入這樣的句子：down run 10；按下回車，這個(gè)時(shí)候，你就看到屏幕上的小狗向下跑動(dòng)了10個(gè)方格大小的長(zhǎng)度；你再輸入up walk 5，按下回車，小狗就會(huì)向上走動(dòng)5個(gè)方格大小的長(zhǎng)度。確實(shí)是有點(diǎn)意思；但是，對(duì)于我這種已經(jīng)不需要這種游戲來(lái)激起我學(xué)習(xí)興趣的人來(lái)說(shuō)，我更喜歡的是去考慮它是如何實(shí)現(xiàn)的，如何將我輸入的一句話去控制小狗移動(dòng)的。而這一切的一切都不得不說(shuō)到今天總結(jié)的解釋器模式了。

解釋器模式

在GOF的《設(shè)計(jì)模式:可復(fù)用面向?qū)ο筌浖幕A(chǔ)》一書中對(duì)解釋器模式是這樣說(shuō)的：給定一個(gè)語(yǔ)言，定義它的文法的一種表示，并定義一個(gè)解釋器，這個(gè)解釋器使用該表示來(lái)解釋語(yǔ)言中的句子。如果一種特定類型的問(wèn)題發(fā)生的頻率足夠高，那么可能就值得將該問(wèn)題的各個(gè)實(shí)例表述為一個(gè)簡(jiǎn)單語(yǔ)言中的句子。這樣就可以構(gòu)建一個(gè)解釋器，該解釋器通過(guò)解釋這些句子來(lái)解決該問(wèn)題。

就如上面說(shuō)的那個(gè)游戲，我輸入up walk 5，我必須按照：移動(dòng)方向+移動(dòng)方式+移動(dòng)距離這種格式輸入我的指令，而這種格式的指令就是一種文法，只有按照了我定義的這種文法去輸入，才能控制屏幕上的小狗去移動(dòng)。當(dāng)然了，我輸入up walk 5，屏幕上的小狗肯定是聽(tīng)不懂的，它不知道我輸入的是什么，這個(gè)時(shí)候需要怎么辦？我需要一個(gè)工具去將我輸入的內(nèi)容翻譯成小狗能聽(tīng)懂的東西，而這個(gè)工具就是定義中提到的解釋器，解釋器對(duì)我輸入的指令進(jìn)行解釋，然后將解釋得到的指令發(fā)送給屏幕上的小狗，小狗聽(tīng)懂了，就進(jìn)行實(shí)際的移動(dòng)。

我們?cè)陂_(kāi)發(fā)中經(jīng)常用到的正則表達(dá)式也是這類問(wèn)題的代表。我們有的時(shí)候需要去匹配電話號(hào)碼、身份證號(hào)；我們不用為了每一種匹配都寫一個(gè)特定的算法，我們可以為每一種匹配定義一種文法，然后去解釋這種文法定義的句子就ok了。

文法規(guī)則和抽象語(yǔ)法樹(shù)

上面對(duì)于解釋器模式的定義中，提及到了一個(gè)詞：文法。在使用代碼實(shí)現(xiàn)解釋器模式之前，是非常有必要去學(xué)習(xí)一下文法的概念，以及如何表示一個(gè)語(yǔ)言的文法規(guī)則。再拿上面的游戲這個(gè)例子進(jìn)行說(shuō)明，我可以定義以下五條文法：

復(fù)制代碼代碼如下:

expression ::= direction action distance | composite //表達(dá)式

composite ::= expression 'and' expression //復(fù)合表達(dá)式

direction ::= 'up' | 'down' | 'left' | 'right' //移動(dòng)方向

action ::= 'move' | 'walk' //移動(dòng)方式

distance ::= an integer //移動(dòng)距離

上面的5條文法規(guī)則，對(duì)應(yīng)5個(gè)語(yǔ)言單位，這些語(yǔ)言單位可以分為兩大類：一類為終結(jié)符（也叫做終結(jié)符表達(dá)式），例如上面的direction、action和distance，它們是語(yǔ)言的最小組成單位，不能再進(jìn)行拆分；另一類為非終結(jié)符（也叫做非終結(jié)符表達(dá)式），例如上面的expression和composite，它們都是一個(gè)完整的句子，包含一系列終結(jié)符或非終結(jié)符。

我們就是根據(jù)上面定義的一些文法可以構(gòu)成更多復(fù)雜的語(yǔ)句，計(jì)算機(jī)程序?qū)⒏鶕?jù)這些語(yǔ)句進(jìn)行某種操作；而我們這里列出的文法，計(jì)算機(jī)是無(wú)法直接看懂的，所以，我們需要對(duì)我們定義的文法進(jìn)行解釋；就好比，我們編寫的C++代碼，計(jì)算機(jī)是看不懂的，我們需要進(jìn)行編譯一樣。解釋器模式，就提供一種模式去給計(jì)算機(jī)解釋我們定義的文法，讓計(jì)算機(jī)根據(jù)我們的文法去進(jìn)行工作。

在文法規(guī)則定義中可以使用一些符號(hào)來(lái)表示不同的含義，如使用“|”表示或，使用“{”和“}”表示組合，使用“*”表示出現(xiàn)0次或多次等，其中使用頻率最高的符號(hào)是表示“或”關(guān)系的“|”，如文法規(guī)則“bool Value ::= 0 | 1”表示終結(jié)符表達(dá)式bool Value的取值可以為0或者1。

除了使用文法規(guī)則來(lái)定義一個(gè)語(yǔ)言，在解釋器模式中還可以通過(guò)一種稱之為抽象語(yǔ)法樹(shù)的圖形方式來(lái)直觀地表示語(yǔ)言的構(gòu)成，每一棵語(yǔ)法樹(shù)對(duì)應(yīng)一個(gè)語(yǔ)言實(shí)例，對(duì)于上面的游戲文法規(guī)則，可以通過(guò)以下的抽象語(yǔ)法樹(shù)來(lái)進(jìn)行表示：

在抽象語(yǔ)法樹(shù)種，可以通過(guò)終結(jié)符表達(dá)式和非終結(jié)符表達(dá)式組成復(fù)雜的語(yǔ)句，每個(gè)文法規(guī)則的語(yǔ)言實(shí)例都可以表示為一個(gè)抽象語(yǔ)法樹(shù)，就是說(shuō)每一條具體的語(yǔ)句都可以用類似上圖所示的抽象語(yǔ)法樹(shù)來(lái)表示，在圖中終結(jié)符表達(dá)式類的實(shí)例作為樹(shù)的葉子節(jié)點(diǎn)，而非終結(jié)符表達(dá)式類的實(shí)例作為非葉子節(jié)點(diǎn)。抽象語(yǔ)法樹(shù)描述了如何構(gòu)成一個(gè)復(fù)雜的句子。

UML類圖

AbstractExpression：聲明一個(gè)抽象的解釋操作，這個(gè)接口被抽象語(yǔ)法樹(shù)中所有的節(jié)點(diǎn)所共享；
TernimalExpression：一個(gè)句子中的每個(gè)終結(jié)符需要該類的一個(gè)實(shí)例，它實(shí)現(xiàn)與文法中的終結(jié)符相關(guān)聯(lián)的解釋操作；
NonternimalExpression：

1.對(duì)于文法中的每一條規(guī)則都需要一個(gè)NonternimalExpression類；
2.為文法中的的每個(gè)符號(hào)都維護(hù)一個(gè)AbstractExpression類型的實(shí)例變量；
3.為文法中的非終結(jié)符實(shí)現(xiàn)解釋操作，在實(shí)現(xiàn)時(shí)，一般要遞歸地調(diào)用表示文法符號(hào)的那些對(duì)象的解釋操作；

Context：包含解釋器之外的一些全局信息；
Client：構(gòu)建一個(gè)需要進(jìn)行解釋操作的文法句子，然后調(diào)用解釋操作進(jìn)行解釋。

實(shí)際進(jìn)行解釋時(shí)，按照以下時(shí)序進(jìn)行的：

1.Client構(gòu)建一個(gè)句子，它是NonterminalExpression和TerminalExpression的實(shí)例的一個(gè)抽象語(yǔ)法樹(shù)，然后初始化上下文并調(diào)用解釋操作；
2.每一非終結(jié)符表達(dá)式節(jié)點(diǎn)定義相應(yīng)子表達(dá)式的解釋操作。而各終結(jié)符表達(dá)式的解釋操作構(gòu)成了遞歸的基礎(chǔ)；
3.每一節(jié)點(diǎn)的解釋操作用作用上下文來(lái)存儲(chǔ)和訪問(wèn)解釋器的狀態(tài)。

使用場(chǎng)合

在以下情況下可以考慮使用解釋器模式：

1.可以將一個(gè)需要解釋執(zhí)行的語(yǔ)言中的句子表示為一個(gè)抽象語(yǔ)法樹(shù)；
2.一些重復(fù)出現(xiàn)的問(wèn)題可以用一種簡(jiǎn)單的語(yǔ)言來(lái)進(jìn)行表達(dá)；
3.一個(gè)語(yǔ)言的文法較為簡(jiǎn)單；
4.執(zhí)行效率不是關(guān)鍵問(wèn)題?！咀ⅲ焊咝У慕忉屍魍ǔ２皇峭ㄟ^(guò)直接解釋抽象語(yǔ)法樹(shù)來(lái)實(shí)現(xiàn)的，而是需要將它們轉(zhuǎn)換成其他形式，使用解釋器模式的執(zhí)行效率并不高?！?/p>

代碼實(shí)現(xiàn)

我們這里用代碼來(lái)實(shí)現(xiàn)上面的游戲，只不過(guò)不是控制小狗在屏幕上移動(dòng)了，而是將對(duì)應(yīng)的控制指令翻譯成漢語(yǔ)進(jìn)行表示，這和翻譯成控制小狗移動(dòng)的指令的原理是一樣的。比如現(xiàn)在有指令：down run 10；那么，經(jīng)過(guò)解釋器模式得到的結(jié)果為：向下跑動(dòng)10。

復(fù)制代碼代碼如下:

#include <iostream>

#include <vector>

using namespace std;

#define MAX_SIZE 256

#define SAFE_DELETE(p) if (p) { delete p; p = NULL; }

const wchar_t *const DOWN = L"down";

const wchar_t *const UP = L"up";

const wchar_t *const LEFT = L"left";

const wchar_t *const RIGHT = L"right";

const wchar_t *const MOVE = L"move";

const wchar_t *const WALK = L"walk";

class AbstractNode

{

public:

     virtual wchar_t *Interpret() = 0;

};

class AndNode : public AbstractNode

{

public:

     AndNode(AbstractNode *left, AbstractNode *right) : m_pLeft(left), m_pRight(right){}

     wchar_t *Interpret()

     {

          wchar_t *pResult = new wchar_t[MAX_SIZE];

          memset(pResult, 0, MAX_SIZE * sizeof(wchar_t));

          wchar_t *pLeft = m_pLeft->Interpret();

          wchar_t *pRight = m_pRight->Interpret();

          wcscat_s(pResult, MAX_SIZE, pLeft);

          wcscat_s(pResult, MAX_SIZE, pRight);

          SAFE_DELETE(pLeft);

          SAFE_DELETE(m_pRight);

          return pResult;

     }

private:

     AbstractNode *m_pLeft;

     AbstractNode *m_pRight;

};

class SentenceNode : public AbstractNode

{

public:

     SentenceNode(AbstractNode *direction, AbstractNode *action, AbstractNode *distance) :

          m_pDirection(direction), m_pAction(action), m_pDistance(distance){}

     wchar_t *Interpret()

     {

          wchar_t *pResult = new wchar_t[MAX_SIZE];

          memset(pResult, 0, MAX_SIZE * sizeof(wchar_t));

          wchar_t *pDirection = m_pDirection->Interpret();

          wchar_t *pAction = m_pAction->Interpret();

          wchar_t *pDistance = m_pDistance->Interpret();

          wcscat_s(pResult, MAX_SIZE, pDirection);

          wcscat_s(pResult, MAX_SIZE, pAction);

          wcscat_s(pResult, MAX_SIZE, pDistance);

          SAFE_DELETE(pDirection);

          SAFE_DELETE(pAction);

          SAFE_DELETE(pDistance);

          return pResult;

     }

private:

     AbstractNode *m_pDirection;

     AbstractNode *m_pAction;

     AbstractNode *m_pDistance;

};

class DirectionNode : public AbstractNode

{

public:

     DirectionNode(wchar_t *direction) : m_pDirection(direction){}

     wchar_t *Interpret()

     {

          wchar_t *pResult = new wchar_t[MAX_SIZE];

          memset(pResult, 0, MAX_SIZE * sizeof(wchar_t));

          if (!_wcsicmp(m_pDirection, DOWN))

          {

               wcscat_s(pResult, MAX_SIZE, L"向下");

          }

          else if (!_wcsicmp(m_pDirection, UP))

          {

               wcscat_s(pResult, MAX_SIZE, L"向上");

          }

          else if (!_wcsicmp(m_pDirection, LEFT))

          {

               wcscat_s(pResult, MAX_SIZE, L"向左");

          }

          else if (!_wcsicmp(m_pDirection, RIGHT))

          {

               wcscat_s(pResult, MAX_SIZE, L"向右");

          }

          else

          {

               wcscat_s(pResult, MAX_SIZE, L"無(wú)效指令");

          }

          SAFE_DELETE(m_pDirection);

          return pResult;

     }

private:

     wchar_t *m_pDirection;

};

class ActionNode : public AbstractNode

{

public:

     ActionNode(wchar_t *action) : m_pAction(action){}

     wchar_t *Interpret()

     {

          wchar_t *pResult = new wchar_t[MAX_SIZE];

          memset(pResult, 0, MAX_SIZE * sizeof(wchar_t));

          if (!_wcsicmp(m_pAction, MOVE))

          {

               wcscat_s(pResult, MAX_SIZE, L"移動(dòng)");

          }

          else if (!_wcsicmp(m_pAction, WALK))

          {

               wcscat_s(pResult, MAX_SIZE, L"走動(dòng)");

          }

          else

          {

               wcscat_s(pResult, MAX_SIZE, L"無(wú)效指令");

          }

          SAFE_DELETE(m_pAction);

          return pResult;

     }

private:

     wchar_t *m_pAction;

};

class DistanceNode : public AbstractNode

{

public:

     DistanceNode(wchar_t *distance) : m_pDistance(distance){}

     wchar_t *Interpret()

     {

          wchar_t *pResult = new wchar_t[MAX_SIZE];

          memset(pResult, 0, MAX_SIZE * sizeof(wchar_t));

          wcscat_s(pResult, MAX_SIZE, m_pDistance);

          SAFE_DELETE(m_pDistance);

          return pResult;

     }

private:

     wchar_t *m_pDistance;

};

class InstructionHandler

{

public:

     InstructionHandler(wchar_t *instruction) : m_pInstruction(instruction), m_pTree(NULL){}

     void Handle();

     void Output();

private:

     void SplitInstruction(wchar_t **&instruction, int &size);

     wchar_t *m_pInstruction;

     AbstractNode *m_pTree;

};

void InstructionHandler::Handle()

{

     AbstractNode *pLeft = NULL;

     AbstractNode *pRight = NULL;

     AbstractNode *pDirection = NULL;

     AbstractNode *pAction = NULL;

     AbstractNode *pDistance = NULL;

     vector<AbstractNode *> node; // Store the instruction expression

     // Split the instruction by " "

     wchar_t **InstructionArray = NULL;

     int size;

     SplitInstruction(InstructionArray, size);

     for (int i = 0; i < size; ++i)

     {

          if (!_wcsicmp(InstructionArray[i], L"and")) // The instruction is composited by two expressions

          {

               wchar_t *pDirectionStr = InstructionArray[++i];

               pDirection = new DirectionNode(pDirectionStr);

               wchar_t *pActionStr = InstructionArray[++i];

               pAction = new ActionNode(pActionStr);

               wchar_t *pDistanceStr = InstructionArray[++i];

               pDistance = new DistanceNode(pDistanceStr);

               pRight = new SentenceNode(pDirection, pAction, pDistance);

               node.push_back(new AndNode(pLeft, pRight));

          }

          else

          {

               wchar_t *pDirectionStr = InstructionArray[i];

               pDirection = new DirectionNode(pDirectionStr);

               wchar_t *pActionStr = InstructionArray[++i];

               pAction = new ActionNode(pActionStr);

               wchar_t *pDistanceStr = InstructionArray[++i];

               pDistance = new DistanceNode(pDistanceStr);

               pLeft = new SentenceNode(pDirection, pAction, pDistance);

               node.push_back(pLeft);

          }

     }

     m_pTree = node[node.size() - 1];

}

void InstructionHandler::Output()

{

     wchar_t *pResult = m_pTree->Interpret();

     setlocale(LC_ALL,"");

     wprintf_s(L"%s\n", pResult);

     SAFE_DELETE(pResult);

}

void InstructionHandler::SplitInstruction(wchar_t **&instruction, int &size)

{

     instruction = new wchar_t*[10];

     memset(instruction, 0, 10 * sizeof( wchar_t*));

     for (int i = 0; i < 10; ++i)

     {

          instruction[i] = new wchar_t[10];

          memset(instruction[i], 0, 10 * sizeof(wchar_t));

     }

     size = 0;

     int n = 0;

     while (*m_pInstruction != L'\0')

     {

          if (*m_pInstruction == L' ')

          {

               size++;

               m_pInstruction++;

               n = 0;

               continue;

          }

          instruction[size][n++] = *m_pInstruction++;

     }

     size++;

}

int main()

{

     wchar_t *pInstructionStr = L"up move 5 and down walk 10";

     InstructionHandler *pInstructionHandler = new InstructionHandler(pInstructionStr);

     pInstructionHandler->Handle();

     pInstructionHandler->Output();

     SAFE_DELETE(pInstructionHandler);

}

在上面的代碼中，我沒(méi)有用到Context類，一般Context類作為環(huán)境上下文類，用于存儲(chǔ)解釋器之外的一些全局信息，它通常作為參數(shù)被傳遞到所有表達(dá)式的解釋方法interpret中，可以在Context對(duì)象中存儲(chǔ)和訪問(wèn)表達(dá)式解釋器的狀態(tài)，向表達(dá)式解釋器提供一些全局的、公共的數(shù)據(jù)，此外還可以在Context中增加一些所有表達(dá)式解釋器都共有的功能，減輕解釋器的職責(zé)。而我們?cè)诖a中定義的一些常量，完全可以放入到Context類中，作為上下文的全局?jǐn)?shù)據(jù)。

主要優(yōu)點(diǎn)

1.易于改變和擴(kuò)展文法。由于在解釋器模式中使用類來(lái)表示語(yǔ)言的文法規(guī)則，因此可以通過(guò)繼承等機(jī)制來(lái)改變或擴(kuò)展文法；
2.每一條文法規(guī)則都可以表示為一個(gè)類，因此可以方便地實(shí)現(xiàn)一個(gè)簡(jiǎn)單的語(yǔ)言；
3.實(shí)現(xiàn)文法較為容易；在抽象語(yǔ)法樹(shù)中每一個(gè)表達(dá)式節(jié)點(diǎn)類的實(shí)現(xiàn)方式都是相似的，這些類的代碼編寫都不會(huì)特別復(fù)雜；
4.增加新的解釋表達(dá)式較為方便。如果用戶需要增加新的解釋表達(dá)式只需要對(duì)應(yīng)增加一個(gè)新的終結(jié)符表達(dá)式類或非終結(jié)符表達(dá)式類，原有表達(dá)式類代碼無(wú)須修改，符合“開(kāi)閉原則”。

主要缺點(diǎn)

1.對(duì)于復(fù)雜文法難以維護(hù)；在解釋器模式中，每一條規(guī)則至少需要定義一個(gè)類，因此如果一個(gè)語(yǔ)言包含太多文法規(guī)則，類的個(gè)數(shù)將會(huì)急劇增加，導(dǎo)致系統(tǒng)難以管理和維護(hù)，此時(shí)可以考慮使用語(yǔ)法分析程序等方式來(lái)取代解釋器模式；
2.執(zhí)行效率低；由于在解釋器模式中使用了大量的循環(huán)和遞歸調(diào)用，因此在解釋較為復(fù)雜的句子時(shí)其速度很慢，而且代碼的調(diào)試過(guò)程也很麻煩。

總結(jié)

解釋器模式在實(shí)際的系統(tǒng)開(kāi)發(fā)中使用的非常少，因?yàn)樗鼤?huì)引起效率、性能以及維護(hù)方面的問(wèn)題，并且難度較大，一般在一些大中型的框架型項(xiàng)目中能夠找到它的身影。而現(xiàn)在又有很多的開(kāi)源庫(kù)提供了對(duì)實(shí)際需要的支持，所以，我們?cè)趯?shí)際開(kāi)發(fā)中沒(méi)有必要再去重復(fù)造輪子，能夠理解了解釋器模式就好了。

您可能感興趣的文章: