解释器模式

定义

解释器模式使用频率并不高，通常用来描述如何构建一个简单“语言”的语法解释器。它只在一些非常特定的领域被用到，比如编译器、规则引擎、正则表达式、SQL 解析等。不过，了解它的实现原理同样很重要，可以帮助我们思考如何通过更简单的规则来表达复杂的逻辑。

解释器模式（Interpreter pattern）的原始定义是：用于定义语言的语法规则表示，并提供解释器来处理句子中的语法

假设设计了一个软件用来进行加减计算，我们第一想法是使用工具类，提供对应的加法和减法的工具方法。

//用于两个整数相加的方法
public static int add(int a, int b) {
    return a + b;
}
// 用于三个整数相加的方法
public static int add(int a, int b, int c) {
    return a + b + c;
}
// 用于多个整数相加的方法
public static int add(int... args) {
    int sum = 0;
    for (int arg : args) {
        sum += arg;
    }
    return sum;
}

上面的形式比较单一、有限，如果形式变化非常多，这就不符合要求，因为加法和减法运算，两个运算符与数值可以有无限种组合方式。比如 5-3+2-1,10-5+20 ...

文法规则和抽象语法树

解释器模式描述了如何为简单的语言定义一个文法，如何在该语言中表达一个句子，以及如何解释这些句子。

在上面提到的加法/减法解释器，每一个输入表达式（比如 2+3+4-5）都包含了 3 个语言单位，可以使用下面的文法规则定义：

文法是用于描述语言的语法结构的形式规则：

expression ::=value | plus | minus
plus ::= expression + expression
minus ::= expression - expression
value ::= number

注意：这里的符号 ::= 表示 定义为 的意思，竖线 | 表示 或，左右的其中一个，引号内为字符本身，引号外为语法。

上面的规则描述为：表达式可以是一个值，也可以是 plus 或者 minus 运算，而 plus 和 minus 又是由表达式组合运算符构成，值的类型为整数型。

抽象语法树

在解释器模式中还可以通过一种称为抽象语法树的图形方式来直观的表达语言的构成，每一棵抽象语法树对应一个语言实例，例如加法/减法表达式语言中的语句 1+2+3-4+1 可以通过下面的抽象语法树表示：

模式原理

• 抽象表达式角色（AbstractExpression）：定义解释器接口，约定解释器规范，主要包含解释方法 interpret() 方法
• 终结符表达式角色（TerminalExpression）： 分为了终结符表达式和非终结符表达式，分别对应文法规则中的终结符和非终结符,文法中的每一个终结符都有一个具体的终结符表达式与之对应（value）。
• 非终结符表达式角色（NonTerminalExpression）：非终结符表达式，文法中的每一个非终结符都有一个具体的非终结符表达式与之对应, 文法中的每条规则都对应一个非终结符表达式。
• 上下文(Context)： 包含了各个解释器需要的数据或者是公共的功能，一般是用来传递所有解释器共享的数据。
• 客户端 （Client）： 主要任务是将需要分析的句子或者表达式转换成使用解释器对象描述的语法树，然后调用解释器的解释方法，当然也可以通过环境角色间接访解释器的解释方法。

解释器模式实现

定义一个进行加减乘除计算的语言，语法规则如下：

• 运算符只包含加、减、乘、除，并且没有优先级的概念。
• 表达式中，先书写数组，后书写运算符，空格隔开；

比如 9 5 7 3 - + * 这样一个表达式，按照上面的语法规则来处理，取出数字 9、5 和 - 运算符号，计算得到 4 ， 于是表达式变成了 4 7 3 + *。 然后，再取出 4 7 和 + 运算符，计算得到 11，表达式变成了 11 3 + *。 最后，取出 11 3 和 + 运算符，计算得到 14，表达式变成了 14 *。 最后，取出 14 和 * 运算符，计算得到 42。

1. 不使用解释器模式的实现

传统的实现方式使用栈来解析后缀表达式：

import java.util.Stack;

/**
 * 传统方式实现后缀表达式计算器
 * 不使用解释器模式，直接使用栈进行解析
 */
public class PostfixCalculator {
    
    /**
     * 计算后缀表达式
     * @param expression 后缀表达式，如 "9 5 7 3 - + *"
     * @return 计算结果
     */
    public static int evaluate(String expression) {
        Stack<Integer> stack = new Stack<>();
        String[] tokens = expression.trim().split("\\s+");
        
        for (String token : tokens) {
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else if (isOperator(token)) {
                if (stack.size() < 2) {
                    throw new IllegalArgumentException("表达式格式错误：操作数不足");
                }
                int b = stack.pop();
                int a = stack.pop();
                int result = performOperation(a, b, token);
                stack.push(result);
            } else {
                throw new IllegalArgumentException("未知的符号: " + token);
            }
        }
        
        if (stack.size() != 1) {
            throw new IllegalArgumentException("表达式格式错误：操作符不足");
        }
        
        return stack.pop();
    }
    
