首页 > 其他分享 >解释器模式

解释器模式

时间：2023-05-21 18:22:27浏览次数：36  
标签：解释器 TokenType 模式 Token tokenMap put new

begin 2023年04月15日16:49:35

引子

本科软件工程专业有这么一门课叫《编译原理》，课程内容已经忘了七七八八，但尤为清楚的是上机大作业是拷贝的，课程分数92。

定义

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

给定一个语言，定义其语法的表示以及一个用该表示来解释该语言中的句子的解释器。——《设计模式：可复用面向对象软件的基础》

解释器模式是一种行为型设计模式。

使用场景

Use the Interpreter pattern when there is a language to interpret, and you can represent statements in the language as
abstract syntax trees.The Interpreter pattern works best when

  • the grammar is simple. For complex grammars, the class hierarchy for the grammar becomes large and unmanageable.
    Tools such as parser generators are a better alternative in such cases. They can interpret expressions without
    building abstract syntax trees, which can saves pace and possibly time.

  • efficiency is not a critical concern. The most efficient interpreters are usually not implemented by interpreting
    parse trees directly but by first translating them into another form. For example, regular expressions are often
    transformed into state machines. But even then,the translator can be implemented by the Interpreter pattern, so the
    pattern is still applicable.

当有语言要解释时，请使用解释器模式，您可以将语言中的语句表示为抽象语法树。解释器模式在以下情况下效果最佳：

  • 语法很简单。对于复杂语法，语法的类层次结构变得很大且难以管理。在这种情况下，解释器生成器等工具是更好的选择。
    他们可以在不构建抽象语法树的情况下解释表达式，这可以节省速度和可能的时间。
  • 效率不是一个关键问题。最有效的解释器通常不是通过直接解释解释树来实现的，而是首先将它们转换为另一种形式来实现的。
    例如，正则表达式通常转换为状态机。但即便如此，翻译器也可以通过解释器模式实现，因此该模式仍然适用。

图示

解释器模式结构图:

解释器模式结构图

角色

抽象表达式(AbstractExpression)：

  • 声明抽象语法树中所有节点通用的抽象解释操作。

终结符表达式(TerminalExpression)：

  • 实现与文法中的终结符关联的解释操作。
  • 句子中的每个终结符都需要一个实例。

非终结符表达式(NonterminalExpression)：

  • 对文法中每一条规则R->R1R2...Rn都需要一个具体的非终结符表达式类。
  • 维护每个符号 R1 到 Rn 的抽象表达式类型的实例变量。
  • 实现语法中非终结符的解释操作。解释通常在表示 R1 到 Rn 的变量上递归调用自身。

上下文(Context)：

  • 包含对解释器全局的信息

客户端(Client)：

  • 构建（或给定）一个抽象语法树，表示语法定义的语言中的特定句子。
    抽象语法树由 NonterminalExpression 和 TerminalExpression 类的实例组装而成。
  • 调用解释(interpreter)操作

代码示例

实现一个简单函数绘图语言解释器，解释下面代码：

rot is 0;
origin is (0, 0);
scale is (2,20);
for T from 1 to 300 step 1 draw (t,-ln(t));
scale is (20,0.1);
for T from 0 to 8 step 0.1 draw (t,exp(t));
scale is (2,1);
for T from 0 to 300 step 1 draw (t,0);
for T from 0 to 300 step 1 draw (0,t);
for T from 0 to 120 step 1 draw (t,t);
scale is (2,0.1);
for T from 0 to 55 step 1 draw (t,-(t*t));
scale is (10,5);
for T from 0 to 60 step 1 draw (t,sqrt(t));
  • ROT语句：该语句的作用是控制逆时针角度旋转，如上述代码中的rot is 0的意思便是逆时针旋转0°的含义
  • ORIGIN语句：该语句的作用是将坐标系原点平移到横坐标和纵坐标规定的点处，
    如上述代码汇总的origin is (0, 0)便是规定坐标(0, 0)为原点的含义。
  • SCALE语句：该语句的作用是设置横坐标和纵坐标的比例，并将其按照相关比例因子进行缩放，
    如上述代码中的scale is (2, 20)的含义是将横坐标和纵坐标的比例设置为1:10并放大2倍。
  • FOR-DRAW语句：该语句是绘图的核心语句，主要作用是在坐标图上描点并绘图，通过step指定步长，
    如上述代码中的for T from 1 to 300 step 1 draw (t,-ln(t));便是令T从1到300变化，步长为1，绘制出一系列坐标(t, -ln(t))

