解释器模式（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语言语法的表达式和语句。说的就是这个意思
范式基本规则
::= 表示定义，由什么推导出
尖括号 < > 内为必选项；
方括号 [ ] 内为可选项；
大括号 { } 内为可重复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对象
也可以通过方法解析抽象语法树，都可以根据实际场景处理
简言之，解释器模式不关注抽象语法树的创建，仅仅关注解析处理
所以个人看法：
但凡你的问题场景可以抽象为一种语言，也就是有规则、公式，有套路就可以使用解释器模式
不过如果有替代方法，能不用就不用
如果非要用，你也不要自己写
转载务必注明出处：程序员潇然，疯狂的字节X，https://crazybytex.com/thread-117-1-1.html
计算机科学
7926 人阅读
|
0 人回复
苏公网安备 32011502011619号