您當前位置：首頁 > php開源 > php教程 > 解釋器模式(Interpreter)

解釋器模式(Interpreter)

來源：程序員人生發布時間：2016-08-05 13:15:11 閱讀次數：3310次

1、模式動機

如果在系統中某1特定類型的問題產生的頻率很高，此時可以斟酌將這些問題的實例表述為1個語言中的句子，因此可以構建1個解釋器，該解釋器通過解釋這些句子來解決這些問題。

解釋器模式描寫了如何構成1個簡單的語言解釋器，主要利用在使用面向對象語言開發的編譯器中。

2、模式定義

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

3、模式結構

解釋器模式

4、參與者

AbstractExpression: 抽象表達式
TerminalExpression: 終結符表達式
NonterminalExpression: 非終結符表達式
Context: 環境類
Client: 客戶類

5、示例代碼

設計與實現1個4則算術運算解釋器

可以分析任意+、-、*、/表達式，并計算其數值
輸入表達式為1個字符串表達式
輸出結果為雙精度浮點數(Double)

輸入是1個用字符串表達的4則運算，比如 1 + 2 * 3 。目的是試圖去理解這個字符串表達的運算指令，然后計算出結果 7。之所以是1個解釋器 Interpreter，而不是1個編譯器 Compiler，是由于程序是去理解指令并且履行指令，而不是把指令編譯成機器代碼來運行；后者是編譯器的目標。

第1個部份，是截取輸入字符串，然后返回單元指令。比如，對指令 1 + 2 * 3 – 4 / 5，就需要被分解成以下所示的單元指令集：
tokenize

第2個部份，把單元指令集組成1個樹結構，稱之為Abstract Syntax Tree。依照將來需要解釋的順序，優先履行的指令放在樹的葉的位置，最后履行的指令是樹根Root。
parse

程序只有 2 種單元指令：操作數 NumExpression 和 運算符 OpExpression 。
定義了1個抽象類，叫做 Expression，然后NumExpression和 OpExpression 繼承了該抽象類。

Expression

源代碼

package design.pattern;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 運算符枚舉類
 * 
 * @author Administrator
 *
 */
enum Op {
    Plus('+'), Minus('-'), Multiply('*'), Divide('/');

    char value;

    Op(char value) {
        this.value = value;
    }

    static Op getValue(char ch) {
        switch (ch) {
        case '+':
            return Plus;
        case '-':
            return Minus;
        case '*':
            return Multiply;
        case '/':
            return Divide;
        default:
            return null;
        }
    }
}

/**
 * 運算符優先級枚舉類
 * 
 * @author Administrator
 *
 */
enum Prioirty {
    Lv2(2), Lv1(1), Lv0(0);

    int value;

    Prioirty(int value) {
        this.value = value;
    }

    int getValue() {
        return value;
    }
}

/**
 * 抽象表達式
 * 
 * @author Administrator
 *
 */
abstract class Expression {
    abstract public double interpreter(Syntax root);
}

/**
 * 操作數表達式
 * 
 * @author Administrator
 *
 */
class NumExpression extends Expression {
    private double value;

    public NumExpression(double value) {
        this.value = value;
    }

    public double getValue() {
        return value;
    }

    public double interpreter(Syntax root) {
        return ((NumExpression) (root.getExpression())).getValue();
    }

    public String toString() {
        return String.valueOf(value);
    }
}

/**
 * 運算符表達式
 * 
 * @author Administrator
 *
 */
class OpExpression extends Expression {
    private Op value;

    public OpExpression() {
    }

    public OpExpression(Op value) {
        this.value = value;
    }

    public Op getValue() {
        return value;
    }

    public Prioirty getPrioirty() {
        switch (this.value) {
        case Plus:
        case Minus:
            return Prioirty.Lv1;
        case Multiply:
        case Divide:
            return Prioirty.Lv2;
        default:
            return Prioirty.Lv0;
        }
    }

    public double interpreter(Syntax root) {
        double lvalue, rvalue;
        if (root.getLeft() == null)
            lvalue = 0;
        else
            lvalue = ((Expression) root.getLeft().getExpression()).interpreter(root.getLeft());

        if (root.getRight() == null)
            rvalue = 0;
        else
            rvalue = ((Expression) root.getRight().getExpression()).interpreter(root.getRight());

        switch (((OpExpression) root.getExpression()).getValue()) {
        case Plus:
            return lvalue + rvalue;
        case Minus:
            return lvalue - rvalue;
        case Multiply:
            return lvalue * rvalue;
        case Divide:
            return lvalue / rvalue;
        default:
            return 0;
        }
    }

    public String toString() {
        return value.toString();
    }
}

/**
 * 解釋器
 * 
 * @author Administrator
 *
 */
public class Interpreter {
    private Expressionizer expressionizer = new Expressionizer();

    public SyntaxTree eval(String expr) {
        ArrayList<Expression> expressions = expressionizer.parse(expr);
        SyntaxTree astree = new SyntaxTree();

        for (Expression e : expressions) {
            astree.append(e);
        }
        return astree;
    }

