一、前言

1.1 作者介绍

王波，SphereEx MeshLab 研发工程师，目前专一于 Database Mesh，Cloud Native 的研发。Linux，llvm，yacc，ebpf user。 Gopher & Rustacean and c bug hunter。

GitHub: https://github.com/wbtlb

1.2 背景

在上篇文章《Pisa-Proxy 之 SQL 解析实际》中介绍了 Pisa-Proxy 的外围模块之一 SQL 解析器的相干内容。在 MySQL 和 PostgreSQL 中 SQL 解析是通过 Yacc 实现的，同样 Pisa- Proxy 的 SQL 解析器是由相似 Yacc 这样的工具实现的，所以本篇文章会围绕 SQL 解析器为大家介绍一些编译原理和 Lex & Yacc 的应用，同时也会为读者展现如何通过 Lex & Yacc 实现一个简略的 SQL 解析器。从而帮忙大家更好地了解 Pisa-Proxy 中 SQL 解析器是如何工作的。

二、编译器初探

一个程序语言不论是咱们罕用的 Java，Golang 或者是 SQL 实质上都是一个记号零碎，如同自然语言一样，它的残缺定义应该包含语法和语义两个方面。一种语言的语法其实是对应的一组规定，用它能够造成和产生一个适合的程序。以后应用最宽泛的伎俩是上下文无关的文法，上下文无关的文法作为程序设计语言语法的形容工具。语法只是定义什么样的符号序列是非法的，与这些符号的含意毫无关系。然而在语义中分为两类：动态语义和动静语义。动态语义是指一系列的限定规定，并确定哪些语法对于程序来说是适合的；动静语义也称作运行语义或者执行语义，明确程序具体要计算什么。

2.1 编译器工作流程

如图 2.1.1 中所示，通常编译器将源代码编译成可执行文件次要有以下几步：

  1. 对源文件进行扫描，将源文件的字符流拆分分一个个的词（token），此为词法剖析
  2. 依据语法规定将这些记号结构出语法树，此为语法分析
  3. 对语法树的各个节点之间的关系进行查看，查看语义规定是否被违反，同时对语法树进行必要的优化，此为语义剖析
  4. 遍历语法树的节点，将各节点转化为中间代码，并按特定的程序拼装起来，此为两头代码生成
  5. 对中间代码进行优化
  6. 将中间代码转化为指标代码
  7. 对指标代码进行优化，生成最终的目标程序

                                        图 2.1.1

对于 SQL 解析来说，就能够将上图中的步骤简化为如图2.1.2 的模式，源码输出（SQL 语句），将 SQL 语句进行词法剖析，生成 SQL 中特定的 token 记号流。而后拿到记号流后进行语法分析后生成最终的 SQL AST。

                                        图 2.1.2

2.2 词法剖析

上文中提到，无论是编译器还是 SQL 解析器有一个关键步骤就是要对源文件做词法剖析，词法剖析咱们能够了解为对 SQL 语句自身做分词解决。那么在这个阶段，SQL 解析器要做的工作就是从左到右扫描源文件，将 SQL 语句宰割成一个个的 token，这里说的 token 是指 SQL 中不能再进一步宰割的一串字符。例如图 2.1.2 中的 SQL 语句，通过词法剖析后，生成的 token 为：SELECT、*、FROM、pisa_proxy 等等。

在 SQL 语句中能用到的 token 类别也是无限的，比方保留字 SELECT、INSERT、DELETE 等等。还有操作符，比方：算术操作符、比拟操作符。还有标识符，比方：内置函数名等等。在此阶段每扫描一个 token 会被保护到一个数据结构中，而后在下个阶段语法分析阶段应用。
通常来说，词法剖析有间接扫描，正则匹配扫描形式。

2.2.1 间接扫描法

间接扫描法逻辑十分清晰，每次扫描依据第一个字符判断属于哪种类型的 token，而后采取不同的策略扫描出一个残缺的 token，而后再进行下一轮扫描。在 Pisa-Proxy 中的 SQL 解析中，词法剖析就采纳了这种实现形式，用 Python 展现如何实现一个简略的 SQL 词法分析器对 SQL 进行扫描，代码如下：

