May you do good and not evil.
May you find forgiveness for yourself and forgive others.
May you share freely, never taking more than you give.

前言

 对于非计算机专业的同学，在学习SQLite源码时肯定也会有一个很大的疑问，SQL是如何被解析和执行的？大家应该都明白，SQL虽然非常精简和易读，但其语句是可变长的，同时又支持许多表达式、函数等复杂特性，如果仅用if...else...完美的覆盖SQL的解析，那几乎是不可能的。因此你可能会急迫的去源码里寻找答案，并且很容易的找到两个关键函数sqlite3RunParser、sqlite3Parser，代码并不算长，你喜出望外，意识到自己终于要揭开SQL解析的神秘面纱了，但待你定下神来一句一行的想去读懂这两个函数时，却绞尽脑汁，终究看不懂这一堆乱七八糟的东西...
 我并不例外，看了两天这块代码，网上查资料，这方面的信息少之又少，终究没能找到一篇可以让我理解为什么的文章，还好SQLite的注释非常详细：the parse.c file generated by lemon and the tokenize.c file are concatenated 。让我如此郁闷的代码，原来是被一个叫lemon的程序自动生成的，再查lemon，语法分析、LALR(1)、自动生成、编译器的编译器、Lex/Yacc、Bison...一堆的关键词都指向了计算机专业核心专业课程--编译原理，那么只能从这里寻求突破了。

编译原理

 程序语言是向人以及计算机描述计算过程的符号，一个程序语句，在可以被运行之前，它首先需要被翻译成一种能够被计算机执行的形式。完成这项翻译工作的软件系统称为编译器（compiler）。而编译原理正是编译器的设计和实现的理论基础。SQL(Structured Query Language)，既然也是一个可以被计算机识别的语言，毫无悬念，可以基于编译原理指导完成解析。

1.编译过程

 大道至简，科学的产生就是先从具体到抽象得到基本原理的过程，而技术的应用则是以基本原理所描述的模型为基础，寻求对自然事物的科学描述的过程。因此，计算机语言的解析过程和自然语言的翻译过程必然是高度一致的。我们从如下一个英文句子的翻译过程中，理解一下计算机语言的编译过程。

The compiler can translate a program from source language to target language.
1.识别句子中的每一个单词 =>词法分析
2.分析句子的语法结构 =>语法分析
3.根据句子的结构进行初步翻译 =>中间代码生成
4.对译文进行修饰 =>优化
5.写出最后的译文 =>目标代码产生

2.词法分析

2.1 词法分析的职责和流程

 词法分析器的主要任务是读入源程序的输入字符、将它们组成词素，生成并输出一个词法单元序列，每个词法单位对应一个词素。这个词法单元序列被输出到语法分析器中进行语法分析。词法分析器通常还要和符号表进行交互，当词法分析器发现一个标识符的词素时，它将这个词素添加到符号表中。在某些情况下，词法分析器会从符号表中读取有关标识符种类的信息，以确定向语法分析器传送哪个词法单元。

词法分析器在编译器中的位置

 词法分析器的大概工作过程为：扫描器调用预处理子程序，将源程序输入到输入缓冲区中，预处理子程序读取输入缓冲区数据，剔除无用的空白、跳格、回车等编辑性字符、给出句末符等，并将处理后的更规范的文本输入到扫描缓冲区。扫描器从扫描缓冲区中读入字符并根据词法规则进行分词，输出单词符号。

词法分析器结构

