更改DCG是確定性

Question

如何改變這種文法是確定性

e --> []. 
e --> "*". 
e --> s_e. 
e --> e, s_e. 
s_e --> ("a",e);("b",e). 

我只是不知道從哪裏把切割，以避免回溯。

Answer 1

您可以重寫了最後的規則如下：

s_e --> "a", e. 
s_e --> "b", e. 

現在看來，可能感知到將下面的削減：

s_e --> "a", !, e. 
s_e --> "b", !, e. 

您也可以放置在原有的緊湊 形式的削減與（;）/ 2，但我覺得上面更透明。 如果s_e沒有用相同的輸入列表調用多個 次，以上是有效的。

但您的語法有缺陷，e是左遞歸， 和s_e將被多次調用相同的 輸入列表。意思是你的文法將例如 循環用於否定句，即它將不能夠 來拒絕它們，並且在 重做一個肯定句之後，即當輸入 已被接受時，你的文法將循環。

所以你需要額外的消除左邊的 遞歸，因爲正常的Prolog深度拳頭搜索 無法處理它。最簡單的是用一個新的非終端用右遞歸替換 。即你 可以寫成如下爲電子商務的作品：

e --> s_e, rest_e. 
e --> "*", rest_e. 
e --> []. 

rest_e --> s_e, rest_e. 
rest_e --> "*", rest_e. 
rest_e --> []. 

而且我們可以把削減以及：

e --> s_e, !, rest_e. 
e --> "*", !, rest_e. 
e --> []. 

rest_e --> s_e, !, rest_e. 
rest_e --> "*", !, rest_e. 
rest_e --> []. 

而且上面的語法在 稍微修改這個意義上，多個空Ë製作不要 通過s_e進入e本身。它也比較貪婪，因爲這些子產品總是完全被解析的 。因此，例如上一句：

aaa 

只解析爲：

a(a(a)) 

而不是：

a(a)a 

或者：

aa(a) 

或者：

aaa 

但是，否則它應該接受相同的句子，如果DCG 將自底向上執行並且不會有 問題與左遞歸。

最好的問候