在前两篇文章中已经讲述了 bison 如何解析 sql 语句并生成 AST 树。那么 MySQL是如何和 bison 的程序关联起来的呢，并通过gdb 调试一下。在MySQL 源码解读之-语法解析（二）中我们用到了许多词法解析和语法解析的术语概念，例如 DFA, LALR。了解这些概念建议学习一下编译原理课程。
mysql 用到的 bison 关键字
| token | 标志0-255被保留作为字符值，⾃定义产⽣的token标志从258开始 |
| type | 为非终结符指明类型 |
| left | 表示左结合 |
| right | 表示右结合 |
| nonassoc | 表示无结合 |
| parse-param | 通过%parse-param {param} 来给 yyparse(param)传参数 |
| lex-param | 通过%lex-param {param} 来给 yylex(param)传参数 |
| start | 指定起始符号 |
| pure-parser | 指定希望解析器是可重⼊的 |
| expect | 告诉编译器预⻅多少次的移动归约冲突 |
token 用来定义终结符，例如 SELECT_SYM
left right nonassoc 指定运算符的结合方式，例如 + -等。优先级按照定义从上到下依次降低
start 起始符号，所有的文法从 start 开始，mysql中即为 start_entry
其他符号可以自查手册，建议参考书籍《flex 与 bison》
分析并调试语法解析过程
我们以最简单的 select * from bank; 为例，通过词法分析，该语句会被解析为 4 个token。我们在函数 THD::sql_parser 出打断点：然后执行 select 语句
可以看到，此处定义了根节点root，并作为参数传给 MYSQLparse。因为 yyparse 是 MYSQLparse 的宏定义，该函数由bison 自动生成比较复杂，此处不再跟进去调试。我们直接分析sql_yacc.yy文件。
可以看到，线程描述符和根节点 root被作为参数传了进来。 接下来就是根据文法进行匹配，我们可以通过 bison 的debug 进行分析。
可以先删除 gdb 断点，执行如下语句打开 bison 的debug 模式：
- set debug = "d,parser_debug";
如下是 debug 日志：
- Starting parse # 开始解析
- Entering state 0 # 进入状态 0
- Reading a token: Next token is token SELECT_SYM (: ) # 预读下一个 token SELECT_SYM(748)
- Shifting token SELECT_SYM (: ) # 移进 SELECT_SYM
- Entering state 42 # 进入状态 42
- Reading a token: Next token is token '*' (: ) # 预读下一个 token *(42)
- Reducing stack by rule 1380 (line 10081): # 根据第1380个规则进行归约 (10081行)
- -> $$ = nterm select_options (: ) # select_options被归约为空串 ε
- Stack now 0 42 # 当前栈为 0 42
- Entering state 1022 # 进入状态 1022
- Next token is token '*' (: ) # 下一个 token *
- Shifting token '*' (: ) # 移进 *
- Entering state 874 # 进入状态 874
- Reducing stack by rule 1400 (line 10171): # 根据第 1400 个规则 (10171行)
- $1 = token '*' (: ) # 终结符的值为 *
- -> $$ = nterm select_item_list (: ) # 把*归约成 select_item_list ($$ = NEW_PTN PT_select_item_list)
- Stack now 0 42 1022 # 当前栈 0 42 1022
- Entering state 1509 # 进入状态 1509
- Reading a token: Next token is token FROM (: ) # 读取下一个 token FROM
- Shifting token FROM (: ) # 移进 FROM
- Entering state 2250 # 进入状态 2250
- Reading a token: Next token is token IDENT_QUOTED (: ) # 读取下一个token IDENT_QUOTED
- Shifting token IDENT_QUOTED (: ) # 移进 IDENT_QUOTED
- Entering state 368 # 进入状态368
- Reducing stack by rule 2298 (line 14842): # 根据第2298个规则 (14842行)
- $1 = token IDENT_QUOTED (: ) # $1(即表名 bank) 为 IDENT_QUOTED
- -> $$ = nterm IDENT_sys (: ) # 把IDENT_QUOTED归约成 IDENT_sys
- Stack now 0 42 1022 1509 2250 # 当前栈 0 42 1022 1509 2250
- Entering state 722 # 进入状态 722 ($$= $1)
- Reducing stack by rule 2308 (line 14975): # 根据第 2308 个规则 (14975行)
- $1 = nterm IDENT_sys (: ) # $1为IDENT_sys(表名 bank)
- -> $$ = nterm ident (: ) # 把IDENT_sys归约为 ident ($$=$1, 此时ident的值为 bank)
- Stack now 0 42 1022 1509 2250 # 当前状态栈为 0 42 1022 1509 2250
- Entering state 1099 # 进入状态 1099
- Reading a token: Next token is token END_OF_INPUT (: ) # 读取下一个 token 为 END_OF_INPUT
- Reducing stack by rule 2293 (line 14807): # 根据第 2293 个规则进行归约 (14807行)
- $1 = nterm ident (: ) # $1为 ident(bank)
- -> $$ = nterm table_ident (: ) # 把 ident 归约成 table_ident -> $$= NEW_PTN Table_ident(to_lex_cstring($1))
- Stack now 0 42 1022 1509 2250 # 当前状态栈 0 42 1022 1509 2250
- Entering state 2998 # 进入状态 2998
- Next token is token END_OF_INPUT (: ) # 下一个 token 为 END_OF_INPUT
- Reducing stack by rule 1771 (line 11993): # 根据第 1771 个规则进行归约 (11993行)
- -> $$ = nterm opt_use_partition (: ) # opt_use_partition 归约为空串 ε
- Stack now 0 42 1022 1509 2250 2998 # 当前状态栈 0 42 1022 1509 2250 2998
- Entering state 3663 # 进入状态 3663
- Next token is token END_OF_INPUT (: ) # 读取下一个 token END_OF_INPUT
- Reducing stack by rule 1858 (line 12370): # 根据第 1858 个规则进行归约 (12370行)
- -> $$ = nterm opt_table_alias (: ) # opt_table_alias 归约为空串 ε
- Stack now 0 42 1022 1509 2250 2998 3663 # 当前状态栈 0 42 1022 1509 2250 2998 3663
- Entering state 4210 # 进入状态 4210
- Next token is token END_OF_INPUT (: ) # 读取下一个 token END_OF_INPUT
- Reducing stack by rule 1819 (line 12257): # 根据第 1819 个规则进行归约 (12257行)
- -> $$ = nterm opt_index_hints_list (: ) # opt_index_hints_list 归约为空串 ε
- Stack now 0 42 1022 1509 2250 2998 3663 4210 # 当前状态栈 0 42 1022 1509 2250 2998 3663 4210
- Entering state 4588 # 进入状态 4588
- Reducing stack by rule 1821 (line 12262): # 根据第 1821 个规则进行归约 (12262行)
- $1 = nterm opt_index_hints_list (: ) # $1 为 opt_index_hints_list 即 空串 ε
- -> $$ = nterm opt_key_definition (: ) # opt_index_hints_list 归约成 opt_key_definition 所以opt_key_definition也是空串 ε
- Stack now 0 42 1022 1509 2250 2998 3663 4210 # 当前状态栈 0 42 1022 1509 2250 2998 3663 4210
- Entering state 4589 # 进入状态 4589
- Reducing stack by rule 1784 (line 12053): # 根据第 1784 个规则进行归约 (12053行)
- $1 = nterm table_ident (: ) # $1 为table_ident （表名 back）
- $2 = nterm opt_use_partition (: ) # $2 为opt_use_partition 空串 ε
- $3 = nterm opt_table_alias (: ) # $3 为opt_table_alias 空串 ε
- $4 = nterm opt_key_definition (: ) # $4 为opt_key_definition 空串 ε
- -> $$ = nterm single_table (: ) # 归约成single_table $$= NEW_PTN PT_table_factor_table_ident($1, $2, $3, $4)
- Stack now 0 42 1022 1509 2250 # 当前状态栈 0 42 1022 1509 2250
- Entering state 2994 # 进入状态 2994
- Reducing stack by rule 1774 (line 12027): # 根据第 1774 个规则 (12027行)
- $1 = nterm single_table (: ) # $1为 single_table 当前已经是一个PT_table_factor_table_ident类的实例化对象
- -> $$ = nterm table_factor (: ) # 把 single_table直接归约成table_factor （默认规则,等同于 $$ = $1）
- Stack now 0 42 1022 1509 2250 # 当前栈状态 0 42 1022 1509 2250
- Entering state 2991 # 进入状态 2991
- Reducing stack by rule 1747 (line 11831): # 根据第 1747 个规则进行归约 (11831行)
- $1 = nterm table_factor (: ) # $1为table_factor
- -> $$ = nterm table_reference (: ) # 把 table_factor 归约成 table_reference $$ = $1
- Stack now 0 42 1022 1509 2250 # 当前状态栈 0 42 1022 1509 2250
- Entering state 2989 # 进入状态 2989
- Next token is token END_OF_INPUT (: ) # 下一个 token 为 END_OF_INPUT
- Reducing stack by rule 1376 (line 10047): # 根据第 1376 个规则进行归约 (10047行)
- $1 = nterm table_reference (: ) # $1为 table_reference 当前为 PT_table_factor_table_ident类的实例化对象
- -> $$ = nterm table_reference_list (: ) # 把 table_reference归约为table_reference_list 执行$$.init(YYMEM_ROOT);
- Stack now 0 42 1022 1509 2250 # 当前栈状态 0 42 1022 1509 2250
- Entering state 2988 # 进入状态 2988
- Next token is token END_OF_INPUT (: ) # 下一个 token 为 END_OF_INPUT
- Reducing stack by rule 1375 (line 10043): # 根据第 1375 个规则进行归约 (10043行)
- $1 = nterm table_reference_list (: ) # $1 为 table_reference_list
- -> $$ = nterm from_tables (: ) # 直接把 table_reference_list 归约成 from_tables
- Stack now 0 42 1022 1509 2250 # 当前栈状态为 0 42 1022 1509 2250
- Entering state 2987 # 进入状态 2987
- Reducing stack by rule 1373 (line 10038): # 根据第 1373 个规则进行归约 (10038行)
- $1 = token FROM (: ) # $1为 token FROM
- $2 = nterm from_tables (: ) # $2 为 from_tables
- -> $$ = nterm from_clause (: ) # 归约成 from_clause $$= $2
- Stack now 0 42 1022 1509 # 当前栈状态为 0 42 1022 1509
- Entering state 2252 # 进入状态 2252
- Reducing stack by rule 1372 (line 10034): # 根据第 1372 个规则进行归约 (10034行)
- $1 = nterm from_clause (: ) # $1 为 from_clause
- -> $$ = nterm opt_from_clause (: ) # 直接把 from_clause 归约成 opt_from_clause
- Stack now 0 42 1022 1509 # 当前栈状态 0 42 1022 1509
- Entering state 2251 # 进入状态 2251
- Next token is token END_OF_INPUT (: ) # 下一个 token END_OF_INPUT
- Reducing stack by rule 1862 (line 12380): # 根据第 1862 个规则进行归约 (12380行)
- -> $$ = nterm opt_where_clause (: ) # opt_where_clause 归约成空串 ε
- Stack now 0 42 1022 1509 2251 # 当前状态栈为 0 42 1022 1509 2251
- Entering state 3000 # 进入状态 3000
- Next token is token END_OF_INPUT (: ) # 下一个 token 为 END_OF_INPUT
- Reducing stack by rule 1881 (line 12509): # 根据第 1881 个规则进行归约 (12509行)
- -> $$ = nterm opt_group_clause (: ) # opt_group_clause 归约成空串 ε $$ = NULL
- Stack now 0 42 1022 1509 2251 3000 # 当前栈状态 0 42 1022 1509 2251 3000
- Entering state 3666 # 进入状态 3666
- Next token is token END_OF_INPUT (: ) # 下一个 token END_OF_INPUT
- Reducing stack by rule 1865 (line 12389): # 根据第 1865 个规则进行归约 (12389行)
- -> $$ = nterm opt_having_clause (: ) # opt_having_clause 归约成空串 ε $$ = NULL
- Stack now 0 42 1022 1509 2251 3000 3666 # 当前栈状态 42 1022 1509 2251 3000 3666
- Entering state 4214 # 进入状态 4214
- Next token is token END_OF_INPUT (: ) # 下一个 token END_OF_INPUT
- Reducing stack by rule 1876 (line 12470): # 根据第 1876 个规则进行归约 (12470行)
- -> $$ = nterm opt_window_clause (: ) # opt_window_clause 归约成空串 ε $$ = NULL
- Stack now 0 42 1022 1509 2251 3000 3666 4214 # 当前栈状态 0 42 1022 1509 2251 3000 3666 4214
- Entering state 4595 # 进入状态 4595
- Reducing stack by rule 1370 (line 10009): # 根据第 1370 个规则进行归约 (10089行)
- $1 = token SELECT_SYM (: ) # $1 为终结符 SELECT_SYM
- $2 = nterm select_options (: ) # $2 为 select_options 空串 ε
- $3 = nterm select_item_list (: ) # $3 为 select_item_list *
- $4 = nterm opt_from_clause (: ) # $4 为表名，此处表现为一个类对象
- $5 = nterm opt_where_clause (: ) # $5 为 opt_where_clause 空串 ε
- $6 = nterm opt_group_clause (: ) # $6 为 opt_group_clause 空串 ε
- $7 = nterm opt_having_clause (: ) # $7 为 opt_having_clause 空串 ε
- $8 = nterm opt_window_clause (: ) # $8 为 opt_window_clause 空串 ε
- -> $$ = nterm query_specification (: ) # 该文法归约成query_specification $$= NEW_PTN PT_query_specification(....)
- Stack now 0 # 当前栈为 0
- Entering state 118 # 进入状态 118
- Reducing stack by rule 1366 (line 9966): # 根据第 1366 个规则进行归约 (9966行)
- $1 = nterm query_specification (: ) # $1 为 query_specification
- -> $$ = nterm query_primary (: ) # 把 query_specification 归约成 query_primary $$= $1
- Stack now 0 # 当前栈为 0
- Entering state 117 # 进入状态 117
- Reducing stack by rule 1358 (line 9933): # 根据第 1358 个规则进行归约 (9933行)
- $1 = nterm query_primary (: ) # $1 为 query_primary
- -> $$ = nterm query_expression_body (: ) # 把 query_primary 归约成 query_expression_body $$= $1
- Stack now 0 # 当前栈状态 0
- Entering state 115 # 进入状态 115
- Next token is token END_OF_INPUT (: ) # 下一个 token END_OF_INPUT
- Reducing stack by rule 1890 (line 12571): # 根据第 1890 个规则进行归约 (12571行)
- -> $$ = nterm opt_order_clause (: ) # 把opt_order_clause归约为 空串 ε $$ = NULL
- Stack now 0 115 # 当前栈状态 0 115
- Entering state 1169 # 进入状态 1169
- Next token is token END_OF_INPUT (: ) # 读取下一个 token END_OF_INPUT
- Reducing stack by rule 1899 (line 12608): # 根据第 1899 个规则进行归约 (12608行)
- -> $$ = nterm opt_limit_clause (: ) # 把 opt_limit_clause 归约为 空串 ε $$ = NULL
- Stack now 0 115 1169 # 当前栈状态 0 115 1169
- Entering state 1713 # 进入状态 1713
- Reducing stack by rule 1351 (line 9888): # 根据第 1351 个规则进行归约 (9888行)
- $1 = nterm query_expression_body (: ) # $1为 query_expression_body 目前是一个类对象
- $2 = nterm opt_order_clause (: ) # $2为 opt_order_clause 空串 ε
- $3 = nterm opt_limit_clause (: ) # $3为 opt_limit_clause 空串 ε
- -> $$ = nterm query_expression (: ) # 根据该文法归约成 query_expression $$ = NEW_PTN PT_query_expression($1, $2, $3)
- Stack now 0 # 当前栈状态 0
- Entering state 114 # 进入状态 114
- Next token is token END_OF_INPUT (: ) # 下一个 token END_OF_INPUT
- Reducing stack by rule 1342 (line 9784): # 根据第 1342 个规则进行归约 (9784行)
- $1 = nterm query_expression (: ) # $1为 query_expression
- -> $$ = nterm select_stmt (: ) # 把query_expression 归约成select_stmt $$ = NEW_PTN PT_select_stmt($1)
- Stack now 0 # 当前栈状态 0
- Entering state 112 # 进入状态 112
- Reducing stack by rule 91 (line 2355): # 根据第 91 个规则进行归约 (2355行)
- $1 = nterm select_stmt (: ) # $1为 select_stmt
- -> $$ = nterm simple_statement (: ) # 把select_stmt归约成simple_statement
- Stack now 0 # 当前栈状态 0
- Entering state 68 # 进入状态 68
- Reducing stack by rule 13 (line 2273): # 根据第 13 个规则 (2273行)
- $1 = nterm simple_statement (: ) # $1为 simple_statement
- -> $$ = nterm simple_statement_or_begin (: ) # 把simple_statement归约成 simple_statement_or_begin { *parse_tree= $1 }
- Stack now 0 # 当前栈状态 0
- Entering state 67 # 进入状态 67
- Next token is token END_OF_INPUT (: ) # 下一个 token END_OF_INPUT
- Shifting token END_OF_INPUT (: ) # 移进END_OF_INPUT
- Entering state 1138 # 进入状态 1138
- Reducing stack by rule 10 (line 2260): # 根据第 10 个规则进行归约 (2260行)
- $1 = nterm simple_statement_or_begin (: ) # $1为 simple_statement_or_begin
- $2 = token END_OF_INPUT (: ) # $2为 token END_OF_INPUT
- -> $$ = nterm sql_statement (: ) # 归约成 sql_statement YYLIP->found_semicolon= NULL
- Stack now 0 # 当前栈状态 0
- Entering state 66 # 进入状态 66
- Reducing stack by rule 1 (line 2177): # 根据第 1 个规则进行归约 (2177行)
- $1 = nterm sql_statement (: ) # $1为 sql_statement
- -> $$ = nterm start_entry (: ) # 直接把 sql_statement 归约成start_entry
- Stack now 0 # 当前栈状态 0
- Entering state 65 # 进入状态 65
- Reading a token: Now at end of input. # 读取一个token, 现在已经位于输入流的末端
- Shifting token $end (: ) # 移进 $end
- Entering state 1137 # 进入状态 1137
- Stack now 0 65 1137 # 当前栈状态 0 65 1137
- Cleanup: popping token $end (: ) # 弹出 token $end
- Cleanup: popping nterm start_entry (: ) # 弹出 start_entry 语法解析结束，该 sql 被解析成一个正确的 sql 语法
如上所示 select * from bank; 最后归约成 start_entry。则说明该语句是一个正确的 sql 语法。我们再举一个反例，执行 selectt 1; 我们知道这是一个错误的语法，此时我们再看一下解析器的 debug 日志：
因此我们可以看到，如果 sql 出现语法错误是在语法解析阶段判断出来的。
前文中我们讲到，bison 做完语法解析后会返回一颗 AST 树，现在我们通过p命令，逐步打印出整个解析树。前边我们可以看到源代码中对根节点的定义为 root。然后根据 bison 的 debug 日志，从 start_entry 一步步推导出所有叶子节点。
1）、我们先打印下 root 节点，如下图所示：root 节点是 PT_select_stmt。 通过查看 PT_select_stmt类的定义，我们可以PT_select_stmt类的私有成员 m_qe 的类型为 PT_query_expression_body *。通过查看bison 的 debug 日志，我们也可以分析到最终是由 select_stmt 归约得到的。select_stamt 的执行码为 $$ = NEW_PTN PT_select_stmt($1)。
$1是类型PT_query_expression。PT_query_expression是PT_query_expression_body 的子类。此处可以通过查看 类PT_select_stmt的构造函数代码查看该类的实例化过程
2）、我们继续反向分析 bison 的 debug 日志。PT_select_stmt是由PT_query_expression归约得到的，我们看 query_expression的执行码 $$ = NEW_PTN PT_query_expression($1, $2, $3)。 PT_query_expression对象是由 query_expression_body作为入参得到的。 而query_expression_body是由query_specification先归约成query_primary，query_primary再归约成query_expression_body。
而PT_query_primaey是query_expression_body的子类。PT_query_specification是PT_query_primary的子类。所有如下图所示，m_body应该是类PT_query_specification的实例化对象。
3、通过查看PT_query_specification类的代码，可以看到该类的 from_clause成员是一个<PT_table_reference *>容器。打印它的 value.table_name 属性即可看到，我们此次查询的表名bank。
4、此处我们虽然看到了表名，依然可以进一步分析这个表名的来源。PT_query_specification是由于 SELECT_SYM select_item_list opt_from_clause归约形成。opt_from_clause由from_clause归约形成。经过多层归约，opt_from_clause最初是由 single_table $$= NEW_PTN PT_table_factor_table_ident($1, $2, $3, $4)逐级归约得到。 PT_table_factor_table_ident是PT_table_reference的子类，因此我们可以把m_array[0]强转为 PT_table_factor_table_ident *
此处我们通过PT_table_factor_table_ident的 value属性打印出来了表名，是因为我们在 gdb时候代码运行到了 make_sql_cmd 函数，value 的设置是make_sql_cmd完成的，并不是 MySQLparser 做的，因为yy 文件很难用 gdb 调试，我在这里解析过程中找 value 的初始化找了好久没找到。自己挖坑自己跳，此处留个记号
5、上图我们可以看到类PT_table_factor_table_ident的 value 成员是一个 TABLE_LIST对象，我们一样获取到了表名。TBALE_LIST 我们可以在父类 PT_table_reference 中找到定义：
- class PT_table_reference : public Parse_tree_node {
- public:
- TABLE_LIST *value;
- virtual PT_joined_table *add_cross_join(PT_cross_join *cj);
- };
6、继续分析 bison 的 debug 日志。PT_table_factor_table_ident对象的初始化过程，第一个参数为Table_ident。而非终结符table_ident的执行码为 $$= NEW_PTN Table_ident(to_lex_cstring($1))，$1就是我们读取到的字符 bank
至此为止，我们已经找到了树的最低层。
7、我们再看一下其他节点，目前还差 * 没有分析，我们继续看 bison 的 debug 日志。
- Reducing stack by rule 1400 (line 10171): # 根据第 1400 个规则 (10171行)
- $1 = token '*' (: ) # 终结符的值为 *
- -> $$ = nterm select_item_list (: ) # 把*归约成 select_item_list ($$ = NEW_PTN PT_select_item_list)
-
- 对应的 c 执行码如下：
- Item *item = NEW_PTN Item_asterisk(@$, nullptr, nullptr);
- $$ = NEW_PTN PT_select_item_list;
- if ($$ == nullptr || item == nullptr || $$->push_back(item))
- MYSQL_YYABORT;
*被直接归约成了 select_item_list。 PT_select_item_list类的定义如下：从命令我们不难看出，这是个 item 列表。继续分析 bison 的 debug 日志，select_item_list作为入参被归约成了PT_query_specification。然后最终被归约成PT_select_stmt，和前边表名一样的步骤。
到目前为止，我们已经把整个树的所有节点都分析完成了。下边我们手绘一下整个 AST 树。
到目前为止，经过bison，即MySQLparser 函数解析后的 sql生产的 AST 树就是这个样子的。
湘公网安备 43102202000103号