当然，我们的解释器还需要具备识别注释、出错处理等基本功能，下面是我实现过程中遵循的一些小的原则：

  • 语句以分号结尾，处理过程中按从上到下的顺序进行处理
  • 大小写不敏感，不管是关键字还是变量名都是如此（在读入时都转换成大写）
  • 默认ROT旋转的方向为逆时针旋转
编译原理相关知识

解释器模式常用于对简单语言的编译或分析实例中，为了掌握好它的结构与实现，必须先了解编译原理中的“文法、句子、语法树”等相关概念。

1、文法

文法是用于描述语言的语法结构的形式规则。如：rot is 0;origin is (0, 0);scale is (2,20);用文法表示：

<句子> -> <主语><谓语><表语> 
<主语> -> <代词> | <名词>
<谓语> -> <动词> 
<表语> -> <名词> | <形容词>
 <名词> -> rot|origin|scale
 <动词> -> is
 <形容词> -> 0|(0,0)|(2,20)
注：这里的符号"->"表示“定义为”的意思，用"<"和">"括住的是非终结符，没有括住的是终结符。
2、句子

句子是语言的基本单位，是语言集中的一个元素，它由终结符构成，能由“文法”推导出。

如，上面的文法可以推导出rot is 0;origin is (0, 0);scale is (2,20);，所以这些都是句子。

3、语法树

语法树是句子结构的一种树型表示，它代表了句子的推导结果，它有利于理解句子语法结构的层次。

rot is 0;的语法树如下：

语法树

代码示例

本代码示例代码相对于本文来说过于冗长，下面带有有所省略，有兴趣请参考我的github：interpreter。

代码示例主要流程：

  • 1.读取需要解释的文件
  • 2.使用词法分析器，一个一个依次读取标识符，识别为一个终结符。
  • 3.使用语法分析器，识别具体语句如旋转语句、比例缩放语句等非终结符的开始符号，并对语句进行语法分析
  • 4.调用画图工具，画图

抽象表达式：

// 语法
public interface Grammar {
   void interpret(Parser parser);
}

终结符表达式：

// 终结符类型
public enum TokenType {
    ROT, IS, ORIGIN, SCALE, FOR, FROM, TO, STEP, DRAW, // 保留字
    T, // 参数
    SEMICOLON, COMMA, LEFT_BRACKET, RIGHT_BRACKET, // 分隔符
    EOF, // 文件结束符
    PLUS, MINUS, MUL, DIV, // 运算符
    LN, EXP, SQRT, SIN, COS, POWER, // 函数
    NUMBER // 数字
}
// 具体终结符
public class Token implements Grammar {
    public static final Map<String, Token> TOKEN_MAP;

    static {
        Map<String, Token> tokenMap = new HashMap<>();
        tokenMap.put("ROT", new Token(TokenType.ROT, "ROT"));
        tokenMap.put("IS", new Token(TokenType.IS, "IS"));
        tokenMap.put("ORIGIN", new Token(TokenType.ORIGIN, "ORIGIN"));
        tokenMap.put("SCALE", new Token(TokenType.SCALE, "SCALE"));
        tokenMap.put("FOR", new Token(TokenType.FOR, "FOR"));
        tokenMap.put("FROM", new Token(TokenType.FROM, "FROM"));
        tokenMap.put("TO", new Token(TokenType.TO, "TO"));
        tokenMap.put("STEP", new Token(TokenType.STEP, "STEP"));
        tokenMap.put("DRAW", new Token(TokenType.DRAW, "DRAW"));
        tokenMap.put(";", new Token(TokenType.SEMICOLON, ";"));
        tokenMap.put("(", new Token(TokenType.LEFT_BRACKET, "("));
        tokenMap.put(")", new Token(TokenType.RIGHT_BRACKET, ")"));
        tokenMap.put(",", new Token(TokenType.COMMA, ","));
        tokenMap.put("NUMBER", new Token(TokenType.NUMBER, null));
        tokenMap.put("EOF", new Token(TokenType.EOF, null));
        tokenMap.put("T", new Token(TokenType.T, "T"));
        tokenMap.put("+", new Token(TokenType.PLUS, "+"));
        tokenMap.put("-", new Token(TokenType.MINUS, "-"));
        tokenMap.put("*", new Token(TokenType.MUL, "*"));
        tokenMap.put("/", new Token(TokenType.DIV, "/"));
        tokenMap.put("LN", new Token(TokenType.LN, null));
        tokenMap.put("EXP", new Token(TokenType.EXP, null));
        tokenMap.put("SQRT", new Token(TokenType.SQRT, null));
        tokenMap.put("SIN", new Token(TokenType.SIN, null));
        tokenMap.put("COS", new Token(TokenType.COS, null));
        tokenMap.put("^", new Token(TokenType.POWER, null));
        TOKEN_MAP = tokenMap;
    }

