这个上下文无关语法如何使用Prolog功能中的差异列表？

Question

我正在阅读Prolog中关于上下文无关语法的本教程,他们在页面底部提到使用差异列表在Prolog中实现上下文无关语法,包括以下代码块:

s(X,Z):-  np(X,Y),  vp(Y,Z). 

np(X,Z):-  det(X,Y),  n(Y,Z). 

vp(X,Z):-    v(X,Y),  np(Y,Z). 
vp(X,Z):-    v(X,Z). 

det([the|W],W). 
det([a|W],W). 

n([woman|W],W). 
n([man|W],W). 

v([shoots|W],W).

它提到:

仔细考虑这些规则.例如,s规则说:我知道一对列表X和Z表示一个句子,如果(1)我可以消耗X并留下Y,而X和Y对代表一个名词短语,(2)然后我可以继续消耗Y而将Z留在后面,而YZ代表一个动词短语.np规则和第二个vp规则的工作方式类似.

和

将第一个列表视为需要消耗的内容(或者如果您愿意:输入列表),将第二个列表视为我们应该留下的内容(或:输出列表).从这个(相当程序上)的角度来看差异列表

[a,woman,shoots,a,man]  [].

代表一个女人射杀一个男人的句子,因为它说:如果我消耗左边的所有符号,并留下右边的符号,那么我就有我感兴趣的句子.也就是说,我们感兴趣的句子是这两个列表的内容之间的差异.

这就是我们需要知道的差异列表来重写我们的识别器.如果我们只是牢记消费某些东西的想法,并留下一些东西,我们会获得以下认知:

作为解释,但这只是没有做任何事情来澄清这段代码给我.我知道它比使用更有效append/3,但至于消费和留下其他人的概念,它似乎比以前的append/3实现更令人困惑,我只是无法做出正面或反面.此外,当我将该代码复制并粘贴到Prolog可视化工具中以试图理解它时,可视化工具表示存在错误.谁能对此有所了解？

Answer 1

列为事实

让我们试着用一个反例来解释这一点。让我们用简单的事实来指定名词、动词等：

det(the). 
det(a). 

n(woman). 
n(man). 

v(shoots).

现在我们可以实现一个名词短语 np：

np([X,Y]) :-
    det(X),
    n(Y).

换句话说，我们说“名词短语是一个有两个词的句子，第一个是 a det，第二个是 a n”。这将起作用：如果我们查询np([a,woman])，它将成功等。

但是现在我们需要做一些更高级的事情，定义动词短语。有两种可能的动词短语：一种带有动词和名词短语，最初定义为：

vp(X,Z):- v(X,Y),np(Y,Z).

我们可以将其定义为：

vp([X|Y]) :-
    v(X),
    np(Y).

还有一个只有一个动词：

vp(X,Z):- v(X,Z).

那可以转换成：

vp([X]) :-
    v(X).

猜测问题

然而，问题是这两种变体的词数不同：动词短语有一个词和三个词。这不是一个真正的问题，但现在说 - 我知道这不是正确的英语 - 存在一个定义为vp后跟的句子np，所以这将是：

s(X,Z):-  vp(X,Y),  np(Y,Z).

在原始语法中。

问题是，如果我们想把它转换成我们新的表示方式，我们需要知道vp会消耗多少（多少词会被 吃掉vp）。我们无法提前知道这一点：由于此时我们对句子了解不多，因此无法猜测是否vp会吃掉一个或三个词。

我们当然可以猜测单词的数量：

s([X|Y]) :-
    vp([X]),
    np(Y).
s([X,Y,Z|T]) :-
    vp([X,Y,Z]),
    np(Z).

但我希望你能想象，如果你用 1、3、5 和 7 个词来定义动词短语，事情就会变得有问题。解决此问题的另一种方法是将其留给 Prolog：

s(S) :-
    append(VP,NP,S),
    vp(VP),
    np(NP).

现在 Prolog 会先猜测如何将句子细分为两个部分，然后尝试匹配每个部分。但问题是对于一个有n 个单词的句子，有n 个断点。

例如，Prolog 首先将其拆分为：

VP=[],NP=[shoots,the,man,the,woman]

（记住我们交换了动词短语和名词短语的顺序）。vp如果它得到一个空字符串，显然不会很高兴。所以很容易被拒绝。但接下来它说：

VP=[shoots],NP=[the,man,the,woman]

现在vp只对 感到满意shoots，但需要一些计算工作才能实现这一点。np然而，对这么长的部分并不感兴趣。所以 Prolog 再次回溯：

VP=[shoots,the],NP=[man,the,woman]

现在vp会再次抱怨它已经给出了太多的话。最后 Prolog 将正确拆分它：

VP=[shoots,the,woman],NP=[the,woman]

关键是它需要大量的猜测。而对于这些猜测vp，并np需要正常工作。对于一个真正复杂的语法，vp并np可能进一步分裂产生了巨大的尝试和错误的量的句子。

真正的原因是append/3没有“语义”线索如何拆分句子，因此它尝试了所有可能性。然而，人们更感兴趣的是一种vp可以提供有关它真正想要的句子份额的信息的方法。

此外，如果您必须将句子分成 3 部分，那么这样做的方法的数量甚至会增加到O(n^2)等等。所以猜测是行不通的。

您也可以尝试生成一个随机动词短语，然后希望动词短语匹配：

s(S) :-
    vp(VP),
    append(VP,NP,S),
    np(NP).

但在这种情况下，猜测的动词短语的数量将呈指数级增长。当然你可以给出“提示”等来加快这个过程，但仍然需要一些时间。

解决方案

您想要做的是将句子的一部分提供给每个谓词，使谓词看起来像：

predicate(Subsentence,Remaining)

Subsentence是以该谓词开头的单词列表。例如，对于名词短语，它可能看起来像[the,woman,shoots,the,man]。每一个谓语消耗它感兴趣的话：单词达到一定点。在这种情况下，名词短语只对 感兴趣['the','woman']，因为那是名词短语。为了做剩余的解析，它返回剩余的部分[shoots,the,woman]，希望其他一些谓词可以消耗句子的剩余部分。

对于我们简单的事实表：

det([the|W],W). 
det([a|W],W). 

n([woman|W],W). 
n([man|W],W). 

v([shoots|W],W).

因此，这意味着如果您查询 setence: [the,woman,shoots,...]，并询问它det/2是否是限定词，它会说：“是的，the是限定词，但其余部分[woman,shoots,...]”不是限定词的一部分，请将其与其他内容匹配。

这种匹配是因为一个列表被表示为一个链表。[the,woman,shoots,...], 实际上表示为[the|[woman|[shoots|...]]]（因此它指向下一个“子列表”）。如果你匹配：

    [the|[woman|[shoots|...]]]
det([the|W]                   ,W)

它会统一[woman|[shoots|...]]用W，从而导致：

det([the|[woman|[shoots|...]],[woman|[shoots|...]]).

因此返回剩余的列表，它因此消耗了the部分。

高级谓词

现在，如果我们定义名词短语：

np(X,Z):-  det(X,Y),  n(Y,Z).

我们再次调用 with [the,woman,shoots,...]，它将查询X与该列表的统一。它将首先调用det将消耗的the，无需任何回溯。接下来Y等于[woman,shoots,...]，现在的n/2消耗女人又回来了[shoots,...]。这也是np将返回的结果，另一个谓词将不得不使用它。

用处

假设您将您的名字作为附加名词介绍：

n([doug,smith|W],W).

（抱歉使用小案例，否则 Prolog 会将这些视为变量）。

它只会尝试将前两个单词与dougand匹配smith，如果成功，则尝试匹配句子的其余部分。所以你可以做一个像这样的句子：（[the,doug,smith,shoots,the,woman]对不起，而且在英语中，一些名词短语直接映射到名词，np(X,Y) :- n(X,Y)所以the可以删除更复杂的英语语法）。

猜测彻底消除？

猜测完全消除了吗？没有。在消费方面仍有可能存在重叠。例如，您可以添加：

n([doug,smith|W],W).
n([doug|W],W).

在这种情况下，如果您查询[the,doug,smith,shoots,the,woman]. 它将首先消耗/吃掉 in det，然后它会寻找一个名词来消耗 from [doug,smith,...]。有两个候选人。Prolog 将首先尝试只吃doug，并[smith,shoots,...]作为一个完整的动词短语匹配，但由于smith它不是动词，它会回溯，重新考虑只吃一个词，因此决定同时吃，doug并smith作为名词代替。

关键是在使用 append 时，Prolog 也必须回溯。

结论

通过使用差异列表，您可以吃任意数量的单词。返回余数，使得其他句子部分（如动词短语）旨在消耗余数。此外，该列表始终是完全有根据的，因此绝对不会首先使用蛮力生成各种动词短语。