写点什么

Spark Sql 编译模块 - 词法、语法分析器 Antlr4(一

作者:飞哥
  • 2022 年 7 月 20 日
  • 本文字数:4337 字

    阅读完需:约 14 分钟

Spark Sql编译模块-词法、语法分析器Antlr4(一

spark sql 中对于词法、语法的分析使用的 antlr,所以,需要先对 antlr4 有一个大致的了解。

Antlr 基本概念


一门语言由有效的句子组成,一个句子由短语组成,一个短语由子短语和词汇符号组成。要实现一门语言,我们必须构建一个能读取句子以及对发现的短语和输入符号作出适当反应的应用。


这样的应用必须能识别特定语言的所有有效的句子、短语和子短语。识别一个短语意味着我们能确定短语的各种组件并能指出它与其它短语的区别。


例如,我们把输入 a=5 识别为赋值语句,这就意味着我们知道 a 是赋值目标以及 5 是要存储的值。识别赋值语句 a=5 也意味着应用认为它是明显不同于,比如说,a+b 语句的。在识别后,应用将执行适当的操作。例如 performAssignment("a", 5)或者 translateAssignment("a", 5)。


识别语言的程序被称为语法分析器。语法指代控制语言成员的规则,每条规则都表示一个短语的结构。为了更容易地实现识别语言的程序,通常我们会把识别语言的语法分析拆解成两个相似但不同的任务或阶段。


把字符组成单词或符号(记号)的过程被称为词法分析或简单标记化。我们把标记输入的程序称为词法分析器。


词法分析器能把相关的记号组成记号类型,例如 INT(整数)、ID(标志符)、FLOAT(浮点数)等。当语法分析器只关心类型的时候,词法分析器会把词汇符号组成类型,而不是单独的符号。记号至少包含两块信息:记号类型(确定词法结构)和匹配记号的文本。


第二阶段是真正的语法分析器,它使用这些记号去识别句子结构,在本例中是赋值语句。默认情况下,ANTLR 生成的语法分析器会构建一个称为语法分析树或语法树的数据结构,它记录语法分析器如何识别输入句子的结构和它的组件短语。

配置 Antlr

spark 中 antlr 的版本


  <antlr4.version>4.8</antlr4.version>
复制代码

本地配置 antlr4.8

Antlr官方文档


配置


 alias antlr4='java -Xmx500M -cp "/Users/didi/Documents/softdir/antlr-4.8-complete.jar:$CLASSPATH" org.antlr.v4.Tool'  alias grun='java -Xmx500M -cp "/Users/didi/Documents/softdir/antlr-4.8-complete.jar:$CLASSPATH" org.antlr.v4.gui.TestRig'
复制代码

IDEA 中配置 Antlr

新建一个 MAVEN 项目


(1)new -> project ->maven(2)在 pom 文件中引入 antlr 相关的依赖 pom.xml 文件如下


因为 idea 的版本在安装时,预装了 antlr4.10 版本,所以,此处以 4.10 为例


<?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0"         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">    <parent>        <artifactId>dataware</artifactId>        <groupId>org.example</groupId>        <version>1.0-SNAPSHOT</version>    </parent>    <modelVersion>4.0.0</modelVersion>
<artifactId>antlrCalculator</artifactId>
<properties> <maven.compiler.source>8</maven.compiler.source> <maven.compiler.target>8</maven.compiler.target> <antlr4.version>4.10</antlr4.version> </properties>
<dependencies> <dependency> <groupId>org.antlr</groupId> <artifactId>antlr4-runtime</artifactId> <version>${antlr4.version}</version> </dependency> </dependencies> <build> <pluginManagement> <plugins> <plugin> <groupId>org.antlr</groupId> <artifactId>antlr4-maven-plugin</artifactId> <version>${antlr4.version}</version> </plugin> </plugins> </pluginManagement> </build>
</project>
复制代码


(3)安装 antlr 插件



这一块可以通过点击



来查看想要安装的版本

antlr 在 idea 中的使用

(1)新建一个.g4 的文件,这里新建一个 Calculator.g4 ,用来定义一个计算的方法


 grammar Calculator;
prog : stat+;
stat: expr NEWLINE # print | ID '=' expr NEWLINE # assign | NEWLINE # blank ;
expr: expr op=('*'|'/') expr # MulDiv | expr op=('+'|'-') expr # AddSub | INT # int | ID # id | '(' expr ')' # parenthese ;
MUL : '*' ;DIV : '/' ;ADD : '+' ;SUB : '-' ;ID : [a-zA-Z]+ ;INT : [0-9]+ ;NEWLINE :'\r'? '\n' ;DELIMITER : ';';WS : [ \t]+ -> skip;
复制代码


(2) 设置 antlr 的 config



这里可以选择自己想要的目录,接下来所生成的代码将会在这个目录下,最好是将其放在和 g4 相同的目录下,方便自己查看。


点击



用来生成相对应的 java 代码,生成文件包含



查看语法树


在 CalculatorVistorImpl.g4 中右击 prog 所在行,然后右击



然后输入一些简单的测试计算



就会生成图中的语法树

抽象语法树的访问(Vistor 方式)

抽象语法树的例子

定义一个新的实现接口 CalculatorVistorImp 继承 CalculatorBaseVisitor 实现代码为下:


public class CalculatorVistorImp  extends CalculatorBaseVisitor<Integer> {
//存储变量 private HashMap<String,Integer> variable= new HashMap<>();
public CalculatorVistorImp(){ this.variable=variable;
} //遇到print 节点,计算结果,打印出来 public Integer visitPrint(CalculatorParser.PrintContext ctx){ Integer result=ctx.expr().accept(this); System.out.println(result); return null; }
//分别获取expr 节点的值,并计算乘除结果 public Integer visitMulDiv(CalculatorParser.MulDivContext ctx){ Integer param1 =ctx.expr(0).accept(this); Integer param2 = ctx.expr(1).accept(this); if(ctx.op.getType() == CalculatorParser.MUL){ return param1 * param2; } if(ctx.op.getType() == CalculatorParser.DIV){ return param1/param2; } return null; }
//分别获取expr节点的值,并计算结果 public Integer visitAddSub(CalculatorParser.AddSubContext ctx){ Integer param1 =ctx.expr(0).accept(this); Integer param2 = ctx.expr(1).accept(this); if(ctx.op.getType()==CalculatorParser.ADD){ return param1+param2; } if(ctx.op.getType()==CalculatorParser.SUB){ return param1-param2; } return null; } //当遇到Id时从变量表获取数据 public Integer visitId(CalculatorParser.IdContext ctx){ return variable.get(ctx.getText()); } //当遇到Int节点时直接返回数据 public Integer visitInt(CalculatorParser.IntContext ctx){ return Integer.parseInt(ctx.getText()) ; } //当遇到赋值语句时,获取右边expr的值存储到变量表中 public Integer visitAssign(CalculatorParser.AssignContext ctx){ String name=ctx.ID().getText(); Integer value=ctx.expr().accept(this); variable.put(name,value); return super.visitAssign(ctx); }}
复制代码


定义测试类


    public static void main(String[] args) {        String expression = "a = 12\n" +                "b = a * 3\n" +                "a + b\n" +                "a - b\n";        CalculatorLexer lexer = new CalculatorLexer(CharStreams.fromString(expression));        CommonTokenStream tokens = new CommonTokenStream(lexer);        CalculatorParser parser = new CalculatorParser(tokens);        parser.setBuildParseTree(true);        ParseTree root = parser.prog();        CalculatorBaseVisitor<Integer> visitor = new CalculatorVistorImp();        root.accept(visitor);    }
复制代码


运行结果为:


例子分析

在语法定义中定义了 prog、expr、stat 3 中表达式的计算


而所生成的文件中



其中,Calculator.tokens 和 CalculatorLexer.tokens 是内部的 Token 定义,CalculatorLexer 和 CalculatorParser 是生成的词法分析器和语法分析器。 剩下的 java 文件代表着两种访问语法树的方式,CalculatorListener 和 CalculatorBaseListener 对应监听器模式,CalculatoVisitor 和 CalculatorBaseVisitor 对应访问者模式。


通过实现 Visitor 中的关键逻辑,可以直接调用 ANTLR4 生成的各个模块了。


根据输入的字符流相继构造词法分析器(Lexer) 和语法分析器(Parser),然后创建相应的 Visitor 来访问语法分析器解析得到的语法树,最后返回结果。

访问者模式

访问者模式是一种将算法与对象结构分离的软件设计模式 。 这种模式的工作方法如下:假 设拥有一个由许多对象构成的对象结构,这些对象的类都拥有一个 accept 方法用来接受访问者 对象;访问者是一个接口,它拥有一个 visit 方法,这个方法对访问到的对象结构中不同类型的 元素做出不同的反应;在对象结构的一次访问过程中,遍历整个对象结构,对每个元素都实施。


accept 方法,在每个元素的 accept 方法中回调访问者的 visit 方法, 从而使访问者得以处理对象 结构 的每个元素;可以针对对象结构设计不同的 具体访问者类来完成不同的操作 。


而 spark 中有很多地方都使用到了这点。

Antlr 基础类的介绍

各个类的解释如下:


  • Tree 接口,是所有节点的接口。它定义了获取父节点,子节点,节点数据的接口

  • SyntaxTree 接口,增加了获取当前节点涉及到的分词范围(antlr4 会先将语句分词,然后才将分词解析成树)

  • ParserTree 接口,增加了支持 Visitor 遍历树的接口

  • TerminalNode 接口,表示叶子节点,增加了获取当前节点的分词(叶子节点表示字符常量,或者在 antlr4 为文件中的 lexer)

  • TerminalNodeImpl 类, 实现了 TerminalNode 接口,表示正常的叶子节点

  • ErrorNodeImpl 类,继承 TerminalNodeImpl 类,表示错误的叶子节点

  • RuleNode 接口,非叶子节点,表示一个句子的语法, 对应 antlr4 文件中的 parser rule

  • RuleContext 类,实现了 RuleNode 接口

  • ParserRuleContext 类,在 RuleContext 的基础上实现了查询子节点的方法,并且支持 Listener 遍历

  • InterpreterRuleContext 和 RuleContextWithAltNum 时用于特殊用途的

  • 在使用的过程中,我们主要使用 TerminalNodeImpl(叶子节点)和 ParserRuleContext(非叶子节点)两个类


发布于: 刚刚阅读数: 5
用户头像

飞哥

关注

公众号:飞哥小记,喜欢自问的程序媛 2019.11.05 加入

还未添加个人简介

评论

发布
暂无评论
Spark Sql编译模块-词法、语法分析器Antlr4(一_飞哥_InfoQ写作社区