这个问题是关于如何在Prolog中使用差分列表的上下文无关文法，它是如何工作的？

Question

这个问题是关于如何在Prolog中使用差分列表的上下文无关文法，它是如何工作的？

parsingprologdcglogic-programmingdifference-lists

9

我正在阅读一篇关于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)然后我可以继续消耗Y并留下Z，且Y和Z表示动词短语，则X和Z表示句子。np规则和第二个vp规则类似。

以及

Think of the first list as what needs to be consumed (or if you prefer: the input list ), and the second list as what we should leave behind (or: the output list ). Viewed from this (rather procedural) perspective the difference list
[a,woman,shoots,a,man]  [].
represents the sentence a woman shoots a man because it says: If I consume all the symbols on the left, and leave behind the symbols on the right, then I have the sentence I am interested in. That is, the sentence we are interested in is the difference between the contents of these two lists.

That’s all we need to know about difference lists to rewrite our recogniser. If we simply bear in mind the idea of consuming something, and leaving something behind in mind, we obtain the following recogniser:

作为解释，但对我来说并没有澄清这段代码的含义。我知道使用它比使用append/3更有效率，但关于消耗一些东西并留下其他东西的概念，似乎比之前的append/3实现更加混乱，我无法理解。此外，当我将该代码复制并粘贴到Prolog可视化工具中以尝试理解时，可视化工具会显示错误。有人能够解释一下吗？

- Doug Smith

1

可视化工具提示需要输入查询语句。您在输入代码时是否已经输入了查询语句？代码中并没有包含查询语句，您需要手动输入查询语句。例如，在输入代码后，您可以尝试使用查询语句s([a,woman,shoots,a,man], X)?。 - lurker

1

说实话，这是一个非常棒的区别列表解释。 - vmg

1

@false：你说的“科学十年未得”的意思是什么？ - Willem Van Onsem

1

感谢提供 Prolog 可视化工具的链接！ - CapelliC

1

@CommuSoft：大约十年来，人们一直怀疑逻辑和语法形式之间的关系。毫不明显的是如何使用定理证明来高效地解析文本（即对于无歧义的语法是线性的）。正是Colmerauer的贡献使得这种特定编码得以理解。从记忆中，Cohen关于Prolog的历史，以及Kowalsky的描述都强调了这一方面。 - false

显示剩余2条评论

4个回答

2

这个答案是对@mat的答案的跟进。让我们一步一步来：

我们从 @mat 的答案中给出的代码开始：

s --> np, vp.

np --> det, n.

vp --> v, np. vp --> v.

det --> [the]. det --> [a].

n --> [woman]. n --> [man].

v --> [shoots]。

到目前为止，我们使用了 (',')/2： (A,B) 表示 序列 A 后跟序列 B。

接下来，我们还将使用 ('|')/2： (A|B) 表示 序列 A 或序列 B。

有关语法主体中控制结构的信息请阅读此手册章节。

s --> np, vp.

np --> det, n.

vp --> v, np | v.

det --> [the] | [a].

n --> [woman] | [man].

v --> [shoots]。

我们可以通过“内联”一些内容使代码更加简洁：

s --> np, vp.

np --> ([the] | [a]), ([woman] | [man]).

vp --> v,np | v.

v --> [shoots]。

如何进行更多的内联 - 如 @mat 在他的评论中建议的那样...

s --> np, [shoots], (np | []).

np --> ([the] | [a]), ([woman] | [man])。

把它发挥到极致！（以下可以写成一行。）

不同的表达方式都有其优点和缺点，例如，非常紧凑的代码更难扩展，但在空间有限的情况下可能是必需的——比如将代码放在演示文稿上。

示例查询：

?- phrase(s,Ws).
  Ws = [the, woman, shoots, the, woman]
; Ws = [the, woman, shoots, the, man]
; Ws = [the, woman, shoots, a, woman]
; Ws = [the, woman, shoots, a, man]
; Ws = [the, woman, shoots]
; Ws = [the, man, shoots, the, woman]
; Ws = [the, man, shoots, the, man]
; Ws = [the, man, shoots, a, woman]
; Ws = [the, man, shoots, a, man]
; Ws = [the, man, shoots]
; Ws = [a, woman, shoots, the, woman]
; Ws = [a, woman, shoots, the, man]
; Ws = [a, woman, shoots, a, woman]
; Ws = [a, woman, shoots, a, man]
; Ws = [a, woman, shoots]
; Ws = [a, man, shoots, the, woman]
; Ws = [a, man, shoots, the, man]
; Ws = [a, man, shoots, a, woman]
; Ws = [a, man, shoots, a, man]
; Ws = [a, man, shoots].                  % 20 solutions

