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]。您可以将其视为 单词序列 ，我 "borrowed" 来自 @Vikramnath Venkatasubramani 的火车类比，因此归功于 him/her。现在如果我们调用 s([the,man,kisses,the,woman],C)。 C 将 return [].

发生的情况是，每个谓词都会断开零、一辆或多辆货车。所以这意味着在这种情况下：

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

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

How do Prolog translates DCG rules into definite clauses?

prolog

dcg