3

我在尝试在 prolog 中实现一个非常简单的无约束语法时遇到了一个无限递归问题。

这是我的规则：（vp -> 动词短语，np -> 名词短语，ap -> adj 短语，pp -> prep 短语）

    verb(S) :- member(S, [put,  pickup, stack, unstack]).
    det(S) :- member(S, [the]).
    adj(S) :- member(S, [big, small, green, red, yellow, blue]).
    noun(S) :- member(S, [block, table]).
    prep(S) :- member(S, [on, from]).

    vp([V|R]) :- verb(V), pp(PP), np(NP), append(NP, PP, R).
    np([D, N]) :- det(D), noun(N).
    np([D|R]) :- det(D), ap(AP), noun(N), append(AP, [N], R).
    ap([A]) :- adj(A).
    ap([A|R]) :- adj(A), ap(R).
    pp([P|R]) :- prep(P), np(R).

我遇到的问题是ap的规则可以产生任意长的形容词字符串，所以在某些时候，我会通过尝试所有这些无限的可能性来满足查询。

例如，下面的查询永远不会产生 S = [put, the, red, block, on, the, green, block] 因为它会首先将左侧“red”的形容词短语扩展为无限可能，然后再尝试使用正确的。

?- vp(S)
S = [put, the, red, green, block, on, the, block] ;
4

3 回答 3

5

简短的回答是：使用定句语法 ( ) 来表示您的语法。有关典型编码，请参见此答案。

但现在你的程序中的实际问题。你不仅不会得到想要的答案；情况更糟：即使在程序的一个更简单的片段中，您也会遇到同样的问题。这是您的程序中仍然没有终止的最小片段：

动词（S）：- 成员（S，[put，pickup，stack，unstack]）。
det(S) :- 成员(S, [the])。
adj(S) :- member(S, [big, small, green, red, yellow, blue])。
名词（S）：-假，成员（S，[块，表]）。
准备（S）：-成员（S，[on，from]）。

vp([V|R]) :- 动词(V), pp(PP), false , np(NP), append(NP, PP, R)。
np([D, N]) :- false , det(D), noun(N)。
np([D|R]) :- det(D), ap(AP), false ,名词(N), append(AP, [N], R)。
ap([A]) :- false， adj(A)。
ap([A|R]) :- adj(A), ap(R), false。
pp([P|R]) :- prep(P), np(R), false。

?- vp([put, the, red, green, block, on, the, block])。

通过插入目标false，我们得到了仍然没有终止的程序的一小部分。实际源是ap/1递归的，但不受实际输入的限制。有关更多示例，请参见。

没有简单的方法来修复您的程序。最简单的方法是使用语法。

于 2013-03-27T21:10:18.567 回答
0

基本问题是 Prolog 被定义为对规则进行 DFS，因此当涉及跨无限搜索空间（如您的情况）的生成问题时，部分空间可以保持不变。与平台无关的解决方法是通过深度限制来增加语法，并在每次递归调用时减少深度。一旦深度达到0，失败。通过重复查询（例如，vp(S, 1). vp(S, 2).）逐步增加深度，您可以保证状态空间的所有部分最终都会被触及。

这基本上只是迭代深化。如果你在 SWI-PL 上，你也可以使用call_with_depth_limit/3谓词来做同样的事情，而无需修改语法。

于 2014-06-23T06:38:59.880 回答
0

好像您在滥用 Prolog 生成能力，将 append 放在最后一个位置。我试图换一个更明智的地方：

...
vp([V|R]) :- verb(V), append(NP, PP, R), pp(PP), np(NP).
np([D, N]) :- det(D), noun(N).
np([D|R]) :- det(D), append(AP, [N], R), ap(AP), noun(N).
...

现在你的解析器显然可以工作了。

?- vp([put, the, red, green, block, on, the, block]).
true .

但我建议，就像已经错误的 (+1) 一样，切换到 DCG 进行解析。

于 2013-03-28T07:44:02.947 回答