解析表達文法

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

基本介紹

  • 中文名：解析表達文法
  • 簡稱：PEG
  • 性質：形式文法
  • 領域：計算機
簡介,定義,語法,語義,解析表達式的解釋,根據解析表達文法實現解析器,優勢,劣勢,

簡介

解析表達文法以純公式的形式的展現遞歸下降解析器的基礎語法，對這個具體的解析器可能會採用的實現方法不做任何限定。解析表達文法看起來與正則表達式和巴科斯範式的上下文無關文法(CFG)很像，但是表達的意思不同。和CFG不同的是，PEG不能有二義性；解析一個字元串的時候，這個字元串只產生一個確定的解析樹。這個特性使得PEG更適合計算機語言的解析，對於自然語言就不是很合適。
解析表達文法2004年由布萊恩·福特引入，以純公式的形式的展現遞歸下降解析器的基礎語法，對這個具體的解析器可能會採用的實現方法不做任何限定。解析表達文法看起來與正則表達式和巴科斯範式的上下文無關文法（CFG）很像，但是表達的意思不同。
和CFG不同的是，PEG不能有二義性；解析一個字元串的時候，這個字元串只產生一個確定的語法分析樹。據推測，存在上下文無關語言，不能用PEG處理，但尚未得到證實。這個特性使得PEG更適合計算機語言的解析，對於一般的CFG算法（如依爾利算法）的性能可以與之比擬的自然語言就不是很合適。

定義

語法

形式上，一個解析表達文法由以下部分組成：
  • 一個有限的非終結符的集合N
  • 一個有限的終結符的集合 Σ，和N沒有交集
  • 一個有限的解析規則的集合P
  • 一個被稱作起點表達式的解析表達式eS
P中的每一個解析規則以A←e的形式出現，這裡A是一個非終結符，e是一個解析表達式。解析表達式是類似正則表達式的層次表達式：
  1. 原子解析表達式由以下組成:
  2. 任何的終結符，
  3. 任何的非終結符，
  4. 空字元串 ε.
  5. 給定已經存在的解析表達式e,e1和e2, 一個新的解析表達式可以通過以下操作構成:
  6. 序列:e1e2
  7. 有序選擇:e1/e2
  8. 零個或更多:e*
  9. 一個或更多:e+
  10. 可選:e?
  11. 肯定斷言: &e
  12. 否定斷言:!e

語義

CFG和PEG的關鍵不同是PEG的選擇操作符是有序的。如果第一個可能成功了，那么第二個可能就忽略。因此PEG的有序選擇是不可以互換的，這點和上下文無關文法或者正則表達式在教科書上的定義不同。有序選擇類似於某些邏輯編程語言中的軟截斷操作符。
與上下文無關文法或者其他生成文法不同，在解析表達文法裡面，對應某個非終結符，必須且只能有一個的解析規則。這意味著，在PEG裡面，解析規則就是定義，每一個非終結符必須有且只能由一個定義。
這導致的區別就是如果一個上下文無關文法被直接轉換為解析表達文法，所有的不確定性的地方都會被確定下來，方法是從所有可能的解析樹中選擇一個分支。通過仔細安排文法可能項的順序，編程的人就可以自由控制那一個解析分支被選中。

解析表達式的解釋

解析表達文法裡面的每一個非終結符本質上表示遞歸下降解析器裡面的一個解析函式，其對應的解析表達式展示了這個函式包含的代碼內容。概念上，每一個解析函式接受一個輸入字元串作為參數，返回以下其中一個結果:
  • 成功，函式可能向前移動或者“消耗”一個或多個輸入字元串的字元
  • 失敗，不消耗任何字元
一個非終結符有可能成功但是不消耗任何輸入字元，這也是一種不同於失敗的結果。
只由一個終結符組成的原子解析表達式：成功，如果輸入字元串的第一個字元就是定義中的終結符，這種情況下消耗這個輸入字元；否之失敗。由空字元串組成的原子解析表達式總是成功並且不消耗任何輸入。只由一個非終結符A組成的原子解析表達式表示對非終結符A的解析函式的遞歸調用。
序列操作符e1e2首先調用e1， 如果e1成功， 接著對e1消耗剩下的輸入字元串調用e2， 最後返回結果。如果e1或者e2失敗，那么序列表達式e1e2失敗。
選擇操作符e1/e2首先調用e1， 如果e1成功， 立刻返回結果。否則如果e1失敗，選擇操作符回溯到輸入字元串匹配e1的原始位置，調用e2， 最後返回e2結果。
零個或多個，一個或多個，和可選操作符分別消耗零個或多個，一個或多個，或者零個或一個連續重複的子表達式e。與上下文無關文法和正則表達式不同的 是，儘管如此，在PEG里這些操作符總是執行貪婪的行為，那就是消耗儘可能多的輸入，而且絕對不回溯。（正則表達式一開始執行貪婪匹配，但是如果整個正則表達式失敗後，會回退並嘗試短一些的匹配。）例如，解析表達式a*總是儘可能多的消耗輸入字元串中連續出現的a，解析表達式(a* a)則必然會失敗因為前半部分a*絕對不會留下一丁點a給後半部分去匹配。
最後，肯定斷言和否定斷言實現了句法斷言。&e 表達式調用子表達式e，如果e成功，則返回成功；否則返回失敗。無論結果如何都不消耗任何字元。反之，當e失敗時！e 表達式成功，e成功時！e 表達式失敗， 同樣無論結果如何都不消耗任何字元。因為向前判斷的子表達式e 可以任意的複雜，所以斷言表達式提供了強大的句法向前判斷和去除二義性的能力。

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

所有的解析表達文法都能夠被直接轉化為遞歸下降解析器。儘管如此，因為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。而這個循環定義是不可分析的。

相關詞條

熱門詞條

聯絡我們