    private static boolean isNumber(String token) {
        try {
            Integer.parseInt(token);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }
    
    private static boolean isOperator(String token) {
        return "+".equals(token) || "-".equals(token) || 
               "*".equals(token) || "/".equals(token);
    }
    
    private static int performOperation(int a, int b, String operator) {
        switch (operator) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/": 
                if (b == 0) {
                    throw new ArithmeticException("除数不能为零");
                }
                return a / b;
            default:
                throw new IllegalArgumentException("不支持的运算符: " + operator);
        }
    }
    
    public static void main(String[] args) {
        String expression = "9 5 7 3 - + *";
        try {
            int result = evaluate(expression);
            System.out.println("表达式: " + expression);
            System.out.println("结果: " + result);
        } catch (Exception e) {
            System.err.println("计算错误: " + e.getMessage());
        }
    }
}

传统实现的缺点：

• 所有逻辑都集中在一个方法中，难以扩展
• 添加新的运算符需要修改 performOperation 方法
• 缺乏抽象层次，难以理解表达式的结构
• 违反开闭原则

2. 使用解释器模式的实现

使用解释器模式，我们可以将表达式抽象为语法树，每个节点都是一个解释器：

import java.util.List;
import java.util.ArrayList;

/**
 * 抽象表达式接口
 */
interface Expression {
    int interpret(Context context);
}

/**
 * 上下文类，存储解释器需要的共享数据
 */
class Context {
    private List<String> tokens;
    private int position;
    
    public Context(String expression) {
        this.tokens = new ArrayList<>();
        String[] parts = expression.trim().split("\\s+");
        for (String part : parts) {
            tokens.add(part);
        }
        this.position = 0;
    }
    
    public boolean hasNext() {
        return position < tokens.size();
    }
    
    public String next() {
        if (hasNext()) {
            return tokens.get(position++);
        }
        throw new IllegalStateException("没有更多的符号");
    }
    
    public String peek() {
        if (hasNext()) {
            return tokens.get(position);
        }
        throw new IllegalStateException("没有更多的符号");
    }
    
    public void reset() {
        position = 0;
    }
}

/**
 * 终结符表达式 - 数字
 */
class NumberExpression implements Expression {
    private int value;
    
    public NumberExpression(int value) {
        this.value = value;
    }
    
    @Override
    public int interpret(Context context) {
        return value;
    }
    
    @Override
    public String toString() {
        return String.valueOf(value);
    }
}

/**
 * 非终结符表达式 - 加法
 */
class AddExpression implements Expression {
    private Expression left;
    private Expression right;
    
    public AddExpression(Expression left, Expression right) {
        this.left = left;
        this.right = right;
    }
    
    @Override
    public int interpret(Context context) {
        return left.interpret(context) + right.interpret(context);
    }
    
    @Override
    public String toString() {
        return "(" + left + " + " + right + ")";
    }
}

/**
 * 非终结符表达式 - 减法
 */
class SubtractExpression implements Expression {
    private Expression left;
    private Expression right;
    
    public SubtractExpression(Expression left, Expression right) {
        this.left = left;
        this.right = right;
    }
    
    @Override
    public int interpret(Context context) {
        return left.interpret(context) - right.interpret(context);
    }
    
    @Override
    public String toString() {
        return "(" + left + " - " + right + ")";
    }
}

/**
 * 非终结符表达式 - 乘法
 */
class MultiplyExpression implements Expression {
    private Expression left;
    private Expression right;
    
    public MultiplyExpression(Expression left, Expression right) {
        this.left = left;
        this.right = right;
    }
    
    @Override
    public int interpret(Context context) {
        return left.interpret(context) * right.interpret(context);
    }
    
    @Override
    public String toString() {
        return "(" + left + " * " + right + ")";
    }
}

/**
 * 非终结符表达式 - 除法
 */
class DivideExpression implements Expression {
    private Expression left;
    private Expression right;
    
    public DivideExpression(Expression left, Expression right) {
        this.left = left;
        this.right = right;
    }
    
    @Override
    public int interpret(Context context) {
        int rightValue = right.interpret(context);
        if (rightValue == 0) {
            throw new ArithmeticException("除数不能为零");
        }
        return left.interpret(context) / rightValue;
    }
    
    @Override
    public String toString() {
        return "(" + left + " / " + right + ")";
    }
}

