MySQL 源码解读之-语法解析（三）
在前两篇文章中已经讲述了 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_qe应该是类PT_query_specification的实例化对象。
3、继续根据 bison 的 debug 日志向上分析，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的子类，因此我们经过转化，最后打印出表名：
其他分析这里就不再一一跟进了，套娃简直恶心。
标签：opt,nterm,42,归约,语法,token,源码,MySQL,query From： https://www.cnblogs.com/jkin/p/16887718.html