parsing - Prolog 解析堆栈不足

Question

我有这个代码

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). 时，我什至没有得到解析。我知道这是因为有一些无限循环正在运行，但我只是无法指出它在哪一点循环。我认为可能会发生这种情况，因为我的所有变量都使用相同的名称，但后来我将它们更改为单独的名称，但它没有改变任何内容。

有人有提示吗？

提前致谢!

Answer 1

堆栈溢出原因

让我们看看代码中的以下行:

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].