parse(Words,Tree) :-
        parse(Words,[],[Tree]),
        Tree = [S|_], start_symbol(S).

parse([W|Words],Stack,Reduced) :-
        ( ( complete(Stack,RedStack)
          ; predict(Stack,RedStack)
          ), parse([W|Words],RedStack,Reduced)
        ; shift(W,Stack,RedStack),
            parse(Words,RedStack,Reduced)
        ).
parse([],Stack,Reduced) :-
        ( ( complete(Stack,RedStack)
          ; predict(Stack,RedStack)
          ), parse([],RedStack,Reduced)
        ; Reduced = Stack ).

shift(W,Stack,[Tree|Stack]) :-
        ( word(W,A), Tree = [A,W]
        ; A = [W], Tree = [A] ).
complete([[B|Trees],(C ---> RevTrees,[B|Beta])|Stack],
         [(C ---> [[B|Trees]|RevTrees],Beta)|Stack]).
complete([(C ---> RevTrees,[])|Stack],
         [[C|Trees]|Stack]) :-
        reverse(RevTrees,Trees).
complete(Stack,[[C]|Stack]) :- 
        (C ---> []).

predict([[B|Trees]|Stack],Reduced) :-
        (A ---> Alpha),
        tupleToList(Alpha,[B|Beta]),
        Reduced = [(A ---> [[B|Trees]],Beta)|Stack].
tupleToList((B,C),[B|Cs]) :- !, tupleToList(C,Cs).
tupleToList([],[]).
tupleToList([W],[[W]]).
tupleToList(B,[B]).
