词法语法分析

词法分析由称为“词法分析器”的词法分析程序完成的，在数据库中，它将sql视为一个字符流，从左到右对这个字符流进行扫描，将其切分为“单词”流。

单词是具有独立意义的基本语法单元，也被称为“记号”（token）。sql中的关键字（例如SELECT、UPDATE等）、标识符（例如列名、表名）、常量（字符串、数字等）、运算符（加减乘除等）等都是单词。

转化为“单词”流之后，数据库系统的“语法解析”模块进一步分析并生成抽象语法树，描述这条sql的类型和组织结构，供其他模块（例如语义分析、查询优化等）使用。本篇文章将着重讲解词法分析的原理细节。

2.1 文法

如何正确识别并切分出字符流中的单词呢？当然，首先需要清楚地定义“单词”是如何基于字符构建的。

例如：标识符是由数字/字母/下划线构成的字符串序列，且首字符不能是数字；字符串常量是由引号括起来的字符序列，根据前缀又可以进一步区分为：位串常量（例如B‘00101’）、十六进制位串常量（例如X‘1FF’）、Unicode转义常量（例如U&'d061t+000061'）等等。

根据这些定义，似乎就能按部就班地实现一个词法分析器了。如果只是为某一个特定产品实现词法分析功能，确实足够了，但是计算机学科的前辈们却将这个问题上升为一个通用性问题：如何“形式化”地描述一个语言，并在计算机上实现有效且自动化的计算。

其中“形式化”的描述是实现计算机自动计算的基础，也是为这个问题求得一个通解的基础。这样一来，每当需要实现词法分析功能时，开发者只需提供词法的形式化的描述，就能复用给出的“通解”来实现一个词法分析器了。形式化的描述就需要使用到“文法”这么一个工具，下面将介绍如何是用来文法来形式化地描述词法规则的吧。

“文法”（grammar）最早是有语言学家在研究自然语言的过程中提出来的，用于描述自然语言结构特征。

例如：

<句子> → <主语> <谓语>

<主语> → <冠词> <形容词> <名词>

...

同样，为了形式化描述字符是如何构成“单词”， “单词”又如何构成程序/SQL语言（问题扩大化到了语法解析），也需要定义相应的“文法”。

一般将文法定义为一个四元组的G = (V, T, P, S)，其中：

• V，非终结符的非空有穷集合。非终结符，也可以称之为语法变量，例如上面的“<句子>”、“<主语>”等都是语法变量；

• T，终结符集合的非空有穷集合。对词法分析来说，终结符就是sql中字符；对于语法解析来说，终结符就是具体的单词；

• P，产生式的非空有穷集合。产生式也可以称为语法规则，其形式为：A → B，表示A的定义为B。其中A∈V， B∈(V U T)*。

• S，起始符号，且S∈V。

另外，在讨论“文法”时会经常提及两个操作：派生和规约。

当文法G中存在产生公式A →B，则符号串“αAβ”可以推导出“αBβ”，则称“αAβ”派生出“αBβ”，记为“αAβ” ⇒“αBβ”；当a⇒b⇒c ... ⇒z，则可以记为a (⇒)* z。相应的，称“αBβ”可以规约为“αAβ”。

这个四元组的文法G就能形式化地定义一门“语言”：L(G) = {w | S (⇒)*w && w∈T* }，即由起始符号S派生出来的“终结符”序列的集合。

这里简单举一个例子，用文法来形式化定义的程序语言中的标识符的结构（其中“｜”标识是或者的意思，用来简化文法的书写）：

V = {<id>, <letter>,<digit>},T = {A,B...Z,a,b,...z,0,1,...9},S=<id>,P = {<id> → <letter> | <id> <digit> |<id> <letter>          <letter> → A | B |... | Z | a | b | ... | z | _<digit> → 0 | 1 | ... | 9};

其中语法规则P用“递归”的形式定义标识符的构成：字母/下划线开头，后接数字/字母/下划线。这种递归的定义方式使得文法的表达非常复杂的词法或者语法结构。

