3

我正在尝试实现一个 dcg，它采用 {a,b,c,d}* 形式的一组字符串。我遇到的问题是，如果我有一个形式为 s([a,c,b], [])，它返回 true，这是正确的答案，但是当我有一个 s([a,c,f],[]) 形式的查询时，它不返回答案并且它用完了本地堆栈。

s --> [].
s --> s,num.
num --> [a].
num--> [b].
num--> [c].
num--> [d].
4

2 回答 2

9

利用phrase/2

让我们尝试phrase(s,[a,b,c])代替s([a,b,c],[]). 原因很简单：通过这种方式，我们清楚地表明我们使用的是 DCG ( ) 而不是普通的谓词。phrase/2是语法的“官方”接口。

所以你的第一个问题是为什么在“给出正确答案”phrase(s,[a,c,f])时不终止——正如你所说。phrase(s,[a,b,c])现在，这很容易回答：两者都不会终止！但phrase(s,[a,b,c])找到了解决方案/答案。

通用端接

这是要区分的两件事：如果您输入查询并得到类似trueor的答案X = a；您可能有兴趣获得更多。通常，您通过输入SPACE或;ENTER在顶层执行此操作。因此，只有在找到第一个或多个答案后，查询才可能开始循环。随着时间的推移，这变得相当混乱：你是否应该永远记住这个谓词可能会产生答案？另一个谓词产生两个，只有稍后才会循环？

最简单的出路是建立通用终止的概念，这是这里最强大的概念。AGoal终止当且仅当Goal, false终止。这个false目标对应于SPACE无限期击球；直到整个查询失败的那一刻。

所以现在尝试：

?- 短语（s，[a，c，f]），错误。
** 循环 **

但是也：

?- 短语（s，[a，b，c]），错误。
** 循环 **

从通用终止的角度来看，两个查询都不会终止。在最常用的词中，终止等同于普遍终止。找到答案或解决方案就是这样，但不是终止。因此，只要您对答案感到满意，有些查询看起来无害，但实际上不会终止。但是很高兴您这么快就发现了这一点：如果您仅在正在运行的应用程序中发现这一点，那就更糟了。

找出原因

作为下一步，让我们确定未终止的原因。您可能会尝试使用调试器或跟踪器，但很可能它根本不会给您一个很好的解释。但是有一个更简单的方法：使用。只需将非终结符添加{false}到您的语法中；并将目标false转化为谓词。我们可以在这里利用一个非常漂亮的属性：

如果故障片没有终止，则原始程序不会终止。

因此，如果我们很幸运并且找到了这样一个切片，那么我们肯定知道只有在剩余的可见部分以某种方式更改时才会发生终止。最有用的切片是：

?- 短语（s，[a，b，c]），假

s --> [], {false}。
s --> s, {false} , num。

您的程序所剩无几！没了num//0！没人在乎num//0。这意味着：num//0可以描述任何东西，无论如何——程序仍然会循环。

为了解决这个问题，我们必须改变可见部分的一些东西。所剩无几！正如您已经观察到的，我们这里有一个左递归。修复它的经典方法是：

重新制定语法

您可以轻松地将您的语法重新表述为正确的递归：

s --> []。
s --> 数量，s。

现在两个查询都终止了。这是编译器构造中的经典方式。

但是在某些情况下，语法的重新表述是不合适的。这个简单的例子不是这种类型的，但它经常出现在带有一些预期歧义的语法中。在这种情况下，您仍然可以：

添加终止诱导参数

?- Xs = [a,b,c], 短语(s(Xs,[]), Xs)。

s(Xs,Xs) --> []。
s([_|Xs0],Xs) --> s(Xs0,Xs1), 数量, {Xs1=Xs}。

固有的非终止查询

无论您做什么，请记住，并非每个查询都可以终止。如果你问： » 告诉我所有存在的自然数——真的是所有的，一个一个！« 那么回答这个问题的唯一方法就是从 0 开始，然后将它们数起来。所以有疑问，有无限的答案/解决方案，我们不能责怪可怜的 Prolog 试图实现我们的愿望。然而，在这种情况下，我们最喜欢的是以公平的方式列举所有的解决方案。我们可以使用具有良好终止属性的语法来做到这一点；也就是说，一种以固定长度列表终止的文法。像这样：

?- 长度（Xs，M），短语（s，Xs）。

有关如何应用失败切片的其他示例，请参阅标签。

于 2012-11-22T00:59:57.603 回答
0

我不知道这是否有帮助，因为我使用的序言似乎有一个非常不同的语法，但我只是编写了以下程序来尝试匹配你的程序，它工作正常。

程序

s([]).
s([X|Xs]) :- num(X), s(Xs).

num(a).
num(b).
num(c).
num(d).

输出

?- [prologdcg].
% prologdcg compiled 0.00 sec, 2,480 bytes
true.

?- s([a,c,b]).
true.

?- s([a,c,f]).
false.

使用 SWI-prolog 运行。

于 2012-11-22T00:06:30.663 回答