設計：小艾
稽核：丁奇
編輯：宇亭
作者：柳湛宇（花名：烏淄）
浙江大學-軟體工程-在讀碩士、StoneDB 核心研發實習生
一、MySQL 的解析器
MySQL 所使用的解析器（即 Lexer 和 Parser 的組合）是嵌入了 C/C++語言的 yacc/lex 組合，在 linux/GNU 體系上，這一組合的實作是 GNU Bison/Flex，即 Flex 負責生成 tokens， Bison 負責文法解析。
對于 Bison，請參閱[1]
Bison 本是一個自底向上（Bottom-Up）的解析器，但是由于曆史原因，MySQL 文法編寫的規則是以自頂向下（Top-Down）的，這将會産生一些問題，我們首先簡要介紹這兩種解析模式。
二、自底向上與自頂向下解析模式
更多詳細講解，請參閱[2]
當我們在談論自底向上和自頂向下兩種解析模式時，局面是我們手上已經有了編寫完成的文法規則和将輸入語句詞法解析完成後的 token 數組，而之後的任務總體上就是建構文法解析樹。
以下 yacc 文法限制和比對序列（「例 1」）用于展示兩種解析模式的不同。
exp1:
'a' 'b' | 'b' 'c';
exp2:
'x' 'y' 'z' | 'a' exp3;
exp3:
'c' 'd' | exp1 'd';
以a b c d作為輸入序列。
自底向上（Bottom-Up）解析模式
自底向上的解析模式類似于進行「拼圖」。對每一個入棧後 token 組成的序列，都盡可能嘗試将其規約（reduce）成一個文法規則中規定的表達式并将新的表達式壓棧。在達到 token 數組末尾時，棧中的表達式應且僅應比對一個頂層表達式，如果因為規約順序不符合實際表達式順序而無法比對到頂層表達式，則應當進行回溯并嘗試新的規約選擇。
對于例 1，自底向上解析模式的解析步驟為：
- a不能被規約（沒有可以比對a的表達式子項）
- a b可以被規約：
- exp1 c d被規約為exp1 exp3
- exp1 exp3無法被規約
- 達到序列末尾，需要回溯
- a b規約為exp1
- exp1 c無法被規約
- exp1 c d可以被規約:
- 是以，exp1 c d無法被規約
- 達到序列末尾，需要回溯
- 是以，a b無法被規約
- a b c可以被規約：
- a b c可以被規約為a exp1
- a exp1 d可以被規約：
- a exp1 d可以被規約為a exp3
- a exp3可以被規約：
- a exp3可以被規約為exp2
- 達到序列末尾，a b c d成功比對表達式exp2
自頂向下（Top-Down）解析模式
自頂向下的表達式類似于「多叉樹的先序周遊」。對于給定的每一個 token 子序列，都嘗試斷言（Assertion）其比對一個表達式，并進一步遞歸地考察：
❝
1.這個序列是否能通過斷言比對該表達式的子選項；
2.斷言比對子選項後，其對應改規則可歸約的子串是否比對子選項中的表達式。
❞
每當斷言失敗時，同樣進行回溯，來嘗試比對不同的表達式或表達式内不同的子選項，直至建構正确的文法解析樹或比對失敗而報錯。
對于例 1，自頂向下解析模式的解析步驟為：
- 假設（此處的原語是斷言，Assertion）a b c d比對exp1的第一個子選項'a' 'b'
- 斷言錯誤，是以排除這一選項；
- 同樣地，顯然可以排除exp1的第二個子選項'b' 'c'和exp2的第一個子選項'x' 'y' 'z',此處省略這些步驟；
- 假設a b c d比對exp2的第二個子選項'a' exp3
- 應有b c d比對exp3
- 假設b c d比對'c' 'd'
- 斷言錯誤，排除這一選項
- 假設b c d比對exp1 'd'
- 應有b c比對exp1
- 假設b c比對'a' 'b'
- 斷言錯誤，排除這一選項
- 假設b c比對'b' 'c'
- 斷言正确且無子表達式，比對成功，a b c d比對exp2
二者的對比與 MySQL 面臨的問題
可以看到，自底向上解析模式更符合計算機程式的風格，其将規約操作提前，在後半部分執行比對和回溯動作。但其缺點在于，每一次比對和回溯的觸發點都僅僅在達到 token 數組末尾時進行，是以如果沒有優先級限制，每次有效回溯的代價都較大。
自頂向下的解析模式更符合人類閱讀和編寫文法檔案的習慣，其将斷言和回溯動作提前，将實際的比對動作置于解析的後半段。這樣的模式缺點在于，它需要回溯的次數更多，同時文法愈發複雜，如果沒有合适的斷言順序（實際上對于不同的 SQL 語句，最優的斷言順序也不盡相同），就會有更多備援的比較分支和更深的有效回溯長度。
由于 MySQL 因曆史原因選擇了易讀的自頂向下的解析模式，其在文法解析時，會産生二義性帶來的兩種沖突（conflict）：移位/規約（shift/reduce）沖突和規約/規約（reduce/reduce）沖突，而使用自底向上解析模式的 posgres[3]則不會産生這兩種沖突。
三、移位/規約沖突與規約/規約沖突
兩種操作
首先簡要介紹自底向上分析方法的移位（shift）和規約（reduce）操作。按自底向上的解析模式，解析器對輸入符号串從左到右掃描，讀取輸入并與文法規則比較，其中：
- 移位操作是将符号從輸入流轉入分析棧中的操作。如果目前輸入與文法規則比對，解析器就将目前輸入移入（shift）文法棧中，并繼續嘗試處理下一個符号。簡單示範見下例 2:
對于如下文法定義：
simpleStrSeq:
'a' 'b' 'c' | 'e' 'f' 'g';
處理輸入串a b c時，處理前兩個 token 時都會将其直接放入文法棧，因為它們比對simpleStrSeq表達式。
- 規約操作是将文法棧上的一部分内容替換為相應的非終結符的操作。當解析器發現輸入與文法規則的右側比對時，它可以執行歸約操作，将右側的符号替換為對應的非終結符。簡單示範見下例 3：
對于如下文法定義：
%type<int> num
%%
product:
num '*' num;
plus:
product '*' product;
%%
處理輸入串1 * 2 + 3 * 4時，在處理到符号2時，會将文法棧中現有的1 * 2規約（reduce）為product，進一步地，會在處理到4時将3 * 4規約為product，将product + product規約為plus。
兩種沖突
上述的移位和規約操作是針對自底向上範式提出的，是以使用自頂向下順序編寫文法限制，就會産生移位/規約沖突與規約/規約沖突：
- 移位/規約沖突：移位/規約沖突指當解析器處理一個符号時，它既可以進行移位（shift）操作，将符号部分或完全比對一個表達式，同時也可以進行規約（reduce）操作，将目前文法棧内的内容聯合輸入替換成表達式。簡單示範見下例 4:
對于如下文法定義：
%type<int> num
%%
numToken:
numToken '+' numToken | num;
%%
❝
當處理輸入1 + 2 + 3時，處理到符号2時，解析器既可以僅僅将其視作numToken的第二個子選項，移入（shift）文法棧，也可以将其與文法棧中部分内容結合組成1 + 2，比對成為一個numToken表達式。是以，這個輸入合法文法樹（指最終結果隻有一個頂層表達式）就有 2 個：
❞
- 規約/規約沖突：規約/規約沖突是在解析器在遇到一個輸入符号時，存在多個可以進行歸約操作的情況。這種沖突通常在文法規則中存在二義性或相似的産生式時發生。簡單示範見下例 5:
對于如下文法定義：
%type<int> num
%%
numToken:
numToken '+' numToken | numToken '*' numToken | num;
%%
❝
當處理輸入1 + 2 * 3時，解析器既可以将2其視作numToken的第 1 個子選項的後半部分規約為加法，也可以将其視作numToken第 2 個與子項的前半副本，規約為乘法。是以，這個輸入合法文法樹（指最終結果隻有一個頂層表達式）就有 2 個：
❞
MySQL 中的文法沖突
我們之前提到，由于曆史原因和可讀性考慮，MySQL 的 yacc 文法檔案采用自頂向下的編寫方式，它引入了上述兩種文法沖突。産生沖突的原因是，自頂向下的解析方法需要層層進行斷言與子表達式的比對，而在更頂層的子表達式無法在實際上以自底向上執行的 Bison 解析器中直接确定比對選項。
這意味着文法沖突并不總是意味着語句的二義性而導緻解析失敗（對于确實需要指定關聯性和優先級的操作符，MySQL 也對它們進行了%left、%right、%nonassoc），事實上 MySQL 的問題是廣泛存在的 shift/reduce 沖突引起的斷言失敗數量增加，進而使得解析時間變長。
正如我們從上圖中看到的，MySQL 各個版本中都有相當數量的 shift/reduce 沖突，但除了圖中顯示的 MySQL 4.0 中存在的 4 個會導緻解析二義性的 reduce/reduce 沖突[4]，shift/reduce 沖突不會使得解析器最終得到正确的結果，是以 MySQL8.0 的态度是：
❝
1.We do not accept any reduce/reduce conflicts
2.We should not introduce new shift/reduce conflicts any more.
❞
四、MySQL 8.0 對文法限制的改進
從上圖中可以看到，MySQL 8.0 版本降低了文法檔案中的 shift/reduce 沖突數量，且随着版本不斷更新，目前這一沖突數量已下降到了 63[5]（通過文法檔案中的%expect語句顯式聲明）。
MySQL 8.0 做出了很多努力來達到這一成果。其中最關鍵一點在于對 query 語句整體格式的重構。MySQL 8.0 以前，相同的文法結構（如 create select 和 select 語句都是用的參數清單，select、update 和 delete 語句中都需要使用的 table 清單等）會直接被不同類型的語句直接引用，而沒有做額外的限制。
在 MySQL 8.0 中，它同意了所有語句的文法結構，将共用的子結構段進行了進一步的限制和封裝，這使得自頂向下的斷言可以更快地比對到對應的文法，同時也能展現于結構上的簡潔性。
以下是 MySQL 5.7 到 MySQL 8.0 上層文法結構對比一覽：
可以看出 MySQL 8.0 使得整體架構更加清晰有序。
同時，8.0 将部分隻有一處定義的文法結構展開到上層結構的子選項中，這樣的操作以增加邊緣功能的代碼行數、降低可讀性為代價減少了 shift/reduce 沖突。此外，MySQL 8.0 通過顯示定義兩個僞 token：%left KEYWORD_USED_AS_IDENT和%left KEYWORD_USED_AS_KEYWORD來顯式地聲明對以關鍵字作為辨別符的行為，減少了解析過程中二義性因其的斷言失敗。
結論
從整體上看，關系資料庫系統對于典型的 SQL 語句在文法解析階段的耗時很短，幾乎可以忽略不計，是以 MySQL 維持其自頂向下解析結構以獲得文法檔案的可讀性和可擴充性是可以了解的。我們可以看到 MySQL 8.0 并沒有對将文法解析子產品更改成類似 Posgres 那樣 LALR 的模式以消除文法沖突，而是盡可能地将文法樹表達的更加簡潔，進而使其對基于 MySQL 文法進行擴充和相容的開發者更加友好。