% Write a predicate
%				sentence(X, Y)
% where X is a sentence, represented as a list of words, and Y is a parse
% tree for the sentence, X.
% For example, the following query should return with the answer **yes.
%
% sentence(
%	[the,black,cat,is,on,the,mat],
%	s(
%		np(article(the), adjective(black), noun(cat)),
%		vp(verb(is), pp(prep(on), np(article(the), noun(mat))))
%	)
% )?
%	                   s
%	           +-------^--------+
%	           np               vp
%	   +-------^+------+    +---^---+
%	article adjective noun verb     pp
%	   |        |      |    |   +---^----+
%	  the     black   cat   is prep      np
%	                            |     +--^--+
%	                            on article noun
%	                                  |     |
%	                                 the   mat
%
%
% The grammar your program should recognise is given below:
%
%	A sentence is a noun phrase followed by a verb phrase.
%	A noun is an article followed by a noun.
%	or a noun phrase is an article follwed by an adjective followed by a noun.
%	A verb phrase is a verb followed by a prepositional phrase.
%	A prepositional phrase is a preposition followed by a noun phrase.
%
% You may assume that the following assertions are present in the database:

article([the|X], X, article(the)).

adjective([black|X], X, adjective(black)).

noun([cat|X], X, noun(cat)).
noun([mat|X], X, noun(mat)).

verb([is|X], X, verb(is)).

preposition([on|X], X, prep(on)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

sentence(X, s(NP, VP)) :-
	noun_phrase(X, Y, NP),
	verb_phrase(Y, [], VP).

noun_phrase(A, D, np(Article, Adjective, Noun)) :-
	article(A, B, Article),
	adjective(B, C, Adjective),
	noun(C, D, Noun).
noun_phrase(A, C, np(Article, Noun)) :-
	article(A, B, Article),
	noun(B, C, Noun).

verb_phrase(A, C, vp(Verb, PP)) :-
	verb(A, B, Verb),
	prepositional_phrase(B, C, PP).

prepositional_phrase(A, C, pp(Prep, NP)) :-
	preposition(A, B, Prep),
	noun_phrase(B, C, NP).

