Prolog如何将DCG规则转换为明确的条款？

Question

我正在研究Definite Clause Grammar,但我有一些问题需要理解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将用于处理其余的车辆.培养.