    private TokenType type;
    private Object value;

    public Token(TokenType type, Object value) {
        this.type = type;
        this.value = value;
    }

    public TokenType getType() {
        return type;
    }

    public Object getValue() {
        return value;
    }

    public Token setValue(Object value) {
        this.value = value;
        return this;
    }

    @Override
    public void interpret(Parser parser) {
        // do nothing
    }
}

非终结符表达式（部分代码省略）：

// 非终结符
// 旋转语句
public class RotateStatement implements Grammar {
   @Override
   public void interpret(Parser parser) {
      /**
       * 解释ROT IS NUMBER，即旋转角度，将角度存入上下文中，供后续语句使用。
       * 语法分析：先识别ROT，然后再识别IS，最后识别NUMBER。
       **/
      parser.matchToken(TokenType.ROT);
      parser.matchToken(TokenType.IS);
      parser.setRot((Double) parser.getCurrentToken().getValue());
      parser.matchToken(TokenType.NUMBER);
      parser.matchToken(TokenType.SEMICOLON);
   }
}

上下文（部分代码已省略）：

// 解释器
public class Parser {
    // 语法规则
    private Lexer lexer;
    // 当前token
    private Token currentToken;
    // 输出
    private String output;
    // 旋转角度
    private double rot;
    // 原点坐标
    private double originX;
    private double originY;
    // 缩放比例
    private double scaleX;
    private double scaleY;
    private double from;
    private double to;
    private double step;
    private ExprNode xNode;
    private ExprNode yNode;
    // 语句解释映射
    private Map<TokenType, Grammar> statementMap;
    public Parser(Lexer lexer) {
        this.lexer = lexer;
        this.output = "";
        this.rot = 0;
        this.originX = 0;
        this.originY = 0;
        this.scaleX = 1;
        this.scaleY = 1;
        statementMap = new HashMap<>();
        statementMap.put(TokenType.ROT, new RotateStatement());
        statementMap.put(TokenType.ORIGIN, new OriginStatement());
        statementMap.put(TokenType.SCALE, new ScaleStatement());
        statementMap.put(TokenType.FOR, new ForStatement());
    }
}
//

客户端：

public class Client {
   public static void main(String[] args) throws IOException {
      Semantic semantic = new Semantic();
      semantic.analyze();
   }
}

解释器执行结果：
普通结果

因为写画图代码的时间正值520，所以随手查找了心形坐标函数，执行结果如下，祝天下所有有情人终成眷属。

心形函数

优点

  • 扩展性好。由于在解释器模式中使用类来表示语言的文法规则，因此可以通过继承等机制来改变或扩展文法。
  • 容易实现。在语法树中的每个表达式节点类都是相似的，所以实现其文法较为容易。

缺点

  • 执行效率较低。解释器模式中通常使用大量的循环和递归调用，当要解释的句子较复杂时，其运行速度很慢，且代码的调试过程也比较麻烦。
  • 会引起类膨胀。解释器模式中的每条规则至少需要定义一个类，当包含的文法规则很多时，类的个数将急剧增加，导致系统难以管理与维护。
  • 可应用的场景比较少。在软件开发中，需要定义语言文法的应用实例非常少，所以这种模式很少被使用到。

总结

当你需要解释某种语言，无论这种语句是否通用，也许只有你自己能解释，并且该语言能表示为语法树，有不会太复杂，可以使用解释器模式。

参考

函数绘图语言解释器

解释器模式

完

