行为型：设计模式之解释器模式（二十二）

 虽然目前计算机编程语言有好几百种，但有时候我们还是希望能用一些简单的语言来实现一些特定的操作，我们只要向计算机输入一个句子或文件，它就能够按照预先定义的文法规则来对句子或文件进行解释，从而实现相应的功能。例如提供一个简单的加法/减法解释器，只要输入一个加法/减法表达式，它就能够计算出表达式结果，如图1所示，当输入字符串表达式为“1 + 2 + 3 – 4 + 1”时，将输出计算结果为3。

图1  加法/减法解释器示意图

C++、Java和C#等语言无法直接解释类似“1+ 2 + 3 – 4 + 1”这样的字符串（如果直接作为数值表达式时可以解释），我们必须自己定义一套文法规则来实现对这些语句的解释，即设计一个自定义语言。在实际开发中，这些简单的自定义语言可以基于现有的编程语言来设计，如果所基于的编程语言是面向对象语言，此时可以使用解释器模式来实现自定义语言。

1 机器人控制程序

       Sunny软件公司开发人员决定自定义一个简单的语言来解释机器人控制指令，根据上述需求描述，用形式化语言来表示该简单语言的文法规则如下：

direction、action和distance，它们是语言的最小组成单位，不能再进行拆分；另一类为非终结符（也称为非终结符表达式），例如expression和composite，它们都是一个完整的句子，包含一系列终结符或非终结符。

       我们根据上述规则定义出的语言可以构成很多语句，计算机程序将根据这些语句进行某种操作。为了实现对语句的解释，可以使用解释器模式，在解释器模式中每一个文法规则都将对应一个类，扩展、改变文法以及增加新的文法规则都很方便，下面就让我们正式进入解释器模式的学习，看看使用解释器模式如何来实现对机器人控制指令的处理。

2 文法规则和抽象语法树

       解释器模式描述了如何为简单的语言定义一个文法，如何在该语言中表示一个句子，以及如何解释这些句子。在正式分析解释器模式结构之前，我们先来学习如何表示一个语言的文法规则以及如何构造一棵抽象语法树。

/减法解释器中，每一个输入表达式，例如“1 + 2 + 3 – 4 + 1”，都包含了三个语言单位，可以使用如下文法规则来定义：

value和operation是后面两个语言单位的定义，每一条语句所定义的字符串如operation和value称为语言构造成分或语言单位，符号“::=”表示“定义为”的意思，其左边的语言单位通过右边来进行说明和定义，语言单位对应终结符表达式和非终结符表达式。如本规则中的operation是非终结符表达式，它的组成元素仍然可以是表达式，可以进一步分解，而value是终结符表达式，它的组成元素是最基本的语言单位，不能再进行分解。

在文法规则定义中可以使用一些符号来表示不同的含义，如使用“|”表示或，使用“{”和“}”表示组合，使用“*”表示出现0次或多次等，其中使用频率最高的符号是表示“或”关系的“|”，如文法规则“boolValue ::= 0 | 1”表示终结符表达式boolValue的取值可以为0或者1。

       除了使用文法规则来定义一个语言，在解释器模式中还可以通过一种称之为抽象语法树(Abstract Syntax Tree, AST)的图形方式来直观地表示语言的构成，每一棵抽象语法树对应一个语言实例，如加法/减法表达式语言中的语句“1+ 2 + 3 – 4 + 1”，可以通过如图2所示抽象语法树来表示：

图22-2  抽象语法树示意图

value和非终结符表达式operation组成复杂的语句，每个文法规则的语言实例都可以表示为一个抽象语法树，即每一条具体的语句都可以用类似图22-2所示的抽象语法树来表示，在图中终结符表达式类的实例作为树的叶子节点，而非终结符表达式类的实例作为非叶子节点，它们可以将终结符表达式类的实例以及包含终结符和非终结符实例的子表达式作为其子节点。抽象语法树描述了如何构成一个复杂的句子，通过对抽象语法树的分析，可以识别出语言中的终结符类和非终结符类。

