Bug辉的博客 不忘初心，方得始终！

GoF设计模式 - 解释器模式

2017-08-14
Bug辉 [原创文章]
编程思想
 

本文为博主原创文章，请遵守文章最后的版权申明。

解释器模式(Interpreter)，行为型模式。对给定的语言的文法创建一种表示（建立模型）并定义对应的解释器，用这个表示去解释语句。解释器模式常用于实现表达式语言或者本文处理。

在《GoF设计模式 - 概述》一文中已经讲述了设计原则等基础知识，如果还没有看，请先看完这篇文章。

解释器模式

解释器模式

角色以及职责

  1. Context： 上下文。封装了解释器的运行环境。
  2. AbstractExpression： 抽象表达式。即给定语言的元素的抽象。
  3. TerminalExpression： 终结符解释器
  4. NonterminalExpression： 非终结符解释器

是不是感觉略抽象呢！ 稍微解释下：
所谓的终结符就是语句中的不可再分的基本元素，而且非终结符则是由终结符以及其他非终结符组成的复合元素。

精英们擅长进行抽象思维，不应该被这点程度的抽象困住的。o(∩_∩)o
如果还是不理解呢，也不要着急，稍微整理下思路，然后继续往下看。通过实例来理解可能会更直观。

适用场景

需要解释给定的某种语言，给定语言的语法并不是非常复杂且对性能要求不高的场景。

实例

由于解释器模式的应用场景本身具有一定的复杂性，会涉及到一些编译原理和数据结构的知识。如果有某些概念不是很理解的话，可以稍作调查然后继续往下看。但不建议深挖，以免思路切不回来。

本文将实现一个类似于jsp的EL表达式的表达式语言解释器，通过这个解释器来演示解释器模式的使用。为了缩减篇幅，这里只支持四则运算。不过，哪怕仅仅实现四则运算，要做的工作也是不少的。所以本文的示例程序代码量略多，请准备好耐心。。

类图

解释器模式

tips: 如果觉得上面的图字太小看不清可以戳图片去看大图。

编码实现

第一步现实现一个上下文类。

/**
 * 表达式上下文
 * @author: Elvin Zeng
 * @date: 17-8-14.
 */
public class ElContext {
    private Map<String, Object> scope;

    public ElContext() {
        this.scope = new HashMap<>();
    }

    public ElContext(Map<String, Object> scope) {
        this.scope = scope;
    }

    public boolean containsKey(Object key) {
        return scope.containsKey(key);
    }

    public Object get(Object key) {
        return scope.get(key);
    }

    public Object put(String key, Object value) {
        return scope.put(key, value);
    }

    public Object remove(Object key) {
        return scope.remove(key);
    }

    public void putAll(Map<? extends String, ?> m) {
        scope.putAll(m);
    }

    public void clear() {
        scope.clear();
    }

    @Override
    public String toString() {
        return "ELContext{" +
                "scope=" + scope +
                '}';
    }
}

第二步定义好表达式的抽象Expression类，对应着解释器模式的AbstractExpression。

/**
 * 表达式
 * @author: Elvin Zeng
 * @date: 17-8-14.
 */
public interface Expression {
    Object getValue(ElContext context);
}

第三步定义两个用于表示终结符的表达式的实现类。

/**
 * 字面常量
 * @author: Elvin Zeng
 * @date: 17-8-14.
 */
public class Literal implements Expression {

    private Object val;

    public Literal(Object val) {
        this.val = val;
    }

    @Override
    public Object getValue(ElContext context) {
        return val;
    }

    @Override
    public String toString() {
        return "Literal{" +
                "val=" + val +
                '}';
    }
}

/**
 * 变量
 * @author: Elvin Zeng
 * @date: 17-8-14.
 */
public class Variable implements Expression{

    private String variableName;

    public Variable(String variableName) {
        this.variableName = variableName;
    }

    @Override
    public Object getValue(ElContext context) {
        return context.get(variableName);
    }

    @Override
    public String toString() {
        return "Variable{" +
                "variableName='" + variableName + '\'' +
                '}';
    }
}

第四步，定义一个四则运算的非终结符的抽象类BinaryExpression，避免几个非终结符实现类的代码重复率过高。由于四则运算全都是二元表达式，所以我将这个抽象类命名为BinaryExpression。

/**
 * 二元表达式
 * @author: Elvin Zeng
 * @date: 17-8-14.
 */