2.2 正则表达式

相比语法解析，词法分析使用的语法规则往往比较简单，一般使用“正则文法”就足以描述“单词”的结构了。所谓“正则文法”，是指当文法的产生式都具有如下形式，其中A、B ∈V，为语法变量，α是终结符：

A → α，

A → α B

“正则文法”有一个有趣的地方，即使用“正则文法”能够表述单词，也能够使用“正则表达式”来描述。因为正则表达式的表达能力和正则文法是相同的，且它们直接可以互相转换，所以一般使用更为直观的正则表达式来表示单词的构成。例如前面例子中，标识符的文法规则用正则表达式可以表述为（为简单起见letter、digit分别表示字母和数字）：letter (letter | digit)*

这个简单例子中包含正则表达式的如下4种基本操作：

大家肯定好奇“正则文法”如何等价转化为“正则表达式”呢？由于转换的目标就是将“起始符”S表示成由“终结符”构成的正则表达式，如果我们将“非终结符”当作变量，“终结符”当作系数，这个过程变成了方程式的求解：通过“代入消元”消除除S之外的所有其他“非终结符”。

这里是一个简单的例子，假设有如下文法：

（1）   S → aS｜aB                                      

（2）   B → bB｜bC｜aB                     

（3）   C→ cC｜c                                      

求解对应正则表达式的过程如下：
根据（3）得到：C = c* c；（4）

根据（2）和（4）得到：B = bC = bc*c       （5）

根据（2）和（5）得到：B = bB｜aB = (a|b)*B = (a|b)* (bc*c) （6）

根据（1）得到：S = a*aB （7）

根据（6）和（7）得到：S = a*aB = a*a(a|b)*(bc*c)。

相应的，正则表达式也能过转换为对应的正则文法，这里就不做详细介绍了。总之，这里要表达的意思就是，词法的结构可以使用更为简洁的正则表达式来表达。

2.3 有穷状态自动机

之所以使用正则表达式来形式化描述词法，除了正则表达式更为简洁直观之外，更为重要的是它能够等价地转化为“有穷状态自动机”的形式，而有穷状态自动机的形式更贴近代码实现。这里举一个简单的例子，比如十六进制的正则表达式为：

hex → 0 x ( 0 | 1 | ... | 9 | a | ... | f | A | ... | F ) ( 0 | 1 | ... | 9 | a | ... | f | A | ... | F)*

相应的有穷状态自动机如下：

该状态机有一个“起始状态”（s1），一个或者多个“接受状态”（s5）。状态机不断地从输入字符流中读取字符，根据“状态跳转函数”从当前状态跳到下一个状态，图中状态之间的连线就是跳转函数：state = trans(state, word)。如果当前字符下，没有可以跳转的状态，就认为是识别失败；如果最终状态是“接受状态”则认为识别成功。可以非常清楚的看到，这状态机能够识别的单词与上面给出的十六进制正则表达式是等价的。根据给出的状态图，实现对应的功能代码就非常简单了，甚至有相关的工具能够直接产生对应的代码，不用开发者自己编写。

上面这个例子中的状态机是一个简单的“确定的有穷状态自动机”，此外还有更为复杂的“非确定的有穷状态自动机”，即当前状态下给定一个输入字符，可以跳转的目标状态可能不止一个，可以证明的是“非确定性状态自动机”是能够等价转换为“确定性状态自动机”的，这里就不再是做过多的介绍，感兴趣的朋友可以搜索一下相关材料。后续介绍中，默认为是“确定的状态自动机”。

开发者提供的是词法的“正则表达式”描述，而我们希望得到的与之等价的“确定的有穷状态自动机”，如何做到的呢？注意到，任何复杂的正则表达式都是建立在简单的正则表达式之上的，通过对简单表达式施加相应的操作，就能得到更为复杂的正则表达式。所以只要能够将简单正则表达式，以及正则表达上的基础操作表述为状态机的形式，那么复杂的正则表达式也能过表述为状态机。