3 解释器模式概述

       解释器模式是一种使用频率相对较低但学习难度较大的设计模式，它用于描述如何使用面向对象语言构成一个简单的语言解释器。在某些情况下，为了更好地描述某一些特定类型的问题，我们可以创建一种新的语言，这种语言拥有自己的表达式和结构，即文法规则，这些问题的实例将对应为该语言中的句子。此时，可以使用解释器模式来设计这种新的语言。对解释器模式的学习能够加深我们对面向对象思想的理解，并且掌握编程语言中文法规则的解释过程。

       解释器模式定义如下：

3所示：

图3  解释器模式结构图

       在解释器模式结构图中包含如下几个角色：

 AbstractExpression（抽象表达式）：在抽象表达式中声明了抽象的解释操作，它是所有终结符表达式和非终结符表达式的公共父类。

 TerminalExpression（终结符表达式）：终结符表达式是抽象表达式的子类，它实现了与文法中的终结符相关联的解释操作，在句子中的每一个终结符都是该类的一个实例。通常在一个解释器模式中只有少数几个终结符表达式类，它们的实例可以通过非终结符表达式组成较为复杂的句子。

 NonterminalExpression（非终结符表达式）：非终结符表达式也是抽象表达式的子类，它实现了文法中非终结符的解释操作，由于在非终结符表达式中可以包含终结符表达式，也可以继续包含非终结符表达式，因此其解释操作一般通过递归的方式来完成。

 Context（环境类）：环境类又称为上下文类，它用于存储解释器之外的一些全局信息，通常它临时存储了需要解释的语句。

       在解释器模式中，每一种终结符和非终结符都有一个具体类与之对应，正因为使用类来表示每一条文法规则，所以系统将具有较好的灵活性和可扩展性。对于所有的终结符和非终结符，我们首先需要抽象出一个公共父类，即抽象表达式类，其典型代码如下所示：

[java]  ​​view plain​​ ​​copy​​ ​​print​​ ​​?​​

1. abstract class AbstractExpression {  
2. public  abstract void interpret(Context ctx);  
3. }  

       终结符表达式和非终结符表达式类都是抽象表达式类的子类，对于终结符表达式，其代码很简单，主要是对终结符元素的处理，其典型代码如下所示：

[java]  ​​view plain​​ ​​copy​​ ​​print​​ ​​?​​

1. class TerminalExpression extends  AbstractExpression {  
2. public  void interpret(Context ctx) {  
3. //终结符表达式的解释操作  
4.        }  
5. }  

       对于非终结符表达式，其代码相对比较复杂，因为可以通过非终结符将表达式组合成更加复杂的结构，对于包含两个操作元素的非终结符表达式类，其典型代码如下：

[java]  ​​view plain​​ ​​copy​​ ​​print​​ ​​?​​

1. class NonterminalExpression extends  AbstractExpression {  
2. private  AbstractExpression left;  
3. private  AbstractExpression right;  
4.         
5. public  NonterminalExpression(AbstractExpression left,AbstractExpression right) {  
6. this.left=left;  
7. this.right=right;  
8.        }  
9.         
10. public void interpret(Context ctx) {  
11. //递归调用每一个组成部分的interpret()方法  
12. //在递归调用时指定组成部分的连接方式，即非终结符的功能  
13.        }       
14. }  

Context，用于存储一些全局信息，通常在Context中包含了一个HashMap或ArrayList等类型的集合对象（也可以直接由HashMap等集合类充当环境类），存储一系列公共信息，如变量名与值的映射关系（key/value）等，用于在进行具体的解释操作时从中获取相关信息。其典型代码片段如下：

[java]  ​​view plain​​ ​​copy​​ ​​print​​ ​​?​​

1. class Context {  
2. private HashMap map = new HashMap();  
3. public void assign(String key, String value) {  
4. //往环境类中设值  
5.      }  
6. public String  lookup(String key) {  
7. //获取存储在环境类中的值  
8.      }  
9. }  

       当系统无须提供全局公共信息时可以省略环境类，可根据实际情况决定是否需要环境类。

