摘要：一般用大寫(xiě)的表示文法的開(kāi)頭，稱為開(kāi)始符號(hào)。更多討論討論地址是精讀手寫(xiě)編譯器文法介紹如果你想?yún)⑴c討論，請(qǐng)點(diǎn)擊這里，每周都有新的主題，周末或周一發(fā)布。

文法用來(lái)描述語(yǔ)言的語(yǔ)法規(guī)則，所以不僅可以用在編程語(yǔ)言上，也可用在漢語(yǔ)、英語(yǔ)上。

我們將一塊語(yǔ)法規(guī)則稱為 產(chǎn)生式，使用 “Left → Right” 表示任意產(chǎn)生式，用 “Left => Right” 表示產(chǎn)生式的推導(dǎo)過(guò)程，比如對(duì)于產(chǎn)生式：

E → i
E → E + E

我們進(jìn)行推導(dǎo)時(shí)，可以這樣表示：E => E + E => i + E => i + i + E => i + i + i

也有使用 Left : Right 表示產(chǎn)生式的例子，比如 ANTLR。BNF 范式通過(guò) Left ::= Right 表示產(chǎn)生式。

舉個(gè)例子，比如 SELECT * FROM table 可以被表達(dá)為：

S → SELECT * FROM table

當(dāng)然這是最固定的語(yǔ)法，真實(shí)場(chǎng)景中，* 可能被替換為其他單詞，而 table 不但可能有其他名字，還可能是個(gè)子表達(dá)式。

一般用大寫(xiě)的 S 表示文法的開(kāi)頭，稱為開(kāi)始符號(hào)。

下面為了方便書(shū)寫(xiě)，使用 BNF 范式表示文法。

終結(jié)符就是語(yǔ)句的終結(jié)，讀到它表示產(chǎn)生式分析結(jié)束，相反，非終結(jié)符就是一個(gè)新產(chǎn)生式的開(kāi)始，比如：

 ::= SELECT  FROM 

 ::=  [ ,  ]

 ::=  [ ,  ]

所有 ::= 號(hào)左邊的都是非終結(jié)符，所以 selectList 是非終結(jié)符，解析 selectStatement 時(shí)遇到了 selectList 將會(huì)進(jìn)入 selectList 產(chǎn)生式，而解析到普通 SELECT 單詞就不會(huì)繼續(xù)解析。

對(duì)于有二義性的文法，可以通過(guò) 上下文相關(guān)文法 方式描述，也就是在產(chǎn)生式左側(cè)補(bǔ)全條件，解決二義性：

aBc -> a1c | a2c
dBe -> d3e

一般產(chǎn)生式左側(cè)都是非終結(jié)符，大寫(xiě)字母是非終結(jié)符，小寫(xiě)字母是終結(jié)符。

上面表示，非終結(jié)符 B 在 ac 之間時(shí)，可以解析為 1 或 2，而在 de 之間時(shí)，解析為 3。但我們可以增加一個(gè)非終結(jié)符讓產(chǎn)生式可讀性更好：

B -> 1 | 2
C -> 3

這樣就將上下文相關(guān)文法轉(zhuǎn)換為了上下文無(wú)關(guān)文法。

根據(jù)是否依賴上下文，文法分為 上下文相關(guān)文法 與 上下文無(wú)關(guān)文法，一般來(lái)說(shuō) 上下文相關(guān)文法 都可以轉(zhuǎn)換為一堆 上下文無(wú)關(guān)文法 來(lái)處理，而用程序處理 上下文無(wú)關(guān)文法 相對(duì)輕松。

SQL 的文法就是上下文相關(guān)文法，在正式介紹 SQL 文法之前，舉一個(gè)簡(jiǎn)單的例子，比如我們描述等號(hào)（=）的文法：

SELECT
  CASE
    WHEN bee = "red" THEN "ANGRY"
    ELSE "NEUTRAL"
  END AS BeeState
FROM bees;

SELECT * from bees WHERE bee = "red";

上面兩個(gè) SQL 中，等號(hào)前后的關(guān)鍵字取決于當(dāng)前是在 CASE WHEN 語(yǔ)句里，還是在 WHERE 語(yǔ)句里，所以我們認(rèn)為等號(hào)所在位置的文法是上下文相關(guān)的。

但是當(dāng)我們將文法粒度變細(xì)，將 CASE WHEN 與 WHERE 區(qū)塊分別交由兩塊文法解決，將等號(hào)這個(gè)通用的表達(dá)式抽離出來(lái)，就可以不關(guān)心上下文了，這種方式稱為 上下文無(wú)關(guān)文法。