下面给出这些简单情形下的转换：

对一个复杂的正则表达式进行转换时，先构建对应的起始状态和接受状态，并用一条边由起始状态指向接受状态，且边的状态转换表达式为需要转换的正则表达式；然后不断地对状态机中的转换表达式不是“简单字符”的边应用上述给出的简单转换，直至状态机中的边对应的转换转换函数全部为“简单字符”。

如何由确定的状态自动机编写词法分析代码，这里就不再赘述了，这已经是一个非常简单明了的问题了。

至此，相信读者已经掌握如何使用正则文法或者正则表达式来定义词法的结构，并将其转换为等价的确定性状态自动机的方法了。也正是由于构建一个词法分析器的流程如此的规范化，已经有很多成熟的工具能帮助我们自动生成生成词法分析器了，只需要向这些工具提供用正则表达式的形式定义好词法结构，以及匹配到对应表达式时产生的“单词”即可。

下面介绍的flex就是这样的一个工具，Postgres数据库也是使用这个工具来自动生成词法分析器的。在使用时，只需要向flex提供事先编写好的词法规则文件即可。下面以postgres的词法规则文件为例子进行简要说明，更为详细的内容可以使用在终端中输入info flex命令来查阅flex的使用文档。

词法规则文件由3部分构成，每部分之间使用“%%”进行分割，其结构如下：

其中，“声明部分”主要是对“规则识别部分”用到的头文件、变量、函数、正则表达式等进行声明。例如：

 规则识别部分由一组识别规则构成，其格式如下：

r1     a1

r2 a2

...

其中ri为正则表达式，用来描述一种单词的模式；ai是一个代码块，当匹配到相应模式时会被调用，可以在此处向上层的语法解析模块返回相应的“单词”，或者做一些其他的处理工作，例如检查字符串的编码是否正确等。例如：

对于给定的输入字符流，可能会存在如下问题：

• 当存在多个正则表达式与当前输入的字符流匹配时，选择哪一个？

flex按照正则表达式匹配的字符流长度来确定，当由多个正则表达式匹配时，选择匹配长度最长的那个；当存在多个匹配长度一样长的正则表达式时，则选择词法规则文件中先定义的正则表达式。

• 不同的上下文下，正则表达式规则的使能问题。例如字符串中的空格不能忽略，而非字符串中的空格则需要忽略；注释中的标识符不需要识别，非注释中的标识符则需要识别等。为此，flex引入“排它状态”（exclusive stats）让用户指定当前上下文下哪些正则表达式是有效的。如下例子中便是如何在注释中只使能部分正则表达式规则的例子：

• 多字节编码的字符流的识别问题。例如在big5编码下，查询请求“select “武功””，其中“功”的编码为A55C，而5C的编码刚好对应于‘’，这种场景下要想正确识别字符串，而不是将其误认为是转义符，就必须要求flex能够正确识别多子节编码的字符，而不是认为字符流只是简单的字节流。然而不幸的是flex不支持多子节编码，也正因为如此，postgres也不支持数据库端的编码为big5；当客户端连接的编码为big5时，postgres需要将客户端发送的请求转换为对应的服务器端编码（例如utf8）再进行处理。而mysql数据库由于没有采用flex，整个词法分析器是自己编写的，并考虑了多子节编码问题，就不存在这样的限制。

规则文件的最后一部分“辅助过程部分”，主要是用来定义声明部分声明的内部函数，这里就不再过多介绍了。

本篇文章主要介绍了词法分析器的基本原理，并以postgres为例子介绍了如何使用工具flex自动生成数据库的词法分析器的。文中介绍的很多知识点在大学的编译原理课程中都有相关介绍，有兴趣的深挖的读者可以回顾一下相关教材。本文有些描述可能存在疏漏，希望读者能够批评指正。

同时欢迎大家扫码👇添加小助手（备注：加入Klustron技术交流群）欢迎大家在交流群共同探讨更多问题及主题。