解釋器模式是一種不很常用的模式,但是比如正則表達式就是一種解釋器模式的思維,所以儘管實際編碼中不常用,理解解釋器模式的含義很重要,本文對解釋器模式進行了簡單的介紹,並且給出了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 |
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; }通過上面的這個方法,我們就可以直接解析字元串了