解析表達文法

在電腦科學領域，解析表達文法，簡稱PEG（英語：Parsing Expression Grammar），是一種分析型形式文法。PEG在2004年由布萊恩·福特（Bryan Ford）推出，它與20世紀70年代初引入的自頂向下的語法分析語言家族密切相關。

在語法上，PEG很接近上下文無關文法（CFG），但是他們採用了不同的解釋：例如PEG中的選擇運算子總是會選中第一個匹配項，而在CFG中則是不明確的。這更接近於字串辨識在實際中的應用，例如使用遞歸下降解析器的情況。另外不像CFG，PEG不能有二義性：在解析一個字串的時候，只能有單一確定的語法分析樹。據推測，存在上下文無關語言，不能用PEG處理，但尚未得到證實。 這個特性使得PEG更適合電腦語言的解析，對於一般的CFG演算法（如依爾利演算法）的效能可以與之比擬的自然語言就不是很合適。

定義

語法

形式上，一個解析表達文法由以下部分組成：

• 一個有限的非終結符的集合 N
• 一個有限的終結符的集合 Σ，和 N 沒有交集
• 一個有限的解析規則的集合 P
• 一個被稱作開始表達式的解析表達式 e_S

P 中的每一個解析規則以 A ← e 的形式出現，這裏 A 是一個非終結符，e 是一個解析表達式。解析表達式是類似正則表達式的層次表達式：

1. 原子解析表達式由以下組成:
   • 任何的終結符，
   • 任何的非終結符，
   • 空字串 ε.
2. 給定已經存在的解析表達式 e, e₁ 和 e₂, 一個新的解析表達式可以通過以下操作構成:
   • 序列: e₁ e₂
   • 有序選擇: e₁ / e₂
   • 零個或更多: e*
   • 一個或更多: e+
   • 可選: e?
   • 肯定斷言: &e
   • 否定斷言: !e

語意

CFG和PEG的關鍵不同是PEG的選擇運算子是有序的。如果第一個選項成功匹配，則忽略第二個選項。因此PEG的有序選擇是不可交換的，這點和上下文無關文法或者正則表達式在教科書上的定義不同。有序選擇類似於某些邏輯編程語言中的軟截斷運算子。

這導致的區別就是如果一個上下文無關文法被直接轉換為解析表達文法，所有的不確定性的地方都會被確定下來，方法是從所有可能的解析樹中選擇一個分支。通過仔細安排文法可能項的順序，編程的人就可以自由控制哪一個解析分支被選中。

與布林上下文無關語法一樣，解析表達式語法也添加了肯定斷言以及否定斷言。因為它們可以使用任意複雜的子表達式「向前檢視」輸入字串，而不需要實際消耗它，所以它們提供了一個強大的語法向前尋找和消歧功能，特別是在重新排序替代方案不能指定所需的準確的解析樹時。

解析表達式的解釋

解析表達文法裏面的每一個非終結符本質上表示遞歸下降解析器裏面的一個解析函數，其對應的解析表達式展示了這個函數包含的代碼內容。概念上，每一個解析函數接受一個輸入字串作為參數，返回以下其中一個結果:

• 成功，函數可能向前移動或者「消耗」一個或多個輸入字串的字元
• 失敗，不消耗任何字元

一個非終結符有可能成功但是不消耗任何輸入字元，這也是一種不同於失敗的結果。

只由一個終結符組成的原子解析表達式：成功，如果輸入字串的第一個字元就是定義中的終結符，這種情況下消耗這個輸入字元；否之失敗。由空字串組成的原子解析表達式總是成功並且不消耗任何輸入。只由一個非終結符A組成的原子解析表達式表示對非終結符A的解析函數的遞歸呼叫。

序列運算子 e₁e₂ 首先呼叫 e₁， 如果 e₁成功， 接着對 e₁ 消耗剩下的輸入字串呼叫 e₂， 最後返回結果。如果 e₁ 或者 e₂ 失敗，那麼序列表達式 e₁e₂ 失敗。

