1 | Apache Doris 源码分析2 - 词法分析和语法分析 |
上回介绍了从 fe 进程启动, 到接收到一条 SQL 并执行的过程, 这回深入分析下 SQL 是如何从一个平平无奇的字符串, 变成了一个适合分析处理的对象的(AST 抽象语法树). 故事的起点还是回到上次的 handleQuery().
1 | //位置: fe/fe-core/src/main/java/org/apache/doris/qe/ConnectProcessor.java |
先看重点1: 词法分析和语法分析 analyze(originStmt)的内部逻辑, 一会儿再看重点2.
1 | //位置:fe/fe-core/src/main/java/org/apache/doris/qe/ConnectProcessor.java |
词法分析 jflex
词法分析的主类是 SqlScanner.java, 这个代码文件是通过工具处理 sql_scanner.flex 而生成的代码. 那咱们就先分析一下这个原始的 .flex 文件.
flex 文件的主要内容由 UserCode, Options and declarations, Lexical rules 三段组成, 段与段之间使用%%分割, 下面结合各段的内容, 分析一下其原理.
1 | // 位置: fe/fe-core/src/main/jflex/sql_scanner.flex |
通过上面的代码片段, 可以看出 jflex 词法分析这个函数的输入和输出分别为:
- 输入:
- 一个 sql 字符串
- 词法上来说, 所有合法的单词的正则表达式
- 特定类型的单词的独特处理方法
- 关键词/操作符列表
- 输出:
- 一个可以返回单词列表, 或者抛出异常函数: public java_cup.runtime.Symbol next_token()
要完成从这种输入到输出的转换逻辑, flex 会构造有限状态自动机并放到输出的 JAVA 类中, JAVA类在扫描字符串的过程中通过这个有限状态自动机来找到一个单词(匹配过程使用最长匹配优先的原则), 有限状态自动机的原理比较通用, 大学编译原理课程里面都会学, 感兴趣的同学可以自行了解.
语法分析 cup
下面以 fe/fe-core/src/main/cup/sql_parser.cup 文件的内容, 介绍一下 CUP 的规范说明.
1 | // 1. package and import specifications |
CUP 的目标在用户给定语法规则的前提下, 构造一个语法解析器函数, 这个构造出来的函数可以接受一系列的 token, 返回一棵抽象语法树(AST). CUP 构造的语法解析器是 LALR(1) 解析器的一种实现, 感兴趣的同学可以去搜索一下相关的原理介绍.
什么是抽象语法树 (AST)
在 Doris 的场景中, 使用了 jflex 作为词法分析器产生一系列的 token, 然后再使用 CUP 来将这些 token 组合成一系列的 AST 抽象语法树 List
以删库跑路的语句 DropDbStmt 为例来分析一下 AST 的结构:
- DropDbStmt
- boolean ifExists
- String dbName
- boolean forceDrop
完整的代码可参考如下:
1 | //位置: fe/fe-core/src/main/java/org/apache/doris/analysis/DropDbStmt.java |
如果分析 SelectStmt 会发现它的 AST 树要复杂很多, 结构如下:
- SelectStmt
- SelectList selectList
- boolean isDistinct
- Map<String, String> optHints
- List<SelectListItem> items
- Expr expr
- TableName tblName
- boolean isStar
- String alias
- ArrayList<String> colLabels
- FromClause fromClause_
- ArrayList<TableRef> tableRefs_
- GroupByClause groupByClause
- GroupingType groupingType
- ArrayList<Expr> groupingExprs
- ArrayList<Expr> oriGroupingExprs
- List<ArrayList<Expr>> groupingSetList
- List<Expr> originalExpr
- Expr havingClause
- Expr whereClause
- Expr havingPred
- AggregateInfo aggInfo
- AggregateInfo mergeAggInfo_
- AggregateInfo secondPhaseDistinctAggInfo_
- AggPhase aggPhase_;
- ExprSubstitutionMap intermediateTupleSmap_
- ExprSubstitutionMap outputTupleSmap_
- ExprSubstitutionMap outputToIntermediateTupleSmap_
- List<Expr> partitionExprs_
- ArrayList<Integer> materializedAggregateSlots_
- boolean isDistinctAgg
- boolean isMultiDistinct_
- ArrayList<Integer> firstIdx_
- ArrayList<Integer> lastIdx_
- AnalyticInfo analyticInfo
- ArrayList<Expr> analyticExprs_
- List<Expr> commonPartitionExprs_
- ExprSubstitutionMap analyticTupleSmap_
- List<Expr> lhs_
- List<Expr> rhs_
- ExprSubstitutionMap baseTblSmap
- List<Expr> lhs_
- List<Expr> rhs_
- ValueList valueList
- List<ArrayList<Expr>> rows
- GroupingInfo groupingInfo
- VirtualSlotRef groupingIDSlot
- TupleDescriptor tupleDescriptor
- TupleId id
- int id
- String debugName
- ArrayList<SlotDescriptor> slots
- SlotId id
- TupleDescriptor parent
- SlotDescriptor src
- TupleId id
- List<Expr> realSlots
- TupleDescriptor tupleDescriptor
- TupleDescriptor virtualTuple
- TupleId id
- int id
- String debugName
- ArrayList<SlotDescriptor> slots
- SlotId id
- TupleDescriptor parent
- SlotDescriptor src
- TupleId id
- Set<VirtualSlotRef> groupingSlots
- TupleDescriptor tupleDescriptor
- TupleId id
- int id
- String debugName
- ArrayList<SlotDescriptor> slots
- SlotId id
- TupleDescriptor parent
- SlotDescriptor src
- TupleId id
- List<Expr> realSlots
- TupleDescriptor tupleDescriptor
- List<BitSet> groupingIdList
- GroupByClause.GroupingType groupingType
- BitSet bitSetAll
- VirtualSlotRef groupingIDSlot
- Expr havingClauseAfterAnaylzed
- SelectList selectList
首层子树结构可参考如下的代码:
1 | // 位置: fe/fe-core/src/main/java/org/apache/doris/analysis/SelectStmt.java |
语法分析小结
通过上面的分析可得到, 可以看出语法分析 cup 这个函数的输入和输出分别为:
- 输入:
- 上面语法分析得到的单词列表 (或扫描器)
- 终结符和非终结符的列表
- 所有终结符的优先关系
- 语法规则的集合
- 输出:
- 返回错误, 或者一个抽象语法树 (AST)
埋个伏笔
以上就是词法分析和语法分析的所有相关的所有内容了, 想了解更多其它语句的 AST 结构, 可以自行去源码中查找. 另外还有一个值得一提的事情是, 所有的语句, 最终都会实现了接口: ParseNode.java, 这个接口的代码如下:
1 | // 位置: fe/fe-core/src/main/java/org/apache/doris/analysis/ParseNode.java |
这个接口主要包含两个方法, 一个是转换为 String 类型的 Sql 语句, 一个是 analyze(Analyzer analyzer) 方法, 后面的分析中, 会重点分析一下这个 analyze 方法.