How does Prolog translate DCG rules to specific locations?

Question

I am studying the phrase “Specific Phrase”, but I have some problem to understand how Prolog translates DCG rules to specific positions. For example, here is a small 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 ask:

 ?-listing(s). 

He answers me:

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

What does it mean? Why are there two arguments?

Also, what does "C" mean:

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

?

Thanks!

Answer 1

dcg uses a concept called difference lists. Suppose you want to perform parsing (you can also create lists with these predicates, but this time ignore).

if you are parsing a list, for example [the,man,kisses,the,woman] . You can see this as a string of words, I “borrowed” train analogues from @Vikramnath Venkatasubramani , so for him. Now, if we call s([the,man,kisses,the,woman],C) . C will return [] .

What happens is that in each predicate zero, one or more cars will be disconnected. Thus, this means that in the case of:

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

np/2 will disable the [the,man] cars, as a result of which he will save the remaining train B=[kisses,the,woman] . Now vp/2 will disconnect all the remaining cars, as a result we get C=[] , an empty train.

How is it implemented

Consider the implementation of the grammar part.

 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 mentioned earlier, you call np([the,man,kisses,the,woman],B) , and np/2 must turn off the cars that make up the name phrase: [the,man] .

np/2 in turn calls det/2 and n/2 . Now det/2 will disable the: the qualifier, and n/2 will disable the man noun 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, if we match patterns, it will be grounded for:

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

So that means he turned off the .

The advantage of using this approach is that shutdown can be performed at a constant time. In fact, the predicate does not know the whole tail of the list.

In addition, this would disable a few words. For example, let's say you add your name as a noun:

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

in this case, n/2 immediately turn off two cars. Other predicates should not know about this, and s/2 , for example, should not decide at what point it breaks the train between np/2 and vp/2 : it allows np/2 disconnect as many cars as it wants, and vp/2 will seek to work with the rest of the train.