2.2 词法分析的形式化处理

 如何让计算机自动的进行词法分析，甚至如何让计算机能够按照词法规则自动的生成词法分析器，都需要对词法分析过程进行形式化处理和分析。为了描述程序中合法的单词，引入正规集和正规式（正规表达式or正则表达式）的概念(集合论知识），利用正则模式构造一段代码，这段代码能够检查输入字符串并在输入的前缀中找出一个和模式匹配的词素，这个过程使用状态转移图可以非常形象的表达。
 作为构造词法分析器的一个中间步骤，将正则模式转换成具有特定风格的流图，称为“状态转换图”。状态转换图有一组被称为“状态”的节点或者圆圈。词法分析器在扫描输入串的过程中寻找和某个模式匹配的词素，而转换图中的每个状态代表一个可能在这个过程中出现的情况。状态图的边从图的一个状态指向另外一个状态，每条边的标号包含了一个或多个符号。通过这样的状态转换图，词法分析器就可以非常容易的被写出来。

状态转换图

 如何实现该状态转换图，自动机理论中有完善的形式化描述策略，即确定性有限自动机(DFA),确定性有限自动机要求有唯一的初态，且从一个状态开始，识别一个新的字符后，一定可以到达一个确定的状态，即其状态转移函数时一个单值的部分映射，因此实现起来非常简单，大概过程包含：

1. 定义初始状态值，并定义一个包含所有状态和输入符号的二维表。
2. 从初始状态开始，循环读入一个符号，并根据当前状态和读入的符号查询二维表，跳转至最新状态。
3. 循环上述步骤直至遇到终态结束。

 但由于确定性有限自动机描述的状态转换过于基础，似乎和实际的需求还有一些差别，计算机科学家们定义了另外一种看上去更一般化的有限自动机--非确定性有限自动机（NFA）。其要求初态不再唯一，可以有多个。同时其状态转移函数不再是单值映射，其允许在输入一个字（由字符扩展到字）后，可以存在到达多种状态的可能。这样一来，从感官上我们会感觉NFA的识别能力似乎更加强大，实现起来会更加复杂，因为定义上看DFA只是NFA的一个特例。但经过理论学家的研究和证明，NFA和DFA的识别能力是相等的，并且研究出了NFA化简DFA的“套路”，这样，人民们可以非常容易的用NFA描述问题，再用确定的理论方法转成DFA进行计算机处理。基于这些理论依据，现在人们已经比较容易的开发出词法分析器生成器，比如Lex。

2.3 SQLite中的词法分析

 虽然像Lex这样的词法分析器生成器已经存在，但由于SQLite中的SQL语句分词比较简单，其并未使用词法分析生成器来自动生成词法分析器，而是作者自己手工编写实现的代码，因此上述的知识点描述，仅用于求解为什么、如何做的问题，对源码的理解并无影响。关于SQLite的词法分析是怎样的逻辑，我们后续文章详细介绍。

3.语法分析

3.1 语法分析的理论体系

 讲到语法分析，不得不提到乔姆斯基的形式语言体系。乔姆斯基，这个本世纪最伟大的语言学家、哲学家，一个地地道道的政治愤青,点我了解CHOMSKY ，最初基于对自然语言研究的动机提出了一套完整的语言体系，但却意外的深刻影响了现代计算机程序设计语言的发展，成为编译理论和方法的基础。
 乔姆斯基把文法分为了四种类型：0型，1型，2型，3型，详细的形式化定义网上或者龙书自行查询，下面是一些对比和简介：

用一张图来描述这几种文法的关系：

乔姆斯基语言体系

3.2 程序设计语言使用文法

 非常遗憾的是，程序设计语言既不是上下文无关文法，又不是上下文有关文法。比如，计算机科学家已经证明形如如下定义的文法，只能用0型文法分析：

分析：这个语言模式描述了是终结符a,b组成的字符串，中间的C也是一个终结符，该语言模式实际上是要求了前后一致、前后匹配。但这个模式在程序设计语言中有着非常广泛的存在：比如 在很多计算机程序涉及语言中要求变量要先定义后使用；有些程序设计语言要求函数调用的形参和实参要保持个数、顺序和类型完全一致；而这些约束实际上就是C模式。即想要用文法描述这类前后相关的约束，上下文无关文法做不到，甚至上下文有关文法也很难做到。但对于现今的程序设计语言，均使用上下文无关文法用来描述它所能描述的文法，因为上下文无关文法非常成熟高效，且能描述程序设计语言中大部分的约束。而对于它无法描述的约束，通常放到语义分析的过程中去做【权衡思想】。
 通过上面的介绍，我们已经知道程序设计语言语法设计实现的理论基础是上下文无关文法，主要得益于该文法的恰当的语言描述能力、成熟高效的计算机处理策略（下推自动机-push-down automata, PDA）。对于下推自动机，是有完整的定义和实现策略的，可网上查询了解，其主要是依赖栈来实现，区别于有限自动机，其核心多了一个有穷的可推入栈的字母表，即可推入堆栈的符号集合，在语法分析源码分析时，将会看到其真正的面目。

3.3 上下文无关文法的实现方法

 谈实现方法前，先看一下句子、句型和语言的基本定义：

文法分析基础定义

 语法分析的任务便是分析一个文法句子的结构，按照文法产生式的规则识别输入符号串是否是一个合法的句子。语法分析的方法大致可以分为两类：

规约：根据文法产生式规则，把串中出现的产生式的右部替换成左部符号
推导：根据文法产生式规则，把串中出现的产生式的左部替换成右部符号

3.4 语法分析事例

3.3.1 自上而下的语法分析
 如下图所示，自上而下分析从文法的开始符号，即树的根节点S出发，向下推导，让它去跟输入串x*y从左到右匹配。S只有一个候选，将S扩展为x A y，输入x，终结符匹配成功，继续往下推导。输入*号，此时规则要求匹配A，A是一个非终结符，有两个候选式，选择第一个候选式扩展两个*号，第一个*号匹配输入，继续调用词法分析器得到输入y，此时语法规则要求输入是一个*号，匹配失败，该层匹配结束。那是不是意味着句子非法呢？其实不然，主要是A有两个候选式，此时应该回溯到A的开始处，选择第2个候选，逐步推导下去，匹配成功。

自上而下分析

 在分析过程中，我们可以发现自上而下分析方法存在的问题：分析过程中，当一个非终结符用一个候选式匹配成功时，这种匹配可能是暂时的，一旦遇到错误，将不得不回溯。除此之外，自上而下分析方法还有一种文法左递归问题，导致语法树会无限扩展下去而陷入死循环，没法读入串进行分析。LL(自左到右，最左推导)分析法主要研究的问题就是如何消除回溯和左递归。

文法左递归问题

3.3.2 自下而上的语法分析
 如下图所示，给定算数表达式文法G，开始符号是非终结符E，它有六个候选。从左到右输入，输入i，规约成E，输入串变成了E*i+i,接着输入*,没有匹配，继续移进。然后继续输入i，i规约成E，语法变成E*E+i。而E*E又可以规约为E,产生式变为E+i，如此继续下去，最后规约得到E，匹配成功。

自下而上分析

 在分析过程中很容易发现，该分析方法非常适合使用栈进行分析，其核心问题是识别可归约串。虽然例子中未涉及到该分析方法的问题，但并不是说这个分析法是完美的。自下而上分析方法会有移进-规约冲突和规约-规约冲突。LR（从左到右扫描输入串、自下而上进行规约）分析法及其各种变种（SLR、LR(1)、LALR(1))就是研究如何进行自下而上分析法如何设计的。

3.5 SQLite 语法分析方法

 SQLite中SQL语句的语法分析使用的是LALR(1)[look ahead LR(1)]分析法实现的 ，LALR技术得到的分析表比LR方法的分析表会小很多(因为其多了一步同心集的合并操作),因此会更加简洁高效。SQLite其语法分析器是一个名字为lemon的程序根据输入语法规则自动生成的代码，我们将在后面的学习中分析lemon程序的工作原理。

4.中间代码生成

 SQLite中的中间代码生成部分带真正了解了SQL如何被解析后，单独开启章节介绍。

5.优化

 SQLite中的优化部分带真正了解了SQL如何被解析后，单独开启章节介绍。

6.目标代码生成

 SQLite中的目标代码生成部分带真正了解了SQL如何被解析后，单独开启章节介绍。