简介

本文最初的目的是为了SQL解析器，这里先对编译的基本概念进行整理。

参考1、参考2

• 概念

  可以把 SQL 文本解析成 AST，然后你再遍历 AST 拿到你需要的信息。

  概念上，首先要区分语言分析器（Parser）和语法解析器（Grammar）两个概念。

  Parser是自动机和机器语言领域的概念，传统意义上，Parser生成的是一个抽象语法树；

  Grammar的工作是去理解Parser的输出，转换为SQL的关系代数表达式；

• 工具

  从已经有的工具来看，你可以最使用第三方Parser生成工具（对于Java是ANTLR，对于C语言是lex/yacc之类）

  • Antlr(presto)
  • calcite
  • lex
  • yacc, LALR(1)词法分析
  • TiDB的parserhttps://github.com/pingcap/tidb/tree/master/parser

• 抽象语法树

  抽象语法树的形式像极了json，将节点抽象成固定的类型，然后解析字符串，构件相应的节点。

  在前边表达式的解析中，介绍过逆波兰算法将表达式表示为后缀形式。

  这里也应该类似，关键字是运算符，其他认为是操作数。

编译过程

参考

1. 词法分析(Lexical Analysis)

   将文本分割成各自的tokens

   

   这个过程是遍历源代码，根据分隔符进行切分，识别出字符代表的类型。

   这里可以上正则表达式，可以用NFA、DFA(有穷自动机)，也有下推自动机

2. 语法分析(Syntactic Analysis)

   tokens被解析成解析树的层级结构

   

   

   语法分析1

   两类语法分析器：自顶向下（递归子程序，预测分析法LL(1)），自底向上（算符优先分析法，LR系列）

3. 语义分析(Senmantic Analysis)

   在语法分析的过程中，可以平行进行语义处理，在语法分析栈旁边设置语义信息栈。

   附带有语义属性的前后文无关文法，是前后文相关的，称为属性文法。

   例如：

   

   将前后文的属性放到语义属性中去。

4. 生成(Generation)： 遍历抽象语法树形成机器码

   这里忽略连接的过程。

   

   

   二进制是机器码，它与汇编一一对应。

关于汇编

1. 定义变量

   

2. 条件语句

   

   

3. 循环语句

   

4. 函数