设计模式 | 解释器模式及典型应用

栏目: 后端 · 发布时间: 5年前

内容简介:解释器模式(Interpreter Pattern):定义一个语言的文法,并且建立一个解释器来解释该语言中的句子,这里的 “语言” 是指使用规定格式和语法的代码。解释器模式是一种类行为型模式。AbstractExpression(抽象表达式):在抽象表达式中声明了抽象的解释操作,它是所有终结符表达式和非终结符表达式的公共父类。TerminalExpression(终结符表达式):终结符表达式是抽象表达式的子类,它实现了与文法中的终结符相关联的解释操作,在句子中的每一个终结符都是该类的一个实例。通常在一个解释

解释器模式(Interpreter Pattern):定义一个语言的文法,并且建立一个解释器来解释该语言中的句子,这里的 “语言” 是指使用规定格式和语法的代码。解释器模式是一种类行为型模式。

角色

AbstractExpression(抽象表达式):在抽象表达式中声明了抽象的解释操作,它是所有终结符表达式和非终结符表达式的公共父类。

TerminalExpression(终结符表达式):终结符表达式是抽象表达式的子类,它实现了与文法中的终结符相关联的解释操作,在句子中的每一个终结符都是该类的一个实例。通常在一个解释器模式中只有少数几个终结符表达式类,它们的实例可以通过非终结符表达式组成较为复杂的句子。

NonterminalExpression(非终结符表达式):非终结符表达式也是抽象表达式的子类,它实现了文法中非终结符的解释操作,由于在非终结符表达式中可以包含终结符表达式,也可以继续包含非终结符表达式,因此其解释操作一般通过递归的方式来完成。

Context(环境类):环境类又称为上下文类,它用于存储解释器之外的一些全局信息,通常它临时存储了需要解释的语句。

设计模式 | 解释器模式及典型应用

示例

使用解释器模式实现一个简单的后缀表达式解释器,仅支持对整数的加法和乘法即可

定义抽象表达式接口

public interface Interpreter {
    int interpret();
}

非终结符表达式,对整数进行解释

public class NumberInterpreter implements Interpreter {
    private int number;

    public NumberInterpreter(int number) {
        this.number = number;
    }

    public NumberInterpreter(String number) {
        this.number = Integer.parseInt(number);
    }

    @Override
    public int interpret() {
        return this.number;
    }
}

终结符表达式,对加法和乘法进行解释

// 加法
public class AddInterpreter implements Interpreter {
    private Interpreter firstExpression, secondExpression;
    public AddInterpreter(Interpreter firstExpression, Interpreter secondExpression) {
        this.firstExpression = firstExpression;
        this.secondExpression = secondExpression;
    }
    @Override
    public int interpret() {    
        return this.firstExpression.interpret() + this.secondExpression.interpret();
    }
    @Override
    public String toString() {
        return "+";
    }
}

// 乘法
public class MultiInterpreter implements Interpreter {
    private Interpreter firstExpression, secondExpression;

    public MultiInterpreter(Interpreter firstExpression, Interpreter secondExpression) {
        this.firstExpression = firstExpression;
        this.secondExpression = secondExpression;
    }
    @Override
    public int interpret() {
        return this.firstExpression.interpret() * this.secondExpression.interpret();
    }
    @Override
    public String toString() {
        return "*";
    }
}

工具类

public class OperatorUtil {
    public static boolean isOperator(String symbol) {
        return (symbol.equals("+") || symbol.equals("*"));

    }
    public static Interpreter getExpressionObject(Interpreter firstExpression, Interpreter secondExpression, String symbol) {
        if ("+".equals(symbol)) {  // 加法
            return new AddInterpreter(firstExpression, secondExpression);
        } else if ("*".equals(symbol)) {    // 乘法
            return new MultiInterpreter(firstExpression, secondExpression);
        } else {
            throw new RuntimeException("不支持的操作符:" + symbol);
        }
    }
}

测试,对后缀表达式 6 100 11 + * 进行求值

public class Test {
    public static void main(String[] args) {
        String inputStr = "6 100 11 + *";
        MyExpressionParser expressionParser = new MyExpressionParser();
        int result = expressionParser.parse(inputStr);
        System.out.println("解释器计算结果: " + result);
    }
}

运行结果

入栈: 6
入栈: 100
入栈: 11
出栈: 11 和 100
应用运算符: +
阶段结果入栈: 111
出栈: 111 和 6
应用运算符: *
阶段结果入栈: 666
解释器计算结果: 666

设计模式 | 解释器模式及典型应用

解释器模式总结

