解释器模式 Interpreter 行为型 设计模式（十九）

 

解释器模式（interpreter）

 

考虑上图中计算器的例子

设计可以用于计算加减运算（简单起见，省略乘除），你会怎么做？ 

 

你可能会定义一个工具类，工具类中有n多静态方法

比如定义了两个方法用于计算a+b 和 a+b-c

public static int add(int a,int b){
return a+b;
}

public static int add(int a,int b,int c){
return a+b-c;
}

但是很明显，如果形式有限，那么可以针对对应的形式进行编程

如果形势变化非常多，这就不符合要求，因为加法和减法运算，两个运算符与数值可以有无穷种组合方式

比如 a+b+c+d+e+f、a-b-c+d、a-b+c....等等 

用有限的方法参数列表组合的形式，怎么可能表达出无穷的变化？

 

也可以通过函数式接口，能够提高一定的灵活性

package function;

@functionalinterface
public interface function1<a,b,c,d,e,f,g, r> {
r xxxxx(a a,b b,c c,d d,e e,f f,g g);
}

好处是可以动态的自定义方程式，但是你可能需要定义很多函数式接口

而且，有限的函数式接口也不能解决无限种可能的

上面的方式都是以有限去应对无限，必然有行不通的时候

显然，你需要一种翻译识别机器，能够解析由数字以及+ - 符号构成的合法的运算序列

如果把运算符和数字都看作节点的话，能够逐个节点的进行读取解析运算

这就是解释器模式的思维

解释器不限定具体的格式，仅仅限定语法，能够识别遵循这种语法的“语言”书写的句子

不固定你的形式，也就是不存在强制为a+b的情形，但是你必须遵循固定语法，数字和 + - 符号组成

java编译器可以识别遵循java语法的表达式和语句，c语言编译器可以识别遵循c语言语法的表达式和语句。说的就是这个意思

 

意图

给定一个语言，定义他的文法的一种表示，并定义一个解释器，这个解释器使用该表示来解释语言中的句子。

解释器模式其实就是编译原理的思维方式

 

如果某种特定类型的问题发生的频率很高，那么就可以考虑将该问题的各个实例表述为一个简单语言中的句子，通过解释器进行识别。

经典的案例就是正则表达式

我们在实际开发中，经常需要判断邮箱地址、手机号码是否正确，如果没有正则表达式

我们需要编写特定的算法函数进行判断，去实现这些规则，比如一个算法可能用来判断是否是邮箱，比如要求必须有@符号

 

正则表达式是用来解决字符串匹配的问题，他是解释器模式思维的一个运用实例

通过定义正则表达式的语法结构，进而通过表达式定义待匹配字符的集合，然后通过通用的算法来解释执行正则表达式

解释器模式将语法规则抽象出来，设置通用的语法规则，然后使用通用算法执行

使用正则表达式你不在需要自己手动实现算法去实现规则，你只需要按照正则表达式的语法，对你需要匹配的字符集合进行描述即可

有现成的通用算法来帮你实现，而语法相对于算法的实现，自然是简单了很多

再比如浏览器解析html，我们知道html页面是由固定的元素组成的，有他的语法结构

但是一个html页面的标签的个数以及标签内容的组合形式却是千变万化的，但是浏览器可以正确的将他们解析呈现出来

这也是一种解释器的模型

 

在解释器模式中，我们需要将待解决的问题，提取出规则，抽象为一种“语言”

比如加减法运算，规则为：有数值和+- 符号组成的合法序列

加减法运算就不能有乘除，否则就不符合语法

“1+2+3”就是这种语言的一个句子

 

比如遥控汽车的操作按钮，规则为：由前进、后退、左转、右转四种指令组成

遥控汽车就不能有起飞，否则就是不符合语法的

“前进 左转 后退 前进 后退”就是这种语言的一个句子

 

解释器就是要解析出来语句的含义

既然需要将待解决的问题场景提取出规则，那么如何描述规则呢？

 

语法规则描述

对于语法规则的定义，也有一套规范用于描述

backus-naur符号（就是众所周知的bnf或backus-naur form）是描述语言的形式化的数学方法

