直譯器模式 Interpreter 行為型 設計模式（十九）

直譯器模式（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

有了規則我們就可以對語法進行描述，這是直譯器模式的基礎工作

比如加減法運算可以這樣定義

抽象語法樹

除了使用文法規則來定義規則，還可以通過抽象語法樹的圖形方式直觀的表示語言的構成

文法規則描述了所有的場景，所有條件匹配的都是符合的，不匹配的都是不符合的

符合語法規則的一個“句子”就是語言規則的一個例項

抽象語法樹正是對於這個例項的一個描述

一顆抽象語法樹對應著語言規則的一個例項

關於抽象語法樹百科中這樣介紹

在電腦科學中，抽象語法樹（abstract syntax tree 或者縮寫為 AST），或者語法樹（syntax tree）

是原始碼的抽象語法結構的樹狀表現形式，這裡特指程式語言的原始碼。

樹上的每個節點都表示原始碼中的一種結構。

之所以說語法是「抽象」的，是因為這裡的語法並不會表示出真實語法中出現的每個細節。

比如 1+2+3+4-5是一個例項

所以說文法規則用於描述語言規則，抽象語法樹描述描述語言的一個例項，也就是一個“句子”

結構

抽象表示式角色AbstractExpression

宣告一個抽象的解釋操作，所有的具體表達式操作都需要實現的抽象介面

介面主要是interpret()方法，叫做解釋操作

回到剛才的例子

上面是我們給加減法運算定義的語法規則，由四條規則組成

其中規則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();
}

package interpret;

public class Value extends AbstractExpression {

private int value;
Value(int value){
this.value = value;
}

@Override
public int interpret() {
return value;
}
}

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();
}
}

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物件

也可以通過方法解析抽象語法樹，都可以根據實際場景處理

簡言之， 直譯器模式不關注抽象語法樹的建立，僅僅關注解析處理

所以個人看法：

但凡你的問題場景可以抽象為一種語言，也就是有規則、公式，有套路就可以使用直譯器模式

不過如果有替代方法，能不用就不用

如果非要用，你也不要自己寫

原文地址: ofollow,noindex">直譯器模式 Interpreter 行為型 設計模式（十九）