Tag

2018年5月1日 星期二

剖析表達文法 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。
Related Posts Plugin for WordPress, Blogger...