public abstract class BinaryExpression implements Expression{
    private Expression leftOperand;
    private Expression rightOperand;

    public BinaryExpression(Expression leftOperand, Expression rightOperand) {
        this.leftOperand = leftOperand;
        this.rightOperand = rightOperand;
    }

    public Expression getLeftOperand() {
        return leftOperand;
    }

    public Expression getRightOperand() {
        return rightOperand;
    }

    @Override
    public String toString() {
        return "{" +
                "leftOperand=" + leftOperand +
                ", rightOperand=" + rightOperand +
                "}";
    }
}

第五步，创建几个非终结符的具体实现类，用于表示加减乘除。

/**
 * 加法表达式
 * @author: Elvin Zeng
 * @date: 17-8-14.
 */
public class AddExpression extends BinaryExpression{

    public AddExpression(Expression leftOperand, Expression rightOperand) {
        super(leftOperand, rightOperand);
    }

    @Override
    public Object getValue(ElContext context) {
        return (double)getLeftOperand().getValue(context)
                + (double)getRightOperand().getValue(context);
    }

    @Override
    public String toString() {
        return "AddExpression" + super.toString();
    }
}

/**
 * 减法表达式
 * @author: Elvin Zeng
 * @date: 17-8-14.
 */
public class SubExpression extends BinaryExpression {

    public SubExpression(Expression leftOperand, Expression rightOperand) {
        super(leftOperand, rightOperand);
    }

    @Override
    public Object getValue(ElContext context) {
        return (double)getLeftOperand().getValue(context)
                - (double)getRightOperand().getValue(context);
    }

    @Override
    public String toString() {
        return "SubExpression" + super.toString();
    }
}

/**
 * 乘法表达式
 * @author: Elvin Zeng
 * @date: 17-8-14.
 */
public class MulExpression extends BinaryExpression{

    public MulExpression(Expression leftOperand, Expression rightOperand) {
        super(leftOperand, rightOperand);
    }

    @Override
    public Object getValue(ElContext context) {
        return (double)getLeftOperand().getValue(context)
                * (double)getRightOperand().getValue(context);
    }

    @Override
    public String toString() {
        return "MulExpression" + super.toString();
    }
}

/**
 * 除法表达式
 * @author: Elvin Zeng
 * @date: 17-8-14.
 */
public class DivExpression extends BinaryExpression{

    public DivExpression(Expression leftOperand, Expression rightOperand) {
        super(leftOperand, rightOperand);
    }

    @Override
    public Object getValue(ElContext context) {
        return (double)getLeftOperand().getValue(context)
                / (double)getRightOperand().getValue(context);
    }

    @Override
    public String toString() {
        return "DivExpression" + super.toString();
    }
}

第六步实现一个将字符串转换为创建好的文法表示（上面的一堆Expression类）的工具类，这里我将其称为ElParser，即表达式语言的解析器。注意这里是解析器不是解释器，也就是说，只做了翻译工作。至于表达式语言的语义是什么这个类不会去管，那是解释器活。不过这个类会略微有点复杂，请给你的耐心充好电。(ーー゛)
前方高能，请准备好耐心！

/**
 * 表达式解析器
 *
 * @author: Elvin Zeng
 * @date: 17-8-14.
 */
public class ElParser {

    private Stack<Expression> operandStack = new Stack<>();  //  操作数栈
    private Stack<String> operatorStack = new Stack<>();  //  操作符栈

    private boolean isOperator(String str) {
        if ("+".equals(str) || "-".equals(str)
                || "*".equals(str) || "/".equals(str)
                || "#".equals(str)) {
            return true;
        }
        return false;
    }

    private boolean isPrecedeThanTopOfStack(String operator) {
        String topOfStack = operatorStack.peek();
        if (("*".equals(operator) || "/".equals(operator))
                && ("+".equals(topOfStack) || "-".equals(topOfStack))) {
            return true;
        }
        if (!"#".equals(operator) && "#".equals(topOfStack)) {
            return true;
        }
        return false;
    }

