剖析表達文法 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 有關的例子：

另外我查 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
• rust 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 的部分因為文件有點少還在卡關當中，下一篇應該會整理相關的用法，然後用它寫個超簡單剖析器。

參考資料：

• 本文基礎 ，大部分的例子都是裡面來的 :P
• 文脈自由文法(CFG)と解析表現文法(PEG)をHaskellのモナドで説明する話
  神文大推（日文就是…），用了 haskell monad 實作了 CFG, PEG parser，兩者的差距只在 Maybe 跟 list 的差別，現在還在研究當中。
• 如何学习解析表达文法(PEG)
  一些 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。