% Final version of the shift-reduce parser
% shift_red_prolog.pl

% Consult the operators and beta_reduce/2

:- [operators, beta_red].

%% Forces reduce before shift

%% Using term_expansion/2, compiles rules and lexical entries containing Prolog code into clauses of the form Rule:- Code. No need for a call to evaluate/1 in the parser.

%% Takes lexical entries of the form Cat ===> ListOfWords and compiles them into data structures with a difference-list on the right hand side of the rule: Cat ==> Words-Words0

term_expansion((X ---> (Y, Code)), ((X ---> Y):- Code)).
term_expansion((X ---> Y), (X ---> Y)).

term_expansion((X ===> (Y, Code)), ((X ===> Ydl):- Code)):-
  make_dl(Y, Ydl).
term_expansion((X ===> Y), (X ===> Ydl)):-
  make_dl(Y, Ydl).

make_dl(L, OpenL-Var):-
  append(L, Var, OpenL).

%% Front end to the parser

parse(Input, Result):-
	parse([], [Result], Input, []).

parse([Stack], [Stack], [], []).

parse(Stack0, Stack, Words0, Words):-
  shift(Stack0, Stack1, Words0, Words1),
  reduce(Stack1, Stack2, Words1, Words1),
  parse(Stack2, Stack, Words1, Words).

shift(Stack, [Cat|Stack], Words0, Words):-
    (Cat ===> Words0-Words).

reduce([Top|Stack0], Stack, Words, Words):-
  reduce_aux(Stack0, [Top], Stack1),
  reduce(Stack1, Stack, Words, Words).

reduce(Stack, Stack, Words, Words).

reduce_aux(Stack, Top, [Cat|Stack]):-
  ( Cat ---> Top).

reduce_aux([Top|Stack0], Store, Stack):-
  reduce_aux(Stack0, [Top|Store], Stack).


'{}'(X):- call(X).