    /**
     * 将字符串解析成表达式的抽象表示
     *
     * @param expressionStr 待解析的字符串
     * @return 表达式的抽象表示
     */
    public Expression parse(String expressionStr) {
        //  先删去空格方便解析
        expressionStr = expressionStr.replaceAll("\\s+", "");
        //  给表达式前后加入边界标识符
        expressionStr = "#" + expressionStr + "#";

        Tokenizer tokenizer = new Tokenizer(expressionStr);
        String token = null;
        token = tokenizer.nextToken();
        do{
            if("#".equals(token) && operatorStack.empty()){
                operatorStack.push(token);
                if (tokenizer.hasMoreTokens()){
                    token = tokenizer.nextToken();
                }
            }else if("#".equals(token) && "#".equals(operatorStack.peek())){
                operatorStack.pop();
            }else {
                if (!isOperator(token)) {
                    operandStack.push(parseTerminal(token));
                    if (tokenizer.hasMoreTokens()){
                        token = tokenizer.nextToken();
                    }
                } else {
                    if (operatorStack.empty()){
                        throw new RuntimeException("异常的表达式");
                    }
                    if (isPrecedeThanTopOfStack(token)){
                        operatorStack.push(token);
                        if (tokenizer.hasMoreTokens()){
                            token = tokenizer.nextToken();
                        }
                    }else{
                        String operator = operatorStack.pop();
                        Expression rightOperand = operandStack.pop();
                        Expression leftOperand = operandStack.pop();

                        Expression expression = parseBinaryExpression(operator,
                                leftOperand,
                                rightOperand);
                        operandStack.push(expression);
                    }
                }
            }
        }while (!operatorStack.empty());

        return operandStack.pop();
    }

    private Expression parseTerminal(String str){
        Expression expression = null;
        if (Pattern.matches("[\\d\\.]+", str)){
            expression = new Literal(Double.valueOf(str));
        }else if (Pattern.matches("[a-zA-Z_]+", str)){
            expression = new Variable(str);
        }
        return expression;
    }

    private Expression parseBinaryExpression(String operatorStr,
                                             Expression leftOperand,
                                             Expression rightOperand){
        Expression expression = null;
        switch (operatorStr){
            case "+":
                expression = new AddExpression(leftOperand, rightOperand);
                break;
            case "-":
                expression = new SubExpression(leftOperand, rightOperand);
                break;
            case "*":
                expression = new MulExpression(leftOperand, rightOperand);
                break;
            case "/":
                expression = new DivExpression(leftOperand, rightOperand);
                break;
            default:
                throw new RuntimeException("未知的运算符");
        }
        return expression;
    }

    /**
     * 表达式分解工具
     */
    private static class Tokenizer {
        private String str;
        private List<String> tokens;
        private int currentIndex;

        public Tokenizer(String str) {
            this.str = str;
            tokens = new LinkedList<>();
            currentIndex = 0;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < str.length(); i++) {
                String currentChar = Character.toString(str.charAt(i));
                if ("*".equals(currentChar) || "/".equals(currentChar)
                        || "+".equals(currentChar) || "-".equals(currentChar)
                        || "#".equals(currentChar)) {
                    if (sb.length() > 0) {
                        tokens.add(sb.toString());
                        sb.delete(0, sb.length());
                    }
                    tokens.add(currentChar);
                } else {
                    sb.append(currentChar);
                }
            }
        }

        /**
         * @return 是否还有token
         */
        public boolean hasMoreTokens() {
            if (null != tokens && tokens.size() > currentIndex) {
                return true;
            } else {
                return false;
            }
        }

        /**
         * @return 下一个token
         */
        public String nextToken() {
            return tokens.get(currentIndex++);
        }
    }
}

ElParser类的实现过程如果一时半会儿看不明白的话也可无视之，后面再慢慢研究。毕竟，本文是为了介绍解释器模式，而不是数据结构。接下来就是客户端了！

/**
 * Client
 * @author: Elvin Zeng
 * @date: 17-8-12.
 */
public class App {
    public static void main(String[] args) {
        ElParser parser = new ElParser();
        ElContext elContext = new ElContext();
        elContext.put("a", 12d);
        elContext.put("b", 3d);
        elContext.put("c", 3d);
        String expressionStr = "a - b * 2 + 6 / c";
        Expression expression = parser.parse(expressionStr);
        System.out.println(expressionStr);
        System.out.println(elContext);
        System.out.println(expression);
        System.out.println(expression.getValue(elContext));

        if (!new Double(8).equals(expression.getValue(elContext))){
            throw new RuntimeException("运行结果是错的！");
        }else {
            System.out.println("运行结果正确！");
        }
    }

}

