行為型：設計模式之解釋器模式（二十二）

雖然目前計算機程式設計語言有好幾百種，但有時候我們還是希望能用一些簡單的語言來實作一些特定的操作，我們隻要向計算機輸入一個句子或檔案，它就能夠按照預先定義的文法規則來對句子或檔案進行解釋，進而實作相應的功能。例如提供一個簡單的加法/減法解釋器，隻要輸入一個加法/減法表達式，它就能夠計算出表達式結果，如圖1所示，當輸入字元串表達式為“1 + 2 + 3 – 4 + 1”時，将輸出計算結果為3。

圖1 加法/減法解釋器示意圖

C++、Java和C#等語言無法直接解釋類似“1+ 2 + 3 – 4 + 1”這樣的字元串（如果直接作為數值表達式時可以解釋），我們必須自己定義一套文法規則來實作對這些語句的解釋，即設計一個自定義語言。在實際開發中，這些簡單的自定義語言可以基于現有的程式設計語言來設計，如果所基于的程式設計語言是面向對象語言，此時可以使用解釋器模式來實作自定義語言。

1 機器人控制程式

Sunny軟體公司欲為某玩具公司開發一套機器人控制程式，在該機器人控制程式中包含一些簡單的英文控制指令，每一個指令對應一個表達式(expression)，該表達式可以是簡單表達式也可以是複合表達式，每一個簡單表達式由移動方向(direction)，移動方式(action)和移動距離(distance)三部分組成，其中移動方向包括上(up)、下(down)、左(left)、右(right)；移動方式包括移動(move)和快速移動(run)；移動距離為一個正整數。兩個表達式之間可以通過與(and)連接配接，形成複合(composite)表達式。

up move 5，則“向上移動5個機關”；輸入控制指令：down run 10 and left move 20，則“向下快速移動10個機關再向左移動20個機關”。

Sunny軟體公司開發人員決定自定義一個簡單的語言來解釋機器人控制指令，根據上述需求描述，用形式化語言來表示該簡單語言的文法規則如下：

expression ::= direction action distance | composite //表達式

composite ::= expression 'and' expression //複合表達式

direction ::= 'up' | 'down' | 'left' | 'right' //移動方向

action ::= 'move' | 'run' //移動方式

distance ::= an integer //移動距離

direction、action和distance，它們是語言的最小組成機關，不能再進行拆分；另一類為非終結符（也稱為非終結符表達式），例如expression和composite，它們都是一個完整的句子，包含一系列終結符或非終結符。

我們根據上述規則定義出的語言可以構成很多語句，計算機程式将根據這些語句進行某種操作。為了實作對語句的解釋，可以使用解釋器模式，在解釋器模式中每一個文法規則都将對應一個類，擴充、改變文法以及增加新的文法規則都很友善，下面就讓我們正式進入解釋器模式的學習，看看使用解釋器模式如何來實作對機器人控制指令的處理。

2 文法規則和抽象文法樹

解釋器模式描述了如何為簡單的語言定義一個文法，如何在該語言中表示一個句子，以及如何解釋這些句子。在正式分析解釋器模式結構之前，我們先來學習如何表示一個語言的文法規則以及如何構造一棵抽象文法樹。

/減法解釋器中，每一個輸入表達式，例如“1 + 2 + 3 – 4 + 1”，都包含了三個語言機關，可以使用如下文法規則來定義：

expression ::= value | operation

operation ::= expression '+' expression | expression '-' expression

value ::= an integer //一個整數值

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 解釋器模式概述

解釋器模式是一種使用頻率相對較低但學習難度較大的設計模式，它用于描述如何使用面向對象語言構成一個簡單的語言解釋器。在某些情況下，為了更好地描述某一些特定類型的問題，我們可以建立一種新的語言，這種語言擁有自己的表達式和結構，即文法規則，這些問題的執行個體将對應為該語言中的句子。此時，可以使用解釋器模式來設計這種新的語言。對解釋器模式的學習能夠加深我們對面向對象思想的了解，并且掌握程式設計語言中文法規則的解釋過程。

解釋器模式定義如下：

