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)模式,布布扣,bubuko.com

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

上一篇:JavaScript判断数据类型总结


下一篇:微信小程序-scroll-view横向滚动和上拉加载