parsing - 在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规则说：如果（1）我可以消费X并留下Y，并且列表对X和Y表示名词短语，并且（2），则我知道列表X和Z对表示一个句子。然后，我可以继续消耗Y并将Z留在后面，而YZ对则表示动词短语。 np规则和第二条vp规则的工作方式相似。


和


将第一个列表想像成需要消耗的东西（或者，如果您喜欢：input list），将第二个列表想像成我们应该留下的东西（或：output list）。从（程序上的）角度来看，差异列表

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

代表一个女人向男人开枪的句子，因为它说：如果我用掉左边的所有符号，而在右边留下符号，那么我就有我感兴趣的句子。也就是说，我们感兴趣的句子是这两个列表的内容之间的区别。

这就是我们需要了解的差异列表以重写我们的识别器的全部内容。如果我们只是简单地记住消费某物的想法，而忘记了某些东西，那么我们将获得以下识别器：


作为一种解释，但这只是做任何事情都无法向我澄清此代码。我知道它比使用 append/3效率更高，但是就消耗事物和将其他事物抛在后面的概念而言，它似乎比以前的 append/3实现更令人困惑，而且我只是做不到任何事情。此外，当我将该代码复制并粘贴到 Prolog visualizer中以尝试理解它时，可视化工具会指出存在错误。有人能对此有所启示吗？

Answer 1

列为事实

让我们尝试通过一个反例对此进行解释。让我们用简单的事实指定名词，动词等：

det(the). 
det(a). 

n(woman). 
n(man). 

v(shoots).

现在我们可以将名词短语 np实现为：

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

换句话说，我们说“名词短语是一个有两个单词的句子，第一个是 det，第二个是 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).

因此，这意味着如果查询一个设置： [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).

然后再次调用 [the,woman,shoots,...]，它将查询与该列表统一的 X。它将首先调用将消耗 det的 the，而无需回溯。下一个 Y等于 [woman,shoots,...]，现在 n/2将消耗女人并返回 [shoots,...]。这也是 np将返回的结果，另一个谓词将必须使用它。

用处

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

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

（很抱歉，使用小写字母，否则Prolog会将其视为变量）。

它只会尝试将前两个单词与 doug和 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]。它首先会消耗/食用 det中的，然后将寻找一个名词要从 [doug,smith,...]中消耗。有两个候选人。 Prolog首先会尝试只吃 doug，并将 [smith,shoots,...]作为整个动词短语匹配，但是由于 smith不是动词，它将回溯，重新考虑只吃一个单词，因此决定同时吃两个 doug和 smith作为名词。

关键是，使用添加时，Prolog也必须回溯。

结论

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