4 完整解决方案

为了能够解释机器人控制指令，Sunny软件公司开发人员使用解释器模式来设计和实现机器人控制程序。针对五条文法规则，分别提供五个类来实现，其中终结符表达式direction、action和distance对应DirectionNode类、ActionNode类和DistanceNode类，非终结符表达式expression和composite对应SentenceNode类和AndNode类。

down run 10 and left move 20”对应的抽象语法树如图4所示：

图4   机器人控制程序抽象语法树实例

5所示：

图22-5   机器人控制程序结构图

22-5中，AbstractNode充当抽象表达式角色，DirectionNode、ActionNode和DistanceNode充当终结符表达式角色，AndNode和SentenceNode充当非终结符表达式角色。完整代码如下所示：

[java]  ​​view plain​​ ​​copy​​

1. //注：本实例对机器人控制指令的输出结果进行模拟，将英文指令翻译为中文指令，实际情况是调用不同的控制程序进行机器人的控制，包括对移动方向、方式和距离的控制等  
2. import java.util.*;  
3.   
4. //抽象表达式  
5. abstract class AbstractNode {  
6. public abstract String interpret();  
7. }  
8.   
9. //And解释：非终结符表达式  
10. class AndNode extends AbstractNode {  
11. private AbstractNode left; //And的左表达式  
12. private AbstractNode right; //And的右表达式  
13.   
14. public AndNode(AbstractNode left, AbstractNode right) {  
15. this.left = left;  
16. this.right = right;  
17.     }  
18.       
19. //And表达式解释操作  
20. public String interpret() {  
21. return left.interpret() + "再" + right.interpret();  
22.     }  
23. }  
24.   
25. //简单句子解释：非终结符表达式  
26. class SentenceNode extends AbstractNode {  
27. private AbstractNode direction;  
28. private AbstractNode action;  
29. private AbstractNode distance;  
30.   
31. public SentenceNode(AbstractNode direction,AbstractNode action,AbstractNode distance) {  
32. this.direction = direction;  
33. this.action = action;  
34. this.distance = distance;  
35.     }  
36.       
37. //简单句子的解释操作  
38. public String interpret() {  
39. return direction.interpret() + action.interpret() + distance.interpret();  
40.     }     
41. }  
42.   
43. //方向解释：终结符表达式  
44. class DirectionNode extends AbstractNode {  
45. private String direction;  
46.       
47. public DirectionNode(String direction) {  
48. this.direction = direction;  
49.     }  
50.       
51. //方向表达式的解释操作  
52. public String interpret() {  
53. if (direction.equalsIgnoreCase("up")) {  
54. return "向上";  
55.         }  
56. else if (direction.equalsIgnoreCase("down")) {  
57. return "向下";  
58.         }  
59. else if (direction.equalsIgnoreCase("left")) {  
60. return "向左";  
61.         }  
62. else if (direction.equalsIgnoreCase("right")) {  
63. return "向右";  
64.         }  
65. else {  
66. return "无效指令";  
67.         }  
68.     }  
69. }  
70.   
71. //动作解释：终结符表达式  
72. class ActionNode extends AbstractNode {  
73. private String action;  
74.       
75. public ActionNode(String action) {  
76. this.action = action;  
77.     }  
78.       
79. //动作（移动方式）表达式的解释操作  
80. public String interpret() {  
81. if (action.equalsIgnoreCase("move")) {  
82. return "移动";  
83.         }  
84. else if (action.equalsIgnoreCase("run")) {  
85. return "快速移动";  
86.         }  
87. else {  
88. return "无效指令";  
89.         }  
90.     }  
91. }  
92.   
93. //距离解释：终结符表达式  
94. class DistanceNode extends AbstractNode {  
95. private String distance;  
96.       
97. public DistanceNode(String distance) {  
98. this.distance = distance;  
99.     }  
100.       
101. //距离表达式的解释操作  
102. public String interpret() {  
103. return this.distance;  
104.     }     
105. }  
106.   
107. //指令处理类：工具类  
108. class InstructionHandler {  
109. private String instruction;  
110. private AbstractNode node;  
111.       
112. public void handle(String instruction) {  
113. null, right = null;  
114. null, action = null, distance = null;  
115. new Stack(); //声明一个栈对象用于存储抽象语法树  
116. " "); //以空格分隔指令字符串  
117. for (int i = 0; i < words.length; i++) {  
118. //本实例采用栈的方式来处理指令，如果遇到“and”，则将其后的三个单词作为三个终结符表达式连成一个简单句子SentenceNode作为“and”的右表达式，而将从栈顶弹出的表达式作为“and”的左表达式，最后将新的“and”表达式压入栈中。                   if (words[i].equalsIgnoreCase("and")) {  
119. //弹出栈顶表达式作为左表达式  
120.                 String word1= words[++i];  
121. new DirectionNode(word1);  
122.                 String word2 = words[++i];  
123. new ActionNode(word2);  
124.                 String word3 = words[++i];  
125. new DistanceNode(word3);  
126. new SentenceNode(direction,action,distance); //右表达式  
127. new AndNode(left,right)); //将新表达式压入栈中  
128.             }  
129. //如果是从头开始进行解释，则将前三个单词组成一个简单句子SentenceNode并将该句子压入栈中  
130. else {  
131.                 String word1 = words[i];  
132. new DirectionNode(word1);  
133.                 String word2 = words[++i];  
134. new ActionNode(word2);  
135.                 String word3 = words[++i];  
136. new DistanceNode(word3);  
137. new SentenceNode(direction,action,distance);  
138. //将新表达式压入栈中  
139.             }  
140.         }  
141. this.node = (AbstractNode)stack.pop(); //将全部表达式从栈中弹出  
142.     }  
143.       
144. public String output() {  
145. //解释表达式  
146. return result;  
147.     }  
148. }  