    public static void main(String[] args) {

        System.out.println("請輸入表達式");
        Scanner scanner = new Scanner(System.in);
        String exp = scanner.nextLine();
        scanner.close();
        Interpreter interpreter = new Interpreter();
        // 構建語法樹
        SyntaxTree context = interpreter.eval(exp);
        Expression EXP = new OpExpression();
        // 解釋語法樹
        double result = EXP.interpreter(context.getRoot());
        System.out.println(result);
    }
}

/**
 * 語法樹節點類
 * 
 * @author Administrator
 *
 */
class Syntax {
    private Expression expression;
    private Syntax left;
    private Syntax right;

    public Syntax(Expression Expression) {
        this.expression = Expression;
        this.left = null;
        this.right = null;
    }

    public Expression getExpression() {
        return expression;
    }

    public Syntax getLeft() {
        return left;
    }

    public void setLeft(Syntax value) {
        this.left = value;
    }

    public Syntax getRight() {
        return right;
    }

    public void setRight(Syntax value) {
        this.right = value;
    }
}

class SyntaxTree {
    private Syntax root;
    private int count;

    public SyntaxTree() {
        this.root = null;
        this.count = 0;
    }

    public Syntax getRoot() {
        return root;
    }

    public int getCount() {
        return count;
    }

    public void append(Expression expression) {
        this.root = this.append(this.root, expression);
        this.count++;
    }

    /**
     * 添加表達式節點到語法樹root中
     * 
     * @param root
     *            語法樹根節點
     * @param expression
     *            表達式
     * @return 語法樹新的根節點
     */
    private Syntax append(Syntax root, Expression expression) {
        // 第1次添加節點
        if (root == null) {
            Syntax newNode = new Syntax(expression);
            root = newNode;
            return root;
        }
        // 添加操作數
        if (expression instanceof NumExpression) {
            // 如果根節點為運算符，則把操作數添加到右端，否則疏忽
            if (root.getExpression() instanceof OpExpression) {
                // 如果右子樹為空則直接添加為右節點
                if (root.getRight() == null) {
                    Syntax newNode = new Syntax(expression);
                    root.setRight(newNode);
                    return root;
                } else {
                    // 右子樹不為空，作為新的語法樹繼續添加
                    root.setRight(this.append(root.getRight(), expression));
                    return root;
                }
            }
            // 添加運算符
        } else if (expression instanceof OpExpression) {
            // 如果根節點為操作數，則新的運算符為根節點，操作數加到左端
            if (root.getExpression() instanceof NumExpression) {
                Syntax newRoot = new Syntax(expression);
                newRoot.setLeft(root);
                root = newRoot;
                return newRoot;
                // 如果根節點為運算符，則根據優先級添加新的運算符到語法樹
            } else if (root.getExpression() instanceof OpExpression) {
                OpExpression expression1 = (OpExpression) expression;
                OpExpression expression2 = (OpExpression) root.getExpression();
                // 新的運算符優先級低于根節點，則將新運算符作為根節點，舊的根加到左端
                if (expression1.getPrioirty().getValue() <= expression2.getPrioirty().getValue()) {
                    Syntax newRoot = new Syntax(expression1);
                    newRoot.setLeft(root);
                    root = newRoot;
                    return newRoot;
                } else {
                    // 新的運算符優先級高于根節點，需要優先運算，則添加到根節點的右子樹
                    root.setRight(append(root.getRight(), expression));
                    return root;
                }
            }
        }
        return root;
    }
}

class Expressionizer {
    private static Character[] Ops = { '+', '-', '*', '/' };
    // private static Character[] Spaces = { ' ', '\0', '\t', '\n', '\r' };

    String getStringRepresentation(ArrayList<Character> list) {
        StringBuilder builder = new StringBuilder(list.size());
        for (Character ch : list) {
            builder.append(ch);
        }
        return builder.toString();
    }

    /**
     * 將字符串轉化為表達式序列
     *
     */
    public ArrayList<Expression> parse(String value) {
        ArrayList<Expression> list = new ArrayList<Expression>();
        ArrayList<Character> buff = new ArrayList<>();

        for (int i = 0; i < value.length(); i++) {
            char ch = value.charAt(i);
            if (ch >= '0' && ch <= '9') {
                buff.add(ch);
            } else if (ch == '.') {
                buff.add('.');
            } else {
                OpExpression expression = null;
                // 查找運算符是不是在Ops表中
                if (Arrays.asList(Ops).indexOf(ch) >= 0) {
                    expression = new OpExpression(Op.getValue(ch));
                }
                // 當前表達式為運算符，則buff中寄存的數字字符序列為1個單獨的操作數
                if (buff.size() > 0) {
                    double num = Double.parseDouble(getStringRepresentation(buff));
                    Expression expression1 = new NumExpression(num);
                    list.add(expression1);
                    buff.clear();
                }
                if (expression != null) {
                    list.add(expression);
                }
            }
        }
        // 最后留下的1個數字
        if (buff.size() > 0) {
            double num = Double.parseDouble(getStringRepresentation(buff));
            Expression Expression1 = new NumExpression(num);
            list.add(Expression1);
            buff.clear();
        }
        // for (Expression c : list)
        // System.out.println(c);
        return list;
    }
}