解釋器模式(Interpreter Pattern)：定義一個語言的文法，并且建立一個解釋器來解釋該語言中的句子，這裡的“語言”是指使用規定格式和文法的代碼。解釋器模式是一種類行為型模式。

3所示：

圖3 解釋器模式結構圖

在解釋器模式結構圖中包含如下幾個角色：

AbstractExpression（抽象表達式）：在抽象表達式中聲明了抽象的解釋操作，它是所有終結符表達式和非終結符表達式的公共父類。

TerminalExpression（終結符表達式）：終結符表達式是抽象表達式的子類，它實作了與文法中的終結符相關聯的解釋操作，在句子中的每一個終結符都是該類的一個執行個體。通常在一個解釋器模式中隻有少數幾個終結符表達式類，它們的執行個體可以通過非終結符表達式組成較為複雜的句子。

NonterminalExpression（非終結符表達式）：非終結符表達式也是抽象表達式的子類，它實作了文法中非終結符的解釋操作，由于在非終結符表達式中可以包含終結符表達式，也可以繼續包含非終結符表達式，是以其解釋操作一般通過遞歸的方式來完成。

Context（環境類）：環境類又稱為上下文類，它用于存儲解釋器之外的一些全局資訊，通常它臨時存儲了需要解釋的語句。

在解釋器模式中，每一種終結符和非終結符都有一個具體類與之對應，正因為使用類來表示每一條文法規則，是以系統将具有較好的靈活性和可擴充性。對于所有的終結符和非終結符，我們首先需要抽象出一個公共父類，即抽象表達式類，其典型代碼如下所示：

[java]

view plain

copy

abstract class AbstractExpression {
public abstract void interpret(Context ctx);
}

終結符表達式和非終結符表達式類都是抽象表達式類的子類，對于終結符表達式，其代碼很簡單，主要是對終結符元素的處理，其典型代碼如下所示：

[java]

view plain

copy

class TerminalExpression extends AbstractExpression {
public void interpret(Context ctx) {
//終結符表達式的解釋操作
}
}

對于非終結符表達式，其代碼相對比較複雜，因為可以通過非終結符将表達式組合成更加複雜的結構，對于包含兩個操作元素的非終結符表達式類，其典型代碼如下：

[java]

view plain

copy

class NonterminalExpression extends AbstractExpression {
private AbstractExpression left;
private AbstractExpression right;
public NonterminalExpression(AbstractExpression left,AbstractExpression right) {
this.left=left;
this.right=right;
}
public void interpret(Context ctx) {
//遞歸調用每一個組成部分的interpret()方法
//在遞歸調用時指定組成部分的連接配接方式，即非終結符的功能
}
}

Context，用于存儲一些全局資訊，通常在Context中包含了一個HashMap或ArrayList等類型的集合對象（也可以直接由HashMap等集合類充當環境類），存儲一系列公共資訊，如變量名與值的映射關系（key/value）等，用于在進行具體的解釋操作時從中擷取相關資訊。其典型代碼片段如下：

[java]

view plain

copy

class Context {
private HashMap map = new HashMap();
public void assign(String key, String value) {
//往環境類中設值
}
public String lookup(String key) {
//擷取存儲在環境類中的值
}
}

當系統無須提供全局公共資訊時可以省略環境類，可根據實際情況決定是否需要環境類。

思考

繪制加法/減法解釋器的類圖并編寫核心實作代碼。

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