解释器模式为自定义语言的设计和实现提供了一种解决方案,它用于定义一组文法规则并通过这组文法规则来解释语言中的句子。虽然解释器模式的使用频率不是特别高,但是它在 正则表达式XML文档解释 等领域还是得到了广泛使用。

主要优点

  • 易于改变和扩展文法 。由于在解释器模式中使用类来表示语言的文法规则,因此可以通过继承等机制来改变或扩展文法。
  • 每一条文法规则都可以表示为一个类,因此可以 方便地实现一个简单的语言
  • 实现文法较为容易 。在抽象语法树中每一个表达式节点类的实现方式都是相似的,这些类的代码编写都不会特别复杂,还可以通过一些 工具 自动生成节点类代码。
  • 增加新的解释表达式较为方便 。如果用户需要增加新的解释表达式只需要对应增加一个新的终结符表达式或非终结符表达式类,原有表达式类代码无须修改,符合 “开闭原则”。

主要缺点

  • 对于复杂文法难以维护 。在解释器模式中,每一条规则至少需要定义一个类,因此如果一个语言包含太多文法规则,类的个数将会急剧增加,导致系统难以管理和维护,此时可以考虑使用语法分析程序等方式来取代解释器模式。
  • 执行效率较低 。由于在解释器模式中使用了大量的循环和递归调用,因此在解释较为复杂的句子时其速度很慢,而且代码的调试过程也比较麻烦。

适用场景

  • 可以将一个需要解释执行的语言中的句子表示为一个抽象语法树。
  • 一些重复出现的问题可以用一种简单的语言来进行表达。
  • 一个语言的文法较为简单。
  • 对执行效率要求不高。

解释器模式的典型应用

Spring EL表达式中的解释器模式

Spring EL表达式相关的类在 org.springframework.expression 包下,类图如下

设计模式 | 解释器模式及典型应用

涉及的类非常多,这里仅对此时我们最关心的几个类做介绍:

SpelExpression,表示一个 EL 表达式,表达式在内部通过一个 AST抽象语法树 表示,EL表达式求值是通过 this.ast.getValue(expressionState); 求值

public class SpelExpression implements Expression {
    private final String expression;
    private final SpelNodeImpl ast;
    private final SpelParserConfiguration configuration;

    @Override
    @Nullable
    public Object getValue() throws EvaluationException {
        if (this.compiledAst != null) {
            try {
                EvaluationContext context = getEvaluationContext();
                return this.compiledAst.getValue(context.getRootObject().getValue(), context);
            }
            catch (Throwable ex) {
                // If running in mixed mode, revert to interpreted
                if (this.configuration.getCompilerMode() == SpelCompilerMode.MIXED) {
                    this.interpretedCount = 0;
                    this.compiledAst = null;
                }
                else {
                    // Running in SpelCompilerMode.immediate mode - propagate exception to caller
                    throw new SpelEvaluationException(ex, SpelMessage.EXCEPTION_RUNNING_COMPILED_EXPRESSION);
                }
            }
        }

        ExpressionState expressionState = new ExpressionState(getEvaluationContext(), this.configuration);
        Object result = this.ast.getValue(expressionState);
        checkCompile(expressionState);
        return result;
    }
    //...省略...
}

SpelNodeImpl:已解析的Spring表达式所代表的ast语法树的节点的通用父类型,语法树的节点在解释器模式中扮演的角色是终结符和非终结符。从类图中可以看到,SpelNodeImpl 的子类主要有 Literal,Operator,Indexer等,其中 Literal 是各种类型的值的父类,Operator 则是各种操作的父类

public abstract class SpelNodeImpl implements SpelNode, Opcodes {
    protected int pos;  // start = top 16bits, end = bottom 16bits
    protected SpelNodeImpl[] children = SpelNodeImpl.NO_CHILDREN;
    @Nullable
    private SpelNodeImpl parent;

    public final Object getValue(ExpressionState expressionState) throws EvaluationException {
        return getValueInternal(expressionState).getValue();
    }
    // 抽象方法,由子类实现,获取对象的值
    public abstract TypedValue getValueInternal(ExpressionState expressionState) throws EvaluationException;
    //...省略...
}

IntLiteral表示整型文字的表达式语言的ast结点

public class IntLiteral extends Literal {
    private final TypedValue value;
    public IntLiteral(String payload, int pos, int value) {
        super(payload, pos);
        this.value = new TypedValue(value); // 
        this.exitTypeDescriptor = "I";
    }
    @Override
    public TypedValue getLiteralValue() {
        return this.value;
    }
    // ...
}

OpPlus表示加法的ast结点,在 getValueInternal 方法中对操作符两边进行相加操作

