无约束语法Prolog

Question

无约束语法Prolog

prologinfinite-loopdcgleft-recursionfailure-slice

4

在尝试在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 = [放, 红色, 块, 在, 绿色, 块, 上]，因为它将首先扩展左侧的形容词短语“红色”到无限可能性，然后才会在右侧进行尝试。

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

- Khodeir

5

我想您的意思是无上下文语法。 - Daniel Lyons

3个回答

1

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

- CapelliC

0

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

这基本上只是迭代加深。如果您使用SWI-PL，则还可以使用call_with_depth_limit/3谓词，在不修改语法的情况下完成完全相同的操作。

- Kyle Dewey

1

这个问题涉及语法，其中输入列表可用于极大地限制搜索空间 - 通常降至最小线性情况。迭代加深一般来说是可以的，但是如果应用得不好，会导致禁止的开销。 - false

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- false · Accepted Answer

简短回答是：使用确定性子句语法（dcg）来表示您的语法。请参见this answer以获得典型编码示例。

但现在针对你程序的实际问题，不仅无法获得所需答案; 情况更糟：即使在您的程序的更简单片段中，您仍将面临相同的问题。以下是最小的程序片段，它仍然不会终止：

动词(S) :- member(S, [放置, 拾取, 堆叠, 取下]).
冠词(S) :- member(S, [这]).
形容词(S) :- member(S, [大的, 小的, 绿色的, 红色的, 黄色的, 蓝色的]).
名词(S) :- false, member(S, [方块, 桌子]).
介词(S) :- member(S, [在, 从])。
动词短语([V|R]) :- 动词(V), 介词短语(PP), false, 名词短语(NP), append(NP, PP, R)。
名词短语([D, N]) :- false, 冠词(D), 名词(N)。
名词短语([D|R]) :- 冠词(D), 形容词短语(AP), false, 名词(N), append(AP, [N], R)。
形容词短语([A]) :- false, 形容词(A)。
形容词短语([A|R]) :- 形容词(A), 形容词短语(R), false。
介词短语([P|R]) :- 介词(P), 名词短语(R), false。
?- 动词短语([放置, 这, 红色的, 绿色的, 方块, 在, 这个方块上])。

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

修复程序并非易事，最简单的方法是使用语法规则。