選擇運算子 e₁ / e₂ 首先呼叫 e₁， 如果 e₁成功， 立刻返回結果。否則如果 e₁ 失敗，選擇運算子回溯到輸入字串匹配 e₁ 的原始位置，呼叫 e₂， 最後返回 e₂ 結果。

零個或多個，一個或多個，和可選運算子分別消耗零個或多個，一個或多個，或者零個或一個連續重複的子表達式e。與上下文無關文法和正則表達式不同的 是，儘管如此，在PEG里這些運算子總是執行貪婪的行為，那就是消耗儘可能多的輸入，而且絕對不回溯。（正則表達式一開始執行貪婪匹配，但是如果整個正則表達式失敗後，會回退並嘗試短一些的匹配。）例如，解析表達式a*總是儘可能多的消耗輸入字串中連續出現的a，解析表達式(a* a)則必然會失敗因為前半部分a*絕對不會留下一丁點a給後半部分去匹配。

最後，肯定斷言和否定斷言實現了句法斷言。&e 表達式呼叫子表達式e，如果e成功，則返回成功；否則返回失敗。無論結果如何都不消耗任何字元。反之，當e失敗時！e 表達式成功，e成功時！e 表達式失敗， 同樣無論結果如何都不消耗任何字元。因為向前判斷的子表達式e 可以任意的複雜，所以斷言表達式提供了強大的句法向前判斷和去除二義性的能力。

範例

這是一個簡單的解析表達文法，它辨識基本的數學表達式，只使用了基本的四個運算子並且只接受正整數作為運算元.

Expr    ← Sum
Sum     ← Product (('+' / '-') Product)*
Product ← Power (('*' / '/') Power)*
Power   ← Value ('^' Power)?
Value   ← [0-9]+ / '(' Expr ')'

在上面這個例子裏面，終結符就是字元文字，用單引號括起來表示。比如'('和')'。[0-9]這個區間是10個字元的縮寫，表示數字0到數字9裏面的任意一個。（這裏區間的語意和正則表達式裏面的一樣。）非終結符就是被定義成其他表達式的符號：Value, Product, Sum, 以及 Expr。

接下來的遞歸規則匹配了標準C風格的if/then/else陳述式。因為/運算子的隱式優先級安排，可選的else陳述式總是會被繫結到最內層的if陳述式。（在上下文無關文法裏，這種結構的文法會導致懸空的else陳述式這種二義性錯誤。

S ← 'if' C 'then' S 'else' S / 'if' C 'then' S

下面的這個遞歸規則匹配Pascal格式的註釋語法，(*和*)括號，其內部可以有巢狀的(*和*)對。註釋符號放在雙引號內內是為了與其他PEG運算子區分開來。

Begin ← '(*'
End   ← '*)'
C     ← Begin N* End
N     ← C / (!Begin !End Z)
Z     ← any single character

解析表達式 foo &(bar) 只有當 foo 後面緊跟着字串 bar 的時候，才會匹配並消耗 foo。而解析表達式 foo !(bar) 只有當 foo 後面沒有緊跟着字串 bar 的時候，才會匹配。表達式 !(a+ b) a 只有當a 不是一連串a後面連着一個b的情況下出現的時候，才能匹配一個單獨的字母a。

解析表達式('a'/'b')*匹配任意長度的a和b序列。解析規則 S ← 'a' S? 'b' 描述了$\{a^{n}b^{n}:n\geq 1\}$. 這樣一個簡單的上下文無關匹配語言。而下面的這個解析表達文法則可以描述經典的非上下文無關文法$\{a^{n}b^{n}c^{n}:n\geq 1\}$：

S ← &(A 'c') 'a'+ B !.
A ← 'a' A? 'b'
B ← 'b' B? 'c'

根據解析表達文法實現解析器

所有的解析表達文法都能夠被直接轉化為遞歸下降解析器。 儘管如此，因為PEG公式提供了理論上不受限制的向前檢查的能力，所以最終得到的解析器在最壞情況下還是可能出現指數級時間複雜度的。

通過儲存增量解析步驟的結果和確保每一個解析函數在同一個輸入位置只被呼叫一次，就可以把任意解析表達文法轉化成一個Packrat Parser，可以實現線性的時間複雜度解析，其代價是足夠大量的空間佔用。

