解析表達文法

在計算機科學領域，解析表達文法，簡稱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.