Hive-技术补充-ANTLR词法语法分析

一、背景

要清晰的理解一条Hql是如何编译成MapReduce任务的，就必须要学习ANTLR。下面是ANTLR的官方网址，下面让我们一起来跟着官网学习吧

ANTLR

二、ANTLR元语言

1、启发

静下来想想，一门语言有什么组成，比如我们的中文：

女朋友昨天在厨房给我做了一顿丰盛的晚餐，让我吃得心满意足。

我们先不说这句话的实现难度(╥﹏╥...)，单论它有什么组成

女朋友	主语
昨天	状语
在厨房	状语
给我	宾语
做了	谓语
一顿	定语
丰盛的	定语
晚餐	宾语
，	标点符号
让我吃得	补语
心满意足	补语
。	标点符号

可能对于我们成年人来说很很容易理解他们，因为我们已经学习并轻松的掌握它了，如果一个幼儿园的小朋友呢？

要想理解里面的意思，就必须对其中的词组和标点符号进行正确的拆分归类。

因此，语言是由一系列有意义的语句组成，而语句又是由词组成，词组又由更小的子词组、标点符号组成，再往细的说每个字都由拼音中的字母组成。

计算机语言也是这样。

如果一个程序可以分析或者执行一种计算机语言，我们就称之为解释器

如果一个程序可以将一种计算机语言翻译成另外一种计算机语言，我们就称之为翻译器，也称编译器。

计算机语言也是有类似我们中文这样的规则，也就是语法，ANTLR语法本身又遵循了一种专门用来描述其他语言的语法，我们称之为ANTLR元语言。

到这里有没有感觉它很强大，它给了你一种创造语言的能力

三、词法分析器

思考以下，我们是如何听到一句话而后理解它的，我们拆分下。

我们先听到了一个一个音，而后组成了一个一个词，而后组成了一个一个句子，最终我们听到了一句完整的话。

还有，我们脑子里已经学习并具备了把多个音组成词，把词组成句子，并理解该句子的场景含义的规则。

编译器收到我们编写计算机语言也是类似的，需要读取每个二进制、组成字符、组成单词或符号、组成一个声明或一个赋值或一个函数。

这个过程就是词法分析

ANTLR中将符号或词法符号称为token，把实现这个词法分析的程序称为词法分析器lexer。

词法符号有两部分信息：
1、类型
2、对应的文本

词法分析器可以将这些词法符号进行归类，例如INT(整数)、ID(标识符)、FLOAT(浮点数)等。

四、语法分析器

这里我们先介绍一个名词：语法分析树

它是一个经过语法规则解析后将每个词存储形成的一个树形数据结构，方便语法分析器可以将最原始的语言通过树形结构传递给下一个程序，与其每个过程都解析下字符流，不如将字符流形成语法分析树，方便各个过程的多次访问和遍历

词法分析器处理字符序列并将生成的词法符号提供给语法分析器，语法分析器随即根据这些信息检查语法的正确性并建造一棵语法分析树。

下面我们看下在建立语法分析树的过程中使用了ANTLR的哪些数据结构和类名。

CharStream、Lexer、Token、Parser，以及ParseTree

ParseTree 的子类 RuleNode 和 TerminalNode 二者分别是树的根节点和叶子节点

子树的根节点的类型实际上是 StatContext AssignContext 以及 ExprContext 他们被成为上下文对象

连接词法分析器和语法分析器的管道是 TokenStream

语法分析树的叶子节点仅仅是存放词法符号流中的词法符号的容器。每个词法符号都记录着自己在字符序列中的开始位置、结束位置，而非保存子字符串的拷贝。其中不存在空白字符串对应的词法符号

五、语法分析器的监听器和访问器

语法分析器已经生成了语法分析树，接着就需要使用它，使用语法分析树的方式有两种：

监听器器和访问器

1、监听器----内建的遍历器

为了遍历树时触发的事件转化为监听器的调用，ANTLR 提供了 ParseTree-Walker 类

ANTLR 会为每个语法文件生成一个ParseTreeListener的子类，在该类中，每条规则都有对应的enter() 和 exit()

例如当遍历器访问 assign 规则对应的节点时，就会调用 enterAssign() 然后将对应语法分析树节点 AssignContext 实例当作参数传递给它

在遍历器访问了 assign 节点的全部节点后调用 exitAssign() ，如图所示：组虚线标识了对语法分析树进行深度优先遍历的过程

下图展示了一条赋值语句生成的语法分析树中，ParseTree-Walker 对监听器方法调用的完整过程

使用监听器的好处就是，我们不需要再编写遍历语法分析树的代码，这一切都是自动进行的

2、访问器---访问者模式

在命令行中加入 -visitor 选项可以指示 ANTLR 为一个语法生成访问器接口，语法中的每条规则对应接口中的一个 visit()

public class HelloWorldParser extends Parser {

    //......省略......
     public static class RContext extends ParserRuleContext {
        
        //......省略......
        @Override
        public <T> T accept(ParseTreeVisitor<? extends T> visitor) {
            if ( visitor instanceof HelloWorldVisitor ) {
                return ((HelloWorldVisitor<? extends T>)visitor).visitR(this);
            }else{
                return visitor.visitChildren(this);
            }
        }
        //......省略......

    }

    //......省略......

}

//这个接口为｛@link HelloWorldParser｝生成的解析树定义了一个完整的通用访问者。
public interface HelloWorldVisitor<T> extends ParseTreeVisitor<T> {

    //访问｛@link HelloWorldParser#r｝生成的解析树
    T visitR(HelloWorldParser.RContext ctx);

}

//这个类提供了｛@link HelloWorldVisitor｝的一个空实现，
//可以扩展它来创建一个只需要处理可用方法子集的访问者
public class HelloWorldBaseVisitor<T> extends AbstractParseTreeVisitor<T> implements HelloWorldVisitor<T> {

    //默认实现返回对{@code-ctx}调用{@link#visitChildren}的结果
    @Override
    public T visitR(HelloWorldParser.RContext ctx) { return visitChildren(ctx); }
}

下面是使用常见的访问者模式对我们的语法分析树进行操作的过程