C++設計モードの解釈器モード


前言
その日、暇で退屈で、オンラインプログラミング学習サイトに行きました.最近あのオンラインプログラミング学習サイトはとても人気があります.以前、ゲイツ、ザックバーグなどの大物が宣伝に来たが、誰もがプログラミングを学ぶべきだと考えていた.どうしたんだ?これが中国なら、まだ人を生かすことができますか?話題は開かないで、やはり私はそのオンラインプログラミングのウェブサイトに行ったでしょう.まず、あなたに小さなゲームをして、プログラミングに興味を奮い立たせます.ゲームはこのようにして、ホームページの上で1つの編集枠があって、スクリーンの上で1匹の子犬がいて、例えばあなたは編集枠の中でこのような文を入力します:down run 10;車に戻ると、スクリーンの子犬が10個の四角い大きさの長さを下に走っているのが見えます.up walk 5を入力して、車に戻ると、子犬は5つの四角い大きさの長さを上に歩きます.確かに少し面白いです.しかし、私のようなこのようなゲームが私の興味を奮い立たせる必要がない人にとって、私はそれがどのように実現されたのか、どのように私が入力した一言を子犬の移動をコントロールしたのかを考えるのが好きです.このすべてのことは、今日まとめた解釈器モードに言わざるを得ません.
インタプリタモード
GOFの「設計モード:多重化可能なオブジェクト向けソフトウェアの基礎」という本では、言語を指定し、文法の表現を定義し、言語の文を説明するために使用される解釈器を定義しています.特定のタイプの問題が発生する頻度が十分に高い場合、その問題の各インスタンスを単純な言語の文として記述する価値がある可能性があります.これにより、これらの文を解釈することによって問題を解決する解釈器を構築することができる.
上のゲームのように、私はup walk 5を入力して、私は:移動方向+移動方式+移動距離というフォーマットに従って私の命令を入力しなければなりません.このフォーマットの命令は文法で、私が定義したこのような文法に従って入力してこそ、スクリーンの上の子犬の移動を制御することができます.もちろん、up walk 5を入力します.スクリーンの子犬はきっと分からないに違いありません.それは私が入力したものが何なのか分かりません.この時どうすればいいですか.私が入力した内容を子犬が理解できるものに翻訳するツールが必要です.このツールは定義の中で言及した解釈器で、解釈器は私が入力した命令を解釈して、それから解釈した命令をスクリーンの子犬に送って、子犬は理解して、実際の移動を行います.
私たちが開発でよく使う正規表現もこのような問題の代表です.私たちは時々電話番号、身分証明書番号を一致させる必要があります.私たちはすべてのマッチングのために特定のアルゴリズムを書く必要はありません.私たちはそれぞれのマッチングのために文法を定義して、この文法定義の文を説明すればokになります.
文法規則と抽象文法ツリー
解釈器モードの定義では,文法という語について述べた.コードを用いて解釈器モードを実現する前に,文法の概念と,一つの言語の文法規則をどのように表すかを学ぶ必要がある.上のゲームの例を説明すると、以下の5つの文法を定義することができます.
expression ::= direction action distance | composite //   
composite ::= expression 'and' expression //     
direction ::= 'up' | 'down' | 'left' | 'right' //    
action ::= 'move' | 'walk' //    
distance ::= an integer //    

