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

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

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

前言

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

解釋器模式

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

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

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

文法規(guī)則和抽象語法樹

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

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

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

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

direction ::= 'up' | 'down' | 'left' | 'right' //移動方向

action ::= 'move' | 'walk' //移動方式

distance ::= an integer //移動距離

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

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

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

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

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

UML類圖

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

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

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

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

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

使用場合

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

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

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

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

          }

          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"移動");

          }

          else if (!_wcsicmp(m_pAction, WALK))

          {

               wcscat_s(pResult, MAX_SIZE, L"走動");

          }

          else

          {

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

          }

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

}

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

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

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

主要缺點(diǎn)

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

總結(jié)

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

您可能感興趣的文章: