%CFG implementation via difference lists with parse trees

s(s(NP,VP),L1,L2):-
	np(NP,L1,L3),
	vp(VP,L3,L2).


np(np(PN),L1,L2):-
	pname(PN,L1,L2).

np(np(DET,NOUN),L1,L2):-
	det(DET,L1,L3),
	noun(NOUN,L3,L2).

vp(vp(VERB,NP),L1,L2):-
	verb(VERB,L1,L3),
	np(NP,L3,L2).

pname(pname(john),[john|T],T).
pname(pname(mary),[mary|T],T).

det(det(the),[the|T],T).
det(det(a),[a|T],T).

noun(noun(politician),[politician|T],T).
noun(noun(child),[child|T],T).
noun(noun(book),[book|T],T).

verb(verb(likes),[likes|T],T).
verb(verb(hates),[hates|T],T).
verb(verb(sleeps),[sleeps|T],T).