请选择 进入手机版 | 继续访问电脑版

[设计模式] 解释器模式 Interpreter 行为型 设计模式(十九)

计算机科学 计算机科学 2536 人阅读 | 0 人回复

解释器模式(Interpreter)

image.png

考虑上图中计算器的例子

设计可以用于计算加减运算(简单起见,省略乘除),你会怎么做?

你可能会定义一个工具类,工具类中有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);
}

image.png

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

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

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

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

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

这就是解释器模式的思维

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

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

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

范式基本规则

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

尖括号 < > 内为必选项;

方括号 [ ] 内为可选项;

大括号 { } 内为可重复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是一个实例

image.png

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

结构

image.png

抽象表达式角色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角色的一般作用

image.png

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

比如 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());
    }
}

image.png

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

我们通过不断重复的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());
    }
}

image.png

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

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

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

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

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

代码示例

完整示例如下

image.png

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

image.png

上述客户端测试代码中,我们定义了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;
  }

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

image.png

总结

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

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

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

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

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

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

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

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

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

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

像我们上面那样, Plus和Minus 的代码差异很小

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

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

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

Expression4J、MESP(Math Expression String Parser)、Jep

所以不要自己实现

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

解释器模式的重点在于AbstractExpression、TerminalExpression、NoneTerminalExpression的提取抽象

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

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

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

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

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

所以个人看法:

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

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

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

common_log.png 转载务必注明出处:程序员潇然,疯狂的字节X,https://crazybytex.com/thread-117-1-1.html

关注下面的标签,发现更多相似文章

文章被以下专栏收录:

    黄小斜学Java

    疯狂的字节X

  • 目前专注于分享Java领域干货,公众号同步更新。原创以及收集整理,把最好的留下。
    包括但不限于JVM、计算机科学、算法、数据库、分布式、Spring全家桶、微服务、高并发、Docker容器、ELK、大数据等相关知识,一起进步,一起成长。
热门推荐
海康摄像头接入 wvp-GB28181-pro平台测试验
[md]### 简介 开箱即用的28181协议视频平台 `https://github.c
[若依]微服务springcloud版新建增添加一个
[md]若依框架是一个比较出名的后台管理系统,有多个不同版本。
[CXX1300] CMake '3.18.1' was not
[md][CXX1300] CMake '3.18.1' was not found in SDK, PATH, or