# -*- coding: utf-8 -*-single_char_operators_typeA = {    ";", ",", "(", ")","/", "+", "-", "*", "%", ".",}single_char_operators_typeB = {    "<", ">", "=", "!"}double_char_operators = {    ">=", "<=", "==", "~="}reservedWords = {    "select", "insert", "update", "delete", "show",    "create", "set", "grant", "from", "where"}class Token:    def __init__(self, _type, _val = None):        if _val is None:            self.type = "T_" + _type;            self.val = _type;        else:            self.type, self.val = _type, _val    def __str__(self):        return "%-20s%s" % (self.type, self.val)class NoneTerminateQuoteError(Exception):    passdef isWhiteSpace(ch):    return ch in " \t\r\a\n"def isDigit(ch):    return ch in "0123456789"def isLetter(ch):    return ch in "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"def scan(s):    n, i = len(s), 0    while i < n:        ch, i = s[i], i + 1        if isWhiteSpace(ch):            continue        if ch == "#":            return        if ch in single_char_operators_typeA:            yield Token(ch)        elif ch in single_char_operators_typeB:            if i < n and s[i] == "=":                yield Token(ch + "=")            else:                yield Token(ch)        elif isLetter(ch) or ch == "_":            begin = i - 1            while i < n and (isLetter(s[i]) or isDigit(s[i]) or s[i] == "_"):                i += 1            word = s[begin:i]            if word in reservedWords:                yield Token(word)            else:                yield Token("T_identifier", word)        elif isDigit(ch):            begin = i - 1            aDot = False            while i < n:                if s[i] == ".":                    if aDot:                        raise Exception("Too many dot in a number!\n\tline:"+line)                    aDot = True                elif not isDigit(s[i]):                    break                i += 1            yield Token("T_double" if aDot else "T_integer", s[begin:i])        elif ord(ch) == 34: # 34 means '"'            begin = i            while i < n and ord(s[i]) != 34:                i += 1            if i == n:                raise Exception("Non-terminated string quote!\n\tline:"+line)            yield Token("T_string", chr(34) + s[begin:i] + chr(34))            i += 1        else:            raise Exception("Unknown symbol!\n\tline:"+line+"\n\tchar:"+ch)if __name__ == "__main__":    print "%-20s%s" % ("TOKEN TYPE", "TOKEN VALUE")    print "-" * 50    sql = "select * from pisa_proxy where id = 1;"    for token in scan(sql):        print token

最终的输入后果如下：

TOKEN TYPE          TOKEN VALUE--------------------------------------------------T_select            selectT_*                 *T_from              fromT_identifier        pisa_proxyT_where             whereT_identifier        idT_=                 =T_integer           1T_;                 ;

由下面的代码咱们能够看到，在一开始咱们定义了几个 token 类型，例如：reservedWords 数组中保护了 SQL 中的保留字，还有 SQL 中的操作符 single_char_operators_typeA。最终的执行后果咱们能够看出，扫描器最终将一条 SQL 语句进行分词最终拆成各自对应类型的 token。

2.2.2 正则表达式扫描法

其实程序的实质就是一组字符串，而语言能够看成非法程序的汇合，因而编译器或者说 SQL 解析的实质是判断输出的字符串是该语言的非法类型，另外也是将语言中的非法程序转换成目标语言的非法程序。所以正则表达式扫描法的实质，也就是在一个无限状态机里来判断字符串是否和正则表达式是否匹配，在前面的介绍中咱们会提到 flex，flex 的实质其实是将用户用正则表达式写的分词匹配模式结构成一个无限状态自动机。

2.3 语法分析

词法剖析完结后，SQL 语句的字符流被拆分成 token，那么语法分析就是要剖析出 SQL 的语法结构，将线性的 token 流转化为树状构造，为后续的语义剖析和 AST 生成做筹备。在编译器中，正则表达式还是难以示意程序语言所代表句子的汇合，所以就引入的上下文无关文法，上下文无关文法可能形容现今程序设计语言的语法结构。