InstructionHandler用于对输入指令进行处理，将输入指令分割为字符串数组，将第1个、第2个和第3个单词组合成一个句子，并存入栈中；如果发现有单词“and”，则将“and”后的第1个、第2个和第3个单词组合成一个新的句子作为“and”的右表达式，并从栈中取出原先所存句子作为左表达式，然后组合成一个And节点存入栈中。依此类推，直到整个指令解析结束。

       编写如下客户端测试代码：

[java]  ​​view plain​​ ​​copy​​

1. class Client {  
2. public static void main(String args[]) {  
3. "up move 5 and down run 10 and left move 5";  
4. new InstructionHandler();  
5.         handler.handle(instruction);  
6.         String outString;  
7.         outString = handler.output();  
8.         System.out.println(outString);  
9.     }  
10. }  

       编译并运行程序，输出结果如下：

5 再谈Context的作用

Context用于存储解释器之外的一些全局信息，它通常作为参数被传递到所有表达式的解释方法interpret()中，可以在Context对象中存储和访问表达式解释器的状态，向表达式解释器提供一些全局的、公共的数据，此外还可以在Context中增加一些所有表达式解释器都共有的功能，减轻解释器的职责。

       在上面的机器人控制程序实例中，我们省略了环境类角色，下面再通过一个简单实例来说明环境类的用途：

       Sunny软件公司开发人员通过分析，根据该格式化指令中句子的组成，定义了如下文法规则：

6所示结构图：

图6    格式化指令结构图

6中，Context充当环境角色，Node充当抽象表达式角色，ExpressionNode、CommandNode和LoopCommandNode充当非终结符表达式角色，PrimitiveCommandNode充当终结符表达式角色。完整代码如下所示：

[java]  ​​view plain​​ ​​copy​​