执行结果

$ java -jar interpreter-1.0-SNAPSHOT.jar
a - b * 2 + 6 / c
ELContext{scope={a=12.0, b=3.0, c=3.0}}
AddExpression{leftOperand=SubExpression{leftOperand=Variable{variableName='a'}, rightOperand=MulExpression{leftOperand=Variable{variableName='b'}, rightOperand=Literal{val=2.0}}}, rightOperand=DivExpression{leftOperand=Literal{val=6.0}, rightOperand=Variable{variableName='c'}}}
8.0
运行结果正确！

有没有感觉很神奇！o(∩_∩)o 哈哈

解释器模式分析

解释器模式的定义是这样的：

Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language.

翻译成中文：

给定一种语言，定义该语言的文法的一种表示，并定义解释器，解释器用这个表示去解释语句。

定义看起来有点抽象。不过没办法，因为解释语句这个问题本身就具有比较高的复杂性。换句话来说，就是对文法本身建立模型。用这套模型去表示这种文法，并用于解释。 所谓的编程，其实就是不断的对这个现实世界中的问题建立模型并将其固化为代码自动化执行的过程。文法本身就是对语言的抽象，而对文法再抽象一层，确实会感觉有点绕。但是这是精英的成长之路中的必经之路，没有捷径。

解释器模式对于应用层程序员来说通常情况下接触的比较少，但是如果要自己编写框架的话就很有用了。比如要创造特定框架使用的某种表达式语言或者脚本，再比如用于创建一个ORM框架。jsp中的EL表达式是用解释器模式实现的，本文也用解释器模式实现了一个简化版的EL表达式。除了EL表达式外，我们的工作过程中还遇到过众多的表达式语言。比如OGNL表达式，Spring的表达式。

解释器模式也有缺点。如果这种语言的文法过于复杂，这个时候，会需要创建非常多的类。又或者对解释的速度有要求，这个时候解释器模式这种解决方案就不太适用了。这种情况下宜用状态机去解决。不过，话说回来。通常情况下，我们并不需要自己去造轮子创造一种语言。因为我们有大量现有的框架！如果真的需要在程序中执行业务脚本的话，也可以考虑用 Lua 这样的成熟且性能非常强大的脚本语言去做（有Java实现的Lua解释器）。

运用解释器模式，我们可以非常轻松的创建一个属于自己的语言的解释器。虽然在生产项目中用现有的开源解决方案是更合理的方式，但是自己实现一个解释器逼格看起来会更高一些哦！就像本文中我实现的那个例子一样。╭(′▽`)╯
前面说过一次了，应用层程序员会很少用到解释器模式。但是这并不代表解释器模式不重要！毕竟人都是要成长的嘛！渐渐的，新人也会参与一些更有技术含量的工作。说不定哪天就要自己写个框架喽！

参考

版权声明

知识共享许可协议
若无特殊说明则文章内容均为博主原创内容，包括但不限于代码、文字、图片。
《GoF设计模式 - 解释器模式》 由 Bug辉 采用 知识共享 署名-非商业性使用-禁止演绎 4.0 国际 许可协议 进行许可。
转载文章时文章署名请注明原作者为Bug辉（Elvin Zeng、zenghui、曾辉也行）并带上原文链接：https://www.bughui.com/2017/08/14/gof-design-pattern-interpreter/

鉴于目前国人版权意识比较薄弱，所以路过的同学可能并不了解CC协议。在此特地介绍一下！上述协议大概的意思是（这里只是简单解释，并不替代协议，以上述协议为准）：
  • 权利：遵守协议的情况下你可以在任何媒介以任何形式复制、发行本作品。
  • 约束：使用本作品得保留署名（作者+原文链接），不得声称或暗示文章是你创作的。
  • 约束：你不可以将本作品用于商业目的。
  • 约束：如果你再混合、转换、或者基于本作品创作，你不可以发布修改后的作品。
  • 在得到作者允许的情况下你可以不用受上述条款约束。
不论本作品是否对你有益，不论你是否认同本作品的观点，本作品都是作者的劳动产物。尊重别人的劳动别人才会尊重你的劳动是吧！


类似文章

上一篇 换工作ing

下一篇 GoF设计模式 - 访问者模式

评论

打赏时请在备注信息中填上你的称呼！好让我把你的名字加入致谢名单。
目录