軟件設計模式學習(十九)解釋器模式

解釋器是一種不常使用的設計模式,它用於描述如何構成一個簡單的語言解釋器,主要應用於使用面向對象語言開發的編譯器和解釋器設計。當我們需要開發一個新的語言時,可以考慮使用解釋器模式

模式動機

如果在系統中某一特定類型的問題發生的頻率很高,此時可以考慮將這些問題的實例表述為一個語言中的句子。再構建一個解釋器,解釋器通過解釋這些句子來解決對應的問題。

舉個例子,我們希望系統提供一個功能來支持一種新的加減法表達式語言,當輸入表達式為 “1 + 2 + 3 – 4 + 1” 時,輸出計算結果為 3。為了實現上述功能,需要對輸入表達式進行解釋,如果不作解釋,直接把 “1 + 2 + 3 – 4 + 1” 丟過去,現有的如 Java、C 之類的編程語言只會把它當作普通的字符串,不可能實現我們想要的計算效果。我們必須自己定義一套規則來實現該語句的解釋,即實現一個簡單語言來解釋這些句子,這就是解釋器模式的模式動機。

模式定義

定義語言的文法,並且建立一個解釋器來解釋該語言中的句子,這裡的 「語言」 意思是使用規定格式和語法的代碼,它是一種類行為型模式。

模式結構

  1. AbstractExpression(抽象表達式)

    聲明了抽象的解釋操作,它是所有終結符表達式和非終結符表達式的公共父類

  2. TerminalExpression(終結符表達式)

    抽象表達式的子類,實現了文法中的終結符相關聯的解釋操作,在句子中每一個終結符都是該類的一個實例。

  3. NonterminalExpression(非終結符表達式)

    也是抽象表達式的子類,實現了文法中的非終結符相關聯的解釋操作,非終結符表達式中可以包含終結符表達式,也可以繼續包含非終結符表達式,因此其解釋操作一般通過遞歸方式來完成。

  4. Context(環境類)

    環境類又稱上下文類,它用於存儲解釋器之外的一些全局信息,通常它臨時存儲了需要解釋的語句。

  5. Client(客戶類)

    客戶類中構造了表示以規定文法定義的一個特定句子的抽象語法樹,該抽象語法樹由非終結符表達式和終結符表達式實例組合而成。在客戶類中還將調用解釋操作,實現對句子的解釋,有時候為了簡化客戶類代碼,也可以將抽象語法樹的構造工作封裝到專門的類中完成,客戶端只需提供待解釋的句子並調用該類的解釋操作即可,該類可以稱為解釋器封裝類

模式分析

還是以之前提到的加減法表達式語言來舉例,我們要為這門語言定義語法規則,可以使用如下文法來定義

expression ::= value | symbol
symbol ::= expression '+' expression | expression '-' expression
value ::= an integer	// 一個整數值

該文法規則包含三條定義語句,第一句是表達式的組成方式,expression 是我們最終要得到的句子,假設是 “1 + 2 + 3 – 4 + 1″,那麼該句的組成元素無非就是兩種,數字(value)和運算符號(symbol),如果用專業術語來描述的話,symbol 和 value 稱為語法構造成分或語法單位。根據句子定義,expression 要麼是一個 value,要麼是一個 symbol。

value 是一個終結符表達式,因為它的組成元素就是一個整數值,不能再進行分解。與之對應的 symbol 則是非終結符表達式,它的組成元素仍舊可以是表達式 expression,expression 又可以是 value 或者 symbol,即可以進一步分解。

按照上述的文法規則,我們可以通過一種稱之為抽象語法樹(Abstract Syntax Tree)的圖形方式來直觀地表示語言的構成,每一顆抽象語法樹對應一個語言實例,如 “1 + 2 + 3 – 4 + 1” 可以通過如圖的抽象語法樹來表示。

每一個具體的語句都可以用類似的抽象語法樹來表示,終結符表達式類的實例作為樹的葉子節點,而非終結符表達式類的實例作為非葉子節點。抽象語法樹描述了如何構成一個複雜的句子,通過對抽象語法樹的分析,可以識別出語言中的終結符和非終結符類。

在解釋器模式中,每一個終結符和非終結符都有一個具體類與之對應,正因為使用類來表示每一個語法規則,使得系統具有較好的擴展性和靈活性。對於所有的終結符和非終結符,首先要抽象出一個公共父類

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

對於終結符表達式,其代碼主要是對終結符元素的處理

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

對於終結符表達式,其代碼比較複雜,因為通過非終結符表達式可以將表達式組合成更複雜的結構。表達式可以通過非終結符連接在一起,對於兩個操作元素的非終結符表達式,其典型代碼如下

