處理序言上下文無關文法

Question

給定一個CFG

S --> a S b | c | d 

我想編寫一個謂語一樣，語法（ 'S'，一句）生成所有可能的

sentences like 
sentence=acb, 
sentence=acd, 
sentence=c, 
sentence=ab...................... 

使用最左邊的推導，如果遇到的符號是終端它應該打印出該終端，如果遇到的符號是非終端'S'，它應該回溯並替換和語法其中一個S b或c或d並重復該過程。

我不希望任何代碼...只是幫助我一些提示如何與

Answer 1

開始讓我們用DCG中逐字編碼你的語法！

s --> [a], s, [b] | [c] | [d]. 

?- phrase(s,Xs). 
ERROR: Out of local stack 

似乎這查詢不終止。即Prolog的非常簡單的執行策略沒有找到解決方案。另一方面，想一想：你的語法描述了一組無限的句子。如果你列舉了一個無限集合，那麼很容易開始「在錯誤的一端」。這正是Prolog在這裏實際做的。

但事情並沒有那麼糟糕。枚舉固定長度的所有句子怎麼樣？我會嘗試5：

?- length(Xs,5), phrase(s,Xs). 
Xs = "aacbb" ; 
Xs = "aadbb" ; 
false. 

在這種情況下，所有的句子都找到了，Prolog甚至向我們保證沒有更多的句子。

?- length(Xs,4), phrase(s,Xs). 
false. 

有沒有長度爲4

的句子現在我們可以通過長枚舉所有句子，。

?- length(Xs,N), phrase(s,Xs). 
Xs = "c", 
N = 1 ; 
Xs = "d", 
N = 1 ; 
Xs = "acb", 
N = 3 ; 
Xs = "adb", 
N = 3 ; 
Xs = "aacbb", 
N = 5 ; 
Xs = "aadbb", 
N = 5 ; 
Xs = "aaacbbb", 
N = 7 

我們在這裏使用了什麼樣的派生？老實說，我不知道，我也不在乎。重要的是知道Prolog何時會終止。在這種情況下，如果長度已知，它將終止。這就是我們所需要知道的保證我們有無窮集合的公平枚舉。事情甚至略勝一籌：s//0也將終止在情況下，長度不一樣

?- Xs = [a,a,b|_], phrase(s,Xs). 
false. 

?- Xs = [a,a,c|_], phrase(s,Xs). 
Xs = "aacbb" ; 
false. 

?- dif(X,Y), Xs = [X,Y|_], phrase(s,Xs). 
X = a, 
Y = c, 
Xs = "acb" ; 
X = a, 
Y = d, 
Xs = "adb" ; 
false. 

編輯知道：我得到了有關使用"acb"的列表[a,c,b]頂層回答一些問題：請參閱this answer一個解釋和library(double_quotes)。