剖析表達文法 PEG 簡介

剖析表達文法 PEG 為 Parsing Expression Grammar 的縮寫，2004 年由 Bryan Ford 教授所提出，相對於一般在編譯器課上教 parsing 所用的 CFG (Context Free Grammar) ，已經被鑽研數十年之久，可說是相當年輕的形式化語言。

其實 PEG 和 CFG 在本體上幾乎沒有不同，從創作概念上來看，CFG 著重的是語法的產生和定義，PEG 則專注在剖析語法上，找資料時就有在中國的知乎論壇上看到這句：「CFG 作為產生式文法，很適合用來生成內容丰富多彩的垃圾郵件」不禁會心一笑，過去定義程式語言，都是先教 CFG，通常都會有這麼一句：「寫出 CFG 就定義了一個程式語言」
生成文法的切入點在<產生>，我們定義產生文法來定義語言，討論各種文法的強度，看看它們能產生什麼，不能產生什麼；用這套文法產生出來的東西，管它到底多亂多醜多長，都符合這個文法（有點回文），從 CFG 的觀點來看，先想好怎麼產生程式語言，接下來再來看怎麼剖析它，然後再討論 LL, LR 等等剖析方法。

PEG 則沒有這麼繞圈圈，PEG 本身即是 parser 的抽象定義，PEG 定義的 parser 會由一條一條規則組成，每條規則會去匹配輸入，如果成功則消耗輸入，失敗則不會消耗輸入。
PEG 的 terminal 規則如下，大致和 CFG 相同：
* 字串即匹配字面上的字串
* eps (ε) 匹配空集合，永遠成功且不消耗輸入
* . 匹配任意字元
* [abc] [a-z] 表示符合集合中任一字元

Non-terminal 的規則是跟 CFG 較多不同之處：
* PEG 同樣提供來自 regexp 的 ? + * 三個結合符號，也就是零或一個、一個或多個、零至多個，全部都是 greedy。
* e1 e2：依序剖析 e1，在剩餘的字串上剖析 e2，如果 e1, e2 任一剖析失敗則整個規則都失敗（記得如果規則失敗則不會消耗 input）。
* e1 / e2：嘗試 e1，失敗的話就換 e2，這是 PEG 跟 CFG 最大的不同之處，CFG 的接續規則是沒有先後次序的，雖然 CFG 的剖析器，通常為了方便會加入一些先後次序來處理歧義性的問題，例如對 dangling else 採用 shift over reduce ，把多的 else 先拉進來，但在 PEG 中這樣的歧義性可以很簡單的用 / 來消除。

S <- “if” C “then” S “else” S / “if” C “then” S

* 另外有兩個 And predicate &e 跟 Not predicate !e：可以向前看之後的內容是否匹配/不匹配 e，但無論成功或失敗，predicate 都不消耗輸入；理論上的 PEG predicate 可以擁有無限的 predicate 能力，但在實作上應該都有一定的限制。

下面可以舉一些跟 non-terminal 有關的例子：
a* a：永遠會失敗，e1 會吃光所有的 a，造成 e2 失敗。
!”_” .：匹配除底線外任意字元。
“>” / “>=”：是個錯誤的寫法，要不是失敗就是 e1 成功消耗 > 字元，第二個 >= 只是裝飾用的，在運算符的匹配上，應該要依序從長到短排序：>> / << / >= / <= / > / </ =。
另外我查 PEG 時也有遇到一些詭異的文法剖析結果，例如參考資料舉出的：

S -> A $
A -> "a" A "a" / "a"

PEG 會很見鬼的匹配 2^n-1 個 a，以 5 個 a 的狀況，後三個 a 會剖析為 A = aAa，但下一步合併失敗，導致第二個 a 被剖析為 A = a，最後只剖析了前三個字元：失敗。

PEG 的好處在於簡單漂亮，每個 PEG 都是無岐義的，實作上一條規則正好對應一條處理函式，類似 parser combinator，由上而下一跟呼叫：parseExpr -> parseTerm -> parseFactor -> identifier / number 這樣的剖析順序，可以把剖析器寫得漂亮好改；也因此一些語言都有開始支援 PEG parser generator：例如 rust 的 rust-peg, pest，haskell 的 peggy，Dlang 的 pegged 等等。
PEG 並不是單純 CFG 的超集或子集，事實上兩者的概念不太一樣，我建議不要把兩者混為一談，例如知名的 a{n} b{n} c{n} 這個 CSG（n個a 接 n個b 接 n個c，這用 CFG 是產生不出來的），卻可以用 PEG 來剖析；目前是否 CFG 產生出來的文法都能用 PEG 來剖析還是一個開放問題，就留給有興趣的人去挑戰了。

會寫這篇文章，因為最近正在試著用 rust pest 寫一個簡單的剖析器，發現有關 PEG 的中文討論相當的少，就先整理一篇，其實目前要查中文，用「解析表達文法」查到的比較多，但台灣的 parse 就是剖析，所以我標題還是下「剖析表達文法」； pest 的部分因為文件有點少還在卡關當中，下一篇應該會整理相關的用法，然後用它寫個超簡單剖析器。

參考資料：
https://github.com/PhilippeSigaud/Pegged/wiki
本文基礎，大部分的例子都是裡面來的 :P
http://qnighy.hatenablog.com/entry/2015/11/12/162424
神文大推（日文就是…），用了 haskell monad 實作了 CFG, PEG parser，兩者的差距只在 Maybe 跟 list 的差別，現在還在研究當中。
https://www.zhihu.com/question/28525605
一些 CFG 跟 PEG 的比較，算簡單易懂，可以看過去

附註：

S -> A $
A -> "a" A "a" / "a"

這個問題，後來我有想通了，先假設 k 個 a 的時候是可以匹配的；在輸入 n 個 a 的時候，每一個 a 都會率先匹配為 aAa 的前一個，最後 k 個 a 則會匹配為 A，但後面已經沒有 a 了，因此倒數 k+1 個 a 開始的 A = aAa 匹配失敗，匹配為 A = a，接著如果要匹配成功，就要前後都有 k 個 a 才行。
得到結論：k 個 a 匹配則下一個為 2 * k + 1。