6

我想用 DCGs 作为发电机。截至目前，语法是

s-->a,b.
a-->[].
a-->a,c.
c-->[t1].
c-->[t2].
b-->[t3].
b-->[t4].

我想生成所有s长度a为< someNumber.

使用?- phrase(a,X),length(X,Y),Y<4.i 可以得到 a少于 4 个项目的所有项目。但是，当所有组合都用尽时，系统 (SWI-Prolog 6.2.5) 似乎停止运行。以前，这里也有人问过类似的问题。但是，作为 Prolog 的新手，我无法使其与上述语法一起使用。有任何想法吗？

更新：（canrememberthename）有一条评论被删除了，不知何故。无论如何，建议使用between(1,4,Y),length(X,Y),phrase(a,X).设置限制。在将我的代码更改为之后，这很好用a-->c,a.

4

2 回答 2

5

进入 Prolog 的第一步通常有点困难。但你走在正确的轨道上：

目前，您的问题是您得到了一些预期的答案/解决方案，但随后系统停止；实际上，它处于无限循环中。你耐心地敲击就发现了SPACE。这可能适用于一小部分解决方案，但使用更大的解决方案会很乏味。想想看所有短于 20 的句子。

有一种简单的键盘和腕管友好方式来模拟击球空间：只需false在末尾添加一个目标，如下所示：

?- 短语(a,X),length(X,Y),Y<4, false。

Prolog 能回答这样一个问题吗？既然false在最后，Prolog 就没有太多选择：要么自己回答；要么自己回答false；或者它循环（或产生错误或产生一些副作用）。在这种情况下，它会循环。

false现在，我们可以通过在您的程序中添加更多目标来缩小问题范围。

?- 短语(a,X),length(X,Y), false , Y<4, false。
**循环**

为了使这更具可读性，我将只使用一个false目标并遍历查询的其余部分：

?- 短语(a,X),length(X,Y), false , Y<4。
**循环**

让我们进一步减少它：

?- 短语(a,X), false , length(X,Y),Y<4。
**循环**

他们都在循环！但是我们得到了一些有趣的见解：由于这些false修饰的查询不会终止，因此原始程序也不会终止。因此，当您查看查询时，第一个目标不会自行终止，因此整个查询也不会终止（有关更多信息，请参阅末尾的细则）。

因此：您必须以某种方式解决第一个目标！

我的第一次尝试是交换length和phrase：

?- 长度（X，Y），短语（a，X），Y<4。

这行得通吗？看看第一个循环的目标：

?- 长度（X，Y），假，短语（a，X），Y<4。

所以这又不会终止。

您必须再次更改程序：

?- between(1,3,Y), length(X,Y), false , phrase(a,X)。
错误的。

所以这就结束了。如果会出现终止问题，phrase(a,X)现在必须承担责任：

?- between(1,3,Y), length(X,Y), phrase(a,X), false。
**循环**

您可能很想查看实际答案：

?- 在（1,3,Y）之间，长度（X,Y），短语（a,X）。
Y = 1,
X = [t1] ;
Y = 1,
X = [t2] ;
错误：超出本地堆栈

您可能会得出结论，这种行为比您最初的定义更糟糕。毕竟，我们现在得到的答案比以前少了。但正是这种推理并不能帮助您改善终止：两者都具有相同的不正确性，您必须首先解决这个问题。因此，通过隐藏答案，您可以更好地专注于其余部分。false

但是为什么你的语法有问题？我们可以继续使用我们的技术来插入目标false以缩小范围。但这次在你的语法范围内。装饰有目标的程序false称为。

只是一个实用的评论：当我在你的程序中插入目标错误时，我将保存程序并输入makeSWI：这样程序会快速重新编译。

尝试了一下后，我得到了以下最小的故障片。请注意，在 DCG 中，false必须写为{false}.

?- between(1,3,Y)，长度(X,Y)，短语(a,X)，假

s--> {false} , a,b。

a-->[], {false}。
a-->a, {false} , c。

c--> {false}， [t1]。
c--> {false} , [t2]。

b--> {false}， [t3]。
b--> {false}， [t4]。

几乎你所有的代码库都属于false！所以你必须解决微小的可见剩余部分。在其他地方改变一些东西是没有意义的。这a --> a, ...必须改变！事实上，改变它来a --> c, s解决问题。

当初为什么要写a --> a, c.？我怀疑您想以公平的方式列举所有解决方案。新版本没有：

?- 短语（a，X）。
X = [] ;
X = [t1] ;
X = [t1, t1] ;
X = [t1, t1, t1] ;
X = [t1, t1, t1, t1] ;
X = [t1, t1, t1, t1, t1] ;
X = [t1, t1, t1, t1, t1, t1] ;
X = [t1, t1, t1, t1, t1, t1, t1] ...

这看起来非常吓人。事实上，它看起来是错误的。不是吗？但是不要让您对此感到困惑：我们这里有无限的句子集。所以 Prolog 唯一正确的反应是产生无限多的答案。因为，如果它们是有限的，就会丢失一些列表！但是，当然，您希望看到以公平的方式列举它们。要得到这个，只需写：

?- 长度（X，N），短语（a，X）。
X = [],
N = 0 ;
X = [t1]，
N = 1 ;
X = [t2]，
N = 1 ;
X = [t1, t1],
N = 2;
X = [t1, t2],
N = 2;
X = [t2, t1],
N = 2;
X = [t2, t2],
N = 2;
X = [t1, t1, t1],
N = 3 ...

这是 Prolog 程序中的一个要点：始终首先寻求最佳（可能）终止属性。并且不要看 Prolog 如何枚举答案的精确顺序。因为，如果一个程序具有更好的终止属性，那么使用它以公平的方式枚举所有解决方案几乎是微不足道的。但是：以公平的方式以终止为代价枚举无限多个解决方案的程序不能用于更有趣的情况。

精美印刷品
请参阅此答案。

于 2013-01-09T17:13:26.117 回答
2

the nonterminal a//0 is both left recursive and 'epsilon' (generate the empty sequence), and phrase/2 will loop immediately after the empty production.

You can solve your problem bounding list' length:

?- between(1,4,Y),length(X,Y),phrase(a,X).

and, as you have already done, removing the left recursion.

于 2013-01-09T15:47:15.517 回答