prologdcg

Prolog recursion grammar


at the moment I am having a problem with looping back to noun_phrase from np2. I was wondering if someone can help me loop back to noun_phrase. Here is some code:

noun_phrase([X|T],(det(X), NP2),Rem):-
   det(X),
   np2(T,NP2,Rem).

np2([H|T],np2(adj(H),Rest),NP) :-
   adj(H),
   np2(T,Rest,Rem),
   noun_phrase(NP,Rem,_).

I want to loop from np2 back to noun_phrase. I think the code for np2 is wrong as I just hacked it together.


Solution

  • Encoding a grammar directly in Prolog is a quite cumbersome process. Yes, you can do this, but if you just started to learn Prolog you are not in the best position. In fact, it took science many years to come up with a particularly efficient encoding – and when this encoding was understood, Prolog was born!

    What you need are grammars – definite clause grammars . Don't try to understand their encoding in Prolog (now), simply get used to them with phrase/2!

    Here is Program 3.11 from Prolog and Natural-Language Analysis by Fernando C. N. Pereira and Stuart M. Shieber. Pereira designed the very style of DCG rules we are using today. This book is one of the most undervalued Prologbooks. And it's free!

    s(s(NP,VP)) --> np(NP), vp(VP).
    
    np(np(Det,N,Rel)) -->
       det(Det),
       n(N),
       optrel(Rel).
    np(np(PN)) --> pn(PN).
    
    vp(vp(TV,NP)) --> tv(TV), np(NP).
    vp(vp(IV)) --> iv(IV).
    
    optrel(rel(epsilon)) --> [].
    optrel(rel(that,VP)) --> [that], vp(VP).
    
    pn(pn(terry)) --> [terry].
    pn(pn(shrdlu)) --> [shrdlu].
    
    iv(iv(halts)) --> [halts].
    
    det(det(a)) --> [a].
    
    n(n(program)) --> [program].
    
    tv(tv(writes)) --> [writes].
    

    If you want to represent the dictionaries as Prolog facts, use in place of

    n(n(program)) --> [program].
    

    rather

    n(n(W)) --> [W],{noun(W)}.
    
    noun(program).
    

    So, let's use it:

    ?- phrase(s(P), Xs).
       P = s(np(det(a),n(program),rel(epsilon)),vp(tv(writes),np(det(a),n(program),rel(epsilon)))),
       Xs = [a,program,writes,a,program]
    ;  P = s(np(det(a),n(program),rel(epsilon)),vp(tv(writes),np(det(a),n(program),rel(that,vp(tv(writes),np(det(a),n(program),rel(epsilon))))))),
       Xs = [a,program,writes,a,program,that,writes,a,program]
    ;  ... .
    

    What a self-referential discourse! But now, all sentences by length which is a bit more edifying:

    ?- length(Xs, N), phrase(s(P), Xs).
       Xs = [terry,halts], N = 2, P = s(np(pn(terry)),vp(iv(halts)))
    ;  Xs = [shrdlu,halts], N = 2, P = s(np(pn(shrdlu)),vp(iv(halts)))
    ;  Xs = [a,program,halts], N = 3, P = s(np(det(a),n(program),rel(epsilon)),vp(iv(halts)))
    ;  Xs = [terry,writes,terry], N = 3, P = s(np(pn(terry)),vp(tv(writes),np(pn(terry))))
    ;  Xs = [terry,writes,shrdlu], N = 3, P = s(np(pn(terry)),vp(tv(writes),np(pn(shrdlu))))
    ;  Xs = [shrdlu,writes,terry], N = 3, P = s(np(pn(shrdlu)),vp(tv(writes),np(pn(terry))))
    ;  ... .