一個Packrat Parser是一種結構上類似於遞歸下降解析器的語法解析器，區別是在解析過程中，它會記下所有互相遞歸呼叫的函數的中間結果。因為儲存了這些資訊，一個 Packrat Parser就擁有了以線性時間複雜度解析多數上下文無關文法和所有解析表達文法的能力（包括某些表示的不是上下文無關文法語言的文法）。

從解析表達文法建立LL剖析器和LR剖析器也是可行的，但是在這兩種情況下，不受限制的向前檢查的能力就不能用了。

優勢

因為PEG更加嚴格更加強大，PEG可以成為很好的正則表達式的替代品。例如，一個正則表達式本身是無法匹配巢狀的括號對，因為正則表達式不是遞歸的，但是PEG卻能做到這點。

所有的PEG都能通過使用Parkrat Parser達到線性時間解析，如同上文所述。

CFG表達的解析器，比如LR解析器，需要首先進行一個單獨的斷詞步驟。這個步驟根據空白的位置或者發音等等因素把輸入分成詞。分詞是必要的，因為 這類解析器使用向前檢查來判斷上下文無關文法是否匹配要求。PEG不需要單獨的斷詞步驟，斷詞的規則和其他文法規則可以用同樣的方式寫在一起。

許多CFG原生的存在二義性，即使它們原本要描述的東西並不具有二義性。C, C++, Java裏面著名的懸空else問題就是一個例子。這個問題通常都是應用文法之外的一個規則解決。而在PEG裏面，因為使用了優先權，所以根本不存在這種問題。

劣勢

PEG是新事物，還沒有被廣泛的應用。相比之下，正則表達式和CFG已經產生了數十年了，用來解析的代碼也已經最佳化的很好，並且很多開發者都熟悉怎麼使用他們。

PEG不能表達左遞歸的解析規則。例如，上面的數學運算文法，通過引入更多的規則，來使得乘法和加法的優先級能夠在一行裏面表達出來這可是非常的有誘惑力的， 結果可能得到下面的文法：

Value   ← [0-9.]+ / '(' Expr ')'
Product ← Expr (('*' / '/') Expr)*
Sum     ← Expr (('+' / '-') Expr)*
Expr    ← Product / Sum / Value

這個文法的問題就是，為了匹配Expr， 你需要首先判斷是否某處匹配Product， 而為了匹配Product， 你又必須判斷是不是此處匹配Expr。而這個迴圈定義是不可分析的。

儘管如此，我們總是可以通過重寫左遞歸規則把左遞歸消除掉。 例如，一個左遞歸可能無限的重複一個規則，就像在CFG裏面的：

string-of-a ← string-of-a 'a' | 'a'

在PEG裏面，可以用加號運算子重寫為：

string-of-a ← 'a'+

PEG還涉及到Packrat Parsing， 一種通過佔用更多的儲存空間來消除不必要解析步驟的方法。Packrat Parsing需要的儲存空間與總的輸入檔案的大小成正比，而不是LR解析器的與解析樹的深度成正比。如果稍作修改，傳統的Packrat Parser也可以支援左遞歸。

參見

• 形式文法
• 正則表達式
• 自頂向下解析的語言
• 解析器-生成器比較
• 解析器組合子

參考文獻

• Medeiros, Sérgio; Ierusalimschy, Roberto. A parsing machine for PEGs. Proc. of the 2008 symposium on Dynamic languages. ACM: article #2. 2008. ISBN 978-1-60558-270-2. doi:10.1145/1408681.1408683. 

外部連結

• Parsing Expression Grammars: A Recognition-Based Syntactic Foundation （頁面存檔備份，存於互聯網檔案館） (PDF slides)
• Converting a string expression into a lambda expression using an expression parser
• The Packrat Parsing and Parsing Expression Grammars Page （頁面存檔備份，存於互聯網檔案館）
• Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking （頁面存檔備份，存於互聯網檔案館）
• The constructed language Lojban has a fairly large PEG grammar （頁面存檔備份，存於互聯網檔案館） allowing unambiguous parsing of Lojban text.