Java设计模式之从[计算器]分析解释器(Interpreter)形式

Java设计模式之从[计算器]分析解释器(Interpreter)模式

解释器模式是一种广泛运用于编译器的设计模式。它的意图是给定一个语言，定义它的文法的一种表示，并定义一个解释器来解释语言中的句子。

本篇的内容和“游戏”无关，是从编译原理的角度来对这个模式进行解释，因为它几乎只出现在编译器中。

下面简单介绍一下编译原理中的文法定义。文法定义可以理解为用类似正则表达式来定义一个文法，它由终结符、非终结符组成。简单来说，终结符是指的具体的符号，非终结符是指的具有递归性质的某类终结符的集合。现在请看一个简单的计算器的BNF文法定义（不熟悉的同学请查阅编译原理的文法一章）：

L → E

E → E1 + T | T

T → T1 * F | T

F→ ( E ) | digit

digit → 1 | 2 | 3 | 4 |...

用通俗的话解释上面的文法定义，就是： L是一个合法的表达式，由E组成，E是由E+T或者T组成，T是由T*F或者T组成，F是由(E)或者digit组成，digit指的就是1、2、3……之类的数字。任何符合这个文法定义的表达式都是合法表达式，如(2*(5+2)-3)*4等。文法的定义包含这递归的思想在里面，对于可递归的符号，如L、E、T、F，它们被称作非终结符，对于digit，它被称作终结符，因为当编译器分析到此处就无需递归了，直接返回一个具体的值，这个递归过程就此终止。

回到本篇文章的主题，假设我们需要计算一个表达式，可以将它表示为一个抽象的语法树。例如，假设我们有 +、-、*三个函数，我们需要计算a*b+(b-a)，在函数式编程中，我们可以这样写：表达式的结果= +( *(a,b), -(b, a) )。其中，+(x,y)表示计算x+y。

为了实现上述思想，请看下面的Java代码：

import java.util.HashMap;
import java.util.Map;

interface Expression{
    int interpret(Context context);
}

class Context {
    private Map<String, Integer> variables = new HashMap<String, Integer>();
    public Integer get(String name){
        return variables.get(name);
    }
    public void add(String name, int value){
        variables.put(name, value);
    }
}

class NumberExpression implements Expression{
    public String name;
    public NumberExpression(String name){
        this.name = name;
    }
    public int interpret(Context context){
        return context.get(name);
    }    
}

class AddExpression implements Expression{
    private Expression left, right;
    public AddExpression(Expression left, Expression right){
        this.left = left;
        this.right = right;
    }
    public int interpret(Context context){
        return left.interpret(context) + right.interpret(context);
    }
}

class SubstractExpression implements Expression{
    private Expression left, right;
    public SubstractExpression(Expression left, Expression right){
        this.left = left;
        this.right = right;
    }
    public int interpret(Context context){
        return left.interpret(context) - right.interpret(context);
    }
}

class MultiplyExpression implements Expression{
    private Expression left, right;
    public MultiplyExpression(Expression left, Expression right){
        this.left = left;
        this.right = right;
    }
    public int interpret(Context context){
        return left.interpret(context) * right.interpret(context);
    }
}

public class Interpreter
{
    public static void main(String[] args) throws InterruptedException {
        int a=5, b=4;
        //计算a*b+(b-a);
        Context context = new Context();
        context.add("a", a);
        context.add("b", b);
        Expression expression = 
                new AddExpression(
                        new MultiplyExpression(new NumberExpression("a"), new NumberExpression("b")),
                        new SubstractExpression(new NumberExpression("b"), new NumberExpression("a"))
                        );
        System.out.println(expression.interpret(context));
    }
}

我们用Expression接口表示一个表达式的接口，其中的interpret方法表示解释表达式的含义。那么，对于非终结符，interpret就调用各个表达式的实现方法（如加、减、乘），对于终结符，则直接返回它的值（为一个整数）。在一个表达式中，我们把表达式的整个作用域成为“上下文（Context）”，在这个上下文中保存着表达式中各个变量的名字和值。因此，我们定义了一个Context类，其中有个HashMap，来保存变量和它对应的值。在上述例子中，NumberExpression是终结符，因此它的interpret方法就是查询上下文中的变量，并返回它的值；对于其他Expression，它们的interpret分别表示加法、减法和乘法，利用面向对象的多态性质，调用Expression接口的interpret方法来实现计算。

在main方法中，我们将两个变量（a、b）加入了上下文context中，由于我们要计算a*b+(b-a)，根据括号、乘法优先原则，其实它是计算两个表达式的加法，因此我们在定义expression的时候，最开始是new了一个AddExpression。其实，解释器模式就是一个递归调用的模式，最后调用expression.interpret(context)将表达式的结果计算出来。

由上可见，解释器模式对于扩展文法、实现文法是十分方便的，然而，假设对于文法中的一条规则，我们都必须要新增一个继承于Expression的类，对于复杂的文法则难以维护，此时应当考虑用其它技术来实现之。

Java设计模式之从[计算器]分析解释器(Interpreter)形式

相关推荐