解释器模式 Interpreter 行为型 设计模式(十九)
程序员文章站
2022-07-06 10:17:11
解释器模式是一种不很常用的模式,但是比如正则表达式就是一种解释器模式的思维,所以尽管实际编码中不常用,理解解释器模式的含义很重要,本文对解释器模式进行了简单的介绍,并且给出了Java代码示例,介绍了解释器模式的意图结构。 ......
解释器模式(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对象
也可以通过方法解析抽象语法树,都可以根据实际场景处理
简言之,解释器模式不关注抽象语法树的创建,仅仅关注解析处理
所以个人看法:
但凡你的问题场景可以抽象为一种语言,也就是有规则、公式,有套路就可以使用解释器模式
不过如果有替代方法,能不用就不用
如果非要用,你也不要自己写