英语约束自由语法序言

Question

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

我的原则是:(vp ->动词短语，np ->名词短语，ap ->形容词短语，pp ->预备短语)

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

Answer 1

简短的回答是:使用定句语法(dcg)来表示语法。关于典型的编码，请参阅此答案。

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

<>之前动词(S):-成员(S，[放，取，叠，拆])。det(S):- member(S， [the])。adj(S):-成员(S，[大，小，绿，红，黄，蓝])。<年代>名词(s): - 假,成员(年代,[块,表])。prep(S):- member(S， [on, from])。副总裁([V | R]):——动词(V)、聚丙烯(pp), 假, <年代> np (np),附加(np、pp R) 。<年代> np ([D N]): - 假,侦破名词(N), (D) 。np ([D | R]):——侦破(D),美联社(ap), 假, <年代>名词(N),附加(美联社,[N], R) 。ap([A]):- false， adj(A)。ap([A|R]):- adj(A)， ap(R)， false。pp([P|R]):- prep(P)， np(R)， false。- vp([放，红，绿，块，on, the, block])。之前

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

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

Answer 2

看起来你在滥用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解析

Answer 3

根本问题是Prolog被定义为对规则进行DFS，所以当涉及到跨无限搜索空间(如您的情况)生成问题时，部分空间可能不会受到影响。一种与平台无关的修复方法是使用深度边界来扩展语法，并在每次递归调用时递减深度。当深度为0时，失败。通过使用重复查询(例如，vp(S, 1). vp(S, 2).)逐步增加深度，您可以保证状态空间的所有部分最终都会被触及。

这基本上只是迭代深化。如果您使用的是SWI-PL，您还可以使用call_with_depth_limit/3谓词来执行完全相同的操作，而无需修改语法。