Prolog如何将DCG规则翻译成确定性子句？

Question

我正在学习确定性子句语法，但是我有些难以理解Prolog如何将DCG规则转换为确定性子句。 例如，这是一个小的DCG语法：

s --> np, vp.

np --> det, n.

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

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

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

v --> [kisses].

如果我提出这个问题：

?-listing(s).

它回答我说：

s(A,C) :- 
     np(A,B),
     vp(B,C).

这是什么意思？为什么有两个参数？

此外，“C”在这里是什么意思：

det(A,B) :-
    'C'(A,the,B).

?

Thank you!

- s.dallapalma

---

你在哪里看到了'C'(A,the,B)？当我尝试时，你原始DCG源代码的列表中并没有显示det/2的定义。但是直接回答这个问题，'C'是一个原子，所以'C'(A,the,B)是对名为'C'的谓词进行调用，它有三个参数：A（变量），the（原子）和B（变量）。s(A,C)有两个参数，因为Prolog在内部添加了一个差分列表参数，这是它实现DCG的方式。通常使用phrase(s, L)调用DCG。 - lurker

我读到有时候Prolog实现会将规则翻译成这样： det --> [the]. 不是 det([the|W],W). 而是 det(A,B) :- 'C'(A,the,B)。 - s.dallapalma

好的，很有趣。就像其他原子一样，'C'是一个原子，所以它只是谓词的名称，没有特殊意义。如果你愿意的话，你甚至可以把一个谓词命名为'This is my awesome predicate'(X, Y)。 :) - lurker

也许这个问题能帮到你？ - Willem Van Onsem

非常感谢您的回答 :)，但我仍然对s(A,C)的工作方式存有疑虑 :/ - s.dallapalma

@CommuSoft，感谢您提供的链接。我注意到这是同一个例子。但是，正如我之前提到的，我对s（A，C）的工作原理以及一般情况下为什么会这样很感兴趣。 - s.dallapalma

Answer 1

dcg 使用了一个叫做差异列表的概念。假设你想要进行解析（你也可以使用这些谓词生成列表，但暂时不考虑这点）。

如果你解析一个列表，比如[the,man,kisses,the,woman]。你可以把它看作是一个单词火车，我从@Vikramnath Venkatasubramani那里“借”了这个比喻，所以感谢他/她。现在如果我们调用s([the,man,kisses,the,woman],C)，C会返回 []。

每个谓词都会断开零个、一个或多个车厢。因此，在以下情况下：

s(A,C) :-
    np(A,B),
    vp(B,C).

np/2将断开车厢[the,man]，导致它仍然存储剩余的火车B=[kisses,the,woman]。现在vp/2将断开所有剩余的车厢，结果是C=[]，一个空火车。

这是如何实现的

让我们考虑语法的部分实现。

s(A,C) :-
    np(A,B),
    vp(B,C).

np(A,B) :-
    det(A,D),
    n(D,B).

vp(B,C) :-
    v(B,E),
    np(E,C).
vp(B,C) :-
    v(B,C).

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

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

v([kisses|W],W).

正如之前所说的，你调用np([the,man,kisses,the,woman],B)，np/2将必须断开形成名词短语的车厢：[the,man]。

np/2接着调用det/2和n/2。现在det/2将断开决定词：the，而n/2将断开名词man，以使其更加明确：

np([the,man,kisses,the,woman],[kisses,the,woman]) :-
    det([the,man,kisses,the,woman],[man,kisses,the,woman]),
    n([man,kisses,the,woman],[kisses,the,woman]).

现在，det/2 不再转移其职责，它被实现为：

det([the|W],W).

现在，如果我们进行模式匹配，这将会归结为：

det([the,man,kisses,the,woman],[man,kisses,the,woman]).

这意味着它已经断开了the。

使用这种方法的优点是，断开连接可以在常量时间内完成。实际上，谓词不知道列表的整个尾部。

此外，它还允许在事实中断开多个单词。例如，假设您将自己的姓名添加为名词：

n([s,dallapalma|W],W).

在这种情况下，n/2 将同时断开两节车厢。其他谓词不需要意识到这一点，例如 s/2 不必决定它在哪个位置将火车分割成 np/2 和 vp/2 之间的部分：它让 np/2 断开它想要的所有车厢，并且 vp/2 将努力处理火车的其余部分。

- Willem Van Onsem