//注：本執行個體對機器人控制指令的輸出結果進行模拟，将英文指令翻譯為中文指令，實際情況是調用不同的控制程式進行機器人的控制，包括對移動方向、方式和距離的控制等
import java.util.*;
//抽象表達式
abstract class AbstractNode {
public abstract String interpret();
}
//And解釋：非終結符表達式
class AndNode extends AbstractNode {
private AbstractNode left; //And的左表達式
private AbstractNode right; //And的右表達式
public AndNode(AbstractNode left, AbstractNode right) {
this.left = left;
this.right = right;
}
//And表達式解釋操作
public String interpret() {
return left.interpret() + "再" + right.interpret();
}
}
//簡單句子解釋：非終結符表達式
class SentenceNode extends AbstractNode {
private AbstractNode direction;
private AbstractNode action;
private AbstractNode distance;
public SentenceNode(AbstractNode direction,AbstractNode action,AbstractNode distance) {
this.direction = direction;
this.action = action;
this.distance = distance;
}
//簡單句子的解釋操作
public String interpret() {
return direction.interpret() + action.interpret() + distance.interpret();
}
}
//方向解釋：終結符表達式
class DirectionNode extends AbstractNode {
private String direction;
public DirectionNode(String direction) {
this.direction = direction;
}
//方向表達式的解釋操作
public String interpret() {
if (direction.equalsIgnoreCase("up")) {
return "向上";
}
else if (direction.equalsIgnoreCase("down")) {
return "向下";
}
else if (direction.equalsIgnoreCase("left")) {
return "向左";
}
else if (direction.equalsIgnoreCase("right")) {
return "向右";
}
else {
return "無效指令";
}
}
}
//動作解釋：終結符表達式
class ActionNode extends AbstractNode {
private String action;
public ActionNode(String action) {
this.action = action;
}
//動作（移動方式）表達式的解釋操作
public String interpret() {
if (action.equalsIgnoreCase("move")) {
return "移動";
}
else if (action.equalsIgnoreCase("run")) {
return "快速移動";
}
else {
return "無效指令";
}
}
}
//距離解釋：終結符表達式
class DistanceNode extends AbstractNode {
private String distance;
public DistanceNode(String distance) {
this.distance = distance;
}
//距離表達式的解釋操作
public String interpret() {
return this.distance;
}
}
//指令處理類：工具類
class InstructionHandler {
private String instruction;
private AbstractNode node;
public void handle(String instruction) {
null, right = null;
null, action = null, distance = null;
new Stack(); //聲明一個棧對象用于存儲抽象文法樹
" "); //以空格分隔指令字元串
for (int i = 0; i < words.length; i++) {
//本執行個體采用棧的方式來處理指令，如果遇到“and”，則将其後的三個單詞作為三個終結符表達式連成一個簡單句子SentenceNode作為“and”的右表達式，而将從棧頂彈出的表達式作為“and”的左表達式，最後将新的“and”表達式壓入棧中。 if (words[i].equalsIgnoreCase("and")) {
//彈出棧頂表達式作為左表達式
String word1= words[++i];
new DirectionNode(word1);
String word2 = words[++i];
new ActionNode(word2);
String word3 = words[++i];
new DistanceNode(word3);
new SentenceNode(direction,action,distance); //右表達式
new AndNode(left,right)); //将新表達式壓入棧中
}
//如果是從頭開始進行解釋，則将前三個單詞組成一個簡單句子SentenceNode并将該句子壓入棧中
else {
String word1 = words[i];
new DirectionNode(word1);
String word2 = words[++i];
new ActionNode(word2);
String word3 = words[++i];
new DistanceNode(word3);
new SentenceNode(direction,action,distance);
//将新表達式壓入棧中
}
}
this.node = (AbstractNode)stack.pop(); //将全部表達式從棧中彈出
}
public String output() {
//解釋表達式
return result;
}
}

InstructionHandler用于對輸入指令進行處理，将輸入指令分割為字元串數組，将第1個、第2個和第3個單詞組合成一個句子，并存入棧中；如果發現有單詞“and”，則将“and”後的第1個、第2個和第3個單詞組合成一個新的句子作為“and”的右表達式，并從棧中取出原先所存句子作為左表達式，然後組合成一個And節點存入棧中。依此類推，直到整個指令解析結束。

編寫如下用戶端測試代碼：

[java]

view plain

copy

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

編譯并運作程式，輸出結果如下：

向上移動5再向下快速移動10再向左移動5

5 再談Context的作用

Context用于存儲解釋器之外的一些全局資訊，它通常作為參數被傳遞到所有表達式的解釋方法interpret()中，可以在Context對象中存儲和通路表達式解釋器的狀态，向表達式解釋器提供一些全局的、公共的資料，此外還可以在Context中增加一些所有表達式解釋器都共有的功能，減輕解釋器的職責。

在上面的機器人控制程式執行個體中，我們省略了環境類角色，下面再通過一個簡單執行個體來說明環境類的用途：