public 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,用於存儲一些全局信息,用於在進行具體的解釋操作時從中獲取相關信息。當系統無須提供全局公共信息時,可以省略環境類

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

模式實例

現需構造一個語言解釋器,使系統可以執行整數間的乘、除和求模運算。當用戶輸入表達式 “3 * 4 / 2 % 4″,輸出結果為 2

  1. 抽象表達式類 Node(抽象節點)

    public interface Node {
        public int interpret();
    }
    
  2. 終結符表達式類 ValueNode(值節點類)

    public class ValueNode implements Node {
    
        private int value;
    
        public ValueNode(int value) {
            this.value = value;
        }
    
        @Override
        public int interpret() {
            return this.value;
        }
    }
    
  3. 抽象非終結符表達式類 SymbolNode(符號節點類)

    public abstract class SymbolNode implements Node {
    
        protected Node left;
        protected Node right;
    
        public SymbolNode(Node left, Node right) {
            this.left = left;
            this.right = right;
        }
    }
    
  4. 非終結符表達式類 MulNode(乘法節點類)

    public class MulNode extends SymbolNode {
    
        public MulNode(Node left, Node right) {
            super(left, right);
        }
    
        @Override
        public int interpret() {
            return super.left.interpret() * super.right.interpret();
        }
    }
    
  5. 非終結符表達式類 DivNode(除法節點類)

    public class DivNode extends SymbolNode {
    
        public DivNode(Node left, Node right) {
            super(left, right);
        }
    
        @Override
        public int interpret() {
            return super.left.interpret() / super.right.interpret();
        }
    }
    
  6. 非終結符表達式類 ModNode(求模節點類)

    public class ModNode extends SymbolNode {
    
        public ModNode(Node left, Node right) {
            super(left, right);
        }
    
        @Override
        public int interpret() {
            return super.left.interpret() % super.right.interpret();
        }
    }
    
  7. 解釋器封裝類 Calculator(計算器類)

    Calculator 類是本實例的核心類之一,Calculator 類中定義了如何構造一棵抽象語法樹,在構造過程中使用了棧結構 Stack。通過一連串判斷語句判斷字符,如果是數字,實例化終結符表達式類 ValueNode 並壓棧;如果判斷為運算符號,則取出棧頂內容作為其左表達式,而將之後輸入的數字封裝在 ValueNode 類型的對象作為其右表達式,創建非終結符表達式 MulNode 類型的對象,最後將該表達式壓棧。

    public class Calculator {
    
        private String statement;
        private Node node;
    
        public void build(String statement) {
    
            Node left = null, right = null;
            Stack<Node> stack = new Stack<Node>();
    
            String[] statementArr = statement.split(" ");
    
            for (int i = 0; i < statementArr.length; i++) {
                if (statementArr[i].equalsIgnoreCase(("*"))) {
                    left = stack.pop();
                    int val = Integer.parseInt(statementArr[++i]);
                    right = new ValueNode(val);
                    stack.push(new MulNode(left, right));
                } else if (statementArr[i].equalsIgnoreCase(("/"))) {
                    left = stack.pop();
                    int val = Integer.parseInt(statementArr[++i]);
                    right = new ValueNode(val);
                    stack.push(new DivNode(left, right));
                } else if (statementArr[i].equalsIgnoreCase(("%"))) {
                    left = stack.pop();
                    int val = Integer.parseInt(statementArr[++i]);
                    right = new ValueNode(val);
                    stack.push(new ModNode(left, right));
                } else {
                    stack.push(new ValueNode(Integer.parseInt(statementArr[i])));
                }
            }
            this.node = stack.pop();
        }
    
        public int compute() {
            return node.interpret();
        }
    }
    
  8. 客戶端測試類 Client

    程序執行時將遞歸調用每一個表達式類的 interpret() 的解釋方法,最終完成對整棵抽象語法樹的解釋。

    public class Client {
    
        public static void main(String[] args) {
            String statement = "3 * 4 / 2 % 4";
            Calculator calculator = new Calculator();
            calculator.build(statement);
            int result = calculator.compute();
            System.out.println(statement + " = " + result);
        }
    }
    
  9. 運行結果

模式優缺點

解釋器模式優點如下:

  1. 易於改變和擴展文法。由於使用類來表示語言的文法規則,可以通過繼承機制來改變或擴展文法。
  2. 易於實現文法。抽象語法樹中每一個節點類的實現方式都是相似的,編寫並不複雜。
  3. 增加了新的解釋表達式的方式。增加新的表達式時無須對現有表達式類進行修改,符合開閉原則

解釋器模式缺點如下:

  1. 對於複雜文法難以維護。
  2. 執行效率低。解釋器模式使用了大量循環和遞歸調用。
  3. 應用場景有限。

軟件設計模式學習(十八)命令模式