public class OpPlus extends Operator {
    public OpPlus(int pos, SpelNodeImpl... operands) {
        super("+", pos, operands);
        Assert.notEmpty(operands, "Operands must not be empty");
    }
    @Override
    public TypedValue getValueInternal(ExpressionState state) throws EvaluationException {
        SpelNodeImpl leftOp = getLeftOperand();

        if (this.children.length < 2) {  // if only one operand, then this is unary plus
            Object operandOne = leftOp.getValueInternal(state).getValue();
            if (operandOne instanceof Number) {
                if (operandOne instanceof Double) {
                    this.exitTypeDescriptor = "D";
                }
                else if (operandOne instanceof Float) {
                    this.exitTypeDescriptor = "F";
                }
                else if (operandOne instanceof Long) {
                    this.exitTypeDescriptor = "J";
                }
                else if (operandOne instanceof Integer) {
                    this.exitTypeDescriptor = "I";
                }
                return new TypedValue(operandOne);
            }
            return state.operate(Operation.ADD, operandOne, null);
        }
        // 递归调用leftOp的 getValueInternal(state) ,获取操作符左边的值
        TypedValue operandOneValue = leftOp.getValueInternal(state);
        Object leftOperand = operandOneValue.getValue();
        // 递归调用children[1]的 getValueInternal(state) ,获取操作符右边的值
        TypedValue operandTwoValue = getRightOperand().getValueInternal(state);
        Object rightOperand = operandTwoValue.getValue();

        // 如果操作符左右都是数值类型,则将它们相加
        if (leftOperand instanceof Number && rightOperand instanceof Number) {
            Number leftNumber = (Number) leftOperand;
            Number rightNumber = (Number) rightOperand;

            if (leftNumber instanceof BigDecimal || rightNumber instanceof BigDecimal) {
                BigDecimal leftBigDecimal = NumberUtils.convertNumberToTargetClass(leftNumber, BigDecimal.class);
                BigDecimal rightBigDecimal = NumberUtils.convertNumberToTargetClass(rightNumber, BigDecimal.class);
                return new TypedValue(leftBigDecimal.add(rightBigDecimal));
            }
            else if (leftNumber instanceof Double || rightNumber instanceof Double) {
                this.exitTypeDescriptor = "D";  
                return new TypedValue(leftNumber.doubleValue() + rightNumber.doubleValue());
            }
            //...省略 Float->F, BigInteger->add, Long->J,Integer->I
            else {
                // Unknown Number subtypes -> best guess is double addition
                return new TypedValue(leftNumber.doubleValue() + rightNumber.doubleValue());
            }
        }
        //...
        return state.operate(Operation.ADD, leftOperand, rightOperand);
    }
    //...
}

通过一个示例,调试查看程序中间经历的步骤

public class SpringELTest {
    public static void main(String[] args) {
        // 1. 构建解析器
        org.springframework.expression.ExpressionParser parser = new SpelExpressionParser();
        // 2. 解析表达式
        Expression expression = parser.parseExpression("100 * 2 + 400 * 1 + 66");
        // 3. 获取结果
        int result = (Integer) expression.getValue();
        System.out.println(result); // 结果:666
    }
}

EL表达式解析后得到表达式 (((100 * 2) + (400 * 1)) + 66)
设计模式 | 解释器模式及典型应用

如果用图形把其这棵AST抽象语法树简单地画出来,大概是这样

设计模式 | 解释器模式及典型应用

调用 expression.getValue() 求值,此时的 ast 是语法树的头结点,也就是 + OpPlus,所以通过 this.ast.getValue(expressionState) 进入了 OpPlus 的 getValue 方法(是父类中的方法),接着进入 getValueInternal 方法,然后递归计算操作符左边的值,递归计算操作符右边的值,最后相加返回

设计模式 | 解释器模式及典型应用

参考:

刘伟.Java设计模式

Java设计模式精讲

设计模式 | 解释器模式及典型应用

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 whirlys@163.com


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

生物信息学算法导论

生物信息学算法导论

N.C.琼斯 / 第1版 (2007年7月1日) / 2007-7 / 45.0

这是一本关于生物信息学算法和计算思想的导论性教科书,原著由国际上的权威学者撰写,经国内知名专家精心翻译为中文,系统介绍推动生物信息学不断进步的算法原理。全书强调的是算法中思想的运用,而不是对表面上并不相关的各类问题进行简单的堆砌。 体现了以下特色: 阐述生物学中的相关问题,涉及对问题的模型化处理并提供一种或多种解决方案: 简要介绍生物信息学领域领军人物; 饶有趣味的小插图使得概念更加具体和形象,方......一起来看看 《生物信息学算法导论》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

URL 编码/解码
URL 编码/解码

URL 编码/解码