憋屈平移CFG到DCG

我想教自己序言和實施一個解釋爲一個簡單的算術CFG：憋屈平移CFG到DCG

<expression> --> number 
<expression> --> (<expression>) 
<expression> --> <expression> + <expression> 
<expression> --> <expression> - <expression> 
<expression> --> <expression> * <expression> 
<expression> --> <expression>/<expression>

到目前爲止，我已經在SWI-序言寫這本擊中下面描述的錯誤數量;

expression(N) --> number(Cs), { number_codes(N, Cs) }. 
expression(N) --> "(", expression(N), ")". 
expression(N) --> expression(X), "+", expression(Y), { N is X + Y }. 
expression(N) --> expression(X), "-", expression(Y), { N is X - Y }. 

number([D|Ds]) --> digit(D), number(Ds). 
number([D]) --> digit(D). 

digit(D) --> [D], { code_type(D, digit) }.

測試與

phrase(expression(X), "12+4").

給出X = 16，這是很好。

phrase(expression(X), "(12+4)").

作品和短語（表達式（X），「12 + 4 + 5」）。沒問題。

但是，試圖

phrase(expression(X), "12-4").

原因「出錯：本地棧」除非我註釋掉「+」規則。雖然我可以添加兩個以上的數字，括號不會遞歸地工作（即「（1 + 2）+3」掛起）。

我確定解決方案很簡單，但我一直無法從我找到的在線教程中弄清楚。

來源

2015-03-31 joeblog

你所做的一切在原理上都是正確的。你說得對：答案很簡單。

但是。

左遞歸在定義子句語法中是致命的;症狀正是你所看到的行爲。

如果您在expression上設置了一個間諜點並使用跟蹤工具，則可以監視堆棧的增長，增長和增長，而解析器根本沒有任何進展。

gtrace. 
spy(expression). 
phrase(expression(N),"12-4").

如果您仔細考慮了Prolog執行模型，可以看到發生了什麼。

我們試圖解析「12-4」作爲表達式。

我們的調用棧包含此調用，從步驟1到expression，我將寫expression（1）。
我們成功地通過「表達式」的第一個子句解析「12」作爲表達式，並且我們記錄了一個選擇點，以備日後需要回溯。事實上，我們需要立即回溯，因爲涉及phrase的父請求表示我們要解析整個字符串，而我們沒有：我們仍然有「-4」。所以我們失敗了，回到選擇點。我們已經表明，「表達式」的第一個子句不成功，所以我們重試第二個子句。

調用堆棧：expression（1）。
我們嘗試解析「12-4」使用「表達」第二條，但立即失敗（初始字符不是「（」）。因此，我們會失敗，重試對第三條款。

調用堆棧：expression（1）。
第三個條款要求我們從輸入開始處解析表達式，然後找到一個「+」和另一個表達式。所以我們現在必須嘗試將輸入的開始解析爲表達式。

調用堆棧：expression（4）expression（1）。
我們嘗試將「12-4」的開頭解析爲一個表達式，並以「12」結束，就像在步驟1中一樣。我們記錄了一個選擇點，以備日後需要回溯。

調用堆棧：expression（4）expression（1）。
我們現在恢復在步驟4中開始的嘗試，將「12-4」解析爲針對「表達式」的子句3的表達式。我們已經完成了第一步;現在我們必須嘗試解析「-4」作爲「表達式」第3條右邊的餘下部分，即"+", expression(Y)。但「 - 」不是「+」，所以我們立即失敗，並返回到最近記錄的選擇點，即步驟5中記錄的選擇點。接下來要嘗試找到解析作爲表達式輸入。我們用「表達式」的第二個子句繼續搜索。

調用堆棧：expression（4）expression（1）。
第二個子句再次失敗。所以我們繼續「表達」的第三個條款。這要求我們在輸入的開頭尋找一個表達式（作爲確定我們當前對「表達式」的兩個調用是否可以成功或失敗的一部分）。所以我們再次稱之爲「表情」。

調用堆棧：expression（7）expression（4）expression（1）。

你可以看到，每次我們調用expression添加到堆棧的時候，我們要取得成功，尋找一個加號，失敗，再嘗試，最終達到第三條，在這一點上，我們會在堆疊上再次撥打電話，然後重試。

簡答題：左遞歸在DCG中是致命的。

它在遞歸下降解析器中也是致命的，解決方案也大致相同：不會重複到左側。

你的語法的非左遞歸版本應該是：

expression(N) --> term(N). 
expression(N) --> term(X), "+", expression(Y), { N is X + Y }. 
expression(N) --> term(X), "-", expression(Y), { N is X - Y }. 
term(N) --> number(Cs), { number_codes(N, Cs) }. 
term(N) --> "(", expression(N), ")".

然而，這使得「 - 」右結合的，並要求初始期限將在許多情況下反覆重新解析，因此常見的在代碼的方法用於生產做一些不怎麼樣的BNF你開始越來越像下面的EBNF版本：

expression = term {("+"|"-") term} 
term = number | "(" expression ")".

我學會了寫（足夠長的時間以前，我已經不記得誰的方式信貸）是這樣的（我發現醜陋在第一，但它生長在你）：

expression(N) --> term(X), add_op_sequence(X,N). 
add_op_sequence(LHS0, Result) --> 
    "+", term(Y), 
    {LHS1 is LHS0 + Y}, 
    add_op_sequence(LHS1,Result). 
add_op_sequence(LHS0, Result) --> 
    "-", term(Y), 
    {LHS1 is LHS0 - Y}, 
    add_op_sequence(LHS1,Result). 
add_op_sequence(N,N) --> []. 

term(N) --> number(Cs), { number_codes(N, Cs) }. 
term(N) --> "(", expression(N), ")".

迄今已累計值在add_op_sequence的左側參數向下傳遞，最終（當序列與空生產結束）傳回了結果是。

稱爲「左角解析」的解析策略是處理此問題的一種方法;關於在自然語言處理中使用Prolog的書籍幾乎總是在討論它。

來源

2015-04-01 02:53:07

非常感謝那非常全面的答案。 – joeblog 2015-04-01 10:05:18

憋屈平移CFG到DCG

回答

相關問題