以咱们自然语言为例，假如有一种编程语言为 SQLX，它只蕴含主-谓-宾 这种构造来说，主语只有你、我、他，谓语只有爱，宾语有 Rust 和 Pisanix，那么语法能够为以下这种模式：

语句 -> 主语 谓语 宾语主语 -> 我主语 -> 你主语 -> 他谓语 -> 爱宾语 -> Rust宾语 -> Pisanix

从下面的例子来看咱们能够别离对主谓宾进行替换，从而写出所有满足此构造的语句。反过来讲咱们能够用任意语句和此构造比照来判断它是否满足 SQLX 语言。由此产生几个概念，下面语法中形如“主语->谓语->宾语”的式子成为产生式

产生式左侧的符号（语句、主语、谓语、宾语）称为非终结符。而“我，你，他，爱，Rust，Pisanix”这些符号无奈再产生新的符号，因而被称为终结符，终结符只能呈现在产生式左边。语句这个词为所有句子产生的终点，所以也被称为起始符号。

通常把一个非 终结符的产生式写在一起，用“｜”隔开，归纳如下：

语句 -> 主语 谓语 宾语主语 -> 你｜我｜他谓语 -> 爱宾语 -> Rust | Pisanix

咱们以一个 SQL 语句为例： SELECT 1 + 1，咱们能够写出这条语句的推到表达式为,分析树如图2.3.1

Expr => Expr Expr + Expr => SELECT Expr + Expr => SELECT number + Expr => SELECT number + number => SELECT 1 + 2

                                      图 2.3.1
2.3.1 两种分析方法

语法分析蕴含两种分析方法：

  1. 自顶向下剖析：自顶向下剖析就是从起始符号开始，一直的挑选出适合的产生式，将两头句子中的非终结符的开展，最终开展到给定的句子。
  2. 自底向上剖析：自底向上剖析的程序和自顶向下剖析的程序刚好相同，从给定的句子开始，一直的挑选出适合的产生式，将两头句子中的子串折叠为非终结符，最终折叠到起始符号

在推导的过程中，每一步都只有惟一的一个产生式能够利用，每一步都能够排除掉其余所有的产生式。但在理论剖析时，在两头过程中可能会遇到所有产生式都不可利用或者有多个产生式能够利用。对于第二种状况，须要采纳回溯，先试探性的抉择一个产生式利用，若始终推导至最终句子（或起始符号），则表明此产生式是可用的，若推导上来遇到第一种状况，则回溯到此处，抉择另一个产生式。如果此处所有产生式都尝试过了全副都遇到第一种状况，则表明最终句子不合乎语法结构。如果此处有多条产生式能够推导至最终句子（或起始符号），则表明语法有歧义。回溯剖析个别都十分慢，因而个别通过精心结构语法来防止回溯。

2.4 小结

以上内容次要介绍了编译器的相干概念，和通过一个简略的例子来直观感触词法剖析的基本原理和工作过程，接下来我会为大家简略介绍一下在词法剖析和语法分析中最罕用到的两个工具 Lex 和 Yacc。

三、意识 Lex 和 Yacc

3.1 意识 Lex

Flex（疾速词法分析器生成器）是 Lex 的收费开源软件替代品。它是生成词法分析器（也称为“扫描器”或“词法分析器”）的计算机程序。扫描仪是一种辨认文本中的词汇模式的程序，用来辨认文本中的词汇模式。

3.1.1 Lex由三局部组成
  • 定义局部：定义段包含文字块、定义、外部表申明、起始条件和转换。
  • 规定局部：规定段为一系列匹配模式和动作，模式个别应用正则表达式书写，动作局部为 C 代码。
  • 用户子程序段：这里为 C 代码，会被原样复制到c文件中，个别这里定义一些辅助函数等，如动作代码中应用到的辅助函数。

这里咱们做一个简略的例子，用 Lex 实现一个简略的 SQL 词法分析器，lex 代码如下:

%{#include <stdio.h>%}%%select                 printf("KW-SELECT      : %s\n", yytext);from                   printf("KW-FROM        : %s\n", yytext);where                  printf("KW-WHERE       : %s\n", yytext);and                    printf("KW-AND         : %s\n", yytext);or                     printf("KW-OR          : %s\n", yytext);[*]                    printf("IDENTIFIED     : %s\n", yytext);[,]                    printf("IDENTIFIED     : %s\n", yytext);[=]                    printf("OP-EQ          : %s\n", yytext);[<]                    printf("KW-LT          : %s\n", yytext);[>]                    printf("KW-GT          : %s\n", yytext);[a-zA-Z][a-zA-Z0-9]*   printf("IDENTIFIED:    : %s\n", yytext);[0-9]+                 printf("NUM:           : %s\n", yytext);[ \t]+                 printf(" ");.                      printf("Unknown : %c\n",yytext[0]);%%int main(int argc, char* argv[]) {    yylex();    return 0;}int yywrap() {    return 1;}# flex sql.l # 用 flex 编译 .l 文件生成 c 代码# lslex.yy.c sql.l# gcc -o sql lex.yy.c # 编译生成可执行二进制文件# ./sql  # 执行二进制文件select * from pisaproxy where id > 1 and sid < 2  # 输出测试 sqlKW-SELECT      : selectIDENTIFIED     : *KW-FROM        : fromIDENTIFIED:    : pisaproxyKW-WHERE       : whereIDENTIFIED:    : idKW-GT          : >NUM:           : 1KW-AND         : andIDENTIFIED:    : sidKW-LT          : <NUM:           : 2

通过下面的例子咱们能够看到，Lex 胜利地将一条 SQL 语句拆分成了独自的 token。

3.2 意识 Yacc

Yacc 是开发编译器的工业级工具, 采纳 LALR(1) 语法分析办法。LR(k) 分析方法，括号中的 k(k>=0) 示意向右查看输出串符号的个数。LR 分析法给出一种能依据以后剖析栈中的符号串和向右程序查看输出串的 k 个符号就可惟一确定分析器的动作是移进还是规约和用哪个产生式规约。

Yacc 和 Lex 一样，也蕴含由“%%”分隔的三个段：定义申明、语法规定、C代码段。

  1. 定义段和预约义标记局部：

下面%{ %}的代码和Lex一样，个别称为定义段。就是一些头文件申明，宏定义、变量定义申明、函数申明等。其中%left示意左联合，%right 示意右联合。最初列出的定义领有最高的优先权。因而乘法和除法领有比加法和减法更高的优先权。+ - * / 所有这四个算术符都是左联合的。使用这个简略的技术，咱们能够打消文法的歧义。

  1. 规定局部：规定段由语法规定和包含C代码的动作组成。规定中指标或非终端符放在右边，后跟一个冒号（:），而后是产生式的左边，之后是对应的动作（用{}蕴含）
  2. 代码局部：该局部是函数局部。当Yacc 解析出错时，会调用 yyerror()，用户可自定义函数的实现。

这里咱们用一个简略的例子通过 Yacc 和 Lex 来实现一个简略的 SQL 解析器

sql.l 代码示例

%{#include <stdio.h>#include <string.h>#include "struct.h"#include "sql.tab.h"int numerorighe=0;%}%option noyywrap%%select                     return SELECT;from                       return FROM;where                      return WHERE;and                        return AND;or                         return OR;[*]                        return *yytext;[,]                        return *yytext;[=]                        return *yytext;[<]                        return *yytext;[>]                        return *yytext;[a-zA-Z][a-zA-Z0-9]*       {yylval.Mystr=strdup(yytext);return IDENTIFIER;}[0-9]+                     return CONST;\n                         {++yylval.numerorighe; return NL;}[ \t]+                     /* ignore whitespace */%%

sql.y 局部代码示例

%{%}%token <numerorighe> NL%token <Mystr> IDENTIFIER CONST '<' '>' '=' '*'%token SELECT FROM WHERE AND OR%type <Mystr> identifiers cond compare op%%lines:    line    | lines line    | lines error    ;line:     select identifiers FROM identifiers WHERE cond NL     {        ptr=putsymb($2,$4,$7);    }    ;    identifiers:    '*' {$$="ALL";}    | IDENTIFIER {$$=$1;}    | IDENTIFIER','identifiers        {            char* s = malloc(sizeof(char)*(strlen($1)+strlen($3)+1));            strcpy(s,$1);            strcat(s," ");            strcat(s,$3); $$=s;        }     ;  select:     SELECT    ;cond:     IDENTIFIER op compare    | IDENTIFIER op compare conn cond;compare:     IDENTIFIER    | CONST    ;op:          '<'    |'='    |'>'    ;conn:       AND    | OR    ;%%
# 此处因为编译过程较为繁琐，此处仅为大家展现要害后果# ./parser "select id,name,age from pisaproxy1,pisaproxy2,pisaproxy3 where id > 1 and name = 'dasheng'"''Row #1 is correct columns: id name age tables: pisaproxy1 pisaproxy2 pisaproxy3

能够看出通过 Lex 首先将 SQL 解析成 token，而后再由 yacc 做语法解析，依据 .y 中的规定将 column 和 tables 正确解出。

四、Pisa-Proxy SQL 解析实现浅析

在 Pisa-Proxy 中的 SQL 解析器是通过 Grmtools 这个工具实现的，Grmtools 是 Rust 实现的 lex 和 yacc 库。Pisa-Proxy 的 SQL 解析次要蕴含两局部内容，首先是 lex.rs 文件，这个文件是通过 Grmtools 提供的办法实现的手写词法分析器，如前文提到，这个模块将 SQL 语句进行分词，生成 token。而后是 grammar.y 文件，该文件中形容了 SQL 语句的推导过程，Grmtools 会通过该文件进行语法分析最终生成 SQL AST。

五、总结

本篇文章次要分享了编译器的相干概念和一些原理，咱们能够理解到 SQL 解析器对于 SQL 语句的意义是什么，以及如何将 SQL 语句字符串模式转化成咱们须要的形象语法树。Lex 和 Yacc 是两个十分弱小的工具，他能够帮忙开发者方便快捷地实现本人的解析器，然而编译原理无所不包也是非常复杂的一门学科。Pisa-Proxy 的 SQL 解析器在实现过程中也遇到很多问题，比方如何解决抵触，二义性，优先级等等问题。前面会持续有文章深度分析 SQL 语句在 Rust 中的具体实现，本文就不再赘叙述。

六. 相干链接：

6.1 Pisanix:

我的项目地址：https://github.com/database-mesh/pisanix

官网地址：Hello from Pisanix | Pisanix

Database Mesh：https://www.database-mesh.io/

SphereEx 官网：https://www.sphere-ex.com

6.2 社区

开源我的项目千万步，Pisanix 才刚起步。开源是一扇门，Pisanix 欢送各位小伙伴一起参加进来，发表本人的想法，分享本人的见解，不论是代码还是文档，issue 还是 pull request，社区一样欢送。各位乐意帮忙数据库治理的小伙伴们，让咱们一起来建设 Pisanix 社区吧~

目前 Pisanix 社区每两周都会组织线上探讨，具体安顿如下，咱们等你~

邮件列表https://groups.google.com/g/database-mesh
英文社区双周会（2022年2月27日起），周三 9:00 AM PSThttps://meet.google.com/yhv-zrby-pyt
中文社区双周会（2022年4月27日起），周三 9:00 PM GMT+8https://meeting.tencent.com/dm/6UXDMNsHBVQO
微信小助手pisanix
Slackhttps://databasemesh.slack.com/
会议记录https://bit.ly/39Fqt3x

七、参考资料

  1. 《编译原理》
  2. 《古代编译原理》
  3. https://github.com/mysql/mysql-server/blob/8.0/sql/sql_yacc.yy
  4. http://web.stanford.edu/class/archive/cs/cs143/cs143.1128/