- repeat

1

不错 (+1)，但如果我在做的话，我也会将其缩短为 vp --> [shoots], ( np | [] ). 并完全省略最后一个从句。更进一步，我会将其写成 s --> np, [shoots], (np | []). 并完全省略 then 最后一个从句，最终只剩下两个从句。 - mat

@mat。没错！我有点模糊了，所以我实际上认为vp是递归的（当然这是虚假的，我应该看穿它）。那么...为什么不将(-->)/2引入为第二步，并首先“仅”引入phrase/2，在phrase的上下文中演示,和|。然后将所有内容放入某个phrase目标的第一个参数中，无需任何新的语法规则即可运行查询？ - repeat

1

我知道你的意思。一开始以列表差异的方式思考确实有点难。好消息是，在像你这样的情况下，通常是不必这样做的。

有一种内置形式叫做确定性子句语法（DCGs），它使得在像你这样的情况下手动编码列表差异变得完全不必要。

在你的例子中，我建议你只需简单地写成：

s --> np, vp.

np --> det, n.

vp --> v, np.
vp --> v.

det --> [the].
det --> [a].

n --> [woman].
n --> [man].

v --> [shoots].

请接受在DCG中，[T]代表终端T，,表示“然后”的事实。这就是用DCG描述列表的方法。

您已经可以使用phrase/2接口来请求所有解决方案：

?- phrase(s, Ls).
Ls = [the, woman, shoots, the, woman] ;
Ls = [the, woman, shoots, the, man] ;
Ls = [the, woman, shoots, a, woman] ;
etc.

一开始以过程化术语理解可能有些困难，因此建议您不要尝试这样做。相反，着重于对语法的声明性阅读，并了解它描述了列表。

稍后，您可以进入更多的实现细节。从简单终端如何翻译开始，然后转向更高级的语法结构：包含单个终端的规则，然后是包含终端和非终端的规则等。

- mat

1

差异列表的工作方式如下（一个外行人的解释）。

考虑append用于连接两个列车X和Y。

X = {1}[2][3][4]     Y = {a}[b][c]

{ } - 代表装有引擎或头部的车厢。

[ ] - 代表尾部的车厢或元素。假设我们可以将引擎从一个车厢中取出并放入另一个车厢中。

附加操作如下：新的火车 Z 现在是 Y，即 {a}[b][c]，然后从 Z 的头部移除引擎并放入尾部车厢中，从 X 中移除该车厢，新的火车 Z 是：

Z = {4}[a][b][c]

相同的过程被重复执行。

Z = {3}[4][a][b][c]
Z = {2}[3][4][a][b][c]
Z = {1}[2][[3][4][a][b][c]

我们的新长火车。

引入差异列表就像在X的末尾有一个可以轻松固定到Y的千斤顶。最终的千斤顶被丢弃。

n([man|W],W).

"

W是关键，将W与后继列表的头部统一是加固过程。

"

- Vikram Venkat

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

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

- Willem Van Onsem · Accepted Answer

列举事实

让我们通过一个反例来解释这个概念。我们用简单的事实来说明名词、动词等：

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可以提供关于它真正想要的句子的信息。

此外，如果你必须将句子分成三个部分，这样做的方式数量甚至增加到O(n^2)等级。因此，猜测不起作用。

你也可以尝试生成一个随机动词短语，然后希望它与原句匹配：

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

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

解决方案

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

predicate(Subsentence,Remaining)

子句是以谓语为开头的单词列表。例如，对于名词短语，它可能看起来像[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中的“the”，然后从[doug,smith,...]中查找一个名词来消耗。有两个候选人。Prolog将首先尝试仅吃掉doug，并将[smith,shoots,...]作为整个动词短语匹配，但由于smith不是动词，它将回溯，重新考虑仅吃掉一个单词，因此决定将doug和smith都作为名词而非动词来消耗。

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

结论

通过使用差分列表，您可以消耗任意数量的单词。剩余部分被返回，使得其他句子部分（如动词短语）旨在消耗剩余部分。该列表还始终完全搞定，因此绝对不会使用蛮力方法先生成各种动词短语。