Java设计模式-解释器模式
解释器(Interpreter)模式，在23种设计模式中属于类行为型模式。
解释器模式：定义一个语言的文法，并建立一个解释器用于解释该文法表示的句子。
引言
在平常开发中解释器模式是一种使用频率低难度相对较大的设计模式，它用于描述如何使用面向对象的方式来构成一个简单的语言解释器。在某些场景下，为了更好地描述某些特定问题，有时会创建一门新的语言，这种语言拥有自己的表达式和结构，即文法规则，然后使用该语言抒写的指令组成一个个指令文件，最后通过解释器解析成特定的代码运行。例如，Android系统启动过程中会加载一个init.rc的配置文件，该文件其实是一个语法文件，并不是一个程序，它是由一种被称为Android初始化脚本语言写成的文件。
在编译原理中，一个算术表达式通过词法分析器形成词法单元，而后这些词法单元再通过词法分析器构建语法分析树，最终形成一颗抽象的语法分析树。这里的词法分析器和语法分析器都可以看做是解释器。
平常所接触的编程语言一般分为两种类型：编译型语言和解释型语言。编译型语言，首先将源代码编译生成机器语言，再由机器运行机器码，进行执行，比较典型的编译型语言就是C与C++。解释型语言，就是有一个解释器，读取一条命令，进行语法分析，然后运行，接着读取下一行，再运行，最具代表性解释器语言应该就是JavaScript了。Java语言属于编译解释型语言，编写的Java类文件会先使用编译器编译成class字节码文件，然后有JVM虚拟机解释执行，所以Java成为编译解释型语言。
接下来我们来看一下如何使用文法描述一门语言，所谓文法只是在形式上对句子结构的描述与定义，并不会涉及语义层面。
这里我们就以一个简单的算术表达式来看下文法的定义规则。
expression ::= value | operation operation ::= expression '+' expression | expression '-' expression value ::= an integer //一个整数值
符号“::=”表示“定义为”的意思，或者说“由...组成”，其左边的语言单位由右边进行说明和定义，语言单位分为终结符表达式和非终结符表达式。如在上述示例中，operation是非终结表达式，意味着它还可以再进一步分解，可以分解为终结表达式或者非终结表达式，而value是终结表达式，不可以再进行分解。
更多关于计算机文法的内容，可以参看网上其它文章，这里就不再继续扩展开了，本文只需要了解一下文法的基本表示即可。
适用性
- 当有一个语言需要解释执行 , 并且可以将该语言中的句子表示为一个抽象语法树时，可使用解释器模式。
- 一些重复出现的问题可以用一种简单的语言来进行表达。
- 一个语言的文法较为简单，执行效率不是关键问题。【注：高效的解释器通常不是通过直接解释抽象语法树来实现的，而是需要将它们转换成其他形式，使用解释器模式的执行效率并不高。】
游戏指令示例
该示例用于模拟一个游戏指令执行器，假设游戏中指令的文法表示如下：
expression ::= direction action distance | composite //表达式 composite ::= expression 'and' expression //复合表达式 direction ::= 'up' | 'down' | 'left' | 'right' //移动方向 action ::= 'move' | 'run' //移动方式 distance ::= an integer //移动距离
如果输入的指令为：
up move 5 and down run 10 and left move 5
我们希望经过解释执行后变为如下语句：
向上移动5再向下快速移动10再向左移动5
// 抽象表达式节点
public interface Node {
String interprete();
}
// 方向节点：终结符表达式
public class DirectionNode implements Node {
private String direction;
public DirectionNode(String direction) {
this.direction = direction;
}
@Override
public String interprete() {
if ("up".equalsIgnoreCase(direction)) {
return "向上";
} else if ("down".equalsIgnoreCase(direction)) {
return "向下";
} else if ("left".equalsIgnoreCase(direction)) {
return "向左";
} else if ("right".equalsIgnoreCase(direction)) {
return "向右";
}
return "无效指令";
}
}
// And节点：非终结符表达式
public class AndNode implements Node {
private Node left;
private Node right;
public AndNode(Node left, Node right) {
this.left = left;
this.right = right;
}
@Override
public String interprete() {
return left.interprete() + "再" + right.interprete();
}
}
// 句子节点：非终结符表达式
public class SentenceNode implements Node {
private Node direction;
private Node action;
private Node distance;
public SentenceNode(Node direction, Node action, Node distance) {
this.direction = direction;
this.action = action;
this.distance = distance;
}
@Override
public String interprete() {
return direction.interprete() + action.interprete() + distance.interprete();
}
}
// 指令执行器
public class InstructionHandler {
private Node node;
public void handle(String instruction) {
Node left, right;
Node direction, action, distance;
Stack stack = new Stack<>();
String[] words = instruction.split(" ");
for (int i = 0; i < words.length; i++) {
if ("and".equalsIgnoreCase(words[i])) {
/**
* 本实例采用栈的方式来处理指令，如果遇到“and”，
* 则将其后的三个单词作为三个终结符表达式连成一个简单句子SentenceNode作为“and”的右表达式，
* 而将从栈顶弹出的表达式作为“and”的左表达式，最后将新的“and”表达式压入栈中。
*/
left = stack.pop(); // 弹出栈顶表达式作为左表达式
String word1 = words[++i];
direction = new DirectionNode(word1);
String word2 = words[++i];
action = new ActionNode(word2);
String word3 = words[++i];
distance = new DistanceNode(word3);
right = new SentenceNode(direction, action, distance); // 右表达式
stack.push(new AndNode(left, right)); // 将新表达式压入栈中
} else {
String word1 = words[i];
direction = new DirectionNode(word1);
String word2 = words[++i];
action = new ActionNode(word2);
String word3 = words[++i];
distance = new DistanceNode(word3);
left = new SentenceNode(direction, action, distance);
stack.push(left); // 将新表达式压入栈中
}
}
this.node = stack.pop();
}
public String output() {
return this.node.interprete();
}
}
// 测试指令
public static void main(String[] args) {
String instruction = "up move 5 and down run 10 and left move 5";
InstructionHandler handler = new InstructionHandler();
handler.handle(instruction);
String outString;
outString = handler.output();
System.out.println(outString);
}
四则运算示例
四则运算解析的难点是求值顺序的问题，因为这里面有乘除、括号等运算符，这些运算符优先级比较高，会导致表达式的执行顺序与表达式的表示顺序有差异。为了避免解析过程中求值顺序问题，在本示例中排除了括号以及乘除运算符。当然了，如果想要进一步做一个可以表示加减乘除以及括号的四则运算解释器，一般可以借助两种方式解析表达式：逆波兰式或者二叉树，在本示例后面会贴出来一个借助逆波兰式求值的解释器执行结果。
// 抽象表达式
public interface Expression {
int interpret();
}
//终结符表达式：数值类型
public class NumberExpression implements Expression {
private String value;
public NumberExpression(String value) {
this.value = value;
}
@Override
public int interpret() {
return Integer.parseInt(this.value);
}
}
// 非终结表达式抽象类
public abstract class AbstractExpression implements Expression {
protected Expression left;
protected Expression right;
public AbstractExpression(Expression left, Expression right) {
this.left = left;
this.right = right;
}
}
// 非终结符表达式：+类型
public class PlusExpression extends AbstractExpression {
public PlusExpression(Expression left, Expression right) {
super(left, right);
}
@Override
public int interpret() {
return left.interpret()+right.interpret();
}
}
// 表达式解析器
public class ExpressionParser {
private Expression expression;
public ExpressionParser(String expression) {
this.parse(expression);
}
private void parse(String expression) {
Stack stack = new Stack<>();
String[] array = formatExpression(expression);
for (int i = 0; i < array.length; i++) {
if (isOperator(array[i])) {
Expression left = stack.pop();
Expression right = new NumberExpression(array[++i]);
stack.push(getMathExpression(left, right, array[i - 1]));
} else {
stack.add(new NumberExpression(array[i]));
}
}
this.expression = stack.pop();
}
public int getExpressionValue() {
return this.expression.interpret();
}
// 根据symbol获取是哪种非终结表达式
private Expression getMathExpression(Expression left, Expression right, String symbol) {
Expression expression = null;
if ("+".equals(symbol)) {
expression = new PlusExpression(left, right);
} else {
expression = new MinusExpression(left, right);
}
return expression;
}
private boolean isOperator(String src) {
return "+".equals(src) || "-".equals(src);
}
// 解析表达式"23+4+65"为数组形式字符串["23","+","4","+","65"]
private String[] formatExpression(String expression) {
StringBuffer buffer = new StringBuffer();
char[] array = expression.toCharArray();
int index = 0;
int count = array.length;
while (index < count) {
if (Character.isWhitespace(array[index])) {
index++;
} else if (Character.isDigit(array[index])) {
while (index < count && Character.isDigit(array[index])) {
buffer.append(array[index]);
index++;
}
buffer.append(" ");
} else {
buffer.append(array[index] + " ");
index++;
}
}
return buffer.toString().split(" ");
}
}
public static void main(String[] args) {
String expression="32+15+8+78-25-9";
ExpressionParser parser=new ExpressionParser(expression);
int value=parser.getExpressionValue();
System.out.println(value); // 99
}
最后我们看一下借助于逆波兰式的代码测试示例。
public static void main(String[] args) {
//String expression="32+15+8+78-25-9+1";//100
//String expression="10+30-20";//20
//String expression="100 * 2 + 400 * 2 + 66";//1066
//String expression="100 * 2 + 400 * 4 / 2+ 66";//1066
//String expression="10*(1+2)+3";//33
//String expression="(1+2)*(2+3)+3";//18
String expression="10*(1+2+6)*(2+3+5)+3";//903
ExpressionParser parser=new ExpressionParser(expression);
int value=parser.getExpressionValue();
System.out.println("计算结果: "+value);
}
代码的执行输出情况如下：
逆波兰式: 10 1 2 + 6 + * 2 3 + 5 + * 3 + 计算: 1+2 计算: 3+6 计算: 10*9 计算: 2+3 计算: 5+5 计算: 90*10 计算: 900+3 计算结果: 903
模式分析
解释器模式类图如下：
- AbstractExpression抽象表达式：它声明了抽象的解释操作，是终结符表达式和非终结符表达式的公共父类。
- TerminalExpression终结符表达式：它实现了文法中与终结符有关的解释操作，在句子中每一个终结符都对应一个该类的实例。
- NonterminalExpression非终结符表达式：它实现了文法中与非终结符有关的解释操作，由于非终结表达式中可以包含终结表达式，也可以包含非终结符表达式，因此其的解释一般通过递归方式进行。
- Context上下文：用于存储解释器之外的全局信息，一般临时存储用于解释的句子。
模式优点
将每一个语法表示成一个类，因此可以方便地实现语言。
由于语法是由许多类组成的，所以也非常容易改变和扩展文法。
增加新的解释表达式较为方便。如果用户需要增加新的解释表达式只需要对应增加一个新的终结符表达式或非终结符表达式类，原有表达式类代码无须修改，符合“开闭原则”。
模式缺点
复杂的文法难以维护。在解释器模式中每一条文法至少需要一个类，因此如果一个语言包含太多的文法规则，那么类的数量将会急剧增加，导致系统难以管理和维护。
执行效率低。由于解释器使用了大量的循环和递归调用，循环效率还好，主要是递归，虽然代码看上去简洁清晰许多，但是可能导致方法调用层次较深，因此需要增加额外的堆栈处理，执行效率会受到很大的影响。
与其它模式关系
一般非终结符表达式类会结合组合模式定义，非终结符表达式本身就是一个抽象表达式，而它又由非终结符表达式或者终结符表达式组合而成，所以这里相当于使用了组合模式。
可以使用FlyWeight共享终结表达式。在一些文法中，一个句子中可能出现多个终结符，此时最好可以共享该终结符的属性。
解释操作不一定要在表达式类中执行，如果经常要创建一种新的解释器, 那么使用Visitor模式将解释放入一个独立的 “访问者”对象更好一些。
结束语
解释器模式在实际开发中使用场景的非常少，特别是应用层软件开发，几乎没有什么应用软件需要专门开发一套简单的语言，通过解释该门语言设计软件架构。
虽然解释器模式应用场景比较少，但是在某些开发场景中确实需要解析数学表达式，这时候不一定自己去造轮子，因为已经有许多相应的库支持解析表达式，如Expression4J、MESP（Math Expression String Parser）、Jep等开源的解析工具包。第三方工具包功能也都异常强大，而且非常容易使用，效率也还不错，实现大多数的数学运算完全没有问题。
如果有接触过Java服务端开发，相信都接触过EL表达式，其实不管是JSP的EL表达式，还是Spring的EL表达式，它们的实现机制也都是依据解释器模式。如下是一个简单的Spring EL表达式的简单实用示例。
ExpressionParser parser = new SpelExpressionParser();
Expression expression = parser.parseExpression("25 * 2 + 100 * 3 + 50");
int result = (Integer) expression.getValue();
System.out.println(result);// 400
通过debug方式可以大致了解EL的实现情况，Spring在解析数学表达式时并不是借助逆波兰式的方式解析的，而是通过解析成一个二叉语法树进行实现的。
