% Bottom-up Shift-Reduce Parser
%  parse(+String,?Result)
%  parses input string String, with Result a list of catogories
%  to be reduced
%  from: Covington (1994), NLP for Prolog Programmers, p. 159

parse(S,Result) :-
	shift_reduce(S,[],Result).


% shift_reduce(+String,+Stack,?Result)
%  parses string String, with Stack the list of categories
%  parsed so far

shift_reduce(S,Stack,Result) :-
	shift(Stack,S,Stack1,S1),       % fails if S = []
	reduce(Stack1,ReducedStack),
	shift_reduce(S1,ReducedStack,Result).

shift_reduce([],Result,Result).


% shift(+Stack,+S,-Newstack,-NewS)
%  shifts first element from S onto Stack

shift(OldSt, [H|Ts], [H|OldSt], Ts).


% reduce(+Stack,-ReducedStack)
%  repeatedly reduces beginning of Stack to form fewer, larger
%  constituents

reduce(Stack, ReducedStack) :-
	brule(Stack, Stack2),
	reduce(Stack2, ReducedStack).

reduce(Stack,Stack).


% PS Rules

brule([vp,np|Xs], [s|Xs]).

brule([n,d|Xs],        [np|Xs]).
brule([np,conj,np|Xs], [np|Xs]).

brule([np,p|Xs], [pp|Xs]).

brule([np,v|Xs], [vp|Xs]).

brule([Word|Xs], [Cat|Xs]) :- word(Cat,Word).


% Lexicon

word(conj, and).

word(d, all).
word(d, every).
word(d, the).

word(n, cat).
word(n, cats).
word(n, dog).
word(n, dogs).
word(n, elephant).
word(n, elephants).

word(p, near).

word(v, amuse).
word(v, amuses).
word(v, chase).
word(v, chases).
word(v, see).
word(v, sees).