处理序言上下文无关语法

Question

给定一个 CFG，

S --> a S b | c | d

生成所有可能的谓词

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

我想编写一个谓词，例如 grammar('S', Sentence) ，如果遇到的符号是 终结符，则使用最左推导 它应该打印出该终端，如果遇到的符号是非终端 'S'，它应该回溯并替换语法之一 a S b 或 c 或 d 并重复 过程。

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

Answer 1

让我们使用 DCG 按字面意思对语法进行编码！

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

?- phrase(s,Xs).
   loops. % 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]：请参阅此答案以获取解释并到 库(double_quotes)。