% Computational Intelligence: a logical approach. 
% Prolog Code.
% A natural language parser using context free grammar from Figure 3.5
% Copyright (c) 1998, Poole, Mackworth, Goebel and Oxford University Press.
%
% Modified by Kazunori Ueda, June 1999

% a sentence is a noun phrase followed by a verb phrase.
sentence(T_0,T_2,s(Np,Vp)) :- 
   noun_phrase(T_0,T_1,Np), 
   verb_phrase(T_1,T_2,Vp).

% a noun phrase is a determiner followed by modifiers followed
% by a noun followed by an optional prepositional phrase.
noun_phrase(T_0,T_4,np(D,M,N,P)) :- 
   det(T_0,T_1,D), 
   modifiers(T_1,T_2,M), 
   noun(T_2,T_3,N), 
   pp(T_3,T_4,P).

% an optional noun phrase is either nothing or a noun phrase
opt_noun_phrase(T,T,-).
opt_noun_phrase(T_0,T_1,N) :-
   noun_phrase(T_0,T_1,N).

% a verb phrase is a verb followed by a noun phrase and an optional pp
verb_phrase(T_0,T_3,vp(V,O,P)) :- 
   verb(T_0,T_1,V), 
   opt_noun_phrase(T_1,T_2,O), 
   pp(T_2,T_3,P).

% an optional prepositional phrase is either
% nothing or a preposition followed by a noun phrase
pp(T,T,-).
pp(T_0,T_2,pp(P,N)) :-
   preposition(T_0,T_1,P),
   noun_phrase(T_1,T_2,N).

% modifiers is a sequence of adjectives
modifiers(T,T,[]).
modifiers(T0,T2,[A|M]) :-
    adjective(T0,T1,A),
    modifiers(T1,T2,M).

% dictionary
det(T,T,-).
det([a|T],T,det(a)).
det([the|T],T,det(the)).
noun([student|T],T,n(student)).
noun([course|T],T,n(course)).
noun([computer|T],T,n(computer)).
adjective([practical | T],T,adj(practical)).
verb([passed|T],T,v(passed)).
verb([failed|T],T,v(failed)).
preposition([with|T],T,prep(with)).

% Example Query:
%?- sentence([the,student,passed,the,practical,course,with,a,computer],[],T).

% T = s(np(det(the),
%          [],
%          n(student),
%          -),
%       vp(v(passed),
%          np(det(the),
%             [adj(practical)],
%             n(course),
%             -),
%          pp(prep(with),
%             np(det(a),
%             [],
%             n(computer),
%             -))))

% T = s(np(det(the),
%          [],
%          n(student),
%          -),
%       vp(v(passed),
%          np(det(the),
%             [adj(practical)],
%             n(course),
%             pp(prep(with),
%                np(det(a),
%                   [],
%                   n(computer),
%                   -))),
%       -))