叫做范式，此后又有扩展的，叫做ebnf

范式基本规则

::= 表示定义，由什么推导出

尖括号 < > 内为必选项；

方括号 [ ] 内为可选项；

大括号 { } 内为可重复0至无数次的项；

圆括号 ( ) 内的所有项为一组，用来控制表达式的优先级

竖线 | 表示或，左右的其中一个

引号内为字符本身，引号外为语法(比如 'for'表示关键字for )

 

有了规则我们就可以对语法进行描述，这是解释器模式的基础工作

比如加减法运算可以这样定义

expression：=value | plus | minus

plus：=expression ‘+’ expression

minus：=expression ‘-’ expression

value：=integer

值的类型为整型数

有加法规则和减法规则

表达式可以是一个值，也可以是一个plus或者minus

而plus和minus又是由表达式结合运算符构成

 

可以看得出来，有递归嵌套的概念

 

抽象语法树

除了使用文法规则来定义规则，还可以通过抽象语法树的图形方式直观的表示语言的构成

文法规则描述了所有的场景，所有条件匹配的都是符合的，不匹配的都是不符合的

符合语法规则的一个“句子”就是语言规则的一个实例

抽象语法树正是对于这个实例的一个描述

一颗抽象语法树对应着语言规则的一个实例

 

关于抽象语法树百科中这样介绍

在计算机科学中，抽象语法树（abstract syntax tree 或者缩写为 ast），或者语法树（syntax tree）

是源代码的抽象语法结构的树状表现形式，这里特指编程语言的源代码。

树上的每个节点都表示源代码中的一种结构。

之所以说语法是「抽象」的，是因为这里的语法并不会表示出真实语法中出现的每个细节。

 

比如 1+2+3+4-5是一个实例

所以说文法规则用于描述语言规则，抽象语法树描述描述语言的一个实例，也就是一个“句子”

结构

抽象表达式角色abstractexpression

声明一个抽象的解释操作，所有的具体表达式操作都需要实现的抽象接口

接口主要是interpret()方法，叫做解释操作

终结符表达式角色terminalexpression

这是一个具体角色，实现与文法中的终结符相关联的解释操作，主要就是interpret()方法

一个句子中的每个终结符都需要此类的一个实例

非终结符表达式noneterminalexpression

这也是一个具体的角色，对文法中的每一条规则r::=r1r2.....rn都需要一个noneterminalexpression 类，注意是类，而不是实例

对每一个r1r2...rn中的符号都持有一个静态类型为abstractexpression的实例变量；

实现解释操作，主要就是interpret()方法

解释操作以递归的方式调用上面所提到的代表r1r2...rn中的各个符号的实例变量

上下文角色context

包含解释器之外的一些全局信息，一般情况下都会需要这个角色

client

构建表示该文法定义的语言中的一个特定的句子的抽象语法树

抽象语法树由noneterminalexpression 和 terminalexpression的实例组装而成

调用解释器的interpret（）方法

终结符和非终结符

通俗的说就是不能单独出现在推导式左边的符号，也就是说终结符不能再进行推导，也就是终结符不能被别人定义

除了终结符就是非终结符

从抽象语法树中可以发现，叶子节点就是终结符 除了叶子节点就是非终结符

角色示例解析

回到刚才的例子

expression：=value | plus | minus

plus：=expression ‘+’ expression

minus：=expression ‘-’ expression

value：=integer 

 

上面是我们给加减法运算定义的语法规则，由四条规则组成

其中规则value：=integer 表示的就是终结符

所以这是一个terminalexpression，每一个数字1+2+3+4-5中的1,2,3,4,5就是terminalexpression的一个实例对象。

 

对于plus和minus规则，他们不是非终结符，属于noneterminalexpression

他们的推导规则分别是通过‘+’和‘-’连接两个expression

也就是角色中说到的“对文法中的每一条规则r::=r1r2.....rn都需要一个noneterminalexpression 类”

也就是说plus表示一条规则，需要一个noneterminalexpression类

minus表示一条规则，需要一个noneterminalexpression类

