[设计模式]解释器(Interpreter)之大胆向MM示爱吧

2021-12-31 13:46:28

为方便读者，本文已添加至索引：

写在前面

“我刚写了个小程序，需要你来参与下。”我把MM叫到我的电脑旁，“来把下面这条命令打进去，这是个练习打(Pian)符(ni)号(de)的小程序，看看你能不能全部打正确”。

[*_]_7@1_9@/(_5@0_3@)*/((_4@)_2$)_$^/$+(_7@)*/_$1_6$/$3_2$/_3$3_3@/_5$

MM诧异地看看我，然后可怜巴巴地坐到屏幕前，对着键盘一个字一个字地敲。她打字超慢的，各种符号都是用两个食指打进去的。她打着打着，说想哭了。我赶忙告诉她，加油，全打正确了有惊喜。

终于，她敲下了回车键。映入眼帘的是：

       _         _

     *   *     *   *

    *      * *      *

    *       *       *

     *             *

       *         *

          *   *

            *

See Result

她忽然就开心起来，问我这个是怎么回事。我告诉她，“这说明你刚才的命令输对了，电脑按照命令画出了它~。要不再接再厉，试试下面这个更有挑战性的？”

[#*]_@*/_(_2@*)/$0_9@*6_(_@*)*2_3@*/$0_6$0_2$*+(_$)*/$0_5$0_3$*3_3@*/(_2@*)_4@+$3_3$*+(_@*)_2$/$4_4@0_$3_2$3_4@*3_3$3_2$/@*7_5@*5_4$3_7@*

……

是不是读者你也想知道这个会是什么结果了吧？这当然跟我们今天的主题，解释器模式有关啦！会在示例一节展开。

其实，我们平时接触到的解释器模式相关的实际例子并不太多，最常见的莫过于正则表达式了。它通过规定一系列的文法规则，并给予了相关的解释操作，从而成为处理字符串的通用强大的工具。首先我们了解下解释器模式的相关技术要点，然后在示例部分，我们将解释上文中所出现的莫名的式子。

要点梳理

  • 目的分类
    • 类行为型模式
  • 范围准则
    • 类（该模式处理类和子类之间的关系，这些关系通过继承建立，是静态的，在编译时刻便确定下来了）
  • 主要功能
    • 给定一个语言，定义它的文法的一种表示，并定义一个解释器，这个解释器使用该表示来解释语言中的句子。
  • 适用情况
    • 当有一个语言需要解释执行, 并且我们可将该语言中的句子表示为一个抽象语法树时，可使用解释器模式。当存在以下情况时，效果最好：
      • 该文法简单。对于复杂的文法, 文法的类层次变得庞大而无法管理
      • 效率不是一个关键问题。最高效的解释器通常不是通过直接解释语法分析树实现。
  • 参与部分
    • AbstractExpression（抽象表达式）：声明一个抽象的解释操作，这个接口为抽象语法树中所有的节点所共享
    • TerminalExpression（终结符表达式）：实现与文法中的终结符相关联的解释操作，一个句子中的每个终结符需要该类的一个实例
    • NonterminalExpression（非终结符表达式）：为文法中的非终结符实现解释操作。解释时，一般要递归调用它所维护的AbstractExpression类型对象的解释操作
    • Context（上下文）：包含解释器之外的一些全局信息
    • Client（用户）：构建(或被给定) 表示该文法定义的语言中一个特定的句子的抽象语法树。该抽象语法树由TerminalExpression和NonterminalExpression的实例装配而成。
  • 协作过程
    • Client构建一个句子，它是TerminalExpression和NonterminalExpression的实例的一个抽象语法树，然后初始化上下文，并调用解释操作。
    • 每一非终结符表达式节点定义相应子表达式的解释操作。
    • 每一节点的解释操作用上下文来存储和访问解释器的状态。
  • UML图

[设计模式]解释器(Interpreter)之大胆向MM示爱吧

示例分析 - 字符画解释器

为了让MM不明觉厉，我想到了通过简单的解释器来实现，从字符串到一个字符画的转换过程。我觉得利用stringstream流可以方便地构建一个字符画，因此，我们首先确定我们实现这个模式的上下文（Context）就是stringstream对象。然后我们定义一些具体的字符操作表达式。它们是可以画出字符画的一些基本操作：

TerminalExpression：

  • Constant：常量表达式。它也是终结符表达式。它的解释操作就是将一个固定的string插入到Context流中。

NonterminalExpression：

  • RepeatExpression：重复表达式。它是非终结符表达式。它的解释操作就是使一个Expression重复N次。
  • AddExpression：加法表达式。非终结符表达式。它的解释操作是使两个Expression拼接在一起。
  • ReverseExpression：反转表达式。非终结符表达式。它的解释操作是使一个Expression逆序。

可以看到这几个表达式是可以构成抽象语法树的。让我们看看代码：

 #ifndef EXPRESSION_H_INCLUDED

 #define EXPRESSION_H_INCLUDED

 #include <string>

 #include <sstream>

 using namespace std;

 // ... Abstract Class ...

 class Expression {

 public:

     Expression() {}

     virtual ~Expression() {}

     virtual void eval(stringstream&) = ;

 };

 // ... RepeatExpression Class ...

 class RepeatExpression : public Expression {

 public:

     RepeatExpression(Expression*, int);

     void eval(stringstream&);

 private:

     Expression* _oper;

     int         _mNum;

 };

 // ... AddExpression Class ...

 class AddExpression : public Expression {

 public:

     AddExpression(Expression*, Expression*);

     void eval(stringstream&);

 private:

     Expression* _oper1;

     Expression* _oper2;

 };

 // ... ReverseExpression Class ...

 class ReverseExpression : public Expression {

 public:

     ReverseExpression(Expression*);

     void eval(stringstream&);

 private:

     Expression* _oper;

 };

 // ... Constant Class ...

 class Constant : public Expression {

 public:

     Constant(const char*);

     Constant(const char*, int);

     void eval(stringstream&);

 private:

     string _mStr;

 };

 #endif // EXPRESSION_H_INCLUDED

expression.h

 #include "expression.h"

 #include <algorithm>

 using namespace std;

 // ... RepeatExpression  BEGIN ...

 RepeatExpression::RepeatExpression(Expression* oper, int m) {

     _oper = oper;

     _mNum = m;

 }

 void RepeatExpression::eval(stringstream& ss) {

     stringstream t_str;

     _oper->eval(t_str);

     for (int i = ; i < _mNum; i++) {

         ss << t_str.str();

     }

 }

 // ... RepeatExpression  END ...

 // ... AddExpression BEGIN ...

 AddExpression::AddExpression(Expression* oper1, Expression* oper2) {

     _oper1 = oper1;

     _oper2 = oper2;

 }

 void AddExpression::eval(stringstream& ss) {

     stringstream t_str;

     _oper1->eval(t_str);

     _oper2->eval(t_str);

     ss << t_str.str();

 }

 // ... AddExpression END ...

 // ... ReverseExpression BEGIN ...

 ReverseExpression::ReverseExpression(Expression* o) {

     _oper = o;

 }

 void ReverseExpression::eval(stringstream& ss) {

     stringstream t_str;

     _oper->eval(t_str);

     string str = t_str.str();

     reverse(str.begin(), str.end());

     ss << str;

 }

 // ... ReverseExpression END ...

 // ... Constant BEGIN ...

 Constant::Constant(const char* str) {

     _mStr = string(str);

 }

 Constant::Constant(const char* str, int len) {

     _mStr = string(str, len);

 }

 void Constant::eval(stringstream& ss) {

     ss << _mStr;

 }

 // ... Constant END ...

expression.cpp

到了这里，我们如果想生成一个字符画: "~~o>_<o~~"，可以这么做：

 stringstream ss;

 Expression* e1 = new RepeatExpression(new Constant("~"), );

 Expression* e2 = new AddExpression(e1, new Constant("o>"));

 Expression* e3 = new AddExpression(e2, new Constant("_"));

 Expression* result = new AddExpression(e3, new ReverseExpression(e2));

 result->eval(ss);

 cout << ss.str() << endl;

其实解释器模式部分的编程已经结束了。但显然这个并没有达到前言中翻译那串莫名字符串的目的。为此，我们还需在此基础上，定义一些语法，写一个语法分析器来将那串字符构建成抽象语法树。这里，我就偷懒了，写了个非常简单，没有什么优化的语法分析器：

// 定义的一些符号含义：

//      []  ----  字符集

//      ()  ----  分组

//      @N  ----  取字符集中第N个字符(N从0开始)

//      *N  ----  *前面的表达式重复N次
//      $N  ----  取第N个分组(N从0开始，分组由括号顺序确定，嵌套的括号以从里到外的规则递增)

//      +   ----  加号两边的表达式拼接

//      ^   ----  ^前面的表达式逆序

//      _N  ----  拼接N个空格

//      /   ----  拼接一个换行符

具体代码如下：

 #ifndef TRANSLATOR_H_INCLUDED

 #define TRANSLATOR_H_INCLUDED

 #include <string>

 #include <vector>

 using namespace std;

 class Expression;

 class Translator {

 public:

     Translator();

     ~Translator();

     Expression* translate(string& str);

 private:

     Expression* translateExp(string& str);

     char*   _mCharSet;

     vector<Expression*> _mExpGroup;

 };

 #endif // TRANSLATOR_H_INCLUDED

Translator.h

 #include "Translator.h"

 #include "expression.h"

 #include <cstring>

 #include <cstdlib>

 using namespace std;

 Translator::Translator() {

     _mCharSet = ;

 }

 Translator::~Translator() {

     if (_mCharSet) delete[] _mCharSet;

 }

 Expression* Translator::translate(string& str) {

     Expression* result = ;

     for(unsigned int i = ; i < str.size(); i++ ) {

         if (str.at(i) == '[') {

             int sEnd = str.find_last_of("]");

             int sLen = sEnd - i - ;

             if (_mCharSet) delete[] _mCharSet;

             _mCharSet = new char[sLen];

             strcpy(_mCharSet, str.substr(i+, sLen).data());

             i = sEnd;

         } else if (str.at(i) == '@') {

             int sChar = atoi(str.substr(i + , ).c_str());

             Expression* tmp = new Constant(&_mCharSet[sChar], );

             result = tmp;

             i = i + ;

         } else if (str.at(i) == '(') {

             int pos = i + ;

             int left = ;

             for (;pos < str.size(); pos++) {

                 if (str.at(pos) == ')') {

                     if (left == )

                         break;

                     else

                         left--;

                 }

                 if (str.at(pos) == '(')

                     left++;

             }

             string t_str = str.substr(i + , pos - i - );

             Expression* tmp = translate(t_str);

             _mExpGroup.push_back(tmp);

             result = tmp;

             i = pos;

         } else if (str.at(i) == '+') {

             string t_str = str.substr(i + );

             result = new AddExpression(result, translate(t_str));

             break;

         } else if (str.at(i) == '*') {

             int pos = i+;

             for (;pos < str.size();pos++) {

                 if (str.at(pos) > '' || str.at(pos) < '') break;

             }

             pos--;

             int sRep = atoi(str.substr(i + , pos - i).c_str());

             Expression* tmp = new RepeatExpression(result, sRep);

             result = tmp;

             i = pos;

         } else if (str.at(i) == '^') {

             Expression* tmp = new ReverseExpression(result);

             result = tmp;

         } else if (str.at(i) == '$') {

             int pos = i+;

             for (;pos < str.size();pos++) {

                 if (str.at(pos) > '' || str.at(pos) < '') break;

             }

             pos--;

             int nGroup = atoi(str.substr(i + , pos - i).c_str());

             if (nGroup >= _mExpGroup.size()) return ;

             result = _mExpGroup[nGroup];

             i = pos;

         } else if (str.at(i) == '/') {

             string t_str = str.substr(i + );

             Expression* tmp = new Constant("\n");

             if (!result) {

                 result = new AddExpression(tmp, translate(t_str));

             }

             else {

                 result = new AddExpression(new AddExpression(result, tmp), translate(t_str));

             }

             break;

         } else if (str.at(i) == '_') {

             int pos = i+;

             for (;pos < str.size();pos++) {

                 if (str.at(pos) > '' || str.at(pos) < '') break;

             }

             pos--;

             int sRep = (pos == i) ?  : atoi(str.substr(i + , pos - i).c_str());

             string t_str = str.substr(pos + );

             Expression* tmp = new RepeatExpression(new Constant(" "), sRep);

             if (!result) {

                 result = new AddExpression(tmp, translate(t_str));

             }

             else {

                 result = new AddExpression(new AddExpression(result, tmp), translate(t_str));

             }

             break;

         }

     }

     return result;

 }

Translator.cpp

再次强调，这个语法分析器，并不是解释器模式所讲的内容。好了，写个简单的main函数就可以运行了：

 #include <iostream>

 #include "expression.h"

 #include "Translator.h"

 using namespace std;

 int main()

 {

     cout << "Input your command below: " << endl;

     string str;

     getline(cin, str);

     Translator translator;

     // ... Generate the Abstract Grammar Tree by Translator

     Expression* myExp = translator.translate(str);

     if (!myExp) return ;

     // ... Call Its Interpret Operation

     stringstream ss;

     myExp->eval(ss);

     cout << ss.str() << endl;

     return ;

 }

那么我们输入之前第二串字符试试：

 *****

   **

  **         ******  **** ****   *****

  **        **    **  **   **   **   **

  **       **     **  **  **   ********

  ##    #  ##     ##  ## ##    ##

 ##    #   ##    ##    ###     ##    ##

#######     #####      ##       ######

MM表示很开心。对于这个示例的UML图：

[设计模式]解释器(Interpreter)之大胆向MM示爱吧

特点总结

我们可以看到，Interpreter解释器模式有以下优点和缺点：

  1. 易于改变和扩展文法。因为该模式使用类来表示文法规则，我们可以使用继承来改变或扩展该文法。多加一种文法就新增一个类。
  2. 也易于实现文法。定义抽象语法树中各个节点的类的实现大体类似。通常它们也可用一个编译器或语法分析程序生成器自动生成。
  3. 复杂的文法难以维护。解释器模式为文法中的每一条规则至少定义了一个类，因此包含许多规则的文法可能难以管理和维护。

同时我们可以看到，它和其他设计模式：Composite（组合）模式有着许多相通的地方。具体可以参见之前的笔记。

写在最后

今天的笔记就到这里了，欢迎大家批评指正！如果觉得可以的话，好文推荐一下，我会非常感谢的！

上一篇：写python时加入缩进设置


下一篇：用VUEJS做一个网易云音乐