处理序言上下文无关文法

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)。