expression是value 或者 plus 或者 minus，所以不需要noneterminalexpression类了

 

非终结符由终结符推导而来

noneterminalexpression类由terminalexpression组合而成

所以需要：抽象表达式角色abstractexpression

 

在计算过程中，一般需要全局变量保存变量数据

这就是context角色的一般作用

 

 

 

 

以最初的加减法为例，我们的句子就是数字和+ - 符号组成

比如 1+2+3+4-5

 

抽象角色abstractexpression

package interpret;
public abstract class abstractexpression {
public abstract int interpret();
}

终结符表达式角色terminalexpression

内部有一个int类型的value，通过构造方法设置值

package interpret;

public class value extends abstractexpression {

private int value;
value(int value){
this.value = value;
}

@override
public int interpret() {
return value;
}
}

加法noneterminalexpression

package interpret;

public class plus extends abstractexpression {

private abstractexpression left;
private abstractexpression right;

plus(abstractexpression left, abstractexpression right) {
this.left = left;
this.right = right;
}


@override
public int interpret() {
return left.interpret() + right.interpret();
}
}

减法 noneterminalexpression

package interpret;

public class minus extends abstractexpression {

private abstractexpression left;
private abstractexpression right;

minus(abstractexpression left, abstractexpression right) {
this.left = left;
this.right = right;
}

@override
public int interpret() {
return left.interpret() - right.interpret();
}
}

客户端角色

package interpret;

public class client {

public static void main(string[] args) {

abstractexpression expression = new minus(
new plus(new plus(new plus(new value(1), new value(2)), new value(3)), new value(4)),
new value(5));
system.out.println(expression.interpret());
}
}

 

上面的示例中，完成了解释器模式的基本使用

我们通过不断重复的new 对象的形式，嵌套的构造了一颗抽象语法树

只需要执行interpret 方法即可获取最终的结果

 

这就是解释器模式的基本原理

非终结符表达式由终结符表达式组合而来，也就是由非终结符表达式嵌套

嵌套就意味着递归，类似下面的方法，除非是终结符表达式，否则会一直递归

int f(int x) {
if (1 == x) {
return x;
} else {
return x+f(x-1);
}
}

上面的示例中，每次使用时，都需要借助于new 按照抽象语法树的形式创建一堆对象

比如计算1+2与3+4

是不是可以转换为公式的形式呢?

也就是仅仅定义一次表达式，不管是1+2 还是3+4还是6+8 都可以计算？

所以我们考虑增加“变量”这一终结符表达式节点

增加变量类variable  终结符节点

内部包含名称和值，提供值变更的方法

package interpret;
public class variable extends abstractexpression{
    private string name;
    private integer value;
    variable(string name,integer value){
        this.name = name;
        this.value = value;
    }
    public void setvalue(integer value) {
        this.value = value;
    }
    @override
    public int interpret() {
        return value;
    }
}

package interpret;
public class client {
public static void main(string[] args) {
        //定义变量x和y,初始值都为0
        variable variablex = new variable("x", 0);
        variable variabley = new variable("y", 0);
        //计算公式为: x+y+x-1
        abstractexpression expression2 = new minus(new plus(new plus(variablex, variabley), variablex),
        new value(1));
        variablex.setvalue(1);
        variabley.setvalue(3);
        system.out.println(expression2.interpret());
        variablex.setvalue(5);
        variabley.setvalue(6);
        system.out.println(expression2.interpret());
    }
}

 

有了变量类 variable，就可以借助于变量进行公式的计算

而且，很显然，公式只需要设置一次，而且可以动态设置

通过改变变量的值就可以达到套用公式的目的

 

一般的做法并不是直接将值设置在变量类里面，变量只有一个名字，将节点所有的值设置到context类中

context的作用可以通过示例代码感受下

 

代码示例

完整示例如下

abstractexpression抽象表达式角色 接受参数context，如有需要可以从全局空间中获取数据

package interpret.refactor;

public abstract class abstractexpression {
public abstract int interpret(context ctx);
}

数值类value 终结符表达式节点

内部还有int value

