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

和

将第一个列表视为需要使用的内容（或者如果您愿意：输入列表），将第二个列表视为我们应该留下的内容（或：输出列表）。从这个（相当程序）的角度来看，差异列表

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

代表一个女人射杀一个男人的句子，因为它说：如果我把左边的符号都吃光了，把右边的符号都留下了，那么我就有了我感兴趣的句子。也就是我们感兴趣的句子是这两个列表内容的区别。

这就是我们需要知道的关于重写我们的识别器的差异列表的全部内容。如果我们简单地记住消费某物并留下某物的想法，我们将获得以下识别器：

作为解释，但这并没有做任何事情来向我澄清这段代码。我知道它比 using 更有效append/3，但至于消耗事物并将其他事物抛在后面的概念，它似乎比以前的append/3实现更令人困惑，我就是无法理解它。此外，当我将该代码复制并粘贴到Prolog 可视化器中以尝试理解它时，可视化器说有错误。任何人都可以对此有所了解吗？

4

4 回答 4

7

作为事实列出

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

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对 only 感到满意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，然后它会寻找一个名词来消费[doug,smith,...]。有两个候选人。Prolog 将首先尝试只吃doug，并匹配[smith,shoots,...]为一个完整的动词短语，但由于smith不是动词，它会回溯，重新考虑只吃一个词，因此决定同时吃两者doug和smith作为名词。

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

结论

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

于 2015-05-13T00:16:07.707 回答
2

这个答案是@mat 答案的后续。让我们一步一步进行：

  1. 我们从@mat 的答案中显示的代码开始：

    s --> np，副总裁。

np --> det，名词。

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

det --> [the]。
det --> [a]。

n --> [女人]。
n --> [人]。

v --> [射门]。

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

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

    有关语法主体中的控制结构的信息，请阅读本手册部分。

    s --> np，副总裁。

np --> det，名词。

vp --> v, np | 五。

det --> [该] | [一个]。

n --> [女人] | [男人]。

v --> [射门]。

  3. 我们可以通过“内联”一点使代码更简洁：

    s --> np，副总裁。

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

vp --> v,np | 五。

v --> [射门]。

  4. 更多内联怎么样——正如@mat 在他的评论中所建议的那样......

    s --> np, [芽], (np | [])。

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

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

    ?- 短语((( [the]
           | [一个女人]
                   | [人]), [射门], ( ( [the]
                                         | [一个女人]
                                                 | [男人]）
                                       | [])),
          WS）。

不同的公式都有其优点/缺点，例如，非常紧凑的代码难以扩展，但在空间稀缺时可能需要 - 例如将代码放在演示幻灯片上时。

示例查询：

?- 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
于 2015-09-28T21:16:50.663 回答
1

Difference lists work like this ( a layman's explanation).

Consider append is used to join two trains X and Y

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

{ } - represents the compartment having the engine or head.

[ ] - represents compartments or elements in the tail. Assume that we can remove the engine from one compartment and put it into another.

Append proceeds like this: The new train Z is now Y i.e., {a}[b][c] next the engine is removed from Z's head and put into tail end compartment removed from X and the new train Z is:

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

The same process is repeated 

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

our new long train.

Introducing Difference lists is like having a toa hook at the end of X that can readily fasten to Y. The final hook is discarded. 

n([man|W],W).

W is the hook here, unification of W with the head of the successor list is the fastening process.

于 2015-07-04T07:27:38.223 回答
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/2DCG 的接口：

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

一开始很难从程序上理解这一点，所以我建议你不要尝试这个。相反，专注于语法的声明性阅读，并看到它描述了列表。

稍后，您可以了解更多实施细节。从简单终结符的翻译方式开始，然后转向更高级的语法结构：包含单个终结符的规则，然后是包含终结符和非终结符的规则等。

于 2015-09-28T20:07:56.083 回答