17、解释器模式（Interpreter Pattern）

1. 解释器模式

1.1 简介

Interpreter(解释器)模式是对特定的计算机程序设计语言，用来解释预先定义的文法。Interpreter模式是一种简单的语法解释器，属于行为模式。给定一个语言，定义它的文法的一种表示，并定义一个解释器，这个解释器使用该表示来解释语言中的句子。

编译原理上的编译器分为词法分析器、语法分析器、语义分析器、中间代码优化器以及最终的最终代码生成器几个部分。而这个解释器其实就是完成了对语法的解析，将一个个的词组解释成了一个个语法范畴，之后拿来使用。Interpreter模式的目的就是使用一个解释器为用户提供一个一门定义语言的语法表示的解释器，然后通过这个解释器来解释语言中的句子。提供了一个实现语法解释器的框架。

Interpreter(解释器)模式大多用来解释一些(自定义的)独特语法，例如某些游戏开发引擎中读取XML文件，或是WindowsPhone开发中的XAML文件，都是使用此模式来进行的。与其说是一种模式，不如说是一种具有通用规范的行为更为准确。

1.2 结构

Interpreter 模式uml：

Interpreter 模式uml.png

Interpreter 模式角色：

AbstractInterpreter 定义interpret操作，声明一个所有的具体表达式都需要实现的抽象接口；这个接口主要是一个interpret()方法，称做解释操作。
TerminalInterpreter 终态节点，实现了抽象表达式所要求的接口；文法中的每一个终结符都有一个具体终结表达式与之相对应。比如公式R=R1+R2，R1和R2就是终结符，对应的解析R1和R2的解释器就是终结符表达式。
NonTerminalInterpreter 非终态节点，内部调用其他的Interpreter。文法中的每一条规则都需要一个具体的非终结符表达式，非终结符表达式一般是文法中的运算符或者其他关键字，比如公式R=R1+R2中，“+"就是非终结符，解析“+”的解释器就是一个非终结符表达式。
Context 上下文对象，存放所有Interpreter共享的信息。一般是用来存放文法中各个终结符所对应的具体值，比如R=R1+R2，给R1赋值100，给R2赋值200，这些信息需要存放到环境中。

2. Interpreter 模式示例

Interpreter 模式的示例代码很简单，只是为了说明模式的组织和使用，实际的解释Interpret 逻辑没有实际提供。

Interpreter模式和Composite模式相似，最终将构造为一颗语法树。以算术表达式"20(3+1)-45+3"为例，用Interpreter 模式写一个计算表达式的示例。

Interpreter接口：

public interface Interpreter {
    double calculate(String expression);
}

终态Interpreter：

public class Number implements Interpreter {

    private double number;

    public Number(double number) {
        super();
        this.number = number;
    }

    @Override
    public double calculate(String expression) {
        return number;
    }

}

非终态加法Interpreter：

public class Add implements Interpreter {

    private Interpreter left;

    private Interpreter right;

    public Add(Interpreter left, Interpreter right) {
        this.left = left;
        this.right = right;
    }

    @Override
    public double calculate(String expression) {
        return left.calculate(expression) + right.calculate(expression);
    }

}

解释器ParserInterpreter（解析算术表达式，构造语法树）：

public class ParserInterpreter implements Interpreter {

    @Override
    public double calculate(String expression) { //1 * (2 + 3)
        StringBuilder number = new StringBuilder();
        LinkedList<Interpreter> interpreters = new LinkedList<>();
        LinkedList<Character> operators = new LinkedList<>();
        for (char ch : expression.toCharArray()) {
            if (isOperator(ch)) {
                //将之前的数字入栈
                if (number.length() > 0) {
                    interpreters.add(new Number(Double.parseDouble(number.toString())));
                    number.setLength(0);
                }
                //组装表达式
                while (interpreters.size() >= 2) {
                    Character lastOp = operators.getLast();
                    //碰到左括号
                    if (isOpenParen(lastOp)) {
                        break;
                    }
                    //碰到了运算符，但下一个运算符优先级是否更高？
                    if (rightOperatorGreater(lastOp, ch)) {
                        break;
                    }
                    Interpreter right = interpreters.removeLast();
                    Interpreter left = interpreters.removeLast();
                    Interpreter interpreter = constructExpression(left, 
                            operators.removeLast(), right);
                    interpreters.addLast(interpreter);
                }
                if (isCloseParen(ch)) {
                    //碰到右括号，直接去掉左括号
                    operators.removeLast();
                } else {
                    //非右括号，直接进栈
                    operators.addLast(ch);
                }
            } else {
                number.append(ch);
            }
        }
        //最后是数字，如1*2+3
        if (number.length() > 0) {
            interpreters.add(new Number(Double.parseDouble(number.toString())));
            number.setLength(0);
        }
        //最后一次运算
        if (operators.size() > 0) {
            Interpreter right = interpreters.removeLast();
            Interpreter left = interpreters.removeLast();
            Interpreter interpreter = constructExpression(left, 
                    operators.removeLast(), right);
            interpreters.addLast(interpreter);
        }
        //调用组装好的树
        return interpreters.pop().calculate(expression);
    }
    
    /**
     * 右边运算符是否优先级更高
     */
    private boolean rightOperatorGreater(char leftOp, char rightOp) {
        if (rightOp == '*' || rightOp == '/') {
            return leftOp == '+' || leftOp == '-';
        }
        return false;
    }
    
    private boolean isOperator(char ch) {
        return ch == '-' || ch == '+' || ch == '/' || ch == '*' || ch == '(' || ch ==')';
    }
    
    private boolean isOpenParen(char ch) {
        return ch == '(';
    }
    
    private boolean isCloseParen(char ch) {
        return ch == ')';
    }
    
    private Interpreter constructExpression(Interpreter left, char op, Interpreter right) {
        switch (op) {
        case '+' :
            return new Add(left, right);
        case '-' :
            return new Sub(left, right);
        case '*' :
            return new Plus(left, right);
        case '/' :
            return new Divide(left, right);
        default:
            break;
        }
        return null;
    }

}

调用示例：

    public static void main(String[] args) {
        ParserInterpreter interpreter = new ParserInterpreter();
        double result = interpreter.calculate("20*(3+1)-4*5+3");
        System.out.println("计算结果为: " + result);
    }

3. 总结

Interpreter 模式优点：

易于改变和扩展文法。由于在解释器模式中使用类来表示语言的文法规则，因此可以通过继承等机制来改变或扩展文法。
每一条文法规则都可以表示为一个类，因此可以方便地实现一个简单的语言。
实现文法较为容易。在抽象语法树中每一个表达式节点类的实现方式都是相似的，这些类的代码编写都不会特别复杂，还可以通过一些工具自动生成节点类代码。
增加新的解释表达式较为方便。如果用户需要增加新的解释表达式只需要对应增加一个新的终结符表达式或非终结符表达式类，原有表达式类代码无须修改，符合“开闭原则”。

Interpreter 模式缺点：

对于复杂文法难以维护。在解释器模式中，每一条规则至少需要定义一个类，因此如果一个语言包含太多文法规则，类的个数将会急剧增加，导致系统难以管理和维护，此时可以考虑使用语法分析程序等方式来取代解释器模式。
执行效率较低。由于在解释器模式中使用了大量的循环和递归调用，因此在解释较为复杂的句子时其速度很慢，而且代码的调试过程也比较麻烦。