設(shè)計(jì)：小艾
審核：丁奇
編輯：宇亭
作者：柳湛宇（花名：烏淄）
浙江大學(xué)-軟件工程-在讀碩士开睡、StoneDB 內(nèi)核研發(fā)實(shí)習(xí)生
一袭艺、MySQL 的解析器
MySQL 所使用的解析器（即 Lexer 和 Parser 的組合）是嵌入了 C/C++語言的 yacc/lex 組合亏吝，在 linux/GNU 體系上主儡，這一組合的實(shí)現(xiàn)是 GNU Bison/Flex雀久，即 Flex 負(fù)責(zé)生成 tokens构眯， Bison 負(fù)責(zé)語法解析芯义。
對(duì)于 Bison哈垢，請(qǐng)參閱[1]
Bison 本是一個(gè)自底向上（Bottom-Up）的解析器，但是由于歷史原因扛拨，MySQL 語法編寫的規(guī)則是以自頂向下（Top-Down）的耘分，這將會(huì)產(chǎn)生一些問題，我們首先簡要介紹這兩種解析模式绑警。
二求泰、自底向上與自頂向下解析模式
更多詳細(xì)講解，請(qǐng)參閱[2]
當(dāng)我們?cè)谡務(wù)撟缘紫蛏虾妥皂斚蛳聝煞N解析模式時(shí)计盒，局面是我們手上已經(jīng)有了編寫完成的語法規(guī)則和將輸入語句詞法解析完成后的 token 數(shù)組渴频，而之后的任務(wù)總體上就是構(gòu)建語法解析樹。
以下 yacc 語法約束和匹配序列（「例 1」）用于展示兩種解析模式的不同北启。
exp1:
'a' 'b' | 'b' 'c';
exp2:
'x' 'y' 'z' | 'a' exp3;
exp3:
'c' 'd' | exp1 'd';
以a b c d作為輸入序列卜朗。
自底向上（Bottom-Up）解析模式
自底向上的解析模式類似于進(jìn)行「拼圖」拔第。對(duì)每一個(gè)入棧后 token 組成的序列，都盡可能嘗試將其規(guī)約（reduce）成一個(gè)語法規(guī)則中規(guī)定的表達(dá)式并將新的表達(dá)式壓棧场钉。在達(dá)到 token 數(shù)組末尾時(shí)蚊俺，棧中的表達(dá)式應(yīng)且僅應(yīng)匹配一個(gè)頂層表達(dá)式，如果因?yàn)橐?guī)約順序不符合實(shí)際表達(dá)式順序而無法匹配到頂層表達(dá)式逛万，則應(yīng)當(dāng)進(jìn)行回溯并嘗試新的規(guī)約選擇泳猬。
對(duì)于例 1，自底向上解析模式的解析步驟為：
-
a不能被規(guī)約（沒有可以匹配a的表達(dá)式子項(xiàng)） -
a b可以被規(guī)約： -
exp1 c d被規(guī)約為exp1 exp3 -
exp1 exp3無法被規(guī)約 - 達(dá)到序列末尾宇植，需要回溯
-
-
a b規(guī)約為exp1 -
exp1 c無法被規(guī)約 -
exp1 c d可以被規(guī)約: - 因此得封，
exp1 c d無法被規(guī)約 - 達(dá)到序列末尾，需要回溯
-
- 因此指郁，
a b無法被規(guī)約 -
a b c可以被規(guī)約： -
a b c可以被規(guī)約為a exp1 -
a exp1 d可以被規(guī)約
-
-
a exp1 d可以被規(guī)約為a exp3 -
a exp3可以被規(guī)約：
-
-
a exp3可以被規(guī)約為exp2 -
達(dá)到序列末尾呛每，
a b c d成功匹配表達(dá)式exp2
-
自頂向下（Top-Down）解析模式
自頂向下的表達(dá)式類似于「多叉樹的先序遍歷」。對(duì)于給定的每一個(gè) token 子序列坡氯，都嘗試斷言（Assertion）其匹配一個(gè)表達(dá)式晨横，并進(jìn)一步遞歸地考察：
?
1.這個(gè)序列是否能通過斷言匹配該表達(dá)式的子選項(xiàng)；
2.斷言匹配子選項(xiàng)后箫柳，其對(duì)應(yīng)改規(guī)則可歸約的子串是否匹配子選項(xiàng)中的表達(dá)式手形。?
每當(dāng)斷言失敗時(shí)，同樣進(jìn)行回溯悯恍，來嘗試匹配不同的表達(dá)式或表達(dá)式內(nèi)不同的子選項(xiàng)库糠，直至構(gòu)建正確的語法解析樹或匹配失敗而報(bào)錯(cuò)。
對(duì)于例 1涮毫，自頂向下解析模式的解析步驟為：
- 假設(shè)（此處的原語是斷言瞬欧，Assertion）
a b c d匹配exp1的第一個(gè)子選項(xiàng)'a' 'b' - 斷言錯(cuò)誤，因此排除這一選項(xiàng)罢防；
- 同樣地艘虎，顯然可以排除
exp1的第二個(gè)子選項(xiàng)'b' 'c'和exp2的第一個(gè)子選項(xiàng)'x' 'y' 'z',此處省略這些步驟； - 假設(shè)
a b c d匹配exp2的第二個(gè)子選項(xiàng)'a' exp3 - 應(yīng)有
b c d匹配exp3 - 假設(shè)
b c d匹配'c' 'b' - 斷言錯(cuò)誤咒吐，排除這一選項(xiàng)
- 假設(shè)
b c d匹配'exp1' 'd'
- 應(yīng)有
- 應(yīng)有
b c匹配exp1 - 假設(shè)
b c匹配'a' 'b' - 斷言錯(cuò)誤野建，排除這一選項(xiàng)
- 假設(shè)
b c匹配'b' 'c' -
「斷言正確且無子表達(dá)式，匹配成功恬叹，」
a b c d「匹配」exp2
- 應(yīng)有
二者的對(duì)比與 MySQL 面臨的問題
可以看到候生，自底向上解析模式更符合計(jì)算機(jī)程序的風(fēng)格，其將規(guī)約操作提前绽昼，在后半部分執(zhí)行匹配和回溯動(dòng)作唯鸭。但其缺點(diǎn)在于，每一次匹配和回溯的觸發(fā)點(diǎn)都僅僅在達(dá)到 token 數(shù)組末尾時(shí)進(jìn)行硅确，因此如果沒有優(yōu)先級(jí)約束目溉，每次有效回溯的代價(jià)都較大唠粥。
自頂向下的解析模式更符合人類閱讀和編寫語法文件的習(xí)慣，其將斷言和回溯動(dòng)作提前停做，將實(shí)際的匹配動(dòng)作置于解析的后半段。這樣的模式缺點(diǎn)在于大莫，它需要回溯的次數(shù)更多蛉腌，同時(shí)語法愈發(fā)復(fù)雜，如果沒有合適的斷言順序（實(shí)際上對(duì)于不同的 SQL 語句只厘，最優(yōu)的斷言順序也不盡相同）烙丛，就會(huì)有更多冗余的比較分支和更深的有效回溯長度。
由于 MySQL 因歷史原因選擇了易讀的自頂向下的解析模式羔味，其在語法解析時(shí)河咽，會(huì)產(chǎn)生二義性帶來的兩種沖突（conflict）：移位/規(guī)約（shift/reduce）沖突和規(guī)約/規(guī)約（reduce/reduce）沖突，而使用自底向上解析模式的 posgres[3]則不會(huì)產(chǎn)生這兩種沖突赋元。
三忘蟹、移位/規(guī)約沖突與規(guī)約/規(guī)約沖突
兩種操作
首先簡要介紹自底向上分析方法的移位（shift）和規(guī)約（reduce）操作。按自底向上的解析模式搁凸，解析器對(duì)輸入符號(hào)串從左到右掃描媚值，讀取輸入并與語法規(guī)則比較，其中：
- 移位操作是將符號(hào)從輸入流轉(zhuǎn)入分析棧中的操作护糖。如果當(dāng)前輸入與語法規(guī)則匹配褥芒，解析器就將當(dāng)前輸入移入（shift）語法棧中，并繼續(xù)嘗試處理下一個(gè)符號(hào)嫡良。簡單演示見下例 2:
對(duì)于如下語法定義：
simpleStrSeq:
'a' 'b' 'c' | 'e' 'f' 'g';
處理輸入串a b c時(shí)锰扶，處理前兩個(gè) token 時(shí)都會(huì)將其直接放入語法棧，因?yàn)樗鼈兤ヅ?code>simpleStrSeq表達(dá)式寝受。
- 規(guī)約操作是將語法棧上的一部分內(nèi)容替換為相應(yīng)的非終結(jié)符的操作坷牛。當(dāng)解析器發(fā)現(xiàn)輸入與語法規(guī)則的右側(cè)匹配時(shí)，它可以執(zhí)行歸約操作很澄，將右側(cè)的符號(hào)替換為對(duì)應(yīng)的非終結(jié)符漓帅。簡單演示見下例 3：
對(duì)于如下語法定義：
%type<int> num
%%
product:
num '*' num;
plus:
product '*' product;
%%
處理輸入串1 * 2 + 3 * 4時(shí)，在處理到符號(hào)2時(shí)痴怨，會(huì)將語法棧中現(xiàn)有的1 * 2規(guī)約（reduce）為product忙干，進(jìn)一步地，會(huì)在處理到4時(shí)將3 * 4規(guī)約為product浪藻，將product + product規(guī)約為plus。
兩種沖突
上述的移位和規(guī)約操作是針對(duì)自底向上范式提出的爱葵，因此使用自頂向下順序編寫語法約束，就會(huì)產(chǎn)生移位/規(guī)約沖突與規(guī)約/規(guī)約沖突：
- 移位/規(guī)約沖突：移位/規(guī)約沖突指當(dāng)解析器處理一個(gè)符號(hào)時(shí)，它既可以進(jìn)行移位（shift）操作月劈，將符號(hào)部分或完全匹配一個(gè)表達(dá)式藤乙，同時(shí)也可以進(jìn)行規(guī)約（reduce）操作坛梁，將當(dāng)前語法棧內(nèi)的內(nèi)容聯(lián)合輸入替換成表達(dá)式划咐。簡單演示見下例 4:
對(duì)于如下語法定義：
%type<int> num
%%
numToken:
numToken '+' numToken | num;
%%
?
當(dāng)處理輸入
1 + 2 + 3時(shí)褐缠，處理到符號(hào)2時(shí)送丰，解析器既可以僅僅將其視作numToken的第二個(gè)子選項(xiàng)，移入（shift）語法棧俐载，也可以將其與語法棧中部分內(nèi)容結(jié)合組成1 + 2登失，匹配成為一個(gè)numToken表達(dá)式揽浙。因此，這個(gè)輸入合法語法樹（指最終結(jié)果只有一個(gè)頂層表達(dá)式）就有 2 個(gè)：image.png
- 規(guī)約/規(guī)約沖突：規(guī)約/規(guī)約沖突是在解析器在遇到一個(gè)輸入符號(hào)時(shí)膛虫，存在多個(gè)可以進(jìn)行歸約操作的情況。這種沖突通常在文法規(guī)則中存在二義性或相似的產(chǎn)生式時(shí)發(fā)生账月。簡單演示見下例 5:
對(duì)于如下語法定義：
%type<int> num
%%
numToken:
numToken '+' numToken | numToken '*' numToken | num;
%%
?
當(dāng)處理輸入
1 + 2 * 3時(shí)局齿，解析器既可以將2其視作numToken的第 1 個(gè)子選項(xiàng)的后半部分規(guī)約為加法抓歼，也可以將其視作numToken第 2 個(gè)與子項(xiàng)的前半副本，規(guī)約為乘法拌禾。因此展哭，這個(gè)輸入合法語法樹（指最終結(jié)果只有一個(gè)頂層表達(dá)式）就有 2 個(gè)：image.png
MySQL 中的語法沖突
我們之前提到匪傍，由于歷史原因和可讀性考慮您市，MySQL 的 yacc 語法文件采用自頂向下的編寫方式役衡，它引入了上述兩種語法沖突茵休。產(chǎn)生沖突的原因是手蝎，自頂向下的解析方法需要層層進(jìn)行斷言與子表達(dá)式的匹配榕莺，而在更頂層的子表達(dá)式無法在實(shí)際上以自底向上執(zhí)行的 Bison 解析器中直接確定匹配選項(xiàng)棵介。
這意味著語法沖突并不總是意味著語句的二義性而導(dǎo)致解析失敹ぱ臁（對(duì)于確實(shí)需要指定關(guān)聯(lián)性和優(yōu)先級(jí)的操作符，MySQL 也對(duì)它們進(jìn)行了%left邮辽、%right、%nonassoc）吨述，事實(shí)上 MySQL 的問題是廣泛存在的 shift/reduce 沖突引起的斷言失敗數(shù)量增加揣云，進(jìn)而使得解析時(shí)間變長亿笤。
正如我們從上圖中看到的栋猖，MySQL 各個(gè)版本中都有相當(dāng)數(shù)量的 shift/reduce 沖突蒲拉，但除了圖中顯示的 MySQL 4.0 中存在的 4 個(gè)會(huì)導(dǎo)致解析二義性的 reduce/reduce 沖突[4]肃拜，shift/reduce 沖突不會(huì)使得解析器最終得到正確的結(jié)果，因此 MySQL8.0 的態(tài)度是：
?
1.We do not accept any reduce/reduce conflicts
2.We should not introduce new shift/reduce conflicts any more.?
四雌团、MySQL 8.0 對(duì)語法約束的改進(jìn)
從上圖中可以看到燃领，MySQL 8.0 版本降低了語法文件中的 shift/reduce 沖突數(shù)量，且隨著版本不斷更新锦援，目前這一沖突數(shù)量已下降到了 63[5]（通過語法文件中的%expect語句顯式聲明）猛蔽。
MySQL 8.0 做出了很多努力來達(dá)到這一成果。其中最關(guān)鍵一點(diǎn)在于對(duì) query 語句整體格式的重構(gòu)灵寺。MySQL 8.0 以前曼库，相同的語法結(jié)構(gòu)（如 create select 和 select 語句都是用的參數(shù)列表，select略板、update 和 delete 語句中都需要使用的 table 列表等）會(huì)直接被不同類型的語句直接引用毁枯，而沒有做額外的約束。
在 MySQL 8.0 中叮称，它同意了所有語句的語法結(jié)構(gòu)种玛，將共用的子結(jié)構(gòu)段進(jìn)行了進(jìn)一步的約束和封裝，這使得自頂向下的斷言可以更快地匹配到對(duì)應(yīng)的語法瓤檐，同時(shí)也能體現(xiàn)于結(jié)構(gòu)上的簡潔性蒂誉。
以下是 MySQL 5.7 到 MySQL 8.0 上層語法結(jié)構(gòu)對(duì)比一覽：
可以看出 MySQL 8.0 使得整體架構(gòu)更加清晰有序。
同時(shí)距帅，8.0 將部分只有一處定義的語法結(jié)構(gòu)展開到上層結(jié)構(gòu)的子選項(xiàng)中右锨，這樣的操作以增加邊緣功能的代碼行數(shù)、降低可讀性為代價(jià)減少了 shift/reduce 沖突碌秸。此外绍移，MySQL 8.0 通過顯示定義兩個(gè)偽 token：%left KEYWORD_USED_AS_IDENT和%left KEYWORD_USED_AS_KEYWORD來顯式地聲明對(duì)以關(guān)鍵字作為標(biāo)識(shí)符的行為，減少了解析過程中二義性因其的斷言失敗讥电。
結(jié)論
從整體上看蹂窖，關(guān)系數(shù)據(jù)庫系統(tǒng)對(duì)于典型的 SQL 語句在語法解析階段的耗時(shí)很短，幾乎可以忽略不計(jì)恩敌，因此 MySQL 維持其自頂向下解析結(jié)構(gòu)以獲得語法文件的可讀性和可擴(kuò)展性是可以理解的瞬测。我們可以看到 MySQL 8.0 并沒有對(duì)將語法解析模塊更改成類似 Posgres 那樣 LALR 的模式以消除語法沖突，而是盡可能地將語法樹表達(dá)的更加簡潔，進(jìn)而使其對(duì)基于 MySQL 語法進(jìn)行擴(kuò)展和兼容的開發(fā)者更加友好月趟。