2023年05月21日17:32:23

标签：解释器,TokenType,模式,Token,tokenMap,put,new
From： https://www.cnblogs.com/mingmingcome/p/17418945.html

相关文章

  • Python 设计模式-观察者模式
    观察者模式是一种行为设计模式，它允许你定义一种订阅机制，可以在对象事件发生时通知多个观察者对象。下面是一个简单的Python观察者模式代码示例：classSubject:"""被观察者类，维护观察者列表，并在状态发生改变时通知观察者"""def__init__(self):self._......
  • 桥接模式（Bridge Pattern）
    模式动机桥接模式（BridgePattern）是一种很实用的结构型模式，如果系统中某个类存在两个独立变化的维度，通过该模式可以将这两个维度分离出来，使得两者可以独立扩展。桥接模式用一种巧妙的方式处理多层继承存在的问题，用抽象关联取代了传统的多重继承，将类之间的静态继承关系转换为动态的......
  • controller是单例模式还是多例模式？spring默认的是单例模式，那么如何保证线程安全
    controller是单例模式还是多例模式在Java中，Controller既可以是单例模式，也可以是多例模式，这取决于具体的实现方式。在单例模式中，Controller只会被实例化一次，多个线程共享同一个实例。这样可以节约系统资源，提高系统性能。但是在多线程环境下，如果不加以保护，可能会出现线程安全的问......
  • 一些小问题和单例模式：饿汉模式和懒汉模式
    智能指针的使用是一种思想，他利用类去管理系统的资源，在一些地方很巧妙的处理了编码不好处理的地方。如下图： 如果是这样一种情况，这个throw抛异常了，此时跳出到catch的地方，处理完程序后再次使用fun函数此时被锁住了，坏了。所以可以用一个类去管理这个锁，使其除了生命周期后自动析构......
  • 实际业务中使用策略模式对代码进行重构
    一.业务描述最近在负责公司一个语音的微服务模块优化，这个模块主要的业务是：1.天猫精灵、小度、若琪、小京鱼、小爱同学、思必驰这些第三方音响对我们的用户进行oauth2/JWT授权； 2.这些第三方音响服务调用我们的设备发现接口对公司的设备信息在第三方平台进行一个存储；3.第三方平台......
  • 适配器模式改造Servlet
    1. 我们编写一个Servlet类直接实现Servlet接口有什么缺点？  11  - 我们只需要service方法，其他方法大部分情况下是不需要使用的。代码很丑陋。2. 适配器设计模式Adapter   11  - 手机直接插到220V的电压上，手机直接就报废了。怎么办？可以找一个充电器。这个充电器就是一个......
  • 聊聊Seata分布式解决方案AT模式的实现原理
    什么是Seata分布式事务解决方案Seata是一款开源的分布式事务解决方案，致力于提供高性能和简单易用的分布式事务服务。为用户提供了AT、TCC、SAGA和XA事务模式，为用户打造一站式的分布式解决方案。AT模式AT模式目前来看是Seata框架独有的一种模式，其它的分布式框架上并没有此种模式......
  • RabbitMQ工作模式-Routing模式
    路由模式：1、每个消费者监听自己的队列，并且设置routingkey。2、生产者将消息发给交换机，由交换机根据routingkey来转发消息到指定的队列。 Routing模式是可以完成订阅模式的工作的，下面的代码在RoutingKey为“inform”的消息中有所体现示例代码：生产者：publicclassP......
  • 我写了本开源书：《3D编程模式》
    大家好，我写了本开源书，罗列了我从自己的实战项目中提炼出来的关于3D编程（主要包括“3D引擎/游戏引擎”、“编辑器”开发）的各种编程模式本书的在线阅读地址在这里：在线阅读本书的源码在Github中，欢迎star，感恩您：Github地址本书的写作花了我300多个小时，将近3个月的全职写作，凝结了我一......
  • 新高考模式志愿填报
    注意志愿之间梯度的问题，建议高、中、低搭配填报，较为合理，避免退档风险。注意志愿之间梯度的问题，建议高、中、低搭配填报，较为合理，避免退档风险。 4、新高考模式下，专业平行志愿填报有哪些参考策略？答：填报高考志愿方法很多，可根据不同情况先选院校再选专业，或者先选专业再选院校，只要......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99