第十七章 解释器模式(Interpreter Pattern)

1 概要

解释器模式(Interpreter Pattern)是一种行为模式(Behavior Design Patters)。它常常用于解释(Interprets)或者翻译(Translate)一种语言。具体的讲，解释器会根据语言的语法结构(Syntax)将其翻译为一棵抽象语法树(Abstract Syntax Tree)，方便程序进一步处理。常见的、能够被解释器高效处理的语言有数学表达式(Mathematical Expression)、正则表达式(Regular Expression)和各种编程语言。例如，一个数学表达式可以翻译为Infix表示法(Infix Notation)，Postfix Notation(又被称为逆波兰式)，或者Prefix Notation(又被称为波兰式)。

2 解释器模式的结构

在解释器模式中有着4个参与方。

1. 抽象表达式(Abstract Expression)定义了表达式的接口。
2. 终结符(Terminal Expression)代表着解释过程中的不可在分的符号。
3. 非终结符(Non-Terminal Expression)代表着解释过程中、还可以分解为更小单位的符号。
4. 客户端(Client)请求将表达式翻译为一棵抽象语法树。

图一 解释器模式结构。

3 解释器示例

我们将使用一个例子来介绍解释器模式的使用方法。在这个例子中，我们将解析和表达"x+y"和"x-y"两种数学表达式。首先，我们先定义表达式的接口Expression，它有唯一的一个成员方法interpret()。

public interface Expression {
    int interpret();
}

类NumberExpression实现了Expression接口。NumberExpression是一种终结符，表示一个整数。

public class NumberExpression implements Expression {
    private Integer number;

    public NumberExpression(String numberStr) {
        this.number = Integer.valueOf(numberStr);
    }

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

类AdditionExpression也实现了Expression接口，表示加法表达式。成员变量left和right分别表示在加号"+"左侧和右侧的表达式。

public class AdditionExpression implements Expression {
    private Expression left = null;
    private Expression right = null;

    public AdditionExpression(Expression left, Expression right) {
        this.left = left;
        this.right = right;
    }

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

    @Override
    public String toString() {
        return this.left.toString() + " + " + this.right.toString();
    }
}

相应的，我们还需要SubtractionExpression来表达减法表达式。

public class SubtractionExpression implements Expression {
    private Expression left = null;
    private Expression right = null;

    public AdditionExpression(Expression left, Expression right) {
        this.left = left;
        this.right = right;
    }

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

    @Override
    public String toString() {
        return this.left.toString() + " - " + this.right.toString();
    }
}

在解析表达式的过程中，我们需要一些方法来帮助我们解析和创建表达式。isOperator()方法判断当前的字符是否为加法或者减法字符。getExpressionObject()方法用于创建加法表达式和减法表达式对象。

public class ParserUtil {
    public static boolean isOperator(String symbol) {
        return Arrays.asList("+", "-").contains(symbol);
    }

    public static Expression getExpressionObject(Expression left, Expression right, String symbol) {
        switch (symbol) {
            case "+":
                return new AdditionExpression(left, right);
            case "-":
                return new SubtractionExpression(left, right);
            default:
                throw new IllegalArgumentException("Invalid Symbol in the Expression");
        }
    }
}

最后，ExpressionParser类展示了表达式解析的过程。在main()函数中，我们将测试表达式"5 3 2 + -"。这是一种逆波兰式表示法，它表示的是表达式：5-(3+2)。

在parse()方法中，示例首先将表达式解析成Token列表。然后，按照顺序访问每个Token。当符号是"+"或者"-"时，我们从堆栈中弹出两个表达式，并创建新的表达式，压入堆栈中。如果不是上述的两个字符，则Token是一个整数。所以，此时，可以直接创建一个NumberExpression对象。所以，parse()方法返回了抽象语法树的根节点。

import java.util.Stack;

public class ExpressionParser {
    private Stack<Expression> stack = new Stack<Expression>();