Sunny軟體公司開發了一套簡單的基于字元界面的格式化指令，可以根據輸入的指令在字元界面中輸出一些格式化内容，例如輸入“LOOP 2 PRINT楊過 SPACE SPACE PRINT 小龍女 BREAK END PRINT郭靖 SPACE SPACE PRINT 黃蓉”，将輸出如下結果：

LOOP表示“循環”，後面的數字表示循環次數；PRINT表示“列印”，後面的字元串表示列印的内容；SPACE表示“空格”；BREAK表示“換行”；END表示“循環結束”。每一個關鍵詞對應一條指令，計算機程式将根據關鍵詞執行相應的處理操作。

現使用解釋器模式設計并實作該格式化指令的解釋，對指令進行分析并調用相應的操作執行指令中每一條指令。

楊過小龍女

郭靖黃蓉

Sunny軟體公司開發人員通過分析，根據該格式化指令中句子的組成，定義了如下文法規則：

expression ::= command* //表達式，一個表達式包含多條指令

command ::= loop | primitive //語句指令

loop ::= 'loopnumber' expression 'end' //循環指令，其中number為自然數

primitive ::= 'printstring' | 'space' | 'break' //基本指令，其中string為字元串

6所示結構圖：

圖6 格式化指令結構圖

6中，Context充當環境角色，Node充當抽象表達式角色，ExpressionNode、CommandNode和LoopCommandNode充當非終結符表達式角色，PrimitiveCommandNode充當終結符表達式角色。完整代碼如下所示：

[java]

view plain

copy

import java.util.*;
//環境類：用于存儲和操作需要解釋的語句，在本執行個體中每一個需要解釋的單詞可以稱為一個動作标記(Action Token)或指令
class Context {
private StringTokenizer tokenizer; //StringTokenizer類，用于将字元串分解為更小的字元串标記(Token)，預設情況下以空格作為分隔符
private String currentToken; //目前字元串标記
public Context(String text) {
new StringTokenizer(text); //通過傳入的指令字元串建立StringTokenizer對象
nextToken();
}
//傳回下一個标記
public String nextToken() {
if (tokenizer.hasMoreTokens()) {
currentToken = tokenizer.nextToken();
}
else {
null;
}
return currentToken;
}
//傳回目前的标記
public String currentToken() {
return currentToken;
}
//跳過一個标記
public void skipToken(String token) {
if (!token.equals(currentToken)) {
"錯誤提示：" + currentToken + "解釋錯誤！");
}
nextToken();
}
//如果目前的标記是一個數字，則傳回對應的數值
public int currentNumber() {
int number = 0;
try{
//将字元串轉換為整數
}
catch(NumberFormatException e) {
"錯誤提示：" + e);
}
return number;
}
}
//抽象節點類：抽象表達式
abstract class Node {
public abstract void interpret(Context text); //聲明一個方法用于解釋語句
public abstract void execute(); //聲明一個方法用于執行标記對應的指令
}
//表達式節點類：非終結符表達式
class ExpressionNode extends Node {
private ArrayList<Node> list = new ArrayList<Node>(); //定義一個集合用于存儲多條指令
public void interpret(Context context) {
//循環處理Context中的标記
while (true){
//如果已經沒有任何标記，則退出解釋
if (context.currentToken() == null) {
break;
}
//如果标記為END，則不解釋END并結束本次解釋過程，可以繼續之後的解釋
else if (context.currentToken().equals("END")) {
"END");
break;
}
//如果為其他标記，則解釋标記并将其加入指令集合
else {
new CommandNode();
commandNode.interpret(context);
list.add(commandNode);
}
}
}
//循環執行指令集合中的每一條指令
public void execute() {
Iterator iterator = list.iterator();
while (iterator.hasNext()){
((Node)iterator.next()).execute();
}
}
}
//語句指令節點類：非終結符表達式
class CommandNode extends Node {
private Node node;
public void interpret(Context context) {
//處理LOOP循環指令
if (context.currentToken().equals("LOOP")) {
new LoopCommandNode();
node.interpret(context);
}
//處理其他基本指令
else {
new PrimitiveCommandNode();
node.interpret(context);
}
}
public void execute() {
node.execute();
}
}
//循環指令節點類：非終結符表達式
class LoopCommandNode extends Node {
private int number; //循環次數
private Node commandNode; //循環語句中的表達式
//解釋循環指令
public void interpret(Context context) {
"LOOP");
number = context.currentNumber();
context.nextToken();
new ExpressionNode(); //循環語句中的表達式
commandNode.interpret(context);
}
public void execute() {
for (int i=0;i<number;i++)
commandNode.execute();
}
}
//基本指令節點類：終結符表達式
class PrimitiveCommandNode extends Node {
private String name;
private String text;
//解釋基本指令
public void interpret(Context context) {
name = context.currentToken();
context.skipToken(name);
if (!name.equals("PRINT") && !name.equals("BREAK") && !name.equals ("SPACE")){
"非法指令！");
}
if (name.equals("PRINT")){
text = context.currentToken();
context.nextToken();
}
}
public void execute(){
if (name.equals("PRINT"))
System.out.print(text);
else if (name.equals("SPACE"))
" ");
else if (name.equals("BREAK"))
System.out.println();
}
}

