PEG和CFG之間有什麼區別？

從這個wikipedia頁：PEG和CFG之間有什麼區別？

上下文無關文法和解析表達語法的根本區別是，PEG的選擇運營商是有序的。如果第一個替代方案成功，則第二個替代方案將被忽略。因此，訂購的選擇是不可交換的，不像無序的選擇，因爲在上下文無關語法和正則表達式。有序選擇類似於軟件削減運算符在一些邏輯可用編程語言。

爲什麼PEG的選擇運算符將匹配短路？是否因爲最大限度地減少內存使用（由於記憶）？

我不確定在正則表達式中選擇運算符是什麼，但我們假設它是這樣的：/[aeiou]/以匹配元音。所以這個正則表達式是可交換的，因爲我可以把它寫在5中的任何一個！（五個階乘）元音字符的排列？即/[aeiou]/的行爲與/[eiaou]/相同。它可交換的優點是什麼？（C.F. PEG的不可交換）

的後果是，如果一個CFG是直接音譯的PEG，在前任何歧義由確定性挑選一個解析從可能的解析樹解決。通過仔細選擇指定的文法備選的順序，程序員對選擇哪個解析樹有很大的控制權。

這是說PEG的語法優於CFG嗎？

來源

2011-03-31 Frankie Ribery

「Superior」？你對「上級」的標準是什麼？ – Gabe 2011-03-31 14:02:03

對於交換性，想想'（飛機）'試圖匹配飛機。 – xanatos 2011-03-31 14:47:35

看起來你很迷惑選擇運算符和角色類的概念。在正則表達式中，字符類用方括號'[aeiou]'分隔，而選擇操作符是管道字符'|'。在PEG中，選擇運算符是斜槓字符'/'。 – hippietrail 2014-08-11 10:56:59

CFG語法是非確定性的，這意味着某些輸入可能導致兩個或更多可能的分析樹。儘管大多數基於CFG的解析器生成器對語法的可確定性存在限制。如果它有兩個或更多的選擇，它會發出警告或錯誤。

PEG語法是確定性的，這意味着任何輸入只能單向解析。

舉一個典型的例子;語法

if_statement := "if" "(" expr ")" statement "else" statement 
       | "if" "(" expr ")" statement;

施加到輸入

if (x1) if (x2) y1 else y2

既可以被解析爲

if_statement(x1, if_statement(x2, y1, y2))

或

if_statement(x1, if_statement(x2, y1), y2)

甲CFG解析器將產生移位/減少衝突，因爲它不能決定我當它到達「else」關鍵字時，它應該轉移（讀取另一個令牌）或減少（完成節點）。當然，有辦法解決這個問題。

一個PEG分析器總是會選擇第一個選擇。

哪一個更好是由你來決定的。我的客觀觀點是，通常PEG語法更容易編寫，而CFG語法更容易分析。

來源

2011-03-31 14:57:46

你能提供一個這樣的CFG語法的示例（2個解析樹）嗎？ – 2011-04-04 05:47:00

感謝您懸賞的例子。現在很清楚。 – 2011-04-12 02:50:27

我認爲你讓CFG和LR混淆並且含糊不清。語法不是確定性/非確定性的，儘管他們的解析器可能是。一個模糊的語法如果符合定義，它仍然是CFG，並且可以爲PEG做一個確定性的語法分析器。

來源

2012-11-17 14:48:24 Apalala

不，CFG有時候是不明確的，因爲它們的「選擇」操作符沒有優先級，所以如果給定的字符串與「選擇」中的兩個選項相匹配，那麼你就有一個模糊性。 PEG中的「選擇」具有優先匹配優先權，所以不存在歧義，因爲最左邊的選項*必然*勝出。 – aaronblohowiak 2013-01-15 01:46:54

不可以。否CFG可能不明確，因爲所有選項同等有效。當相同的短語可以由不同的製作序列生成時，CFG是不明確的。在LL和LR中，歧義意味着解析器/識別器無法知道哪個產品序列（哪個語法樹）對應於給定的短語。 PEG通過按照宣佈順序排列產品來解決歧義問題。它告訴解析器，正確的語法樹是第一個語法樹。 – Apalala 2013-01-15 10:53:14

PEG和CFG之間有什麼區別？

回答

相關問題