Prolog recursion grammar

Tag: recursion , prolog , artificial-intelligence , logic , dcg Author: teresa777 Date: 2012-04-15

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

please provide some encoding (EBNF) of the grammar you want to implement or some examples of input/output. btw: check definite clause grammars, they will simplify the code and avoid a lot of boilerplate

Other Answer1

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(X), Xs).
X = s(np(det(a),n(program),rel(epsilon)),vp(tv(writes),np(det(a),n(program),rel(epsilon)))),
Xs = [a,program,writes,a,program] ;
X = 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(X), Xs).
Xs = [terry,halts],
N = 2,
X = s(np(pn(terry)),vp(iv(halts))) ;
Xs = [shrdlu,halts],
N = 2,
X = s(np(pn(shrdlu)),vp(iv(halts))) ;
Xs = [a,program,halts],
N = 3,
X = s(np(det(a),n(program),rel(epsilon)),vp(iv(halts))) ;
Xs = [terry,writes,terry],
N = 3,
X = s(np(pn(terry)),vp(tv(writes),np(pn(terry)))) ;
Xs = [terry,writes,shrdlu],
N = 3,
X = s(np(pn(terry)),vp(tv(writes),np(pn(shrdlu)))) ;
Xs = [shrdlu,writes,terry],
N = 3,
X = s(np(pn(shrdlu)),vp(tv(writes),np(pn(terry)))) ...

comments:

is there now way to recurse from np2 to nounphrase at all? cos I know thats all I need for it to work. Thank you
@JohnLam: There are a lot of problems in your program. The biggest one: that you do not use DCGs. Also, it is by not evident what exactly you want. Take above code and modify it to your needs.
I know that np2 is wrong and that I am not using DCG. What I want is in np2 I want to call noun_phrase again so I can go through it again.
@JohnLam: You need to state what you want to describe in the grammar - give examples - I assumed something in the line of above grammar - but from your code I really cannot tell what you actually want. My only clue was that it looks a bit like a typical simplistic English grammar.