他不需要从全局空间获取数据，所以interpret方法中的context用不到

增加了tostring方法，用于呈现 数值类的tostring方法直接回显数值的值

package interpret.refactor;

public class value extends abstractexpression {

private int value;

value(int value) {
this.value = value;
}

@override
public int interpret(context ctx) {
return value;
}

@override
public string tostring() {
return new integer(value).tostring();
}
}

变量类variable  终结符表达式

变量类拥有名字，使用内部的string name

变量类的真值保存在context中，context是借助于hashmap存储的

context定义的类型为map<variable, integer>

所以，我们重写了equals以及hashcode方法

variable的值存储在context这一全局环境中，值也是从中获取

package interpret.refactor;

public class variable extends abstractexpression {

private string name;
variable(string name) {
this.name = name;
}


@override
public int interpret(context ctx) {
return ctx.getvalue(this);
}

@override
public boolean equals(object obj) {
if (obj != null && obj instanceof variable) {
return this.name.equals(
((variable) obj).name);
}
return false;
}

@override
public int hashcode() {
return this.tostring().hashcode();
}

@override
public string tostring() {
return name;
}
}

加法跟原来差不多，interpret接受参数context，如有需要从context中读取数据

package interpret.refactor;

public class plus extends abstractexpression {

private abstractexpression left;

private abstractexpression right;

plus(abstractexpression left, abstractexpression right) {
this.left = left;
this.right = right;
}

@override
public int interpret(context ctx) {
return left.interpret(ctx) + right.interpret(ctx);
}

@override
public string tostring() {
return "(" + left.tostring() + " + " + right.tostring() + ")";
}
}

package interpret.refactor;

public class minus extends abstractexpression {

private abstractexpression left;

private abstractexpression right;

minus(abstractexpression left, abstractexpression right) {
this.left = left;
this.right = right;
}

@override
public int interpret(context ctx) {
return left.interpret(ctx) - right.interpret(ctx);
}

@override
public string tostring() {
return "(" + left.tostring() + " - " + right.tostring() + ")";
}
}

环境类context

内部包含一个 private map<variable, integer> map，用于存储变量数据信息

key为variable 提供设置和获取方法

package interpret.refactor;

import java.util.hashmap;

import java.util.map;

public class context {

private map<variable, integer> map = new hashmap<variable, integer>();

public void assign(variable var, integer value) {
map.put(var, new integer(value));
}

public int getvalue(variable var) {
integer value = map.get(var);
return value;
}
}

package interpret.refactor;


public class client {

public static void main(string[] args) {

context ctx = new context();

variable a = new variable("a");
variable b = new variable("b");
variable c = new variable("c");
variable d = new variable("d");
variable e = new variable("e");
value v = new value(1);

ctx.assign(a, 1);
ctx.assign(b, 2);
ctx.assign(c, 3);
ctx.assign(d, 4);
ctx.assign(e, 5);

abstractexpression expression = new minus(new plus(new plus(new plus(a, b), c), d), e);

system.out.println(expression + "= " + expression.interpret(ctx));
}
}

 

上述客户端测试代码中，我们定义了a，b，c，d，e 五个变量

通过context赋值，初始化为1，2，3，4，5

然后构造了公式，计算结果

后续只需要设置变量的值即可套用这一公式

如果需要变动公式就修改表达式，如果设置变量就直接改变值即可

这种模式就实现了真正的灵活*，只要是加减法运算，必然能够运算

不再需要固定的参数列表或者函数式接口，非常灵活 

 

另外对于抽象语法树的生成，你也可以转变形式

比如下面我写了一个简单的方法用于将字符串转换为抽象语法树的expression