分析
從最簡單的情況開始斟酌：分析 1 + 2 + 3 + 4
首先，AST 樹是空的， Root = NULL。
當把 NumExpression 1 插入樹的時候，設置該 Expression 為根。
當把 OpExpression + 插入樹的時候，需要移動把 + 設置成根：

當把 NumExpression 2 插入樹的時候，就把數字 2 插入樹的右邊：

當把 OpExpression + 插入樹的時候（同級別的操作符，順序是左到右），我們就需要把最新的 OpExpression 設置成根，當前樹設置成新根的左邊：

我們可以得出1個很重要的法則：插入1個新的操作符進入 AST 樹的時候，若是樹的根是1個操作符，并且和此新操作符同級，運算順序是由左至右的話，那末新的操作符會成為新的樹的根，現有的樹會成為新樹的左子樹。
假定要插入的操作符不是 +，而是1個優先權比較高的 * 呢？也就是，若是 1 + 2 * 3 的話，AST 會是甚么模樣？
這類情況下，乘法運算符必須移動到樹的右子樹上，并且成為右子樹的根。原右子樹會成為新的右子樹的左子樹。

6、模式分析

解釋器模式描寫了如作甚簡單的語言定義1個文法，如何在該語言中表示1個句子，和如何解釋這些句子。

文法規則實例
expression ::= value | symbol
symbol ::= expression ‘+’ expression | expression ‘-‘
value ::= an integer //1個整數值
在文法規則定義中可使用1些符號來表示不同的含義，如使用“|”表示或，使用“{”和“}”表示組合，使用“*”表示出現0次或屢次等。
抽象語法樹
除使用文法規則來定義1個語言，在解釋器模式中還可以通過1種稱之為抽象語法樹(Abstract Syntax Tree, AST)的圖形方式來直觀地表示語言的構成，每棵抽象語法樹對應1個語言實例。

抽象語法樹描寫了如何構成1個復雜的句子，通過對抽象語法樹的分析，可以辨認出語言中的終結符和非終結符類。

在解釋器模式中，每種終結符和非終結符都有1個具體類與之對應，正由于使用類來表示每個語法規則，使得系統具有較好的擴大性和靈活性。

優點
- 易于改變和擴大文法。
- 易于實現文法。
- 增加了新的解釋表達式的方式。
缺點
- 對復雜文法難以保護。
- 履行效力較低。
- 利用場景很有限。
模式使用
- 可以將1個需要解釋履行的語言中的句子表示為1個抽象語法樹。
- 1些重復出現的問題可以用1種簡單的語言來進行表達。
- 文法較為簡單。
- 效力不是關鍵問題。
模式利用
- 解釋器模式在使用面向對象語言實現的編譯器中得到了廣泛的利用，如Smalltalk語言的編譯器。
- 目前有1些基于Java抽象語法樹的源代碼處理工具，如在Eclipse中就提供了Eclipse AST，它是Eclipse JDT的1個重要組成部份，用來表示Java語言的語法結構，用戶可以通過擴大其功能，創建自己的文法規則。
- 可使用解釋器模式，通過C++、Java、C#等面向對象語言開發簡單的編譯器，如數學表達式解析器、正則表達式解析器等，用于增強這些語言的功能，使之增加1些新的文法規則，用于解釋1些特定類型的語句。
- 在實際項目開發中如果需要解析數學公式，不必再應用解釋器模式進行設計，可以直接使用1些第3方解析工具包，它們可以統稱為數學表達式解析器(Math Expression Parser, MEP)，如Expression4J、Jep、JbcParser、Symja、Math Expression String Parser(MESP)等來取代解釋器模式，它們可以方便地解釋1些較為復雜的文法，功能強大，且使用簡單，效力較好。

7、模式總結

解釋器模式定義語言的文法，并且建立1個解釋器來解釋該語言中的句子，這里的“語言”意思是使用規定格式和語法的代碼，它是1種類行動型模式。
解釋器模式主要包括以下4個角色
- 在抽象表達式中聲明了抽象的解釋操作，它是所有的終結符表達式和非終結符表達式的公共父類；
- 終結符表達式是抽象表達式的子類，它實現了與文法中的終結符相干聯的解釋操作；
- 非終結符表達式也是抽象表達式的子類，它實現了文法中非終結符的解釋操作；
- 環境類又稱為上下文類，它用于存儲解釋器以外的1些全局信息。
對1個簡單的語言可使用1些文法規則來進行定義，還可以通過抽象語法樹的圖形方式來直觀地表示語言的構成，每棵抽象語法樹對應1個語言實例。
解釋器模式的主要優點
- 易于改變和擴大文法
- 易于實現文法并增加了新的解釋表達式的方式
其主要缺點是對復雜文法難以保護，履行效力較低且利用場景很有限。
解釋器模式適用情況包括
- 可以將1個需要解釋履行的語言中的句子表示為1個抽象語法樹；
- 1些重復出現的問題可以用1種簡單的語言來進行表達；
- 文法較為簡單且效力不是關鍵問題。