深入解析MySQL SQL解析：从Lex词法分析到yacc语法构建

1. 从一次诡异的SQL解析错误说起那天下午我正在排查一个线上慢查询。一个看似简单的SELECT * FROM users WHERE status IN (?)语句在某个特定版本的MySQL分支上偶尔会抛出You have an error in your SQL syntax的报错而参数明明是一个合法的JSON数组字符串。用常规的客户端工具和主流MySQL版本测试却一切正常。这种“时好时坏”的语法错误通常不是业务逻辑问题而是更深层的SQL解析器在“理解”你的语句时出现了分歧。为了定位根因我不得不一头扎进MySQL的源码世界而入口正是两个古老而强大的工具yacc和Lex。对于大多数应用开发者而言这两个名字可能非常陌生它们隐藏在数据库引擎的最底层默默地将我们敲下的SELECT、WHERE这些字符转换成数据库内核能够执行的内部指令。理解它们不仅是读懂MySQL源码的钥匙更是深入理解任何一门编程语言或领域特定语言DSL如何被“创造”出来的核心。简单来说Lex或更现代的Flex是一个词法分析器生成器它负责“认字”。当你输入SELECT id FROM t;Lex的工作就是像扫描仪一样把字符流切割成一个个有意义的“单词”Token比如识别出SELECT是一个关键字KW_SELECTid是一个标识符IDENTFROM是另一个关键字KW_FROM。而yacc或GNU Bison是一个语法分析器生成器它负责“造句”。它拿到Lex生成的Token流根据预先定义好的语法规则比如“一个SELECT语句由SELECT关键字、字段列表、FROM子句等构成”检查这些Token的排列顺序是否符合SQL的语法规范并最终构造出一棵抽象语法树AST。这棵AST就是后续查询优化、执行计划生成等所有高级操作的基石。我遇到的诡异错误根源就在于这个分支版本对IN子句后接参数化预编译语句的语法规则定义与词法分析对某些边界字符的识别产生了微妙的冲突。接下来我将结合MySQL 8.0的源码带你深入sql/sql_yacc.yy和sql/sql_lex.h等文件手把手拆解SQL语句是如何从文本变成AST的完整流程并分享从这次排查中获得的关于如何阅读和使用yacc/lex语法文件的实战经验。2. Lex词法分析SQL语句的“分词”系统在MySQL源码目录下词法分析的核心文件是sql/lex.h和由sql/lex_token.h生成的Token定义而实际的词法规则定义在sql/sql_lex.cc中历史上使用独立的.l文件现在已集成。我们可以把Lex的工作想象成一个极度严谨的文本扫描器。2.1 Token的定义与分类首先所有Lex需要识别的“单词类型”都被定义为一个枚举值即Token。在MySQL中你可以在sql/lex_token.h中找到它们这个文件是由编译脚本自动生成的但其源头是语法定义。Token主要分为几大类关键字Keywords如SELECT、FROM、WHERE、IN、INT等。每个关键字对应一个唯一的Token例如KW_SELECT、KW_FROM。操作符Operators如、、-、*、/、、||等对应EQ、PLUS、MINUS等Token。字面量Literals包括数字如NUM、字符串如TEXT_STRING、十六进制数HEX_NUM、二进制数BIN_NUM、NULL字面量等。标识符Identifiers表名、列名、别名、数据库名等对应IDENT或IDENT_QUOTED被反引号包裹的。分隔符Delimiters如,、;、(、)对应COMMA、SEMICOLON、PAR_OPEN、PAR_CLOSE。占位符Placeholders在预处理语句中使用的?对应PARAM_MARKER。Lex的规则就是一系列正则表达式模式与动作的配对。当输入字符流匹配某个模式时就执行对应的动作通常是返回一个Token给yacc。2.2 深入sql_lex.cc看关键规则我们打开sql/sql_lex.cc会看到一个大大的switch语句块它实际上就是手工编写的词法分析器核心MySQL没有使用独立的.l文件而是实现了自己的词法扫描器。但原理与Lex/Flex完全一致。我们看几个关键片段识别标识符和关键字词法分析器会先读取一个“词”。对于像id这样的字符序列它首先会被初步识别为一个“标识符”。然后分析器会去查询一个名为符号表Symbol Table的哈希表。这个表里存储了所有SQL关键字及其对应的Token。如果查到了比如输入是SELECT那么就返回KW_SELECTToken如果没查到比如输入是my_column那么就返回IDENTToken。这个过程称为关键字保留Reserved Keywords。在MySQL中关键字列表非常长且不同SQL模式如ANSI_QUOTES下行为可能不同。识别字符串字面量处理像hello world或hello world这样的字符串非常复杂因为需要考虑转义字符\、字符集、连接符a b在MySQL中会被连接成ab以及是否开启标准SQL模式决定双引号是字符串还是标识符。词法分析器必须准确地找到配对的引号并处理中间的所有内容。识别数字数字看起来简单但也要区分整数42、浮点数3.14、2.5e-3、十六进制0x1A、二进制0b1010等。每种格式都有对应的正则模式和Token。处理注释和空白Lex规则会定义如何跳过空白字符空格、制表符、换行符以及各种注释-- comment、# comment、/* comment */。这些内容对语法没有意义所以识别后直接丢弃不生成Token。踩坑心得字符集与词法分析这是我曾经忽略的一个深层问题。词法分析器工作在字节流上。当你的SQL文件是UTF-8编码而á带重音的a这样的多字节字符出现在标识符或字符串中时Lex规则必须能正确地将多个字节识别为一个“字符”否则分词就会错位。MySQL的词法分析器与字符集系统紧密耦合在初始化词法分析器时必须明确当前会话的字符集以确保正确扫描。如果你的程序涉及多字符集SQL解析这一点至关重要。2.3 Lex如何与yacc协作Lex和yacc通常通过一个共享的yylex()函数接口和全局变量yylval进行协作。yacc在解析时会调用yylex()函数来获取下一个Token。Lex在yylex()函数中从输入流读取字符匹配规则当匹配成功时除了返回Token类型如KW_SELECT外还可以将这个词的语义值Semantic Value赋值给全局变量yylval。例如对于数字字面量123返回TokenNUM同时yylval里可以存储整数值123对于标识符table1返回TokenIDENT同时yylval里可以存储指向字符串table1的指针。yacc拿到Token和其关联的语义值根据语法规则进行组装。在MySQL源码中这个交互过程被封装在sql/sql_yacc.yy的规则和sql/lex.h中定义的LEX结构体等相关上下文中。3. yacc语法分析构建SQL的“语法树”词法分析器把一堆字符变成了有分类的Token流接下来就该yacc登场来检查这些Token流是否符合SQL语法并构建出结构化的表示。MySQL的语法规则定义在sql/sql_yacc.yy这个庞大的文件中超过1万行。这个文件遵循yacc的语法格式。3.1 yacc文件的基本结构一个.yy文件通常包含三个部分用%%分隔%{ /* 序言 (Prologue)C代码包含头文件、变量声明等。 这部分代码会被原样复制到生成的解析器源码顶部。 */ #include sql_class.h #include lex_token.h // ... 其他声明 %} /* 声明 (Declarations)定义Token、操作符优先级、结合性等。 */ %token KW_SELECT KW_FROM KW_WHERE IDENT NUM %left - %left * / // ... %% /* 语法规则 (Grammar Rules)核心部分定义如何从Token组合成语句。 */ select_stmt: KW_SELECT select_list KW_FROM table_references { // 动作构建SELECT语句的AST节点 $$ new PT_select_stmt($2, $4); } ; select_list: * { $$ new PT_select_list_all(); } | expr_list { $$ new PT_select_list_exprs($1); } ; // ... 无数其他规则 %% /* 尾声 (Epilogue)额外的C代码例如辅助函数。 */3.2 理解规则与动作规则是yacc文件的核心采用BNF巴科斯-诺尔范式或EBNF扩展巴科斯-诺尔范式风格。非终结符Non-terminal像select_stmt、select_list、expr它们可以由其他符号推导出来最终对应语法树中的一个节点。终结符Terminal就是Lex返回的Token如KW_SELECT、IDENT、NUM它们是语法树的叶子节点。产生式ProductionA: B C D;表示A可以由B C D序列构成。|表示“或”如select_list: * | expr_list;。动作Action花括号{}内的C代码。当yacc识别到一条规则匹配成功时就会执行对应的动作。动作的主要工作是构建语法树节点并将节点的指针赋值给$$代表当前规则的结果。$1,$2,$3... 则分别引用规则右侧第一个、第二个、第三个符号的语义值即它们对应的AST节点或Token的值。以解析SELECT id FROM users;为例Lex返回Token流KW_SELECT-IDENT(id)-KW_FROM-IDENT(users)-SEMICOLON。yacc从起始规则通常是query或statement开始尝试匹配。它发现可以匹配select_stmt规则。KW_SELECT匹配上了然后尝试匹配select_list。select_list尝试匹配*失败然后尝试匹配expr_list。expr_list可能由单个expr构成而expr可以是一个简单的IDENT。于是expr_list匹配了IDENT(id)并构建了一个表达式节点。这个节点作为$2传递给select_stmt的动作用于构建PT_select_stmt节点。接着匹配KW_FROM和table_references这里匹配了IDENT(users)并构建表引用节点作为$4。最终一个完整的SELECT语句AST节点被创建出来。3.3 优先级与结合性的解决SQL中表达式1 2 * 3的语义是明确的乘法优先。yacc通过%left、%right、%nonassoc声明来解决这个问题。%left -声明和-是左结合的且优先级相同。%left * /声明*和/是左结合的优先级高于和-因为后声明优先级更高。%right 声明赋值运算符是右结合的虽然标准SQL中是比较不是赋值这里仅为举例。当yacc遇到1 2 * 3的Token流时它会产生一个类似(1 (2 * 3))的AST结构而不是((1 2) * 3)。3.4 MySQL语法文件中的复杂之处打开sql/sql_yacc.yy你会被它的规模震撼。它包含了MySQL支持的所有SQL语句和表达式变体。一些复杂特性体现在多重入口语法可能有多个起始符号对应不同类型的语句SELECT、INSERT、UPDATE、DDL等。庞大的表达式体系从简单的字面量、列引用到函数调用、子查询、CASE表达式、窗口函数等表达式语法是嵌套最深、最复杂的部分之一。上下文相关关键字有些词在某些地方是关键字在别处可以是标识符。例如STATUS在SHOW STATUS中是关键字但CREATE TABLE t (status INT)中可以作为列名。这需要在词法分析或语法规则中通过上下文信息进行特殊处理增加了复杂度。优化与扩展为了性能MySQL的语法分析器可能直接进行一些简单的语义检查或转换而不是全部留给后续阶段。4. 实战追踪一个SELECT语句的解析全流程让我们结合一段简化版的代码逻辑模拟MySQL如何解析SELECT id, name FROM users WHERE statusactive;。第1步词法分析 (Lex)输入字符流被送入词法分析器。它依次识别SELECT- 查关键字表 - 返回KW_SELECTyylval未使用关键字通常不需要额外值。空格 - 跳过。id- 查关键字表不是关键字- 返回IDENTyylval指向字符串id。,- 返回COMMA。空格 - 跳过。name- 返回IDENT值name。空格 - 跳过。FROM- 返回KW_FROM。空格 - 跳过。users- 返回IDENT值users。空格 - 跳过。WHERE- 返回KW_WHERE。空格 - 跳过。status- 返回IDENT值status。- 返回EQ。active- 识别单引号字符串 - 返回TEXT_STRINGyylval指向字符串active已去除引号。;- 返回SEMICOLON。至此Token流生成完毕。第2步语法分析 (yacc)yacc解析器开始工作起始规则假设为statement。statement: select_stmt ;。它尝试匹配select_stmt。select_stmt: KW_SELECT select_list KW_FROM table_references opt_where_clause ...。匹配KW_SELECT(Token 1)。尝试匹配select_list。select_list: select_item | select_list , select_item。这是一个左递归规则用于解析逗号分隔的列表。匹配select_item: expr。expr可以匹配IDENT。于是第一个select_item是id。遇到COMMA继续匹配规则第二个select_item是name。最终select_list构建了一个包含两个表达式项的节点列表。匹配KW_FROM(Token 8)。匹配table_references: table_factor。table_factor匹配IDENTusers构建一个表引用节点。匹配可选的opt_where_clause: /* empty */ | KW_WHERE expr。这里匹配到了KW_WHERE(Token 12)。匹配expr。expr规则非常复杂这里匹配了一个等值比较expr: expr EQ expr。左侧的expr匹配IDENTstatus右侧的expr匹配TEXT_STRINGactive。最终构建一个PT_compare节点操作符为EQ。将select_list节点、table_references节点、where条件节点传递给select_stmt的动作构建出顶层的PT_select_stmt节点。匹配SEMICOLON(Token 17)。整个statement规则匹配成功顶层的AST构建完成。第3步产出物——抽象语法树AST此时内存中不再是一串文本或Token而是一棵结构化的树。简化表示如下PT_select_stmt ├── select_list: PT_select_list_exprs │ ├── item1: PT_identifier (nameid) │ └── item2: PT_identifier (namename) ├── from_clause: PT_table_reference (nameusers) └── where_clause: PT_compare (opEQUAL) ├── left: PT_identifier (namestatus) └── right: PT_literal_string (valueactive)这棵AST包含了查询的所有结构化信息但还没有任何语义信息比如users表是否存在id列是什么类型。这些是后续语义分析阶段的工作。5. 调试与排错当解析出错时怎么办回到我最初遇到的问题。面对一个解析错误如何利用yacc和Lex的知识进行调试5.1 理解错误信息yacc生成的解析器在遇到无法匹配语法规则的Token流时会调用yyerror()函数。MySQL中这个函数会报告类似You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near ??? at line 1的错误。关键信息在near ???部分。它指示了解析器在哪个Token附近“卡住”了。5.2 启用调试信息编译时如果你能自己编译MySQL可以在CMake时加上-DWITH_DEBUG1并确保-DCMAKE_BUILD_TYPEDebug。然后在启动mysqld时可以设置环境变量YYDEBUG1。这样解析器会输出详细的移进shift、归约reduce状态信息帮助你跟踪解析过程。不过这个输出极其冗长适用于对yacc状态机非常熟悉的开发者。5.3 静态分析检查语法规则对于大多数情况静态分析.yy文件更有效。我的排查步骤是定位疑似规则错误信息提到near ? IN (...)。所以我首先在sql/sql_yacc.yy中搜索IN关键字相关的语法规则。找到了处理in_predicateIN谓词的部分。in_predicate: expr opt_not KW_IN ( expr_list ) | expr opt_not KW_IN ( subquery ) | expr opt_not KW_IN simple_expr_list ;检查边界情况我的语句是WHERE status IN (?)。?是预编译参数占位符PARAM_MARKER。我需要看expr_list或simple_expr_list是否允许包含单个PARAM_MARKER。通过追溯expr_list的定义expr_list: expr | expr_list , expr最终看到expr可以推导为PARAM_MARKER。所以语法上似乎是允许的。对比版本差异我将有问题的分支版本的sql_yacc.yy和稳定版本的进行diff比较。发现了一个细微差别在某个用于处理子查询上下文的相关规则中对expr_list的上下文限制被修改了导致当IN后面紧跟一个带括号的列表且列表在预编译阶段只包含一个PARAM_MARKER时解析器在某个状态下的“展望”lookaheadToken判断上出现了冲突。这属于yacc的移进-归约冲突Shift-Reduce Conflict或归约-归约冲突Reduce-Reduce Conflict在特定修改后被触发。冲突的根源yacc在生成解析器时如果语法存在歧义它会报告冲突。通常开发者需要根据优先级和结合性规则或重构语法来消除冲突。这次的问题就是一次不完美的“解决”导致的副作用。在稳定版本中通过巧妙的规则顺序和优先级设置避免了冲突而在分支版本中一个无关的修改意外改变了规则优先级使得解析器在遇到(?)时选择了一条错误的解析路径最终导致语法错误。5.4 经验总结如何避免和排查此类问题敬畏语法文件sql_yacc.yy是MySQL的语法宪法任何修改都必须极其谨慎。修改后务必用bison重新生成解析器代码并确保没有新的冲突产生编译时会警告。理解冲突学习基本的yacc冲突知识。当同一个输入序列可以有多种语法树时就会发生冲突。你需要决定是让解析器“移进”更多Token还是立即“归约”当前规则。这通常需要深入理解SQL语义。测试用例全覆盖修改语法后必须用大量极端Case测试特别是涉及嵌套括号、子查询、预编译语句、各种表达式组合的情况。我的案例就是预编译语句边界测试不足导致的。利用社区和版本对比遇到诡异解析错误去查看MySQL官方Bug库或邮件列表类似问题很可能有人遇到过。对比不同版本的语法文件git diff是定位回归问题的利器。6. 进阶自定义SQL方言与语法扩展理解了MySQL的语法解析机制你甚至可以设想如何为自己的业务定制一套SQL方言DSL。虽然修改MySQL源码本身是庞大工程但原理是相通的。例如如果你想添加一个RETURNING子句到UPDATE语句中像PostgreSQL那样你需要在lex中增加关键字在sql/lex.h的关键字列表中添加{ RETURNING, SYM(RETURNING) }并确保生成了对应的KW_RETURNINGToken。在yacc中扩展语法找到update_stmt的规则在其末尾添加可选的opt_returning_clause。update_stmt: KW_UPDATE ... opt_where_clause opt_order_clause opt_limit_clause opt_returning_clause ; opt_returning_clause: /* empty */ | KW_RETURNING select_list ;定义AST节点和动作在动作代码中你需要创建新的AST节点类型如PT_returning_clause来保存select_list并将其挂载到update_stmt节点上。实现语义分析和执行这是最复杂的部分。你需要修改后续的语义分析器理解这个新子句的含义修改查询重写、优化器最终在存储引擎执行完更新后能按照RETURNING子句指定的列收集并返回修改后的数据。这只是一个示意真实操作涉及成千上万行代码的联动。但核心思想就是Lex定义词汇yacc定义句法动作构建AST后续阶段解释AST。7. 工具链从.yy文件到可执行代码我们一直在谈sql_yacc.yy但MySQL源码里并没有直接的yacc或bison生成的.c文件。这是因为这些文件是在编译过程中生成的。生成过程在MySQL的构建系统CMake中配置了一个步骤使用GNU Bisonyacc的现代兼容实现来解析sql_yacc.yy生成sql/sql_yacc.cc和sql/sql_yacc.h文件。同样历史上可能由Lex/Flex生成的文件现在已集成到手写的sql_lex.cc中。生成的解析器sql_yacc.cc包含了一个庞大的状态机函数yyparse()这就是SQL语法解析器的核心实现。sql/sql_parser.cc中的parse_sql()函数会调用yyparse()并设置好相关的词法分析器上下文。依赖关系因此如果你修改了sql_yacc.yy必须重新运行bison来生成sql_yacc.cc然后重新编译整个sql目录。MySQL的构建系统会自动处理这个依赖。对于开发者来说通常不需要直接运行bison。但了解这个流程很重要尤其是当你需要调试解析器本身或者像前面说的对比不同版本生成的解析器状态时。最后我想说的是阅读MySQL的yacc和Lex代码是一次对计算机科学中“编译器前端”的绝佳实践。它让你真正看到我们每天熟练使用的SQL语言是如何从一串平凡的字符经过词法分析的“识字”语法分析的“造句”最终成长为驱动海量数据操作的复杂指令树。下次再遇到语法错误你不妨在脑海中想象一下那个忙碌的、有些固执的解析器它正严格按照一套诞生了几十年的规则努力理解你的意图而有时候它只是需要一点更精确的指引。理解这套机制不仅能帮你解决更深层的bug更能提升你对数据库乃至所有编程语言设计原理的认知层次。