/**
   * 解析字符串,构造抽象语法树 方法只是为了理解：解释器模式 方法默认输入为合法的字符串，没有考虑算法优化、效率或者不合法字符串的异常情况
   *
   * @param sinput 合法的加减法字符串 比如 1+2+3
   */
  public static abstractexpression getast(string sinput) {
    //接收字符串参数形如 "1+2-3"
    //将字符串解析到list valueandsymbollist中存放
    list<string> valueandsymbollist = new arraylist<>();
    //先按照 加法符号 + 拆分为数组,以每个元素为单位使用 +连接起来存入list
    //如果以+ 分割内部还有减法符号 - 内部以减法符号- 分割
    //最终的元素的形式为 1,+,2,-,3
    string[] splitbyplus = sinput.split("\\+");
    for (int i = 0; i < splitbyplus.length; i++) {
      if (splitbyplus[i].indexof("-") < 0) {
        valueandsymbollist.add(splitbyplus[i]);
      } else {
        string[] splitbyminus = splitbyplus[i].split("\\-");
        for (int j = 0; j < splitbyminus.length; j++) {
          valueandsymbollist.add(splitbyminus[j]);
          if (j != splitbyminus.length - 1) {
            valueandsymbollist.add("-");
          }
        }
      }
      if (i != splitbyplus.length - 1) {
        valueandsymbollist.add("+");
      }
    }
    //经过前面处理元素的形式为 1,+,2,-,3
    //转换为抽象语法树的形式
    abstractexpression leftexpression = null;
    abstractexpression rightexpression = null;
    int k = 0;
    while (k < valueandsymbollist.size()) {
      if (!valueandsymbollist.get(k).equals("+") && !valueandsymbollist.get(k).equals("-")) {
        rightexpression = new value(integer.parseint(valueandsymbollist.get(k)));
        if (leftexpression == null) {
          leftexpression = rightexpression;
        }
      }
      k++;
      if (k < valueandsymbollist.size()) {
        rightexpression = new value(integer.parseint(valueandsymbollist.get(k + 1)));
        if (valueandsymbollist.get(k).equals("+")) {
          leftexpression = new plus(leftexpression, rightexpression);
        } else if (valueandsymbollist.get(k).equals("-")) {
          leftexpression = new minus(leftexpression, rightexpression);
        }
        k++;
      }
    }
    return leftexpression;
  }

 

通过上面的这个方法,我们就可以直接解析字符串了

总结

解释器模式是用于解析一种“语言”，对于使用频率较高的，模式、公式化的场景，可以考虑使用解释器模式。

比如正则表达式，将“匹配”这一语法，定义为一种语言

浏览器对于html的解析，将html文档的结构定义为一种语言

我们上面的例子，将加减运算规则定义为一种语言

所以，使用解释器模式要注意“高频”“公式”“格式”这几个关键词

 

解释器模式将语法规则抽象的表述为类

解释器模式为自定义语言的设计和实现提供了一种解决方案，它用于定义一组文法规则并通过这组文法规则来解释语言中的句子。

 

解释器模式非常容易扩展，如果增加新的运算符，比如乘除，只需要增加新的非终结符表达式即可

改变和扩展语言的规则非常灵活

非终结符表达式是由终结符表达式构成，基本上需要借助于嵌套，递归，所以代码本身一般比较简单

像我们上面那样， plus和minus 的代码差异很小

 

如果语言比较复杂，显然，就会需要定义大量的类来处理

解释器模式中大量的使用了递归嵌套，所以说它的性能是很有问题的，如果你的系统是性能敏感的，你就更要慎重的使用

 

据说解释器模式在实际的系统开发中使用得非常少，另外也有一些开源工具

expression4j、mesp（math expression string parser）、jep

所以不要自己实现

 

另外还需要注意的是，从我们上面的示例代码中可以看得出来

解释器模式的重点在于abstractexpression、terminalexpression、noneterminalexpression的提取抽象

也就是对于文法规则的映射转换

而至于如何转换为抽象语法树，这是客户端的责任

我们的示例中可以通过new不断地嵌套创建expression对象

也可以通过方法解析抽象语法树，都可以根据实际场景处理

简言之，解释器模式不关注抽象语法树的创建，仅仅关注解析处理

 

所以个人看法：

但凡你的问题场景可以抽象为一种语言，也就是有规则、公式，有套路就可以使用解释器模式

不过如果有替代方法，能不用就不用

如果非要用，你也不要自己写

原文地址:解释器模式 interpreter 行为型 设计模式（十九）