prolog - 处理序言上下文无关语法

Question

给定 CFG

S --> a S b | c | d

我想写一个谓词，例如grammar('S', Sentence)，它会生成所有可能的

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

使用最左推导，如果遇到的符号是终端，它应该打印出该终端，如果遇到的符号是非终端 'S'，它应该回溯并替换语法a S b或c或d之一，并重复该过程。

我不需要任何代码...只需帮助我一些如何开始的提示

Answer 1

让我们使用 DCG 对语法进行字面编码!

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

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

看来这个查询没有终止。 IE。 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) .