    public Expression parse(String str){
        // 把表达式转换成Token列表。
        String[] tokenList = str.split(" ");

        for (String symbol : tokenList) {
            if (ParserUtil.isOperator(symbol)) {
                // 如果是符号"+"或者"-"，从栈中弹出两个表达式，组成新的表达式，再压回堆栈。
                Expression leftExpression = stack.pop();
                Expression rightExpression = stack.pop();
                System.out.println("Popped up " + leftExpression.interpret() + " and " + rightExpression.interpret());

                Expression resultExpression = ParserUtil.getExpressionObject(leftExpression, rightExpression, symbol);
                stack.push(resultExpression);
                System.out.println("Pushed to stack " + resultExpression.interpret());
            } else {
                // 如果不是符号"+"或者"-"，则是一个整数。
                Expression numberExpression = new NumberExpression(symbol);
                stack.push(numberExpression);

                System.out.println("Pushed to stack " + numberExpression.interpret());
            } 
        }
        return stack.pop();
    }

    public static void main(String[] args) {
       String input = "5 3 2 + -";
       ExpressionParser expressionParser = new ExpressionParser();
       Expression expression = expressionParser.parse(input);
       System.out.println("Final result is " + expression.interpret());
    }
}

4 应用示例

在Java标准库中也使用了解释器模式。我们将简单介绍java.util.regex.Pattern中的解释器模式。如果读者感兴趣，可自行阅读java.text.Normalizer和java.text.Format。

Pattern是Java标准库提供正则表达式(Regular Expression)功能的一个重要的类。下面的代码使用正则表达式，在字符串中匹配包含字母a和b的子串。正则表达式"a*b"被称为一个Pattern。在生成Pattern对象后，通过调用matcher()方法能够在给定的参数字符串中查找匹配的子串。

Pattern p = Pattern.compile("a*b");
Matcher m = p.matcher("aaaaab");
boolean b = m.matches();

Pattern类使用了解释器模式。在调用compile()方法时，Pattern类会解析传入的字符串，并在内部生成一个正则表达式的语法树。其成员变量pattern保存着一份正则表达式字符串的副本，而成员变量root则指向对应的正则表达式语法树的根结点。

// OpenJDK 15
package java.util.regex;

public final class Pattern implements java.io.Serializable {
    private String pattern;

    transient Node root;
}

在这棵树中，Node是这棵树中所有节点的基类。所有的节点需要覆盖match()成员方法，才能正确的实现字符串匹配的功能。

// OpenJDK 15
// Node是Pattern类的一个内部类，源代码在java/util/regex/Pattern.java文件中
static class Node extends Object {
    boolean match(Matcher matcher, int i, CharSequence seq) {
        ...
    }
}

因为节点的种类很多，我们无法将其一一列出。不过，我们选择介绍一个终结符和一个非终结符。类Caret继承自Node，表示的是正则表达式中的字符^。在正则表达式中，Caret是一个终结符。类似的终结符还有$，由类Dollar表示；可重复的最大、最小次数，由类Curly表示等等。

// OpenJDK 15
// Caret是Pattern类的一个内部类，源代码在java/util/regex/Pattern.java文件中
static final class Caret extends Node {
    boolean match(Matcher matcher, int i, CharSequence seq) {
        ...
    }
}

当出现多种情况，可从中选择其一时，由类Branch表示。例如，当使用了?，表示可出现0次或者1次时，Branch对象可以表示这种情况。类Branch也继承自Node，表示的是一个非终结符。

// OpenJDK 15
// Branch是Pattern类的一个内部类，源代码在java/util/regex/Pattern.java文件中
static final class Branch extends Node {
    boolean match(Matcher matcher, int i, CharSequence seq) {
        ...    
    }
}

5 小结

本章介绍了解释器模式的结构和使用方法。解释器模式主要用于解析和处理数学表达式或者一种语言。解析器模式的优势是它能将语言转化为一颗语法树，方便程序进一步处理。