Prolog how to eliminate left recursion

Question

I have written the DCG (Adjective phrase and prepositional phrase) in prolog, when I tried to run it, by entering ip([every,boy,loved,some,girl]), it shows out of local stack. I realised there is something wrong with the nbar. Can someone help me out? Many thanks.

 %tree
 treeP(Term):-
     % Print the tree assuming indentation 0
     treeP(0,Term),
     % Tidy up with linefeed
     nl.

 treeP(_N,Tree):-
     % Tree is just a variable
     var(Tree),!,
     write(Tree).

 treeP(N,[Tree|Trees]):-
     proper_list([Tree|Trees]),!,
     write('['),
     N1 is N+1,
     treePNEL(N1,[Tree|Trees]),
     write(']').

 treeP(N,Tree):-
     % Nonatomic case
     Tree=..[Functor,Argument|Arguments],
     !,
     % Write the functor and opening parenthesis
     write(Functor),write('('),
     % Set N1 to new indentation for arguments
     atom_length(Functor,M), N1 is N+M+1,
     % Pretty-print the arguments
     treePNEL(N1,[Argument|Arguments]),
     % Write right parenthesis
     write(')').

 treeP(_N,Tree):-
     % Noncompound case
     write(Tree).

 treePNEL(N,[Tree1,Tree2|Trees]):-
     treeP(N,Tree1),
     % Go to correct position for further printing
     nl, tab(N),
     treePNEL(N,[Tree2|Trees]).

 treePNEL(N,[Tree]):-
     treeP(N,Tree).

 ip(Sentence):-
     setof(IP,
             ip(IP,Sentence,[]),
             IP),
     treeP(IP).


ip(SSem) --> np(NPSem), ibar(IbarSem),
    {var_replace(NPSem,NPSem1),
     beta(NPSem1@IbarSem,SSem)}.

ibar(VPSem) --> i(MvdVbL),vp(VPSem,MvdVbL).

i([]) --> [].
i([]) --> [Aux],{isAux(Aux)}.
i([Verb]) --> [InflVerb],{pastInfl(Verb,InflVerb),isVerb(Verb)}.
pastInfl(see,saw).
pastInfl(love,loved).

vp(VbarSem,MvdVbL) --> vbar(VbarSem,MvdVbL).
vbar(VbarSem,MvdVbL) --> v(VSem,MvdVbL), np(NPSem),
    {var_replace(VSem,VSem1),
     beta(VSem1@NPSem,VbarSem)}.

v(lbd(s, lbd(x,s@lbd(y,Fla))),[]) --> [Verb],
    {isVerb(Verb),Fla=..[Verb,x,y]}.

v(lbd(s,lbd(x,s@lbd(y,Fla))),[MvdVb])--> [],
    {Fla=..[MvdVb,x,y]}.

np(NbarSem) --> nbar(NbarSem).
nbar(NbarSem) --> adj(AdjSem),nbar(NbarSem1),
    {var_replace(AdjSem,AdjSem1),beta(AdjSem1@NbarSem1,NbarSem)}.
nbar(NbarSem) --> det(DetSem),nbar(NbarSem1),
    {var_replace(DetSem,DetSem1),beta(DetSem1@NbarSem1,NbarSem)}.
nbar(NSem) --> n(NSem).


nbar(NbarSem) --> nbar(NbarSem1),pp(PPSem),
    {var_replace(PPSem,PPSem1),beta(PPSem1@NbarSem1,NbarSem)}.
nbar(NSem) --> n(NSem).
pp(PPSem) --> pbar(PPSem).
pbar(NbarSem) --> po(PPSem),np(NbarSem1),
    {var_replace(PPSem,PPSem1),beta(PPSem1@NbarSem1,NbarSem)}.

isVerb(love).
n(lbd(x,boy(x))) --> [boy].
n(lbd(x,girl(x))) --> [girl].
det(lbd(q,lbd(p,exists(x,(q@x & p@x))))) --> [some].
det(lbd(q,lbd(p,forall(x,(q@x -> p@x))))) --> [every].

nbar(NbarSem) --> adj(AdjSem),nbar(NbarSem1)

nbar(NbarSem) --> det(DetSem),nbar(NbarSem1)

nbar(NbarSem) --> nbar(NbarSem1),pp(PPSem)

when I tried to run it... what query did you enter exactly? — lurker

Paulo Moura Paulo Moura · Accepted Answer · 2016-12-06T14:18:14

Tabling is implemented in recent versions of SWI-Prolog. By declaring the predicates (or non-terminals) using left-recursion as tabled predicates (or non-terminals), you can keep their definitions. For details, consult:

http://www.swi-prolog.org/pldoc/man?section=tabling

Prolog how to eliminate left recursion

1 Answers