3

给定一个 CFG

S --> a S b | c | d

我想写一个谓词，如语法（'S'，句子），它产生所有可能的

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

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

我不想要任何代码......只是帮助我一些技巧如何开始

4

1 回答 1

8

让我们使用 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]：请参阅此答案以获得解释和library(double_quotes).

于 2011-11-30T20:57:25.380 回答