:- dynamic kante/5.

erkenne(_,_) :-           % Predict(0) 
        retractall(kante(_I,_J,_A,_alpha,_beta)),
        start_symbol(S),
        (S ---> Alpha),                      
        closure(0,0,S,[],Alpha),
        fail.
erkenne(Wortfolge,Kategorie) :-
        erkenne(0,Wortfolge,Kategorie).

erkenne(I,[Wort|Rest],Kategorie) :-
        J is I + 1,              
        shift_e(I,J,Wort),
        erkenne(J,Rest,Kategorie).
erkenne(I,[],S) :-        % Eingabe erkannt?                      
        start_symbol(S),  
        kante(0,I,S,_Alpha,[]).

shift_e(I,J,Wort) :-      % Scan(a_(i+1))
        lexword(I,Wort,Kategorie), 
        closure(I,J,Kategorie,[Wort],[]), 
        fail.
shift_e(_,_,_).
closure(I,J,Kopf,Geschlossen,[]) :-
        neue_kante(I,J,Kopf,Geschlossen,[]),
        complete(I,J,Kopf).
complete(I,J,B) :-
        kante(K,I,A,Alpha,[B|Beta]),
        append(Alpha,[B],AlphaB),
        closure(K,J,A,AlphaB,Beta),
        fail.
complete(_,_,_).
closure(I,J,Kopf,Geschlossen,[B|Bs]) :-
        neue_kante(I,J,Kopf,Geschlossen,[B|Bs]),
        expand_e(J,B).

expand_e(J,A) :-                % Predict(J)
        (A ---> Alpha),              
        closure(J,J,A,[],Alpha),  
        fail.                        
expand_e(_,_).
neue_kante(I,J,Kopf,Geschl,Offen) :-
        known_instance(kante(I,J,Kopf,Geschl,Offen)),
        !,fail.
neue_kante(I,J,Kopf,Geschlossen,Offen) :-
        assertz(kante(I,J,Kopf,Geschlossen,Offen)).

known_instance(Term) :- 
        \+ \+ (numbervars(Term,const,0,_), Term).