解释器模式

简介

Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language.
给定一门语言，定义它的文法的一种表示，并定义一个解释器，该解释器使用该表示来解释语言中的句子。

解释器模式（Interpreter Pattern）是一种按照规定的语法（文法）进行解析的模式。

就比如编译器可以将源码编译解释为机器码，让 CPU 能进行识别并运行。解释器模式 的作用其实与编译器一样，都是将一些固定的文法（即语法）进行解释，构建出一个解释句子的解释器。

简单理解，解释器是一个简单语法分析工具，它可以识别句子语义，分离终结符号和非终结符号，提取出需要的信息，让我们能针对不同的信息做出相应的处理。

解释器模式 核心：识别文法，构建解释。

主要解决

如果存在一种特定类型的问题，该类型问题涉及多个不同实例，但是具备固定文法描述，那么可以使用 解释器模式 对该类型问题进行解释，分离出需要的信息，根据获取的信息做出相应的处理。

简而言之，对于一些固定文法构建一个解释句子的解释器。

优缺点

优点

• 扩展性强：在 解释器模式 中由于语法是由很多类表示的，当语法规则更改时，只需修改相应的非终结符表达式即可；若扩展语法时，只需添加相应非终结符类即可；
• 增加了新的解释表达式的方式；
• 易于实现文法：解释器模式 对应的文法应当是比较简单且易于实现的，过于复杂的语法并不适合使用 解释器模式 ；

缺点

• 语法规则较复杂时，会引起类膨胀：解释器模式 每个语法都要产生一个非终结符表达式，当语法规则比较复杂时，就会产生大量的解释类，增加系统维护困难；
• 执行效率比较低：解释器模式 采用递归调用方法，每个非终结符表达式只关心与自己有关的表达式，每个表达式需要知道最终的结果，因此完整表达式的最终结果是通过从后往前递归调用的方式获取得到。当完整表达式层级较深时，解释效率下降，且出错时调试困难，因为递归迭代层级太深；

使用场景

• 一些重复出现的问题可以用一种简单的语言来进行表达；
• 一个简单语法需要解释的场景；

模式讲解

首先来看下 解释器模式 的通用 UML 类图：

解释器模式

从 UML 类图中，我们可以看到，解释器模式 主要包含四种角色：

• 抽象表达式（Expression）：负责定义一个解释方法interpret，交由具体子类进行具体解释；
• 终结符表达式（TerminalExpression）：实现文法中与终结符有关的解释操作。文法中的每一个终结符都有一个具体终结表达式与之相对应，比如公式 R=R1+R2，R1 和 R2 就是终结符，对应的解析 R1 和 R2 的解释器就是终结符表达式。通常一个 解释器模式 中只有一个终结符表达式，但有多个实例，对应不同的终结符（R1，R2）；
• 非终结符表达式（NonterminalExpression）：实现文法中与非终结符有关的解释操作。文法中的每条规则都对应于一个非终结符表达式。非终结符表达式一般是文法中的运算符或者其他关键字，比如公式 R=R1+R2 中，“+"就是非终结符，解析“+”的解释器就是一个非终结符表达式。非终结符表达式根据逻辑的复杂程度而增加，原则上每个文法规则都对应一个非终结符表达式；
• 上下文环境类（Context）：包含解释器之外的全局信息。它的任务一般是用来存放文法中各个终结符所对应的具体值，比如 R=R1+R2，给 R1 赋值100，给 R2 赋值200，这些信息需要存放到环境中；

以下是 解释器模式 的通用代码：

class Client {
    public static void main(String[] args) {
        Context context = new Context();
        // 定义一个语法容器，用于存储一个具体表达式
        Stack<IExpression> stack = new Stack<>();
        for (;;) {
            // 进行语法解析，并产生递归调用
        }
        // 获取得到最终的解析表达式：完整语法树
        IExpression expression = stack.pop();
        // 递归调用获取结果
        expression.interpret(context);

    }

    // 上下文环境类
    static class Context extends HashMap {

    }

    // 抽象表达式
    interface IExpression {
        // 对表达式进行解释
        Object interpret(Context context);
    }

    // 终结符表达式
    static class TerminalExpression implements IExpression {

        @Override
        public Object interpret(Context context) {
            // 实现文法中与终结符有关的操作
            return null;
        }

    }

    // 非终结符表达式
    static class NonterminalExpression implements IExpression {
        public NonterminalExpression(IExpression... expression) {
            // 每个非终结符表达式都会对其他表达式产生依赖
        }

        @Override
        public Object interpret(Context context) {
            // 进行文法处理
            return null;
        }
    }
}

举个例子

例子：请用代码实现表达式求值：a + b - c...

分析：表达式 a + b - c...，我们把整个表达式看成是一个固定格式的文法，其中，a b c 是终结符，+ - 是非终结符。

具体代码如下：

class Client {
    public static void main(String[] args) {
        System.out.println("result: " + new Calculator("10 + 30").calculate());
        System.out.println("result: " + new Calculator("10 + 30 - 20").calculate());
        System.out.println("result: " + new Calculator("10 + 30 - 20 + 15").calculate());
    }

    interface IArithmeticExpression {
        int interpret();
    }

    static class NumExpression implements IArithmeticExpression {
        private int value;

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

        @Override
        public int interpret() {
            return this.value;
        }
    }

    static abstract class OperatorExpression implements IArithmeticExpression {

        protected IArithmeticExpression left;
        protected IArithmeticExpression right;

        public OperatorExpression(IArithmeticExpression left, IArithmeticExpression right) {
            this.left = left;
            this.right = right;
        }
    }

    static class AddExpression extends OperatorExpression {
        public AddExpression(IArithmeticExpression left, IArithmeticExpression right) {
            super(left, right);
        }

        @Override
        public int interpret() {
            return this.left.interpret() + this.right.interpret();
        }
    }

    static class SubtractionExpression extends OperatorExpression {
        public SubtractionExpression(IArithmeticExpression left, IArithmeticExpression right) {
            super(left, right);
        }

        @Override
        public int interpret() {
            return this.left.interpret() - this.right.interpret();
        }
    }

    static class Calculator {
        private Stack<IArithmeticExpression> stack = new Stack<>();

        public Calculator(String expression) {
            this.analyse(expression);
        }

        private void analyse(String expression) {
            String[] elements = expression.split(" ");
            IArithmeticExpression leftExpr, rightExpr;
            for (int i = 0, len = elements.length; i < len; ++i) {
                switch (elements[i]) {
                case "+":
                    leftExpr = this.stack.pop();
                    rightExpr = new NumExpression(Integer.valueOf(elements[++i]));
                    this.stack.push(new AddExpression(leftExpr, rightExpr));
                    break;
                case "-":
                    leftExpr = this.stack.pop();
                    rightExpr = new NumExpression(Integer.valueOf(elements[++i]));
                    this.stack.push(new SubtractionExpression(leftExpr, rightExpr));
                    break;
                default:
                    this.stack.push(new NumExpression(Integer.valueOf(elements[i])));
                    break;
                }
            }
        }

        public int calculate() {
            return this.stack.pop().interpret();
        }
    }
}

注：这里为了方便，我们直接传入具体表达式（表达式格式要求每个元素之间使用空格隔开），省略了使用 Context 存储额外信息。