3

我有这个代码

s(W) :- append(W1,W2,W), np(W1), vp(W2).

vp(W) :- append(W1,W2,W), v(W1), np(W2).

np(W) :-
   (  append(W1,W2,W), pn(W1), ph(W2)
   ;  append(W1,W2,W), det(W1), n(W2)
   ).

pn([hans]).

ph([]).

v([beobachtet]).

n([mann]).
n([fernrohr]).

p([mit]).

det([den]).
det([dem]).

当我投射类似的东西np(X). vp(X).或pp(X)得到一个可能的解析然后出现堆栈错误时。当我投射时，s(X).我什至没有得到解析。我知道这是因为有一些无限循环正在运行，但我无法指出它在哪一点被循环。我认为这可能会发生，因为我的所有变量都使用相同的名称，但后来我将它们更改为单独的，它没有改变任何东西。

有人有提示吗？

提前致谢！

4

2 回答 2

4

出栈原因

让我们看看您的代码中的以下行：

vp(W) :- append(W1,W2,W), v(W1), np(W2).

单独运行append(W1, W2, W)会得到以下结果：

?- append(W1, W2, W).
W1 = [],
W2 = W ;
W1 = [_G1108],
W = [_G1108|W2] ;
W1 = [_G1108, _G1114],
W = [_G1108, _G1114|W2] ;
W1 = [_G1108, _G1114, _G1120],
W = [_G1108, _G1114, _G1120|W2] .

如您所见，W1是一个增加长度的列表。只有长度为 1 才给出解决方案（因为v(W1)）。在第一次实例化之后，W1变得越来越长，并且......，但v(W1)对于更长的列表将不会成功。

DCG语法

在 Prolog 中，您可以使用 DCG 表示法来创建语法。您的语法如下所示：

s --> np, vp.
np --> pn.
np --> det, n.
vp --> v, np.

det --> [den].
det --> [dem].

n --> [mann].
n --> [fernrohr].

pn --> [hans].

v --> [beobachtet].

使用示例

?- phrase(s, S).
S = [hans, beobachtet, hans] ;
S = [hans, beobachtet, den, mann] ;
S = [hans, beobachtet, den, fernrohr] ;
S = [hans, beobachtet, dem, mann] ;
S = [hans, beobachtet, dem, fernrohr] ;
S = [den, mann, beobachtet, hans] ;
S = [den, mann, beobachtet, den, mann] ;
S = [den, mann, beobachtet, den, fernrohr] ;
S = [den, mann, beobachtet, dem, mann] ;
S = [den, mann, beobachtet, dem, fernrohr] ;
S = [den, fernrohr, beobachtet, hans] ;
S = [den, fernrohr, beobachtet, den, mann] ;
S = [den, fernrohr, beobachtet, den, fernrohr] ;
S = [den, fernrohr, beobachtet, dem, mann] ;
S = [den, fernrohr, beobachtet, dem, fernrohr] ;
S = [dem, mann, beobachtet, hans] ;
S = [dem, mann, beobachtet, den, mann] ;
S = [dem, mann, beobachtet, den, fernrohr] ;
S = [dem, mann, beobachtet, dem, mann] ;
S = [dem, mann, beobachtet, dem, fernrohr] ;
S = [dem, fernrohr, beobachtet, hans] ;
S = [dem, fernrohr, beobachtet, den, mann] ;
S = [dem, fernrohr, beobachtet, den, fernrohr] ;
S = [dem, fernrohr, beobachtet, dem, mann] ;
S = [dem, fernrohr, beobachtet, dem, fernrohr].
于 2014-10-24T21:11:27.457 回答
4

在 Prolog 中，不终止通常有点难以理解。以查询为例pn(X)。显然，应该有：

W = [hans] ;
W = [den, mann] ;
W = [den, fernrohr] ;
W = [dem, mann] ;
W = [dem, fernrohr].

作为解决方案，（不管[den, fernrohr]不是德国人）。但是 Prolog 只找到一个，然后循环。从某种意义上说，您可以认为自己很高兴，因为您很早就发现了这个问题。但是想象一下在循环之前有很多答案的情况。所以你的印象是一切都很好，但事实并非如此。

要更快地找到这些问题，请pn(X), false改为询问。虽然这个查询永远不会是真的，它会以完全相同的方式终止，pn(X)但它不会产生所有那些令人讨厌的解决方案。

您甚至可以通过插入程序更进一步false，生成的程序称为故障片。对于您的纯单调程序，以下内容成立：

如果失败切片没有终止（针对特定查询） ，则原始程序不会针对该查询终止。

故障片通常要短得多，因此它们可以更快地阅读和理解。如果是np(X)

?- np(X),假。

np（W）：-
   （附加（W1，W2，W），假，   pn（W1），ph（W2） 
   ；  假，附加（W1，W2，W），det（W1），n（W2）
   ）。

因此，您不再需要浪费时间搜索pn/1、ph/1、det/1或n/1for 循环。仅上述故障片就已经产生了非终止。因此：只要这个问题没有得到解决，查看剩下的程序是没有意义的。

一个直接的解决方法是放在append/3最后。这适用于np/1. 但它不适用于具有固定长度列表的递归非终结符。

在 Prolog 诞生之前，人们确实考虑过这种编码。他们对这种不匹配感到困惑：语法和谓词逻辑都是声明性形式。但是，虽然许多语法可以非常有效地解析，但证明一个句子是由语法描述的似乎意味着一个巨大的搜索空间。在这里使用逻辑的有效方法在哪里？

答案是一种特殊的编码，它允许解析简单语法的效率与手写解析器一样有效，从而产生了 Prolog。迄今为止，这种编码在 Prolog 中用于实现定句语法。请参阅@WouterBeeks 的回答如何做到这一点。

于 2014-10-25T12:05:58.960 回答