1. import java.util.*;  
2.   
3. //环境类：用于存储和操作需要解释的语句，在本实例中每一个需要解释的单词可以称为一个动作标记(Action Token)或命令  
4. class Context {  
5. private StringTokenizer tokenizer; //StringTokenizer类，用于将字符串分解为更小的字符串标记(Token)，默认情况下以空格作为分隔符  
6. private String currentToken; //当前字符串标记  
7.       
8. public Context(String text) {  
9. new StringTokenizer(text); //通过传入的指令字符串创建StringTokenizer对象  
10.         nextToken();  
11.     }  
12.       
13. //返回下一个标记  
14. public String nextToken() {  
15. if (tokenizer.hasMoreTokens()) {  
16.             currentToken = tokenizer.nextToken();  
17.         }  
18. else {  
19. null;  
20.         }  
21. return currentToken;  
22.     }  
23.       
24. //返回当前的标记  
25. public String currentToken() {  
26. return currentToken;  
27.     }  
28.       
29. //跳过一个标记  
30. public void skipToken(String token) {  
31. if (!token.equals(currentToken)) {  
32. "错误提示：" + currentToken + "解释错误！");  
33.             }  
34.         nextToken();  
35.     }  
36.       
37. //如果当前的标记是一个数字，则返回对应的数值  
38. public int currentNumber() {  
39. int number = 0;  
40. try{  
41. //将字符串转换为整数  
42.         }  
43. catch(NumberFormatException e) {  
44. "错误提示：" + e);  
45.         }  
46. return number;  
47.     }  
48. }  
49.   
50. //抽象节点类：抽象表达式  
51. abstract class Node {  
52. public abstract void interpret(Context text); //声明一个方法用于解释语句  
53. public abstract void execute(); //声明一个方法用于执行标记对应的命令  
54. }  
55.   
56. //表达式节点类：非终结符表达式  
57. class ExpressionNode extends Node {  
58. private ArrayList<Node> list = new ArrayList<Node>(); //定义一个集合用于存储多条命令  
59.       
60. public void interpret(Context context) {  
61. //循环处理Context中的标记  
62. while (true){  
63. //如果已经没有任何标记，则退出解释  
64. if (context.currentToken() == null) {  
65. break;  
66.             }  
67. //如果标记为END，则不解释END并结束本次解释过程，可以继续之后的解释  
68. else if (context.currentToken().equals("END")) {  
69. "END");  
70. break;  
71.             }  
72. //如果为其他标记，则解释标记并将其加入命令集合  
73. else {  
74. new CommandNode();  
75.                 commandNode.interpret(context);  
76.                 list.add(commandNode);  
77.             }  
78.         }  
79.     }  
80.       
81. //循环执行命令集合中的每一条命令  
82. public void execute() {  
83.         Iterator iterator = list.iterator();  
84. while (iterator.hasNext()){  
85.             ((Node)iterator.next()).execute();  
86.         }  
87.     }  
88. }  
89.   
90. //语句命令节点类：非终结符表达式  
91. class CommandNode extends Node {  
92. private Node node;  
93.       
94. public void interpret(Context context) {  
95. //处理LOOP循环命令  
96. if (context.currentToken().equals("LOOP")) {  
97. new LoopCommandNode();  
98.             node.interpret(context);  
99.         }  
100. //处理其他基本命令  
101. else {  
102. new PrimitiveCommandNode();  
103.             node.interpret(context);  
104.         }  
105.     }  
106.       
107. public void execute() {  
108.         node.execute();  
109.     }  
110. }  
111.   
112. //循环命令节点类：非终结符表达式  
113. class LoopCommandNode extends Node {  
114. private int number; //循环次数  
115. private Node commandNode; //循环语句中的表达式  
116.       
117. //解释循环命令  
118. public void interpret(Context context) {  
119. "LOOP");  
120.         number = context.currentNumber();  
121.         context.nextToken();  
122. new ExpressionNode(); //循环语句中的表达式  
123.         commandNode.interpret(context);  
124.     }  
125.       
126. public void execute() {  
127. for (int i=0;i<number;i++)  
128.             commandNode.execute();  
129.     }  
130. }  
131.   
132. //基本命令节点类：终结符表达式  
133. class PrimitiveCommandNode extends Node {  
134. private String name;  
135. private String text;  
136.       
137. //解释基本命令  
138. public void interpret(Context context) {  
139.         name = context.currentToken();  
140.         context.skipToken(name);  
141. if (!name.equals("PRINT") && !name.equals("BREAK") && !name.equals ("SPACE")){  
142. "非法命令！");  
143.         }  
144. if (name.equals("PRINT")){  
145.             text = context.currentToken();  
146.             context.nextToken();  
147.         }  
148.     }  
149.       
150. public void execute(){  
151. if (name.equals("PRINT"))  
152.             System.out.print(text);  
153. else if (name.equals("SPACE"))  
154. " ");  
155. else if (name.equals("BREAK"))  
156.             System.out.println();  
157.     }  
158. }  

