词法分析概述¶

词法分析（lexical analysis）是计算机科学中将字符序列转换为单词（Token）序列的过程。进行词法分析的程序或者函数叫作词法分析器（Lexical analyzer，简称Lexer），也叫扫描器（Scanner）。

词法分析器一般以函数的形式存在，供语法分析器调用。词法分析阶段是编译过程的第一个阶段，是编译的基础。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。

词法分析程序实现这个任务。词法分析程序可以使用Lex等工具自动生成,lex可以参考Lex与YACC详解。

词法分析是编译程序的第一个阶段且是必要阶段；词法分析的核心任务是扫描、识别单词且对识别出的单词给出定性、定长的处理；

词法分析 & 语法分析 阶段的入口是**语法分析器**，语法分析器调用词法分析器读取一个 token 进行分析，分析完后再读取一个 token，直到分析完所有的 token，结束整个过程。所以，词法分析 & 语法分析阶段实际上是由语法分析器驱动的。

**词法分析**和**语法解析**有两个较成熟的开源工具Flex和Bison分别用来解决这两个问题。

MySQL出于于性能和灵活考虑，选择了自己完成词法解析部分，语法规则部分使用Bison。词法解析和Bison沟通的核心函数是由词法解析器提供的函数接口yylex()，在Bison中，必要的时候调用yylex()获得词法解析的数据，完成自己的语法解析。Bison的入口时yyparse()，在MySQL中是，MYSQLParse。

在 MySQL 数据库中，客户端向服务器发送过来SQL语句后，服务器首先要进行**词法分析**，而后进行**语法分析**，语义分析，构造执行树，生成执行计划。**词法分析**是第一阶段，然而MySQL并没有使用lex来实现词法分析，但是语法分析却用了yacc，而yacc需要词法分析函数yylex，故在sql_yacc.cc文件最前面我们可以看到如下的宏定义:

MySQL的词法分析器也是手写的，这给算法提供了一定的灵活性。比如，SQL语句中，Token的解析是跟当前使用的字符集有关的。使用不同的字符集，词法分析器所占用的字节数是不一样的，判断合法字符的依据也是不同的。而字符集信息，取决于当前的系统的配置。词法分析器可以根据这些配置信息，正确地解析标识符和字符串。

假设我们有一个名为"employees"的表，它包含了员工的信息，其中包含列：employee_id、first_name、last_name、department、salary

如果语句为：

SELECT first_name, last_name, salary
FROM employees
WHERE department = 'IT';

词法分析

词法分析的任务了：输入的是字符串，输出的是Token串。

在词法分析阶段，MySQL会将输入的SQL语句拆分成不同的词元(Token)。对于这个SELECT语句，词法分析器会产生以下词元：

SELECT, first_name, comma, last_name, comma, salary, FROM, employees, WHERE, department, equal, 'IT', semicolon

在分析过程中，词法分析器使用有限状态机（finite state machine）来确定每个词元的类型。

有限状态机是一种抽象计算机，它在不同的状态之间转换，根据输入的字符来决定状态转换规则。主要的词法分析步骤如下：

跳过空白字符：词法分析器会跳过空格、制表符、换行符等不必要的空白字符。
识别关键字和标识符：词法分析器将识别出SELECT、FROM、WHERE等关键字，并将它们作为相应的词元类型。
识别运算符和标点符号：词法分析器将识别出逗号（comma）、等号（equal）、分号（semicolon）等运算符和标点符号，并将它们作为相应的词元类型。
识别常量：词法分析器将识别出'IT'作为一个字符串常量，并将其作为相应的词元类型。
识别数字：如果SQL语句中有数字，词法分析器也会将其识别为一个数字常量。

MySQL 使用 Bison 语法解析器实现 SQL 语句的解析功能。Bison 解析器的核心逻辑如下：

Bison 语法文件
yylex() 函数：用于实现词法解析器的功能，将输入流识别为 Token 并将它们返回给解析器
yyparse() 函数：语法解析器的入口函数，该函数由 Bison 解析器生成，用于运行执行解析过程

bison的规则文件是sql/sql_yacc.yy，经过编译后会生成sql/sql_yacc.cc文件。

