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

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

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

E → i
E → E + E

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

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

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

S → SELECT * FROM table

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

一般用大寫的 S 表示文法的開頭，稱為開始符號。

下面為了方便書寫，使用 BNF 范式表示文法。

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

 ::= SELECT  FROM 

 ::=  [ ,  ]

 ::=  [ ,  ]

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

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

aBc -> a1c | a2c
dBe -> d3e

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

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

B -> 1 | 2
C -> 3

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

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

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

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

SELECT * from bees WHERE bee = "red";

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

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

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

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

E + E => ?

從最左邊的 E 開始分析，稱為左推導(dǎo)，對語法解析來說是自頂向下的方式，常用方法是遞歸下降。

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

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

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

 ::=  , 
               | 

由于它可以展開：SelectList => SelectList , a => SelectList , b, a => c, b, a。

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

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

Token 見上一期精讀 精讀《手寫 SQL 編譯器 - 詞法分析》

 ::=  

 ::= , 
      | null

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

E → E + F
E → F

E → FG
G → + FG
G → null

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

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

 ::= 
               | , 

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

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

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

 ::=  as 
          |  as
          |  
          | 

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

 ::=  

 ::= 
      | 

 ::= as 

 ::=  
      | 

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

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

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

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

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

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