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

parse([W|Ws],Stack,Reduced) :-
        ( reduce(Stack,RedStack),
            parse([W|Ws],RedStack,Reduced)
        ; shift(W,Stack,WStack),
            parse(Ws,WStack,Reduced) ).
parse([],Stack,Reduced) :-
        ( reduce(Stack,RedStack),
            parse([],RedStack,Reduced)
        ; Reduced = Stack ).

shift(W,Stack,[Tree|Stack]) :-
        ( word(W,A), Tree = [A,W]
        ; A = [W], Tree = [A] ).
reduce(Stack,Reduced) :-
        (B ---> Beta),
        split(Stack,Beta,BetaForest,AlphaForest),
        reverse(BetaForest,BetaTrees),
        Tree = [B|BetaTrees],
        Reduced = [Tree|AlphaForest].

split(Forest,Beta,BetaForest,AlphaForest) :-    
        tupleToList(Beta,BetaL),
        reverse(BetaL,BetaRev),
        newTrees(BetaRev,BetaForest),
        append(BetaForest,AlphaForest,Forest).

newTrees([A|As],[[A|_]|Ts]) :-
        newTrees(As,Ts).
newTrees([],[]).

tupleToList((B,C),[B|Cs]) :- !, tupleToList(C,Cs).
tupleToList([],[]).
tupleToList([W],[[W]]).
tupleToList(B,[B]).
printTree([A|Trees],I) :- 
        !, printTree(A,I),
        J is I + 3, printTrees(Trees,J).
printTree(A,I) :-
        nl, tab(I), writeq(A).

printTrees([T|Ts],I) :-
        printTree(T,I),
        printTrees(Ts,I).
printTrees([],_I).