在 MySQL 中，sql/sql_yacc.yy 文件是使用Bison工具生成语法分析器的输入文件。它描述了MySQL语句的语法规则，使用一种类似于 BNF（Backus-Naur Form）的语法来定义。Bison 会根据这个文件生成 C++ 代码，这些代码实现了MySQL的语法分析器。

sql_yacc.yy 的作用 - 定义 SQL 语法：通过一系列规则，明确定义了SQL语句的组成部分、结构和它们之间的关系。 - 生成语法分析器： Bison 工具会根据sql_yacc.yy文件中的规则生成 C++ 代码，这些代码组成了MySQL的语法分析器。 - 指导语法分析：生成的语法分析器会根据sql_yacc.yy中定义的规则，对输入的 SQL 语句进行语法分析，检查其是否符合 SQL 语法规范。

词法分析中的各种Token，都是在sql/lex_token.h中定义的，这个是文件是通过This file is generated, do not edit. See file sql/gen_lex_token

sql/lex.h                    // symbol
sql/gen_lex_token.{h,cc}     // token
sql/sql_lex_hints.{h,cc}     // hint lexer
sql/sql_hints.yy             // hint parser
sql/parse_tree_hints.{h,cc}  // PT_hint_list, PT_hint, PT_{qb,table,key}_level_hint, PT_hint_sys_var, ...
sql/sql_lex.cc               // consume_optimizer_hints()

Tokens printed in sql/lex_token.h do come from several sources: - tokens from sql_yacc.yy - tokens from sql_hints.yy - fake tokens for digests.

All the token values are mapped in the same space, indexed by the token value directly.

To account for enhancements and new tokens, gap are created, so that adding a token from one source does not change values of tokens from other sources.

This is done to ensure stability in digest computed values.

As of now (8.0.0), the mapping looks like this: - PART 1: [0 .. 255] tokens of single-character lexemes - PART 2: [256 .. ...] tokens < YYUNDEF from sql_yacc.yy - PART 3: [... .. 999] reserved for sql_yacc.yy new tokens < YYUNDEF - PART 4: [1000 .. ...] tokens from sql_hints.yy - PART 5: [... .. 1099] reserved for sql_hints.yy new tokens - PART 6: [1100 .. ...] digest special fake tokens - PART 7: [... .. 1149] reserved for new digest special fake tokens - PART 8: [1150 .. ...] tokens > YYUNDEF from sql_yacc.yy

sql/sql_yacc.cc文件是 MySQL 语法分析器的一个核心组成部分，它是通过 Bison 工具根据 sql/sql_yacc.yy 文件生成的。

生成过程概述 - 编写 sql_yacc.yy 文件：这个文件使用 Bison 语法描述 MySQL SQL 语句的语法规则。 - 运行 Bison：将 sql_yacc.yy 文件作为输入，使用 Bison 工具进行编译。Bison 会根据定义的语法规则生成 C++ 代码，这些代码实现了语法分析器的核心逻辑。 - 生成 sql_yacc.cc 文件： Bison 的输出结果之一就是 sql_yacc.cc 文件。这个文件包含了语法分析器所需要的函数和数据结构。

在 MySQL 的源码中，Bison 的语法文件为sql/sql_yacc.yy，其中主要包含如下三部分： - Bison 声明 - 终结符、语义组的返回值类型 - 语义组的备选规则及行为

// 在语法分析器（如 Bison）中定义了一个名为 ABORT_SYM 的 token，其数值为 258。


/*      Tokens from MySQL 5.7, keep in alphabetical order                 */
%token  ABORT_SYM 258                     /* INTERNAL (used in lex) */
%token  ACCESSIBLE_SYM 259
%token<lexer.keyword> ACCOUNT_SYM 260
%token<lexer.keyword> ACTION 261                /* SQL-2003-N */
%token  ADD 262                           /* SQL-2003-R */
%token<lexer.keyword> ADDDATE_SYM 263           /* MYSQL-FUNC */
%token<lexer.keyword> AFTER_SYM 264             /* SQL-2003-N */

/*   many token and so on */

%token<lexer.keyword> YEAR_SYM 905              /* SQL-2003-R */
%token  ZEROFILL_SYM 906                  /* MYSQL */



/*  Tokens from MySQL 8.0*/
%token  JSON_UNQUOTED_SEPARATOR_SYM 907                 /* MYSQL */
/*   many token and so on                                   */
%token<lexer.keyword> RETURNING_SYM 999                 /* SQL-2016-N */
...

