语言与模式-21解释器模式

2015-02-23 Leave a comment

意图

给定一个语言，定义它的文法的一种表示，并定义一个解释器，这个解释器使用该表示来解释语言中的句子。

适用性

当有一个语言需要解释执行, 并且你可将该语言中的句子表示为一个抽象语法树时，可使用解释器模式。而当存在以下情况时该模式效果最好：
该文法简单对于复杂的文法, 文法的类层次变得庞大而无法管理。此时语法分析程序生成器这样的工具是更好的选择。它们无需构建抽象语法树即可解释表达式, 这样可以节省空间而且还可能节省时间。
效率不是一个关键问题最高效的解释器通常不是通过直接解释语法分析树实现的, 而是首先将它们转换成另一种形式。例如，正则表达式通常被转换成状态机。但即使在这种情况下, 转换器仍可用解释器模式实现, 该模式仍是有用的。

Java实现

抽象表达式角色

public abstract class Expression {
    /**
     * 以环境为准，本方法解释给定的任何一个表达式
     */
    public abstract boolean interpret(Context ctx);
    /**
     * 检验两个表达式在结构上是否相同
     */
    public abstract boolean equals(Object obj);
    /**
     * 返回表达式的hash code
     */
    public abstract int hashCode();
    /**
     * 将表达式转换成字符串
     */
    public abstract String toString();
}

一个Constant对象代表一个布尔常量

public class Constant extends Expression{
    private boolean value;
    public Constant(boolean value){
        this.value = value;
    }
    @Override
    public boolean equals(Object obj) {
        if(obj != null && obj instanceof Constant){
            return this.value == ((Constant)obj).value;
        }
        return false;
    }
    @Override
    public int hashCode() {
        return this.toString().hashCode();
    }
    @Override
    public boolean interpret(Context ctx) {
        return value;
    }
    @Override
    public String toString() {
        return new Boolean(value).toString();
    }
}

一个Variable对象代表一个有名变量

public class Variable extends Expression {
    private String name;
    public Variable(String name){
        this.name = name;
    }
    @Override
    public boolean equals(Object obj) {
        if(obj != null && obj instanceof Variable){
            return this.name.equals(
                    ((Variable)obj).name);
        }
        return false;
    }
    @Override
    public int hashCode() {
        return this.toString().hashCode();
    }
    @Override
    public String toString() {
        return name;
    }
    @Override
    public boolean interpret(Context ctx) {
        return ctx.lookup(this);
    }
}

代表逻辑“与”操作的And类，表示由两个布尔表达式通过逻辑“与”操作给出一个新的布尔表达式的操作

public class And extends Expression {
    private Expression left,right;
    public And(Expression left , Expression right){
        this.left = left;
        this.right = right;
    }
    @Override
    public boolean equals(Object obj) {
        if(obj != null && obj instanceof And){
            return left.equals(((And)obj).left) &&
                right.equals(((And)obj).right);
        }
        return false;
    }
    @Override
    public int hashCode() {
        return this.toString().hashCode();
    }
    @Override
    public boolean interpret(Context ctx) {
        return left.interpret(ctx) && right.interpret(ctx);
    }
    @Override
    public String toString() {
        return "(" + left.toString() + " AND " + right.toString() + ")";
    }
}

代表逻辑“或”操作的Or类，代表由两个布尔表达式通过逻辑“或”操作给出一个新的布尔表达式的操作

public class Or extends Expression {
    private Expression left,right;
    public Or(Expression left , Expression right){
        this.left = left;
        this.right = right;
    }
    @Override
    public boolean equals(Object obj) {
        if(obj != null && obj instanceof Or){
            return this.left.equals(((Or)obj).left) && this.right.equals(((Or)obj).right);
        }
        return false;
    }
    @Override
    public int hashCode() {
        return this.toString().hashCode();
    }
    @Override
    public boolean interpret(Context ctx) {
        return left.interpret(ctx) || right.interpret(ctx);
    }
    @Override
    public String toString() {
        return "(" + left.toString() + " OR " + right.toString() + ")";
    }
}

代表逻辑“非”操作的Not类，代表由一个布尔表达式通过逻辑“非”操作给出一个新的布尔表达式的操作

public class Not extends Expression {
    private Expression exp;
    public Not(Expression exp){
        this.exp = exp;
    }
    @Override
    public boolean equals(Object obj) {
        if(obj != null && obj instanceof Not){
            return exp.equals(
                    ((Not)obj).exp);
        }
        return false;
    }
    @Override
    public int hashCode() {
        return this.toString().hashCode();
    }
    @Override
    public boolean interpret(Context ctx) {
        return !exp.interpret(ctx);
    }
    @Override
    public String toString() {
        return "(Not " + exp.toString() + ")";
    }
}

环境(Context)类定义出从变量到布尔值的一个映射

public class Context {
    private Map<Variable,Boolean> map = new HashMap<Variable,Boolean>();
    public void assign(Variable var , boolean value){
        map.put(var, new Boolean(value));
    }
    public boolean lookup(Variable var) throws IllegalArgumentException{
        Boolean value = map.get(var);
        if(value == null){
            throw new IllegalArgumentException();
        }
        return value.booleanValue();
    }
}

客户端类

public class Client {
    public static void main(String[] args) {
        Context ctx = new Context();
        Variable x = new Variable("x");
        Variable y = new Variable("y");
        Constant c = new Constant(true);
        ctx.assign(x, false);
        ctx.assign(y, true);
        Expression exp = new Or(new And(c,x) , new And(y,new Not(x)));
        System.out.println("x=" + x.interpret(ctx));
        System.out.println("y=" + y.interpret(ctx));
        System.out.println(exp.toString() + "=" + exp.interpret(ctx));
    }
}

Clojure实现

解释器模式其实就是写了个包含上下文的解析器！这可是Clojure的强项!

先演示不带上下文的解析器！其实就是内部DSL!

(defmacro assign [a v]
   `(def ~a ~v))
(assign x false)
(assign y true)
(assign c true)
(assign exp '(or (and c x) (and y (not x))))
(println "x =" x)
(println "y =" y)
(println exp "=" (eval exp))

这里是一个较完整的代码!