Presto 设计与实现（十一）：抽象语法树 AST

1. ANTLR4 是什么？

下面摘自 《ANTLR 4 权威指南》。

定义：

ANTLR 是一款强大的语法分析器生成工具，可用于读取、处理、执行和翻译结构化的文本或二进制文件。

作用：

它被广泛应用于学术领域和工业生产实践，是众多语言、工具和框架的基石。

ANTLR4 的应用实践：

• Twitter 搜索使用 ANTLR 进行语法分析，每天处理超过 20 亿次查询；

• Hadoop 生态系统中的 Hive、Pig、数据仓库和分析系统所使用的语言都用到了 ANTLR；

• Lex Machinal1 将 ANTLR 用于分析法律文本；

• Oracle 公司在 SQL 开发者 IDE 和迁移工具中使用了 ANTLR；

• NetBeans 公司的 IDE 使用 ANTLR 来解析 C++；

• Hibernate 对象-关系映射框架 （ORM）使用 ANTLR 来处理 HQL 语言。

2. ANTLR4 集成流程

Presto 底层基于 ANTLR4 实现了 SQL 语句的词法分析、语法分析和抽象语法树 AST 的生成， ANTLR4 主要的集成流程：

1. 按照 anltr4 的语法规范，编写词法规则和语法规则，存储在后缀为 g4 的文件中，这里面需要注意 grammar 名称必须和文件名保持一致；

2. 安装 antlr4-tools 工具：通过 pip install antlr4-tools 或安装 IDEA ANTLR v4 插件，该工具通过模拟输入验证 g4 文件语法定义的正确性，还可以根据 g4 文件生成开箱即用的一整套代码：词法分析 -> 语法分析 -> 抽象 AST 生成；

3. 项目中添加 antlr4-runtime 依赖，将生成的代码引入到实际的项目中；

4. antlr4 还提供了易于扩展的访问者模式，通过实现 Listener 或 Visitor 相关接口，可以访问 AST 树上的所有节点，这样你可以根据节点不同类型进行处理。

3. Presto 的 AST

Presto 使用 ANTLR4 生成的代码对 SQL 语句解析后，得到语法树 ParserRuleContext，通过 Visitor AstBuilder 对 ParserRuleContext 所有节点进行遍历，遍历过程中会构建 Presto 自己定义的语法树，语法树的节点类型为 Node 抽象类。

Statement 表示 SQL 语句的整体，Query 是对整个查询的抽象：

QuerySpecification 表示查询语句详细的组成部分：

我们再来看下面的查询语句：

经过词法分析、语法分析和生成 ANTLR4 AST 树后，Presto 通过观察者模式自己构建的语法树。