prolog - 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).

?

谢谢!

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将致力于与火车的其余部分一起工作。