前言
最近在集中学习 mysql 源码,刚好分了几个主题,波及到词法解析、语法解析、查询器、优化器等。刚好把筹备的 PPT 内容摘出来整顿成相应的文章。
Mysql 版本:8.0.20
调试工具:lldb
零碎环境:MacOS 10.14.3
在理解词法解析之前,咱们带着几个问题来切入:
(1)什么是词法解析?
(2)Mysql 8.0.20 词法解析有什么优化?
(3)Mysql 8 词法解析都有什么过程?
1. 什么是词法解析?
词法剖析(lexical analysis)是计算机科学中将字符序列转换为单词(Token)序列的过程。进行词法剖析的程序或者函数叫作词法分析器(Lexical analyzer,简称 Lexer),也叫扫描器(Scanner)。词法分析器个别以函数的模式存在,供语法分析器调用。
词法分析阶段是编译过程的第一个阶段,是编译的根底。这个阶段的工作是从左到右一个字符一个字符地读入源程序,即对形成源程序的字符流进行扫描而后依据构词规定辨认单词 (也称单词符号或符号)。词法分析程序实现这个工作。词法分析程序能够应用 Lex 等工具主动生成。
词法剖析是编译程序的第一个阶段且是必要阶段;词法剖析的外围工作是扫描、辨认单词且对辨认出的单词给出定性、定长的解决;实现词法分析程序的罕用路径: 主动生成, 手工生成。
主动生成词法能够参照我之前写的一篇文章:
https://blog.csdn.net/byxiaoyuonly/article/details/107851764
2. 词法解析
2.1 词法解析状态机
词法解析状态机是在词法解析的扫描阶段执行的过程,下图 2 -1- 1 是状态解析 token 的执行过程:
<center> 图 2 -1-1 状态机解析 token 过程 </center>
状态机的主要用途就是解析 token 时的执行过程,比方 MY_LEX_IDENT 状态机会循环匹配字符后,解析字符并返回对应的 token。
对应状态机 | 备注 |
---|---|
MY_LEX_START | 开始解析 token |
MY_LEX_CHAR | 解析单个字符例如 *、:、; |
MY_LEX_IDENT | 解析字符串,匹配关键词,例如“table”、“select”等 |
MY_LEX_IDENT_SEP | 找到字符 ’.’ |
MY_LEX_IDENT_START | 从 ’.’ 开始解析 token |
MY_LEX_REAL | 不齐全实数 |
MY_LEX_HEX_NUMBER | hex 字符串 |
MY_LEX_BIN_NUMBER | bin 字符串 |
MY_LEX_CMP_OP | 不齐全比拟运算符 |
MY_LEX_LONG_CMP_OP | 不齐全比拟运算符 |
MY_LEX_STRING | 字符串 |
MY_LEX_COMMENT | Comment |
MY_LEX_END | 完结 |
MY_LEX_NUMBER_IDENT | 数字 |
MY_LEX_INT_OR_REAL | 齐全整数或不齐全实数 |
MY_LEX_REAL_OR_POINT | 解析. 返回不齐全实数,或者字符 ’.’ |
MY_LEX_BOOL | 布尔 |
MY_LEX_EOL | 如果是 eof,则设置状态 end 完结, |
MY_LEX_LONG_COMMENT | 长 C 正文 |
MY_LEX_END_LONG_COMMENT | 备注完结 |
MY_LEX_SEMICOLON | 分隔符; |
MY_LEX_SET_VAR | 查看:= |
MY_LEX_USER_END | 完结 ’@’ |
MY_LEX_HOSTNAME | 解析 hostname |
MY_LEX_SKIP | 空格 |
MY_LEX_USER_VARIABLE_DELIMITER | 引号字符 |
MY_LEX_SYSTEM_VAR | 例如解析 user@hostname,解析到 @ |
MY_LEX_IDENT_OR_KEYWORD | 判断返回字符串状态或者键盘键值 |
MY_LEX_IDENT_OR_HEX | hex- 数字 |
MY_LEX_IDENT_OR_BIN | bin- 数字 |
MY_LEX_IDENT_OR_NCHAR | 判断返回字符状态,或字符串状态 |
MY_LEX_STRING_OR_DELIMITER | 判断返回字符串状态或者空格字符状态 |
2.2 调试解析源码
咱们能够一起来跟一下源码,如果不会装置编译能够看一下我之前的文章
《【Mysql 源码剖析】MySQL 为什么有时候会选错索引及成本计算》
https://blog.csdn.net/byxiaoyuonly/article/details/107651106
咱们开始调试,首先要先启动下 mysql8.0.20。而后筹备两个终端:一个终端用于操作 mysql 语句、另外一个终端用于调试应用, 如图 2 -2-1。
<center> 图 2 -2-1 关上终端 </center>
能够用 lldb 进行调试:
#lldb -p 过程 ID
<center> 图 2 -2-2 词法解析调用过程 </center>
依据图 2 -2- 2 咱们能够得悉,Mysql8.0.20 会调用 MYSQLlex 办法进行词法解析、MYSQLlex 中会调用 lex_one_token 进行单个 token 解析。如果咱们要调试能够对 lex_one_token 去下一个断点。
(lldb)b lex_one_token
下断点后在 mysql 操作终端操作做一条语句例如“select * from t1;”,此时调试终端会捕捉到断点,调试到图 2 -2-3。
<center> 图 2 -2-3 调试图 </center>
依据上图咱们得悉第一个状态机为 MY_LEX_START,执行状态机进入 switch 后,会通过 yyPeek 办法获取一个字符如图 2 -2-4。来判断这个字符是否为空格,不是空格后,通过“state = state_map;”返回一个状态机。判断时通过 state_map 解析,state_map 在 2.3 大节会介绍。
<center> 图 2 -2-4 MY_LEX_START 调试图 </center>
因为获取单个字符是 s,s 对应 state_map 中的状态机是 MY_LEX_IDENT,MY_LEX_IDENT 状态机会去匹配对应的关键词返回 token。
<center> 图 2 -2-5 MY_LEX_START 调试图 2 </center>
依据图 2 -2- 5 咱们得悉通过 find_keyword 办法能够匹配对应的 token。第一次匹配后咱们失去一个 token(748),748 这个 token 对应 SELECT_SYM,能够在 /mysql-8.0.20/sql/sql_yacc.h 文件中查找到。此时 m_ptr 参数值为“* from t1”, 该参数由返回前调用 lip->yyUnget() 进行左移。lip->next_state 的状态再次设置为 MY_LEX_START。
<center> 图 2 -2-6 MY_LEX_END_LONG_COMMENT 调试图 </center>
当咱们再次调用 lex_one_token 时,解决 MY_LEX_START 状态机时,会过滤调一个空格字符。继续执行获取,获取到“*”字符,又会将状态机设置为 MY_LEX_END_LONG_COMMENT, 而后执行状态机会设置为 MY_LEX_CHAR,返回时下一次的状态设置成了 MY_LEX_START。最初返回一个 token(42),其实这个 42 是 ASCII 到“*”。此时 m_ptr 参数值为“from t1”。再次执行 MY_LEX_START 过程,会设置状态机为 MY_LEX_IDENT,执行 MY_LEX_IDENT 状态机后会返回 token(452), 能够在 /mysql-8.0.20/sql/sql_yacc.h 文件中查找到。对应 FROM。再次执行后会返回状态机 IDENT_QUOTED, 最终返回状态机 MY_LEX_EOL,最终返回 MY_LEX_END 完结。
<center> 图 2 -2-7 调试解析残缺过程 </center>
2.3 state_map 介绍
state_map 是验证状态机的关键步骤,初始化该过程次要在 /mysql-8.0.20/mysys/sql_chars.cc 文件的 init_state_maps 办法中,办法实现如下:
bool init_state_maps(CHARSET_INFO *cs) {
uint i;
uchar *ident_map;
enum my_lex_states *state_map = nullptr;
lex_state_maps_st *lex_state_maps = (lex_state_maps_st *)my_once_alloc(sizeof(lex_state_maps_st), MYF(MY_WME));
if (lex_state_maps == nullptr) return true; // 空指针 OOM
cs->state_maps = lex_state_maps;
state_map = lex_state_maps->main_map;
if (!(cs->ident_map = ident_map = (uchar *)my_once_alloc(256, MYF(MY_WME))))
return true; // OOM
hint_lex_init_maps(cs, lex_state_maps->hint_map);
/* 填充状态以取得更快的解析器 */
for (i = 0; i < 256; i++) {if (my_isalpha(cs, i))
state_map[i] = MY_LEX_IDENT; // 字符串状态机
else if (my_isdigit(cs, i))
state_map[i] = MY_LEX_NUMBER_IDENT;
else if (my_ismb1st(cs, i))
/* To get whether it's a possible leading byte for a charset. */
state_map[i] = MY_LEX_IDENT;
else if (my_isspace(cs, i))
state_map[i] = MY_LEX_SKIP; // 空格状态机
else
state_map[i] = MY_LEX_CHAR; // 字符状态机
}
state_map[(uchar)'_'] = state_map[(uchar)'$'] = MY_LEX_IDENT;
state_map[(uchar)'\''] = MY_LEX_STRING;
state_map[(uchar)'.'] = MY_LEX_REAL_OR_POINT;
state_map[(uchar)'>'] = state_map[(uchar)'='] = state_map[(uchar)'!'] =
MY_LEX_CMP_OP; // 操作合乎匹配状态机
state_map[(uchar)'<'] = MY_LEX_LONG_CMP_OP;
state_map[(uchar)'&'] = state_map[(uchar)'|'] = MY_LEX_BOOL;
state_map[(uchar)'#'] = MY_LEX_COMMENT;
state_map[(uchar)';'] = MY_LEX_SEMICOLON;
state_map[(uchar)':'] = MY_LEX_SET_VAR;
state_map[0] = MY_LEX_EOL; // 完结标记状态机
state_map[(uchar)'/'] = MY_LEX_LONG_COMMENT;
state_map[(uchar)'*'] = MY_LEX_END_LONG_COMMENT; //* 字符匹配状态机
state_map[(uchar)'@'] = MY_LEX_USER_END; //@字符匹配状态机
state_map[(uchar)'`'] = MY_LEX_USER_VARIABLE_DELIMITER;
state_map[(uchar)'"'] = MY_LEX_STRING_OR_DELIMITER;
/*
创立第二个映射以放慢查找标识符的速度
*/
for (i = 0; i < 256; i++) {ident_map[i] = (uchar)(state_map[i] == MY_LEX_IDENT ||
state_map[i] == MY_LEX_NUMBER_IDENT);
}
/* Special handling of hex and binary strings */
state_map[(uchar)'x'] = state_map[(uchar)'X'] = MY_LEX_IDENT_OR_HEX;
state_map[(uchar)'b'] = state_map[(uchar)'B'] = MY_LEX_IDENT_OR_BIN;
state_map[(uchar)'n'] = state_map[(uchar)'N'] = MY_LEX_IDENT_OR_NCHAR;
return false;
}
代码中能疾速匹配状态机,就是因为初始化好了一堆的状态机 map,依据字符能够匹配不同的状态机。状态机的宏在 mysql-8.0.20/include/sql_chars.h 文件中。
2.4 源码解析
要害代码 lex_one_token 解析:
static int lex_one_token(Lexer_yystype *yylval, THD *thd) {
uchar c = 0;
bool comment_closed;
int tokval, result_state;
uint length;
enum my_lex_states state;
Lex_input_stream *lip = &thd->m_parser_state->m_lip; // 取得输出信息
const CHARSET_INFO *cs = thd->charset(); // 取得字符集
const my_lex_states *state_map = cs->state_maps->main_map; // 取得状态
const uchar *ident_map = cs->ident_map; // 字符串宰割合乎
lip->yylval = yylval; // 全局状态
lip->start_token(); // 初始化 token 字符串
state = lip->next_state; // 取得下一个状态
lip->next_state = MY_LEX_START; // 设置下一个状态
for (;;) { // 循环解析状态机
switch (state) {
case MY_LEX_START: // 开始解析 token
while (state_map == MY_LEX_SKIP) { // 解析 token,判断是否为空格
if (c == '\n') lip->yylineno++;
lip->yySkip(); // 解决空格}
/* Start of real token */
lip->restart_token(); // 设置 m_tok_start 和 m_cpp_tok_start
c = lip->yyGet(); // 取得单个字符,并设置 m_cpp_ptr, 并且 m_ptr 移位
state = state_map; // 如果是字符串返回 MY_LEX_IDENT 状态
break;
//...
case MY_LEX_IDENT: // 解析字符串关键词,比方 select、tables 等
const char *start;
if (use_mb(cs)) {
result_state = IDENT_QUOTED;
switch (my_mbcharlen(cs, lip->yyGetLast())) {
case 1:
break;
case 0:
if (my_mbmaxlenlen(cs) < 2) break;
/* else fall through */
default:
int l =
my_ismbchar(cs, lip->get_ptr() - 1, lip->get_end_of_query());
if (l == 0) {
state = MY_LEX_CHAR;
continue;
}
lip->skip_binary(l - 1);
}
while (ident_map) { // 循环获取字符串
switch (my_mbcharlen(cs, c)) {
case 1:
break;
case 0:
if (my_mbmaxlenlen(cs) < 2) break;
/* else fall through */
default:
int l;
if ((l = my_ismbchar(cs, lip->get_ptr() - 1,
lip->get_end_of_query())) == 0)
break;
lip->skip_binary(l - 1);
}
}
} else {for (result_state = c; ident_map; result_state |= c)
;
/* If there were non-ASCII characters, mark that we must convert */
result_state = result_state & 0x80 ? IDENT_QUOTED : IDENT;
}
length = lip->yyLength();
start = lip->get_ptr();
if (lip->ignore_space) {
/*
If we find a space then this can't be an identifier. We notice this
below by checking start != lex->ptr.
*/
for (; state_map == MY_LEX_SKIP; c = lip->yyGet()) {if (c == '\n') lip->yylineno++;
}
}
if (start == lip->get_ptr() && c == '.' && ident_map[lip->yyPeek()]) // 判断字符是否为 '.' '
lip->next_state = MY_LEX_IDENT_SEP;
else { // '(' must follow directly if function
lip->yyUnget();
if ((tokval = find_keyword(lip, length, c == '('))) { // 查找 token
lip->next_state = MY_LEX_START; // Allow signed numbers
return (tokval); // 返回 token
}
lip->yySkip(); // next state does a unget}
yylval->lex_str = get_token(lip, 0, length);
//...
return (result_state); // IDENT or IDENT_QUOTED
//...
case MY_LEX_EOL: //'\0' 结束符
if (lip->eof()) {lip->yyUnget(); // Reject the last '\0'
lip->set_echo(false);
lip->yySkip();
lip->set_echo(true);
/* Unbalanced comments with a missing '*' '/' are a syntax error */
if (lip->in_comment != NO_COMMENT) return (ABORT_SYM);
lip->next_state = MY_LEX_END; // 设置下一个状态机为 MY_LEX_END,持续循环
return (END_OF_INPUT); // 返回 token
}
}
}
}
3.Mysql 8.0.20 词法解析有哪些优化?
在解析 select * from t1; 语句过程中,mysql5 会多一步 MY_LEX_OPERATOR_OR_IDENT 的过程。在 mysql 8.0.20 中优化了该过程, 如图 3 -1。
<center> 图 3 -1 调试 mysql5.6.48 过程 </center>
总结
(1)状态机宏在 /mysql-8.0.20/include/sql_chars.h 中。
(2)疾速匹配字符状态是因为 init_state_maps 办法提前初始化好状态 map。
(3)对应的 token 能够在 /mysql-8.0.20/sql/sql_yacc.h 文件中查找到。
(4)一些字符会间接返回 ASCII, 例如 *