解析表達文法

在計算機科學領域，解析表達文法，簡稱PEG推出，它與20世紀70年代初引入的家族密切相關。在語法上，PEG很接近上下文無關文法的效能可以與之比擬的自然語言就不是很合適。定義.語法.形式上，一個解析表達文法由以下部分組成："P" 中的每一個解析規則以 "A" ← "e" 的形式出現，這裡 "A" 是一個非終結符，"e" 是一個解析表示式。解析表示式是類似正則表示式的層次表示式：語義.CFG和PEG的關鍵不同是PEG的選擇運算子是有序的。如果第一個選項成功匹配，則忽略第二個選項。因此PEG的有序選擇是不可交換的，這點和上下文無關文法或者正則表示式在教科書上的定義不同。有序選擇類似於某些邏輯程式語言中的軟截斷運算子。這導致的區別就是如果一個上下文無關文法被直接轉換為解析表達文法，所有的不確定性的地方都會被確定下來，方法是從所有可能的解析樹中選擇一個分支。透過仔細安排文法可能項的順序，程式設計的人就可以自由控制哪一個解析分支被選中。與布林上下文無關語法一樣，解析表示式語法也添加了肯定斷言以及否定斷言。因為它們可以使用任意複雜的子表示式“向前檢視”輸入字串，而不需要實際消耗它，所以它們提供了一個強大的語法向前查詢和消歧功能，特別是在重新排序替代方案不能指定所需的準確的解析樹時。解析表示式的解釋.解析表達文法裡面的每一個非終結符本質上表示遞迴下降解析器裡面的一個解析函式，其對應的解析表示式展示了這個函式包含的程式碼內容。概念上，每一個解析函式接受一個輸入字串作為引數，返回以下其中一個結果:一個非終結符有可能成功但是不消耗任何輸入字元，這也是一種不同於失敗的結果。只由一個終結符組成的原子解析表示式：成功，如果輸入字串的第一個字元就是定義中的終結符，這種情況下消耗這個輸入字元；否之失敗。由空字串組成的原子解析表示式總是成功並且不消耗任何輸入。只由一個非終結符A組成的原子解析表示式表示對非終結符A的解析函式的遞迴呼叫。序列運算子 "e"1"e"2 首先呼叫 "e"1， 如果 "e"1成功， 接著對 "e"1 消耗剩下的輸入字串呼叫 "e"2， 最後返回結果。如果 "e"1 或者 "e"2 失敗，那麼序列表達式 "e"1"e"2 失敗。選擇運算子 "e"1 / "e"2 首先呼叫 "e"1， 如果 "e"1成功， 立刻返回結果。否則如果 "e"1 失敗，選擇運算子回溯到輸入字串匹配 "e"1 的原始位置，呼叫 "e"2， 最後返回 "e"2 結果。零個或多個，一個或多個，和可選運算子分別消耗零個或多個，一個或多個，或者零個或一個連續重複的子表示式e。與上下文無關文法和正則表示式不同的 是，儘管如此，在PEG裡這些運算子總是執行貪婪的行為，那就是消耗盡可能多的輸入，而且絕對不回溯。例如，解析表示式a*總是儘可能多的消耗輸入字串中連續出現的a，解析表示式(a* a)則必然會失敗因為前半部分a*絕對不會留下一丁點a給後半部分去匹配。最後，肯定斷言和否定斷言實現了句法斷言。&amp;e 表示式呼叫子表示式e，如果e成功，則返回成功；否則返回失敗。無論結果如何都不消耗任何字元。反之，當e失敗時！e 表示式成功，e成功時！e 表示式失敗， 同樣無論結果如何都不消耗任何字元。因為向前判斷的子表示式e 可以任意的複雜，所以斷言表示式提供了強大的句法向前判斷和去除二義性的能力。示例.這是一個簡單的解析表達文法，它識別基本的數學表示式，只使用了基本的四個運算子並且只接受正整數作為運算元.Expr ← SumSum ← Product (('+' / '-') Product)*Product ← Power (('*' / '/') Power)*Power ← Value ('^' Power)?Value ← [0-9]+ / '(' Expr ')'在上面這個例子裡面，終結符就是字元文字，用單引號括起來表示。比如codice_1和codice_2。codice_3這個區間是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* EndN ← C / (!Begin !End Z)Z ← any single character解析表示式 foo &amp;(bar) 只有當 foo 後面緊跟著字串 bar 的時候，才會匹配並消耗 foo。而解析表示式 foo !(bar) 只有當 foo 後面沒有緊跟著字串 bar 的時候，才會匹配。表示式 !(a+ b) a 只有當a 不是一連串a後面連著一個b的情況下出現的時候，才能匹配一個單獨的字母a。解析表示式('a'/'b')*匹配任意長度的a和b序列。解析規則 "S" ← 'a' "S"? 'b' 描述了formula_1. 這樣一個簡單的上下文無關匹配語言。而下面的這個解析表達文法則可以描述經典的非上下文無關文法formula_2：S ← &amp;(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裡面著名的就是一個例子。這個問題通常都是應用文法之外的一個規則解決。而在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也可以支援左遞迴。