sql/sql_yacc.yy；sql/sql_lex.cc；sql/parser_yystype.h

MySQL词法解析的入口函数是sql/sql_lex.cc中定义的 my_sql_parser_lex() 函数。

因为在 Bison 语法文件sql/sql_yacc.yy中定义了 %define api.prefix {my_sql_parser_}，所以 MySQL 的 yylex() 函数即 my_sql_parser_lex() 函数。

/**
  yylex() function implementation for the main parser

  @param [out] yacc_yylval   semantic value of the token being parsed (yylval)
  @param [out] yylloc        "location" of the token being parsed (yylloc)
  @param thd                 THD

  @return                    token number

  @note
  my_sql_parser_lex remember the following states from the
  following my_sql_parser_lex():

  - MY_LEX_END          Found end of query
*/


int my_sql_parser_lex(MY_SQL_PARSER_STYPE *yacc_yylval, POS *yylloc, THD *thd) {}

MYSQLlex函数是 MySQL 词法分析器的核心，负责将 SQL 字符串分割成 Token。 my_sql_parser_lex函数是对 MYSQLlex 函数的封装，提供了一个更高层次的接口，方便其他模块调用词法分析功能。

源代码分析¶

词法分析 & 语法分析¶

初始化字段¶

select子句中，字段可能有 2 种类型，一种是星号（*），一种是普通字段，星号会用 Item_asterisk 类实例化，而 Item_asterisk 类是 Item_field 类的子类。普通字段就直接用 Item_field 类实例化。

词法分析 & 语法分析阶段，各字段只是完成了 Item_field 类的实例化，但是还没有对应到表中真实的字段。此时，Item_field 类实例就像刚刚成形的小蝌蚪，还没有找到妈妈。它的妈妈是 Field 类（或子类）的实例。

要等到查询准备阶段，Item_field 类实例才会去找妈妈，找到妈妈之后，Item_field 类实例中的 field 属性会指向找到的 Field 类（或子类）实例，从此以后，小蝌蚪和妈妈就过上了幸福快乐的生活。

初始化表¶

对于FROM子句中的每个表，都会创建一个 TABLE_LIST 类的实例，TABLE_LIST 类实例中只保存了数据库名、表名、表别名、索引提示这几个我们使用过程中有感知的属性，TABLE_LIST 类实例中有个很重要的属性 table，它的类型是 TABLE，这个类的实例才是真正保存着表中所有信息的地方。

等到查询准备阶段，才会找到 TABLE_LIST 类实例对应的 TABLE 类实例。

这里要特别说明的一点是数据库名，我们一般在写SQL时，FROM 子句中的表名前面是不会带上数据库名的，就像本文示例 SQL 中的一样。在**词法分析 & 语句分析**阶段，初始化表的时候，如果表名前面没有带上数据库名，就会把当前连接中保存的数据库名读取出来，保存到TABLE_LIST类实例的属性中，如果FROM子句中表名前面带了数据库名，则把自带的数据库名保存到**TABLE_LIST**类实例的属性中。

初始化WHERE条件¶

初始化 where 条件要比初始化字段复杂得多，

查询准备阶段¶

在查询准备阶段会干哪些事情？分 3 个部分：

打开表
select * 替换为表字段
填充 where 条件

打开表¶

从存储引擎读取数据之前，MySQL 需要把 SQL 中涉及的所有表的信息读取出来。

二级缓存

字段替换¶

在写 select 语句的过程中，经常会用到星号（*），表示查询表中所有字段，但是表中并没有一个星号字段用来表示所有字段，所以在查询准备阶段，会把星号替换为表中的所有字段。

这个替换过程一般就是直接遍历表中的所有字段，为每个字段创建一个 Item_field 类实例，并且由于是直接遍历表中的 Field 子类实例列表，在创建 Item_field 类实例的时候就关联上了 Field 子类实例。

遍历完表中所有字段之后，形成一个 Item_field 列表，替换掉星号（*）对应的 Item_field 列表就行了，至此，就完成了 select 语句中星号替换为表字段的过程了。

填充条件¶

MySQL 从 InnoDB 读取数据之前，词法分析、语法分析、查询准备、查询优化这些阶段都是 server 层的范围，在 server 层中需要使用索引信息时，使用的都是 MySQL 的索引信息。