英语约束免费语法序言

Question

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

这是我的规则:(vp - >动词短语,np - >名词短语,ap - > adj短语,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],因为它会首先将左侧"红色"上的形容词短语扩展为无限可能性,然后再尝试对.

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

Answer 1

简短的回答是:使用Definite Clause Grammars(dcg)来表示你的语法.有关典型编码,请参阅此答案.

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

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) :- false, member(S, [block, table]).
prep(S) :- member(S, [on, from]).

vp([V|R]) :- verb(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, noun(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递归的,但不受实际输入的限制.有关更多示例,请参阅failure-slice.

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