「補課」進行時：設計模式(20)——解釋器模式

2020 年 12 月 21 日
筆記
設計模式

1. 前文匯總

「補課」進行時：設計模式系列

2. 解釋器模式

解釋器模式這個模式和前面的訪問者模式比較像，當然，我說的比較像是難的比較像，以及使用率是真的比較低，基本上沒有使用的場景，訪問者模式還有點使用場景，解釋器模式，我們又不寫解釋器，這玩意 JVM 都幫我們實現掉了，哪用我們自己實現。

常見的解釋器有 JVM 為我們提供的 Java 語言的解釋器，還有我們經常使用的 MySQL ，也有內置的 SQL 解釋器。

不過沒用是沒用，對應的模式我們還是可以學習一下。

2.1 定義

解釋器模式（Interpreter Pattern）是一種按照規定語法進行解析的方案，其定義如下：

Given a language, define a representation for its grammar along with an
interpreter that uses the representation to interpret sentences in the language.（給定一門語言，定義它的文法的一種表示，並定義一個解釋器，該解釋器使用該表示來解釋語言中的句子。）

2.2 通用類圖

AbstractExpression 抽象解釋器：具體的解釋任務由各個實現類完成，具體的解釋器分別由 TerminalExpression 和 NonterminalExpression 完成。
TerminalExpression 終結符表達式：實現與文法中的元素相關聯的解釋操作，通常一個解釋器模式中只有一個終結符表達式，但有多個實例，對應不同的終結符。
NonterminalExpression 非終結符表達式：文法中的每條規則對應於一個非終結表達式，具體到我們的例子就是加減法規則分別對應到 AddExpression 和 SubExpression 兩個類。非終結符表達式根據邏輯的複雜程度而增加，原則上每個文法規則都對應一個非終結符表達式。
Context 環境角色

2.3 通用程式碼

抽象表達式

public abstract class Expression {
    abstract Object interpreter(Context ctx);
}

抽象表達式比較簡單，通常只有一個方法，但是它是生成語法集合（也叫做語法樹）的關鍵，每個語法集合完成指定語法解析任務，它是通過遞歸調用的方式，最終由最小的語法單元進行解析完成。

終結符表達式

public class TerminalExpression extends Expression {
    // 通常終結符表達式只有一個， 但是有多個對象
    public Object interpreter(Context context) {
        return null;
    }
}

終結符表達式比較簡單，主要是處理場景元素和數據的轉換。

非終結符表達式

public class NonterminalExpression extends Expression {
    // 每個非終結符表達式都會對其他表達式產生依賴
    public NonterminalExpression(Expression ...expressions) {
    }
    @Override
    Object interpreter(Context ctx) {
        // 進行文法處理
        return null;
    }
}

每個非終結符表達式都代表了一個文法規則，並且每個文法規則都只關心自己周邊的文法規則的結果（注意是結果），因此這就產生了每個非終結符表達式調用自己周邊的非終結符表達式，然後最終、最小的文法規則就是終結符表達式，終結符表達式的概念就是如此，不能夠再參與比自己更小的文法運算了。

客戶端

public class Client {
    public static void main(String[] args) {
        Context ctx = new Context();
        Stack<Expression> stack = null;
        for(int i = 0; i < args.length; i++){
            // 進行語法判斷， 併產生遞歸調用
        }
        // 產生一個完整的語法樹， 由各個具體的語法分析進行解析
        Expression exp = stack.pop();
        //具體元素進入場景
        exp.interpreter(ctx);
    }
}

2.4 優點

解釋器是一個簡單語法分析工具，它最顯著的優點就是擴展性，修改語法規則只要修改相應的非終結符表達式就可以了，若擴展語法，則只要增加非終結符類就可以了。

2.5 缺點

解釋器模式會引起類膨脹。
解釋器模式採用遞歸調用方法，將會導致調試非常複雜。
使用了大量的循環和遞歸，效率是一個不容忽視的問題。

3. 四則運算

簡單使用解釋器模式實現一下加減法運算。

首先定義一個計算類，用作解析器封裝：

public class Calculator {
    private Expression expression;

