Java 设计模式——解释器模式

发表于 | 分类于 ，

模式定义

解释器模式（Interpreter Pattern）提供了评估语言的语法或表达式的方式，它属于行为型模式。这种模式实现了一个表达式接口，该接口解释一个特定的上下文。这种模式被用在 SQL 解析、符号处理引擎等。

代码示例

下面这个示例（简单计算器实现），对输入的一段文本（表达式），这里主要支持数字、变量和加法和乘法

  1. 先根据定义的文本规则将其符号化，得到一个符号化列表，同时在最后面加上终止符号，然后返回符号化列表，
  2. 然后根据规则取出token，将其组合解释成表达式。具体规则如下：
    1. 开头必须是变量或者数字；
    2. 先处理乘法在处理加法
  3. 得到表达式后，对表达式进行解析处理，然后得到结果。

具体代码如下：

定义支持的类型（变量、数字、加、乘、空格、终止符）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * 定义符号（空格、数字、加、乘、变量、终止符）
 */
public class Token {
   public enum TokenType {
      SPACE,
      NUMBER,
      ADD,
      MULTIPLY,
      VARIABLE,
      EPSILON, // The end of the entire expression.
   }
   
   private final TokenType type;
   private final String string;
   
   public Token(TokenType type, String string) {
      this.type = type;
      this.string = string;
   }

   @Override
   public String toString() {
      return String.format("(%s, \"%s\")", type, string);
   }

   public TokenType getType() {
      return type;
   }

   public String getString() {
      return string;
   }
   
