# ABNF [BNF][1] 是巴科斯范式, 英語：Backus Normal Form 的縮寫, 也被稱作 巴科斯-諾爾范式, 英語: Backus–Naur Form. Backus 和 Naur 是兩位作者的名字. 必須承認這是一項偉大的發明, BNF 開創了描述計算機語言語法的符號集形式. 如果您還不了解 BNF, 需要先 [Google][2] 一下. 隨時間推移逐漸衍生出一些擴展版本, 這里直接列舉幾條 ABNF [RFC5234][3] 定義的文法規則. **PS: 后續代碼實現部分, 早期的代碼思路不夠精簡, 在現實中很難應用. 后期又做了純規則的實現, 請讀者選擇性閱讀, 以免浪費您寶貴的時間** ```ABNF ; 注釋以分號開始 name = elements ; name 規則名, elements 是一個或多個規則名, 本例只是示意 command = "command string" ; 字符串在一對雙引號中, 大小寫不敏感 rulename = %d97 %d98 %d99 ; 值表示 "abc", 大小寫敏感, 中間的空格是 ABNF 規則定界符 foo = %x61 ; a, 上面的 "%d" 開頭表示用十進制, "%x" 表示用十六進制 bar = %x62 ; b, "%x62" 等同 "%d98" CRLF = %d13.10 ; 值點連接, 等同 "%d13 %d10" 或者 "%x0D %x0A" mumble = foo bar foo ; Concatenation 級聯, 上面定義了 foo, bar, 等同區分大小寫的 "aba" ruleset = alt1 / alt2 ; Alternative 替代, 匹配一個就行, 以 "/" 分界 ruleset =/ alt3 ; 增量替代以 "=/" 指示 ruleset = alt1 / alt2 / alt3 ; 等同于上面兩行 ruleset = alt1 / ; 你也可以分成多行寫 alt2 / alt3 DIGIT = %x30-39 ; Value range 值范圍, 用 "-" 連接, 等同下面 DIGIT = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9" charline = %x0D.0A %x20-7E %x0D.0A ; 值點連接和值范圍組合的例子 seqGroup = elem (foo / bar) blat ; Grouping 分組, 一對圓括號包裹, 與下面的含義完全不同 seqGroup = elem foo / bar blat ; 這是兩個替代, 上面是三個級聯 integer = 1*DIGIT ; Repetition 重復, 1 至 無窮 個 DIGIT some = *1DIGIT ; 0 至 1 個 DIGIT someAs = 0*1DIGIT ; 等同上一行 year = 1*4DIGIT ; 1 至 4 個 DIGIT foo = *bar ; 0 至 無窮 個 bar baz = 3foo ; 3 次重復 foo, 等同 3*3foo number = 1*DIGIT ["." 1*DIGIT] ; Optional 可選規則, 用中括號包裹, 等同下面兩種寫法 number = 1*DIGIT *1("." 1*DIGIT) number = 1*DIGIT 0*1("." 1*DIGIT) foobar = <foo bar is foo bar> baz ; prose-val 用尖括號括起來, 值就可以包含空格和VCHAR ; 范圍是 *(%x20-3D / %x3F-7E) ``` 上面的描述用的也是 ABNF, 事實上這些文字就源自 RFC5234 規范. 級聯規則就是一個順序匹配的序列, 好比 Seq 順序規則或者叫 And 規則. 替代好比 Or 規則或者叫 Any 規則. # 四則運算表達式 現在我們嘗試一下四則運算表達式的 ABNF 寫法. 我們從人腦運算方式逐步推演出正確的寫法. 周知四則運算會包含數字和運算符還有括號. ```ABNF ; 錯誤寫法一 ; Expr 表示要解決的問題, 四則運算規則 Expr = Num / ; Num 表示數字, 僅僅一個數字也可以構成Expr Num Op Expr / ; Op 運算符 "(" Expr ")" / ; 括號會改變 Expr 運算優先級 Expr Op Expr ; 最復雜的情況 Op = "+" / "-" / "*" / "/" ; 運算符的定義 Num = 1*(0-9) ; 最簡單的正整數定義 ``` 上面的寫法模擬人腦做四則運算的習慣, 很明顯絕大多數解析器都無法使用這個規則. 因為出現了[左遞歸][4]. "最復雜的情況" 這一行中 Expr 出現在規則的最左邊, 這將導致解析器遞歸, 造成死循環. 雖然可以把解析器設計的復雜一些, 解決左遞歸, 但這會使解析器很復雜, 并造成效率低下, 時間復雜度陡增, 所以通常要求寫規則時就消除左遞歸. 繼續分析推演. 消除左遞歸一般通過因式分解(factor)或者引入新的規則條款(terms)解決. 通過 factor 或者 term 解除左遞歸發生的可能性, 好比多繞幾個圈子, 多給解析器幾條路, 讓解析器繞過死循環的路徑. 下面加上了 Repetition 重復規則. 我們先按照人腦思維, 乘法除法優先的順序來寫. ```ABNF ; 錯誤寫法二 Expr = Term *Mul / ; Mul 是乘法, *Mul 表示可能有或沒有, Term 就是要繞的圈子了. Term *Quo ; 除法和乘法一樣, Term 這個圈子其實表示的還是 Expr. Term = Factor *Add / ; 一個圈子明顯不行, 再繞個圈子 Factor, Factor *Sub ; 這兩行描述加減法, 邏輯都沒錯吧, 都是可能有, 也可能沒有 Factor = Num / ; 繞再多圈子總是要回來的, 數字總要有吧 "(" Expr ")" ; 括號的運算總要有吧 Add = "+" Term ; 一旦出現運算符, 后面一定會有后續的表達式吧 Sub = "-" Term Mul = "*" Factor Quo = "/" Factor Num = 1*(0-9) ``` 看上去會發生左遞歸么? 不會, 怎么繞你都不會死循環, 因為 Factor 的第一條規則 Num , 給繞圈圈一個結束的機會. 這個叫終結符. 但是這個寫法是錯誤的. 你可以在腦子里模擬下 `1+2-3`, 到 `-` 號的時候就解析不下去了. `1+2` 被 ```ABNF Term = Factor *Add ``` 匹配了, 但是后面還有`-`號, 被匹配的是加法規則 ``` Add = "+" Term ; 最后一個又回到 Term ``` 但是 Term 無法匹配減號, Term 推演規則中沒有以減號開頭的. 你說重頭來不就行了? 不行, 解析器執行的規則是找到一條路可以一直走下去, 如果走不動了, 就表示這條規則匹配完成了, 或者失敗了. 減號來的時候, 如果假設解析器認為 `1+2` 已經走完, 減號來的時候還是要從 Expr 開始, 不能直接從 Sub 開始, 開始只能有一個, 從 Expr 開始推導不出首次就匹配 "-" 號的. 所以 `1+2-3` 沒有走完, 解析進行不下去了. 那上面的問題出在哪里呢? 問題在: **終結符在推導循環中不能首次匹配** 問題的邏輯是: **可以窮舉開始和結尾, 不能窮舉中間過程.** 解決方法是循環或者遞歸: **在循環和遞歸中已經沒有明確的開始,頭尾相接就沒有頭尾了,沒有頭尾也意味能一直繞下去** 綜合這三句話, 我們解決問題的方法也就出來了: 1. 引入Term, Factor 消除左遞歸 2. 要給終結符在循環中首次匹配的機會或者說不阻斷循環的進行 終結符就是推導循環到了最后, 不包含推導循環中的其他規則名. 再來符號就是新的, 要重頭開始. 有終結但無法繼續重頭開始, 圈子繞不下去了. 繼續推演, 我們先確定終結符. 我們用個小技巧, 按優先級合并運算符. ```ABNF ; 正確寫法 Expr = Term *Sum ; 繼續繞圈子, *Sum 有或者沒有, 先寫求和是有原因的 Term = Factor *Mul ; 再寫乘積, *Sum 不匹配, 就嘗試乘積 Sum = SumOp Term ; 求和的運算, 有運算符必定要有后續表達式 Mul = MulOp Factor ; 乘積的運算, Factor = Num / ; 引向終結 "(" Expr ")" ; 括號永遠都在 Num = 1*(0-9) ; 數字, 這可以是獨立的終結符 SumOp = "+" / "-" ; 加或者減, 可以叫做求和, 小技巧 MulOp = "*" / "/" ; 乘或者除, 可以叫做乘積 ``` 把這兩種寫法左右排列, 看的更清楚 ```ABNF ; 錯誤寫法 ; 正確寫法 Expr = Term *Mul / ; Expr = Term *Sum ; 蛇頭 Term *Quo ; Term = Factor *Mul ; 蛇頭 Term = Factor *Add / ; Sum = SumOp Term ; 咬蛇尾 Factor *Sub ; Mul = MulOp Factor ; 咬蛇尾 Factor = Num / ; Factor = Num / "(" Expr ")" ; "(" Expr ")" Add = "+" Term ; SumOp = "+" / Sub = "-" Term ; "-" Mul = "*" Factor ; MulOp = "*" / Quo = "/" Factor ; "/" Num = 1*(0-9) ; Num = 1*(0-9) ``` 你應該發現了, 主要區別是: 運算符和后續的 Expr 的結合處理方式不同. 左側的規則是: (數字,運算符,數字) 然后還想找 (數字,運算符,數字). 右側的規則是: (數字,運算符) 然后繼續 (數字,運算符), 最后找到終結. 左側規劃了一條既定的有終結路線, 走不了幾步就終結了. 蛇頭沒咬到蛇尾, 咬到七寸了. 右側規劃了一條蛇頭咬蛇尾的循環路線, 循環中所有的規則名都有機會匹配. # 解析器 **這是早期思路所寫的代碼, 事實上我自己用起來也很不舒服, 也一直沒有放出來, 就當做失敗的例子吧** ABNF 具有很強的表達能力, 這里以 ABNF 為基礎分析要分離出的規則元素. 終結符和非終結符, 可以這樣描述 1. atom 終結符, 就是個對輸入字符進行判斷的函數 2. term 非終結符, 可能有多個或多層 term/atom 組合, 也可用 group 這個詞 3. factor 抽象接口, term 和 atom 的共性接口, 代碼實現需要抽象接口 用 group 替換 term 在語義上也是成立的, 一個獨立的 term 也可以看作只有一項規則元素的 group. 元素關系可以分 1. Concatenation 級聯匹配 2. Alternation 替代匹配 atom 可以看作只有一項的級聯, group 需要選擇兩者之一. 那么 group 需要可以增加規則元素的接口 1. Add(factor) 在做解析的時候常采用循環的方法, 某個循環結束后會產生兩個狀態 1. ok 解析是否成功 2. end 解析是否結束 任何時候遇到 end, 無論處于那一級循環中, 都要終止解析. 如果不是 end, 那么依據元素關系和解析是否成功進行判斷, 決定嘗試匹配下一個規則元素或者返回 !ok, !end. 其他 1. 給 term/group, atom/factor 命名或設定 id 2. 設置 term/group, atom/factor 的重復屬性 repeat. 綜合上述分析大致的接口設計如下 ```go type Factor interface { /** 每個 Factor 都有一個唯一規則 ID Grammar 的 id 固定為 0. Atom, Group 自動生成或者設定. 自動生成的 ID 為負數. */ Id() int /** 返回 Factor 的風格. 常量 KGrammar / KGroup / KFactor. 這里簡單用 int 類型區分 */ Kind() int /** Mode 返回 Factor 所使用的匹配模式 Atom 總是返回常量 MConcatenation. */ Mode() int /** 匹配腳本 參數: Scanner 是個 rune 掃描器, Record 用于記錄解析過程. 返回值: ok 是否匹配成 end 是否終止匹配, 事實上由 Record 決定是否終止匹配 */ Process(script Scanner, rec Record) (ok, end bool) } // 語法接口也基于 Factor type Grammar interface { Factor /** 生成一個 Term 過渡對象. 初始重復 1 次, 1*1. 初始匹配模式為 MConcatenation. 參數 id 如果 <= 0 或者發生重復, 那么自動生成負數 id. */ Term(id int) Term // 為 Grammar.Process 設置最初規則. Start(rule ...Factor) Grammar // 設置為 Concatenation 匹配模式 Concatenation() Grammar // 設置為 Alternation 匹配模式 Alternation() Grammar } /** term 是個中間件, 最終要轉化為 Group/Factor */ type Term interface { Factor // 為 Term 命名. 不檢查名稱唯一性. Named(string) Term /** 設置 Repeat, 參數 a, b 對應 ABNF 的 repeat 定義 a*b. 如果 b < a, 把 b 作為 0 處理. */ Repeat(a, b uint) Term // 轉為 Group Group() Group // 由 Atom 轉為 Factor Atom(atom Atom) Factor } /** Group 具有 Add 方法 */ type Group interface { Factor // 設置為 Concatenation 匹配模式 Concatenation() Group // 設置為 Alternation 匹配模式 Alternation() Group /** 添加一組規則. 如果沒有通過檢查返回 nil */ Add(rule ...Factor) Group } ``` 從中可以看出, Term 是個過渡接口, 設計這個的原因是: ABNF 文法中的規則定義和程序中的類型定相似, 次序無所謂, 只要有定義. 很明顯實現解析器的時候, 這些元素是以變量的形式存在的, 我們需要先生成變量, 然后在進行關系組合. 筆者實現了一個 ```go // 丑陋的 Term 表現四則運算 // g 是個 Grammar 對象, 起個名字叫 Arithmetic g := New("Arithmetic") // 先生成規則元素, Atom 的參數 id 是預定義的常量 expr := g.Term().Named("Expr").Group() end := g.Term().Named("EOF").Atom(IdEof, ItsEOF) num := g.Term().Named("Num").Atom(NUM, ItsNum) // GenLiteral 是個輔助函數函數, 生成字符串匹配 Atom C := g.Term().Named("(").Atom(LPAREN, GenLiteral(`(`, nil)) D := g.Term().Named(")").Atom(RPAREN, GenLiteral(`)`, nil)) term := g.Term().Named("Term").Group() sum := g.Term().Zero().Named("Sum").Group() factor := g.Term().Named("Factor").Group().Alternation() mul := g.Term().Zero().Named("Mul").Group() sumOp := g.Term().Named("SumOp").Group().Add( g.Term().Named("+").Atom(ADD, GenLiteral(`+`, nil)), g.Term().Named("-").Atom(SUB, GenLiteral(`-`, nil)), ).Alternation() mulOp := g.Term().Named("MulOp").Group().Add( g.Term().Named("*").Atom(MUL, GenLiteral(`*`, nil)), g.Term().Named("/").Atom(QUO, GenLiteral(`/`, nil)), ).Alternation() nested := g.Term().Named("Nested").Group().Add(C, expr, D) // 組合規則元素 g.Start(end, expr) expr.Add(term, sum) term.Add(factor, mul) sum.Add(sumOp, term) mul.Add(mulOp, factor) factor.Add(num, nested) // 這里省略了 script 和 rec 的生成 g.Process(script, rec) ``` Term 的出現, 雖然邏輯上完整了, 代碼寫出來看上去很丑陋. 看來只有通過輔助函數簡化代碼了. # 手工至上 連續兩章學習解析器, 事實上筆者自己嘗試實現了一個基于 ABNF 的解析器雛形. 然而由于采用了遞歸的匹配方式, 最終的測試結果讓人非常沮喪, 和 go 官方提供的 json 包對比解析速度慢幾十倍. go 官方的 json 包是純手工代碼實現的. 采用大家常常聽到的先詞法分析后語法分析的方法, 事實擺在眼前, 這種手工的方法真的是最快的. 同樣的方法我們在 go 的標準庫中可以找到多處, 各種教課書中講的解析相關知識根本就沒用上, 效率有目共睹. 直接看相關源代碼就能了解細節. **手工代碼構造的先詞法分析后語法分析的解析器是最快的** # 再接再厲 [Zxx][] 是很偶然的一次 Q 群聊天玩笑的產物, 到目前為止這依然是個設想(玩笑). 好在新的 [zxx abnf][] 產生了. 這次嘗試了另外的思路, 到目前為止感覺還不錯. 如前文所述, 可以從 ABNF 規范中抽離出獨立的匹配規則, 下文用 R 代表一個規則. 1. Zero 規則對應 R* 匹配零次或多次 2. Option 規則對應 R{0,1} 匹配零次或一次 3. More 規則對應 R{1,} 匹配一次或多次 4. Any 規則對應多個規則匹配任意一個 5. Seq 規則對應多個規則被順序匹配 6. Term 所有規則是有 Term 組成的. 這些只是基本的匹配規則邏輯. 毫無疑問, 文法解析是從一個字節一個字節進行的, 前文的實現也是這么思考的. 現在換個角度考慮問題: 字符串也好, 叫做 Token 也罷, 真正要做的是判斷一個 Token 是否滿某個條件. 我們知道解析的最小單位是 Token, 我們個 Token 加一個成員方法 ```go // Has 返回 token 等于 tok 或者包括 tok func (token Token) Has(tok Token) bool // 這里截取部分 Token 定義 const ( EOF Token = iota Type // 分類標記 // 預定義類型 BYTE STRING UINT INT ) ``` 那么 Type.Has(INT) 的值就為 true. 即 Token 的 Has 方法為前述的 ABNF 規則提供了最底層的判斷. Token 的類型不再重要, Has 保證了一切. 現實中可從掃描器得到 Token. 而 [zxx abnf][] 只關心相關的規則定義. 列舉下相關定義, 有些注釋省略, 完整代碼在 [zxx abnf][]: ```go // Flag 表示規則匹配 Token 后的狀態 type Flag int const ( Matched Flag = 1 << iota // 匹配成功, 消耗掉一個 Token Standing // 規則成立, 可以繼續匹配 Token Finished // 規則完整, 不再接受匹配 Token // 下列標記由算法維護, Match 返回值不應該包含這些標記. Handing // 正在進行處理中(Match), 可用來檢查發生遞歸 Cloning // 正在進行克隆 Custom // 通用標記位, 包括更高的位都由 Match 自定義用途, ) type Rule interface { // Match 返回匹配 tok 的狀態標記. 實現必須遵守以下約定: // // 返回值為下列之一: // // 0 // Matched // Matched|Standing // Matched|Finished // Finished // // 自動重置: // // 規則狀態為 0, Finished, Matched|Finished 時自動重置, 可接受新的匹配. // // EOF 重置: 當最終狀態為 // // Matched 最終狀態是不確定完整匹配. // Matched|Standing 最終狀態是完整匹配. // // 時使用 Match(EOF) 重置規則并返回 Finished, 其它狀態不應該使用 EOF 來重置. // // 末尾完整測試: // // 類似 Seq(Term(XX),Option(YY),Option(ZZ)) 規則, 單個 XX 也是合法的, // 但是由于 Option 的原因, 匹配單個 XX 的狀態為 Matched, // 因此再匹配一個不可能出現的 Token, 可以測試規則是否完整. // Match(tok Token) Flag // Bind 應只在遞歸嵌套規則變量時使用, 先聲明規則變量后綁定規則. // 其他情況都不應該使用 Bind. Bind(Rule) // Clone 返回克隆規則, 這是深度克隆, 但不含遞歸. // 遞歸規則在 Match 中通過判斷 Handing 標記及時建立的. Clone() Rule // IsOption 返回該規則是否為可選規則. // 事實上除了 Option 是明確的可選規則外, 其它組合可能產生事實上的可選規則. IsOption() bool } // Term 用來包裝 Token // Term 產生任一 Token 匹配規則. Match 方法返回值為: // // 0 // Matched | Finished // Finished 當 EOF 重置或者 tok == nil // func Term(tok ...Token) Rule func Option(rule Rule) Rule func Once(rule Rule) Rule // More 產生重復匹配規則. // rule 必須初次匹配成功, 然后當 rule 匹配結果為 0, Finished 時嘗試 sep 匹配, // 如果 sep 匹配成功則繼續匹配 rule. // func More(rule, sep Rule) Rule // Any 產生任一匹配規則. // 不要用 Any(rule, Term()) 替代 Option, 那會讓 IsOption() 不可靠. func Any(rule ...Rule) Rule // Seq 產生順序匹配規則 func Seq(rule ...Rule) Rule ``` 你可能注意到其中沒有 Zero 規則, 因為不需要它, Flag 的 Finished 隱含的兼容了 Zero 規則. 只有 Flag(0) 才表示失敗, Finished 雖然表示 Token 未被匹配, 但是規則是成立的, Token 由后續規則繼續匹配好了. **先寫這么多, 就 5 個規則, 寫多了反而添亂** [1]: http://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E5%B7%B4%E7%A7%91%E6%96%AF%E8%8C%83%E5%BC%8F [2]: https://www.google.com.hk/search?q=BNF%20EBNF [3]: http://tools.ietf.org/html/rfc5234 [4]: http://zh.wikipedia.org/wiki/%E5%B7%A6%E9%81%9E%E6%AD%B8 [Zxx]: https://github.com/ZxxLang/zxx [zxx abnf]: https://github.com/ZxxLang/zxx/tree/master/abnf