How do Prolog translates DCG rules into definite clauses?

Question

I'm studying Definite Clause Grammar, but I have some problem to understand how Prolog translates DCG rules into definite clauses. For example, here's a little grammar written as DCG:

s --> np, vp.

np --> det, n.

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

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

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

v --> [kisses].

If I pose the query:

?-listing(s).

It answer to me with:

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

What does it mean? Why there are two arguments?

Also, what does 'C' mean here:

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

?

Thank you!

Answer 1

The dcg makes use of a concept called difference lists. Let's assume you want to do parsing (you can also generate lists with these predicates, but let's ignore that for now).

if you parse a list, like [the,man,kisses,the,woman]. You can see this as a train of words, I "borrowed" the train analogy from @Vikramnath Venkatasubramani, so credits to him/her. Now if we call s([the,man,kisses,the,woman],C). C will return [].

What happens is that at each predicate will disconnect zero, one or more wagons. So it means that in the case of:

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

np/2 will disconnect the wagons [the,man], resulting in the fact that it still stores the remaining train B=[kisses,the,woman]. Now the vp/2 will disconnect all the remaining wagons resulting in C=[], an empty train.

How is this implemented

Let's consider the implementation of part of the grammar.

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

So as said before, you call np([the,man,kisses,the,woman],B), and np/2 will have to disconnect the wagons that form the noun-phrase: [the,man].

np/2 on his turn calls det/2 and n/2. Now det/2 will disconnect the determiner: the, and n/2 will disconnect the noun man, so to make it more explicit:

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

Now det/2 no longer redirects its responsibilities, it is implemented as:

det([the|W],W).

Now in case we do pattern matching, this will ground to:

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

So this means it has disconnected the the.

The advantage of using this approach is that disconnecting can be done in constant time. Indeed, the predicate is not aware of the entire tail of the list.

Furthermore it would allow to disconnect multiple words in a fact. For instance say, you add your name as a noun:

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

in that case n/2 will disconnect two wagons at once. Other predicates do not need to be aware of this, nor does s/2 for instance have to decide at which point it splits the train between the np/2 and the vp/2: it lets np/2 disconnect as much wagons as it wants, and vp/2 will aim to work with the remainder of the train.