附上一個(gè) mysql 上下文無(wú)關(guān)文法集合。

上面提到的推導(dǎo)符號(hào) => 在實(shí)際運(yùn)行過(guò)程中，顯然有兩種方向左和右：

E + E => ?

從最左邊的 E 開(kāi)始分析，稱為左推導(dǎo)，對(duì)語(yǔ)法解析來(lái)說(shuō)是自頂向下的方式，常用方法是遞歸下降。

從最右邊的 E 開(kāi)始分析，稱為右推導(dǎo)，對(duì)語(yǔ)法解析來(lái)說(shuō)是自底向上的方式，常用方法是移進(jìn)、規(guī)約。

右推導(dǎo)過(guò)程比左推導(dǎo)過(guò)程復(fù)雜，所以如果考慮手寫(xiě)，最好使用左推導(dǎo)的方式。

比如 select 的 selectList 產(chǎn)生式，它可以表示為：

 ::=  , 
               | 

由于它可以展開(kāi)：SelectList => SelectList , a => SelectList , b, a => c, b, a。

但程序執(zhí)行時(shí)，讀到這里會(huì)進(jìn)入死循環(huán)，因?yàn)?SelectList 可以被無(wú)限展開(kāi)，這就是左遞歸問(wèn)題。

消除左遞歸一般通過(guò)轉(zhuǎn)化為右遞歸的方式，因?yàn)樽筮f歸完全不消耗 Token，而右遞歸可以通過(guò)消耗 Token 的方式跳出死循環(huán)。

Token 見(jiàn)上一期精讀 精讀《手寫(xiě) SQL 編譯器 - 詞法分析》

 ::=  

 ::= , 
      | null

這其實(shí)是一個(gè)通用處理，可以抽象出來(lái)：

E → E + F
E → F

E → FG
G → + FG
G → null

不過(guò)我們也不難發(fā)現(xiàn)，通過(guò)通用方式消除左遞歸后的文法更難以閱讀，這是因?yàn)橛盟姥h(huán)的方式解釋問(wèn)題更容易讓人理解，但會(huì)導(dǎo)致機(jī)器崩潰。

筆者建議此處不要生硬的套公式，在套了公式后，再對(duì)產(chǎn)生式做一些修飾，讓其更具有語(yǔ)義：

 ::= 
               | , 

即便是上下文無(wú)關(guān)的文法，通過(guò)遞歸下降方式，許多時(shí)候也必須從左向右超前查看 K 個(gè)字符才能確定使用哪個(gè)產(chǎn)生式，這種文法稱為 LL(k)。

但如果每次超前查看的內(nèi)容都有許多字符相同，會(huì)導(dǎo)致第二次開(kāi)始的超前查看重復(fù)解析字符串，影響性能。最理想的情況是，每次超前查看都不會(huì)對(duì)已確定的字符重復(fù)查看，解決方法是提取左公因式。

設(shè)想如下的 sql 文法：

 ::=  as 
          |  as
          |  
          | 

其實(shí) Text 本身也是比較復(fù)雜的產(chǎn)生式，最壞的情況需要對(duì) Text 連續(xù)匹配六遍。我們將 Text 公因式提取出來(lái)就可以僅匹配一遍，因?yàn)闊o(wú)論是何種 Field 產(chǎn)生式，都必定先遇到 Text：

 ::=  

 ::= 
      | 

 ::= as 

 ::=  
      | 

和消除左遞歸一樣，提取左公因式也會(huì)降低文法的可讀性，需要進(jìn)行人為修復(fù)。不過(guò)提取左公因式的修復(fù)沒(méi)辦法在文法中處理，在后面的 “函數(shù)式” 處理環(huán)節(jié)是有辦法處理的，敬請(qǐng)期待。

對(duì) SQL 的文法來(lái)說(shuō)不存在優(yōu)先級(jí)的概念，所以從某種程度來(lái)說(shuō)，SQL 的語(yǔ)法復(fù)雜度還不如基本的加減乘除。

在實(shí)現(xiàn)語(yǔ)法解析前，需要使用文法描述 SQL 的語(yǔ)法，文法描述就是語(yǔ)法分析的主干業(yè)務(wù)代碼。

下一篇將介紹語(yǔ)法分析相關(guān)知識(shí)，幫助你一步步打造自己的 SQL 編譯器。

討論地址是：精讀《手寫(xiě) SQL 編譯器 - 文法介紹》 · Issue #94 · dt-fe/weekly

如果你想?yún)⑴c討論，請(qǐng)點(diǎn)擊這里，每周都有新的主題，周末或周一發(fā)布。