/**
 * 表达式解析器 - 构建抽象语法树
 */
class ExpressionParser {
    
    public Expression parse(String expression) {
        Context context = new Context(expression);
        return parseExpression(context);
    }
    
    private Expression parseExpression(Context context) {
        if (!context.hasNext()) {
            throw new IllegalArgumentException("表达式为空");
        }
        
        String token = context.next();
        
        // 如果是数字，创建数字表达式
        if (isNumber(token)) {
            return new NumberExpression(Integer.parseInt(token));
        }
        
        // 如果是运算符，需要两个操作数
        if (isOperator(token)) {
            Expression left = parseExpression(context);
            Expression right = parseExpression(context);
            
            switch (token) {
                case "+": return new AddExpression(left, right);
                case "-": return new SubtractExpression(left, right);
                case "*": return new MultiplyExpression(left, right);
                case "/": return new DivideExpression(left, right);
                default:
                    throw new IllegalArgumentException("不支持的运算符: " + token);
            }
        }
        
        throw new IllegalArgumentException("未知的符号: " + token);
    }
    
    private boolean isNumber(String token) {
        try {
            Integer.parseInt(token);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }
    
    private boolean isOperator(String token) {
        return "+".equals(token) || "-".equals(token) || 
               "*".equals(token) || "/".equals(token);
    }
}

/**
 * 客户端 - 使用解释器模式的计算器
 */
public class InterpreterCalculator {
    
    public static void main(String[] args) {
        String expression = "9 5 7 3 - + *";
        
        try {
            // 创建解析器
            ExpressionParser parser = new ExpressionParser();
            
            // 解析表达式，构建抽象语法树
            Expression syntaxTree = parser.parse(expression);
            
            // 创建上下文
            Context context = new Context(expression);
            
            // 解释执行
            int result = syntaxTree.interpret(context);
            
            System.out.println("表达式: " + expression);
            System.out.println("语法树: " + syntaxTree);
            System.out.println("结果: " + result);
            
            // 演示如何轻松扩展新的运算符
            demonstrateExtension();
            
        } catch (Exception e) {
            System.err.println("计算错误: " + e.getMessage());
        }
    }
    
    /**
     * 演示如何轻松扩展新的运算符
     */
    private static void demonstrateExtension() {
        System.out.println("\n=== 扩展性演示 ===");
        
        // 可以轻松添加新的运算符，比如幂运算
        class PowerExpression implements Expression {
            private Expression base;
            private Expression exponent;
            
            public PowerExpression(Expression base, Expression exponent) {
                this.base = base;
                this.exponent = exponent;
            }
            
            @Override
            public int interpret(Context context) {
                return (int) Math.pow(base.interpret(context), exponent.interpret(context));
            }
            
            @Override
            public String toString() {
                return "(" + base + " ^ " + exponent + ")";
            }
        }
        
        // 创建简单的幂运算表达式
        Expression powerExpr = new PowerExpression(
            new NumberExpression(2), 
            new NumberExpression(3)
        );
        
        Context context = new Context("2 3 ^");
        int powerResult = powerExpr.interpret(context);
        System.out.println("幂运算: " + powerExpr + " = " + powerResult);
    }
}

解释器模式的优点：

• 结构清晰：每个表达式都是一个独立的类，职责单一
• 易于扩展：添加新的运算符只需要创建新的表达式类
• 符合开闭原则：新增功能不需要修改现有代码
• 可读性强：抽象语法树直观地表达了表达式的结构
• 可维护性好：每个表达式类的逻辑独立，便于测试和维护

总结

优点

• 易于改变和扩展文法：因为在解释器模式中，使用类来表示语言的文法规则的，因此可以通过继承等机制改变或者扩展文法，每一个文法规则都可以表示为一个类，因此我们可以快速的实现一个迷你的语言。
• 实现文法比较容易： 在抽象语法树中，每一个表达式节点类的实现方式都是相似的，这些类的代码编写都不会特别复杂。
• 增加新的解释表达式比较方便： 如果用户需要增加新的解释表达式，只需要对应增加一个新的表达式类就可以了，原有的表达式类不需要修改，符合开闭原则。

缺点

• 对于复杂的文法难以维护： 在解释器中，一条规则至少要定义一个类，因此一个语言中如果有太多的文法规则，就会使类的个数急剧增加，难以维护
• 执行效率低： 解释器模式中大量的使用了循环和递归调用，所有复杂的句子执行起来速度比较慢。

使用场景

• 当语言的文法简单，并且执行效率不是关键问题。
• 当问题重复出现，且可以用一种简单的语言来表达。
• 当一个语言需要解释执行，并且语言中的句子可以表示为一个抽象的语法树的时候。