Context类似一个工具类，它提供了用于处理指令的方法，如nextToken()、currentToken()、skipToken()等，同时它存储了需要解释的指令并记录了每一次解释的当前标记(Token)，而具体的解释过程交给表达式解释器类来处理。我们还可以将各种解释器类包含的公共方法移至环境类中，更好地实现这些方法的重用和扩展。

       针对本实例代码，我们编写如下客户端测试代码：

[java]  ​​view plain​​ ​​copy​​

1. class Client{  
2. public static void main(String[] args){  
3. "LOOP 2 PRINT 杨过 SPACE SPACE PRINT 小龙女 BREAK END PRINT 郭靖 SPACE SPACE PRINT 黄蓉";  
4. new Context(text);  
5.               
6. new ExpressionNode();  
7.         node.interpret(context);  
8.         node.execute();  
9.     }  
10. }  

       编译并运行程序，输出结果如下：

6 解释器模式总结

XML文档解释等领域还是得到了广泛使用。与解释器模式类似，目前还诞生了很多基于抽象语法树的源代码处理工具，例如Eclipse中的Eclipse AST，它可以用于表示Java语言的语法结构，用户可以通过扩展其功能，创建自己的文法规则。

      1. 主要优点

      解释器模式的主要优点如下：

      (1)

      (2) 每一条文法规则都可以表示为一个类，因此可以方便地实现一个简单的语言。

      (3) 实现文法较为容易。在抽象语法树中每一个表达式节点类的实现方式都是相似的，这些类的代码编写都不会特别复杂，还可以通过一些工具自动生成节点类代码。

      (4) 增加新的解释表达式较为方便。如果用户需要增加新的解释表达式只需要对应增加一个新的终结符表达式或非终结符表达式类，原有表达式类代码无须修改，符合“开闭原则”。

      2. 主要缺点

      解释器模式的主要缺点如下：

      (1) 对于复杂文法难以维护。在解释器模式中，每一条规则至少需要定义一个类，因此如果一个语言包含太多文法规则，类的个数将会急剧增加，导致系统难以管理和维护，此时可以考虑使用语法分析程序等方式来取代解释器模式。

      (2) 执行效率较低。由于在解释器模式中使用了大量的循环和递归调用，因此在解释较为复杂的句子时其速度很慢，而且代码的调试过程也比较麻烦。

      3. 适用场景

      在以下情况下可以考虑使用解释器模式：

      (1) 可以将一个需要解释执行的语言中的句子表示为一个抽象语法树。

      (2) 一些重复出现的问题可以用一种简单的语言来进行表达。

      (3) 一个语言的文法较为简单。

      (4) 执行效率不是关键问题。【注：高效的解释器通常不是通过直接解释抽象语法树来实现的，而是需要将它们转换成其他形式，使用解释器模式的执行效率并不高。】

      解释器模式可以说是所有设计模式中难度较大、使用频率较低的一个模式，如果您能够静下心来把这几篇文章都看完，我相信您对解释器模式应该有了一个较为全面的了解，欢迎大家与我交流和讨论。

      感谢您能够坚持看完这六篇关于解释器模式的文章，！