   public double getAsNumber() throws InterpreterException {
      if (type != TokenType.NUMBER) {
         throw new InterpreterException("Incorrect token type. ");
      }
      return Double.valueOf(string);
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
 * 将输入内容按规则解析成Token列表
 */
public class Tokenizer {
    private static class TokenRule {
        private final Pattern pattern;
        private final TokenType type;

        public TokenRule(String pattern, TokenType type) {
            this.pattern = Pattern.compile(pattern);
            this.type = type;
        }

        public Pattern getPattern() {
            return pattern;
        }

        public TokenType getType() {
            return type;
        }
    }

    private static final List<TokenRule> rules = new ArrayList<TokenRule>();

    static {
        rules.add(new TokenRule("^\\d+(\\.\\d+)?", TokenType.NUMBER));
        rules.add(new TokenRule("^[ \t\n\r]+", TokenType.SPACE));
        rules.add(new TokenRule("^\\+", TokenType.ADD));
        rules.add(new TokenRule("^\\*", TokenType.MULTIPLY));
        rules.add(new TokenRule("^[A-Za-z][A-Za-z0-9]*", TokenType.VARIABLE));
    }

    public static List<Token> tokenize(String exprStr) throws InterpreterException {
        Tokenizer tokenizer = new Tokenizer(exprStr);
        return tokenizer.tokenize();
    }

    private final String exprStr;

    private Tokenizer(String exprStr) {
        this.exprStr = exprStr;
    }

    private List<Token> tokenize() throws InterpreterException {
        List<Token> tokens = new ArrayList<Token>();
        int pos = 0;
        int len = exprStr.length();
        while (pos < len) {
            CharSequence sequence = exprStr.subSequence(pos, len);
            boolean matched = false;
            for (TokenRule rule : rules) {
                Matcher matcher = rule.getPattern().matcher(sequence);
                if (!matcher.find()) {
                    continue;
                }
                matched = true;
                pos += matcher.end();
                TokenType type = rule.getType();
                if (type != TokenType.SPACE) {
                    Token token = new Token(type, matcher.group());
                    tokens.add(token);
                }
                break;
            }
            if (!matched) {
                throw new InterpreterException("Tokenizer error at: \"" + sequence + "\"");
            }
        }
        tokens.add(new Token(TokenType.EPSILON, ""));
        return tokens;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/**
 * 定义词法解析器，根据规则将输入的Tokens转化成待解释的表达式
 */
public class Parser {
    private final List<Token> tokens;
    int next = 0;

    public static Expression parse(List<Token> tokens) throws InterpreterException {
        return new Parser(tokens).parse();
    }

    private Parser(List<Token> tokens) {
        this.tokens = tokens;
    }

    private Expression parse() throws InterpreterException {
        next = 0;
        Expression expression = expression();
        except(TokenType.EPSILON);
        return expression;
    }

    private Expression expression() throws InterpreterException {
        Expression expression = term();// 先乘法
        while (accept(TokenType.ADD)) {// 在加法
            expression = new AddExpression(expression, term());
        }
        return expression;

    }

    private Expression term() throws InterpreterException {
        Expression expression = factor();
        while (accept(TokenType.MULTIPLY)) {
            expression = new MultiplyExpression(expression, term());
        }
        return expression;
    }

    /**
     * 获取 常量或变量表达式
     * @return 常量或变量表达式
     * @throws InterpreterException 不是商量两种类型就抛异常
     */
    private Expression factor() throws InterpreterException {
        if (accept(TokenType.NUMBER)) {
            return new NumberExpression(current().getAsNumber());
        }
        except(TokenType.VARIABLE);
        return new VariableExpression(current().getString());
    }

    /**
     * 获取指定类型Token
     * @param tokenType 获取的token类型
     * @return 如果是期待的类型，返回true，同时更新next指针；不是则返回false；
     */
    private boolean accept(TokenType tokenType) {
        if (tokens.get(next).getType() == tokenType) {
            ++next;
            return true;
        } else {
            return false;
        }
    }

    /**
     * 需要的类型
     * @param tokenType 期待的类型
     * @throws InterpreterException 不是期待的token类型则抛出异常
     */
    private void except(TokenType tokenType) throws InterpreterException {
        if (!accept(tokenType)) {
            throw new InterpreterException(
                    "Parser error. Unexcepted token at: \""
                            + getRemainingString() + "\"");
        }
    }

    /**
     * 当前处理的token
     * @return 当前处理的token
     */
    private Token current() {
        return tokens.get(next - 1);
    }

    private String getRemainingString() {
        StringBuffer buffer = new StringBuffer();
        for (int i = next; i < tokens.size(); ++i) {
            if (i != next)
                buffer.append(" ");
            buffer.append(tokens.get(i).getString());
        }
        return buffer.toString();
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 解释器中心，客户端通过该类进行输入文本的解释，不需要关心具体解释器的实现（类似于中介者）
 */
public class Interpreter {
   
   private final List<Token> tokens;
   private final Expression rootExpression;

   public Interpreter(String expressionString) throws InterpreterException {
      tokens = Tokenizer.tokenize(expressionString);
      rootExpression = Parser.parse(tokens);
   }

   public List<Token> getTokens() {
      return tokens;
   }

   public Expression getRootExpression() {
      return rootExpression;
   }

}

一下部分开始定义表达式

先是接口

1
2
3
4
5
6
/**
 * 定义解释器（表达式）接口
 */
public interface Expression {
    double interpret(Map<String, Double> context) throws InterpreterException;
}

然后是四种类型的解释器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 加法解释器
 */
public class AddExpression implements Expression {

   private final Expression leftExpression; 
   private final Expression rightExpression; 
   
   public AddExpression(Expression leftExpression, Expression rightExpression) {
      this.leftExpression = leftExpression;
      this.rightExpression = rightExpression;
   }

   @Override
   public double interpret(Map<String, Double> context) throws InterpreterException {
      return leftExpression.interpret(context) + rightExpression.interpret(context);
   }

   @Override
   public String toString() {
      return String.format("(%s + %s)", leftExpression, rightExpression);
   }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 乘法解释器实现
 */
public class MultiplyExpression implements Expression {

   private final Expression leftExpression; 
   private final Expression rightExpression; 
   
   public MultiplyExpression(Expression leftExpression, Expression rightExpression) {
      this.leftExpression = leftExpression;
      this.rightExpression = rightExpression;
   }

   @Override
   public double interpret(Map<String, Double> context) throws InterpreterException {
      return leftExpression.interpret(context) * rightExpression.interpret(context);
   }
   
   @Override
   public String toString() {
      return String.format("(%s * %s)", leftExpression, rightExpression);
   }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 数字解释器
 */
public class NumberExpression implements Expression {

    private final double value;

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

    @Override
    public double interpret(Map<String, Double> context) {
        return value;
    }

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

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 变量解释器实现
 */
public class VariableExpression implements Expression {

   private final String name;

   public VariableExpression(String name) {
      this.name = name;
   }

   @Override
   public double interpret(Map<String, Double> context) throws InterpreterException {
      if (context.containsKey(name)) {
         return context.get(name);
      } else {
         throw new InterpreterException("Variable not found: " + name);
      }
   }
   
   @Override
   public String toString() {
      return name;
   }

}

由于可能会存在解释异常，所以定义了一个异常类

1
2
3
4
5
6
7
public class InterpreterException extends Exception {
   private static final long serialVersionUID = 8459803686326291973L;

   public InterpreterException(String message) {
      super(message);
   }
}

编写客户端运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class Main {

    static final boolean VERBOSE_PARSE = true;
    static final boolean VERBOSE_DEBUG = true;
    static final double EPS = 1e-7;
    static final Map<String, Double> context = new HashMap<String, Double>();

    static {
        context.put("age", 18.0);
        context.put("height", 170.0);
    }

    private static void execute(String expressionString, double excepted) {
        System.out.println("Attempting to evaluate: " + expressionString);
        try {
            Interpreter interpreter = new Interpreter(expressionString);
            if (VERBOSE_PARSE) {
                printTokens(interpreter.getTokens());
                System.out.println("Parse tree: "
                        + interpreter.getRootExpression());
            }
            double value = interpreter.getRootExpression().interpret(context);
            boolean correct = Math.abs(value - excepted) < EPS;
            System.out.println(String.format(
                    "* %s!! Excepted: %.4f, evaluated: %.4f",
                    correct ? "Correct" : "Incorrect", excepted, value));
        } catch (InterpreterException e) {
            System.out.println("Error: " + e);
            if (VERBOSE_DEBUG) {
                e.printStackTrace();
            }
        }
    }

    private static void printTokens(List<Token> tokens) {
        StringBuffer buffer = new StringBuffer("Tokens: ");
        for (Token token : tokens) {
            buffer.append(token);
        }
        System.out.println(buffer);
    }

    public static void main(String[] args) {
//    execute("1.5", 1.5);
//    execute("1 + 2 + 3 + 4 + 5", 1 + 2 + 3 + 4 + 5);
//    execute("2 * 3 + 5 * 7", 2 * 3 + 5 * 7);
        execute("age * 10 + height * 1.5", get("age") * 10 + get("height") * 1.5);
    }

    public static double get(String key) {
        return context.get(key);
    }
}

输出结果

1
2
3
4
Attempting to evaluate: age * 10 + height * 1.5
Tokens: (VARIABLE, "age")(MULTIPLY, "*")(NUMBER, "10")(ADD, "+")(VARIABLE, "height")(MULTIPLY, "*")(NUMBER, "1.5")(EPSILON, "")
Parse tree: ((age * 10.0) + (height * 1.5))
* Correct!! Excepted: 435.0000, evaluated: 435.0000

从代码量来看，这个示例还是比较复杂的，由此可见编译器实现的复杂程度。

模式总结

对于一些固定文法构建一个解释句子的解释器。如果一种特定类型的问题发生的频率足够高，那么可能就值得将该问题的各个实例表述为一个简单语言中的句子。这样就可以构建一个解释器，该解释器通过解释这些句子来解决该问题。注意由于解释器模式实现方式通常会或多或少的存在使用迭代（或递归）的场景，所以一定要做好终止条件的判断。

优缺点

  • 优点

    1. 可扩展性比较好，灵活。
    2. 增加了新的解释表达式的方式。
    3. 易于实现简单文法。

  • 缺点

    1. 可利用场景比较少；
    2. 对于复杂的文法比较难维护；
    3. 解释器模式会引起类膨胀；
    4. 解释器模式采用递归调用方法；

使用场景

通常使用在编译器、运算表达式计算中，另外Xml解析、Json解析都或多或少体现了解释器模式的应用。

  1. 可以将一个需要解释执行的语言中的句子表示为一个抽象语法树。
  2. 一些重复出现的问题可以用一种简单的语言来进行表达。
  3. 一个简单语法需要解释的场景。

注意事项

  1. 需要注意构建语法树，定义终结符与非终结符的方式。
  2. 可利用场景比较少，JAVA 中如果碰到可以用 expression4J 代替。
  3. 构建环境类来描述解释器运行的所需的环境，包含解释器之外的一些全局信息，一般是 HashMap。