Context類似一個工具類，它提供了用于處理指令的方法，如nextToken()、currentToken()、skipToken()等，同時它存儲了需要解釋的指令并記錄了每一次解釋的目前标記(Token)，而具體的解釋過程交給表達式解釋器類來處理。我們還可以将各種解釋器類包含的公共方法移至環境類中，更好地實作這些方法的重用和擴充。

針對本執行個體代碼，我們編寫如下用戶端測試代碼：

[java]

view plain

copy

class Client{
public static void main(String[] args){
"LOOP 2 PRINT 楊過 SPACE SPACE PRINT 小龍女 BREAK END PRINT 郭靖 SPACE SPACE PRINT 黃蓉";
new Context(text);
new ExpressionNode();
node.interpret(context);
node.execute();
}
}

編譯并運作程式，輸出結果如下：

楊過小龍女

郭靖黃蓉

思考

預測指令“LOOP 2 LOOP 2 PRINT楊過 SPACE SPACE PRINT 小龍女 BREAK END PRINT 郭靖 SPACE SPACE PRINT 黃蓉 BREAK END”的輸出結果。

6 解釋器模式總結

XML文檔解釋等領域還是得到了廣泛使用。與解釋器模式類似，目前還誕生了很多基于抽象文法樹的源代碼處理工具，例如Eclipse中的Eclipse AST，它可以用于表示Java語言的文法結構，使用者可以通過擴充其功能，建立自己的文法規則。

1. 主要優點

解釋器模式的主要優點如下：

(1)

(2) 每一條文法規則都可以表示為一個類，是以可以友善地實作一個簡單的語言。

(3) 實作文法較為容易。在抽象文法樹中每一個表達式節點類的實作方式都是相似的，這些類的代碼編寫都不會特别複雜，還可以通過一些工具自動生成節點類代碼。

(4) 增加新的解釋表達式較為友善。如果使用者需要增加新的解釋表達式隻需要對應增加一個新的終結符表達式或非終結符表達式類，原有表達式類代碼無須修改，符合“開閉原則”。

2. 主要缺點

解釋器模式的主要缺點如下：

(1) 對于複雜文法難以維護。在解釋器模式中，每一條規則至少需要定義一個類，是以如果一個語言包含太多文法規則，類的個數将會急劇增加，導緻系統難以管理和維護，此時可以考慮使用文法分析程式等方式來取代解釋器模式。

(2) 執行效率較低。由于在解釋器模式中使用了大量的循環和遞歸調用，是以在解釋較為複雜的句子時其速度很慢，而且代碼的調試過程也比較麻煩。

3. 适用場景

在以下情況下可以考慮使用解釋器模式：

(1) 可以将一個需要解釋執行的語言中的句子表示為一個抽象文法樹。

(2) 一些重複出現的問題可以用一種簡單的語言來進行表達。

(3) 一個語言的文法較為簡單。

行為型：設計模式之解釋器模式（二十二）

1 機器人控制程式

2 文法規則和抽象文法樹

3 解釋器模式概述

4 完整解決方案

5 再談Context的作用

6 解釋器模式總結

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method