上の5つの文法規則は、5つの言語単位に対応しており、これらの言語単位は2つの大きなクラスに分けることができる.1つは、上のdirection、action、distanceなどの終結符(終結符式とも呼ばれる)であり、これらは言語の最小構成単位であり、これ以上分割することはできない.もう1つのクラスは、非終端(非終端式とも呼ばれる)です.たとえば、上記のexpressionおよびcompositeは、一連の終端または非終端を含む完全な文です.
私たちは上で定義したいくつかの文法に基づいてより複雑な文を構成することができ、コンピュータプログラムはこれらの文に基づいて何らかの操作を行う.ここにリストされている文法は、コンピュータでは直接理解できないので、定義した文法を説明する必要があります.例えば、私たちが書いたC++コードは、コンピュータが読めないので、コンパイルする必要があります.解釈器モードは、コンピュータに私たちが定義した文法を説明し、コンピュータに私たちの文法に基づいて仕事をさせるモードを提供します.
文法規則定義では、「|」で表すか、「{」と「}」で組み合わせて表すか、「*」で0回以上現れるかなど、異なる意味を表す記号を使用できます.使用頻度が最も高い記号は「または」関係を表す「|」です.文法規則「bool Value:::=0|1」が示すように、終端式bool Valueの値は0または1とすることができる.
1つの言語を定義するために文法規則を使用するだけでなく、解釈器モードでは抽象文法ツリーと呼ばれる図形で言語の構成を直感的に表すことができ、各文法ツリーは1つの言語インスタンスに対応し、上記のゲーム文法規則については、以下の抽象文法ツリーを介して表すことができる.
抽象構文ツリーでは、複雑な文を終端式と非終端式で構成できます.各構文規則の言語インスタンスは抽象構文ツリーとして表すことができます.つまり、各具体的な文は、上図に示すような抽象構文ツリーで表すことができ、図中の終端式クラスのインスタンスはツリーの葉ノードとして表されます.非リーフノードとして、終端式クラスのインスタンスではありません.抽象構文ツリーは、複雑な文をどのように構成するかを説明します.
UMLクラス図
AbstractExpression:抽象構文ツリー内のすべてのノードによって共有される抽象的な解釈操作を宣言します.TernimalExpression:文の各終端には、文法の終端に関連する解釈操作を実現するクラスのインスタンスが必要です.NonternimalExpression:
  • 文法の各規則にはNonternimalExpressionクラスが必要です.
  • は、文法の各シンボルに対してAbstractExpressionタイプのインスタンス変数を維持する.
  • は文法中の非終端子で解釈操作を実現し、実現時には文法記号を表すオブジェクトの解釈操作を再帰的に呼び出すのが一般的である.

  • Context:解釈器以外のグローバル情報を含む;Client:解釈操作が必要な文法文を構築し、解釈操作を呼び出して解釈します.
    実際に説明する場合、以下のタイミングで行います.
  • Clientは、NoterminalExpressionとTerminalExpressionのインスタンスの抽象構文ツリーであり、コンテキストを初期化して解釈操作を呼び出す文を構築します.
  • 各非終端表現ノードは、対応するサブ表現の解釈動作を定義する.各ターミナル式の解釈操作は再帰的な基礎を構成している.
  • 各ノードの解釈動作は、インタプリタの状態を格納およびアクセスするために作用コンテキストを使用する.

  • 使用する場合
    次の場合、インタプリタモードを使用することが考えられます.
  • は、実行を解釈する必要がある言語の文を抽象構文ツリーとして表すことができる.
  • いくつかの重複した問題は簡単な言語で表現することができる.
  • 一つの言語の文法は比較的簡単です.
  • の実行効率は重要な問題ではありません.【注意:効率的な解釈器は、抽象構文ツリーを直接解釈することによって実現されるのではなく、他の形式に変換する必要があり、解釈器モードを使用する実行効率は高くありません.】

  • コード実装
    ここではコードで上記のゲームを実現しますが、子犬が画面上を移動するのを制御するのではなく、対応する制御命令を中国語に翻訳して表示するのは、子犬の移動を制御する命令に翻訳する原理と同じです.例えば今命令があります:down run 10;さて、インタプリタモードにより得られる結果は、下に10を走行することである.
    #include 
    #include 
    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
    "
    , 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クラスは環境コンテキストクラスとして使用され、解釈器以外のグローバル情報を格納するために使用されます.通常、パラメータとしてすべての式の解釈方法interpretに渡されます.Contextオブジェクトに式解釈器の状態を格納およびアクセスし、式解釈器にグローバルな、共通のデータに加えて、Contextですべての式解釈器が共有する機能を追加し、解釈器の役割を軽減することもできます.コードで定義した定数の一部は、コンテキストのグローバルデータとしてContextクラスに完全に格納できます.
    主な利点
  • 文法の変更と拡張が容易です.解釈器モードではクラスを用いて言語の文法規則を表すため、継承などのメカニズムによって文法を変更または拡張することができる.
  • 各文法規則は1つのクラスとして表すことができるので、簡単な言語を容易に実現することができる.
  • 文法の実現は比較的容易である.抽象構文ツリーの各式ノードクラスの実装方法は似ており、これらのクラスのコード作成は特に複雑ではありません.
  • 新しい解釈式を追加するのは便利です.ユーザーが新しい解釈式を追加する必要がある場合、新しい終端式クラスまたは非終端式クラスを追加する必要がある場合は、既存の式クラスコードを変更する必要はなく、「開閉の原則」に合致します.

  • 主な欠点
  • は複雑な文法に対して維持しにくい.解釈器モードでは、各ルールは少なくとも1つのクラスを定義する必要があるため、1つの言語に文法ルールが多すぎると、クラスの個数が急激に増加し、システムの管理とメンテナンスが困難になるため、解釈器モードの代わりに文法分析プログラムなどの方法を使用することが考えられる.
  • の実行効率が低い.解釈器モードでは多くのループと再帰呼び出しが使用されるため,複雑な文を解釈する際に速度が遅く,コードのデバッグプロセスも面倒である.

  • まとめ
    解釈器モードは、効率、パフォーマンス、メンテナンスの問題を引き起こし、難易度が高いため、実際のシステム開発で使用されることは非常に少ない.一般的には、大中型のフレームワーク型プロジェクトでその姿を見つけることができる.現在では多くのオープンソースライブラリが実際のニーズをサポートしているので、実際の開発で車輪を繰り返す必要はありません.釈器モードを理解すればいいのです.
    2014年1月21日大連、東軟.