    // 構造函數，傳參並解析
    public Calculator(String expStr) {
        // 安排運算先後順序
        Stack<Expression> stack = new Stack<>();
        // 表達式拆分為字元數組
        char[] charArray = expStr.toCharArray();

        Expression left = null;
        Expression right = null;

        for(int i=0; i<charArray.length; i++) {
            switch (charArray[i]) {
                case '+':
                    left = stack.pop();
                    right = new VarExpression(String.valueOf(charArray[++i]));
                    stack.push(new AddExpression(left, right));
                    break;
                case '-':
                    left = stack.pop();
                    right = new VarExpression(String.valueOf(charArray[++i]));
                    stack.push(new SubExpression(left, right));
                    break;
                default :
                    stack.push(new VarExpression(String.valueOf(charArray[i])));
                    break;
            }
        }
        this.expression = stack.pop();
    }

    public int run(HashMap<String, Integer> var) {
        return this.expression.interpreter(var);
    }
}

接下來是一個抽象表達式：

public abstract class Expression {
    abstract int interpreter(HashMap<String, Integer> var);
}

下面是一個變數解析器：

public class VarExpression extends Expression {
    private String key;
    public VarExpression(String key) {
        this.key = key;
    }
    @Override
    int interpreter(HashMap<String, Integer> var) {
        return var.get(this.key);
    }
}

變數解析器的主要作用是從 map 中將數據一個一個取出來。

接下來是一個抽象運算符號解析器：

public class SymbolExpression extends Expression {
    protected Expression left;
    protected Expression right;

    public SymbolExpression(Expression left, Expression right) {
        this.left = left;
        this.right = right;
    }
    @Override
    int interpreter(HashMap<String, Integer> var) {
        return 0;
    }
}

因為是運算符號，而每個運算符號都只和自己左右兩個數字有關係，左右兩個數字有可能也是一個解析的結果，無論何種類型，都是 Expression 類的實現類。

接下來是兩個具體的運算符號解析器，一個加號解析器和一個減號解析器：

public class AddExpression extends SymbolExpression {
    public AddExpression(Expression left, Expression right) {
        super(left, right);
    }

    @Override
    int interpreter(HashMap<String, Integer> var) {
        return super.left.interpreter(var) + super.right.interpreter(var);
    }
}

public class SubExpression extends SymbolExpression {
    public SubExpression(Expression left, Expression right) {
        super(left, right);
    }

    @Override
    int interpreter(HashMap<String, Integer> var) {
        return super.left.interpreter(var) - super.right.interpreter(var);
    }
}

最後是我們的客戶端類：

public class Client {
    public static void main(String[] args) throws IOException {
        String expStr = getExpStr();
        HashMap<String, Integer> var = getValue(expStr);
        Calculator calculator = new Calculator(expStr);
        System.out.println("運算結果：" + expStr + "=" + calculator.run(var));
    }

    public static String getExpStr() throws IOException {
        System.out.print("請輸入表達式：");
        return (new BufferedReader(new InputStreamReader(System.in))).readLine();
    }

    public static HashMap<String, Integer> getValue(String expStr) throws IOException {
        HashMap<String, Integer> map = new HashMap<>();
        for(char ch : expStr.toCharArray()) {
            if(ch != '+' && ch != '-' ) {
                if(! map.containsKey(String.valueOf(ch))) {
                    System.out.print("請輸入" + String.valueOf(ch) + "的值：");
                    String in = (new BufferedReader(new InputStreamReader(System.in))).readLine();
                    map.put(String.valueOf(ch), Integer.valueOf(in));
                }
            }
        }
        return map;
    }
}

執行結果如下：

請輸入表達式：a+b-c
請輸入a的值：10
請輸入b的值：20
請輸入c的值：13
運算結果：a+b-c=17

解釋器模式在實際的系統開發中使用得非常少，因為它會引起效率、性能以及維護等問題，一般在大中型的框架型項目能夠找到它的身影，如一些數據分析工具、報表設計工具、科學計算工具等。

如果遇到確定要使用解析器的場景，可以考慮一下 Expression4J 、 MESP（Math Expression String Parser）、 Jep 等開源的解析工具包，功能都異常強大，而且非常容易使用，效率也還不錯，實現大多數的數學運算沒有問題，完全自己沒有必要從頭開始編寫解釋器。

Tags: 設計模式