[科普中國]-解析表達文法

解析表達文法，簡稱PEG，是一種形式文法。這種文法用一個識別字符串的規(guī)則的集合來描述某種形式語言。

簡介解析表達文法以純公式的形式的展現(xiàn)遞歸下降解析器的基礎語法，對這個具體的解析器可能會采用的實現(xiàn)方法不做任何限定。解析表達文法看起來與正則表達式和巴科斯范式的上下文無關文法(CFG)很像，但是表達的意思不同。和CFG不同的是，PEG不能有二義性；解析一個字符串的時候，這個字符串只產生一個確定的解析樹。這個特性使得PEG更適合計算機語言的解析，對于自然語言就不是很合適。

解析表達文法2004年由布萊恩·福特引入，以純公式的形式的展現(xiàn)遞歸下降解析器的基礎語法，對這個具體的解析器可能會采用的實現(xiàn)方法不做任何限定。解析表達文法看起來與正則表達式和巴科斯范式的上下文無關文法（CFG）很像，但是表達的意思不同。

和CFG不同的是，PEG不能有二義性；解析一個字符串的時候，這個字符串只產生一個確定的語法分析樹。據(jù)推測，存在上下文無關語言，不能用PEG處理，但尚未得到證實。這個特性使得PEG更適合計算機語言的解析，對于一般的CFG算法（如依爾利算法）的性能可以與之比擬的自然語言就不是很合適。1

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

一個有限的非終結符的集合N

一個有限的終結符的集合 Σ，和N沒有交集

一個有限的解析規(guī)則的集合P

一個被稱作起點表達式的解析表達式eS

P中的每一個解析規(guī)則以A←e的形式出現(xiàn)，這里A是一個非終結符，e是一個解析表達式。解析表達式是類似正則表達式的層次表達式：

原子解析表達式由以下組成:

任何的終結符，

任何的非終結符，

空字符串 ε.

給定已經(jīng)存在的解析表達式e,e1和e2, 一個新的解析表達式可以通過以下操作構成:

序列:e1e2

有序選擇:e1/e2

零個或更多:e*

一個或更多:e+

可選:e?

肯定斷言: &e

否定斷言:!e

語義CFG和PEG的關鍵不同是PEG的選擇操作符是有序的。如果第一個可能成功了，那么第二個可能就忽略。因此PEG的有序選擇是不可以互換的，這點和上下文無關文法或者正則表達式在教科書上的定義不同。有序選擇類似于某些邏輯編程語言中的軟截斷操作符。

與上下文無關文法或者其他生成文法不同，在解析表達文法里面，對應某個非終結符，必須且只能有一個的解析規(guī)則。這意味著，在PEG里面，解析規(guī)則就是定義，每一個非終結符必須有且只能由一個定義。

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

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

成功，函數(shù)可能向前移動或者“消耗”一個或多個輸入字符串的字符

失敗，不消耗任何字符

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

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

序列操作符e1e2首先調用e1， 如果e1成功， 接著對e1消耗剩下的輸入字符串調用e2， 最后返回結果。如果e1或者e2失敗，那么序列表達式e1e2失敗。

選擇操作符e1/e2首先調用e1， 如果e1成功， 立刻返回結果。否則如果e1失敗，選擇操作符回溯到輸入字符串匹配e1的原始位置，調用e2， 最后返回e2結果。

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

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

根據(jù)解析表達文法實現(xiàn)解析器所有的解析表達文法都能夠被直接轉化為遞歸下降解析器。盡管如此，因為PEG公式提供了理論上不受限制的向前檢查的能力，所以最終得到的解析器還是可以避免最壞情況下指數(shù)級時間復雜度的。

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

一個Packrat Parser是一種結構上類似于遞歸下降解析器的語法解析器，區(qū)別是在解析過程中，它會記下所有互相遞歸調用的函數(shù)的中間結果。因為保存了這些信息，一個 Packrat Parser就擁有了以線性時間復雜度解析多數(shù)上下文無關文法和所有解析表達文法的能力（包括某些表示的不是上下文無關文法語言的文法）。

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

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

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

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

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

劣勢PEG是新事物，還沒有被廣泛的應用。相比之下，正則表達式和CFG已經(jīng)產生了數(shù)十年了，用來解析的代碼也已經(jīng)優(yōu)化的很好，并且很多開發(fā)者都熟悉怎么使用他們。

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

Value ← [0-9.]+ / '(' Expr ')'Product ← Expr (('*' / '/') Expr)*Sum ← Expr (('+' / '-') Expr)*Expr ← Product / Sum / Value這個文法的問題就是，為了匹配Expr， 你需要首先判斷是否某處匹配Product， 而為了匹配Product， 你又必須判斷是不是此處匹配Expr。而這個循環(huán)定義是不可分析的。2

本詞條內容貢獻者為:

王沛 - 副教授、副研究員 - 中國科學院工程熱物理研究所