%Regelformat

regel(satz,[np,vp]).
regel(rels,[rp,vi]).
regel(np,[det,n]).
regel(np,[det,n,rels]).
regel(vp,[vi]).
regel(vp,[vt,np]).

lex(det,[das]).
lex(n,[gestirn]).
lex(rp,[das]).
lex(vi,[blinkt]).
lex(vt,[umkreist]).



/*Parsen von oben nach unter und links nach recht;
entsprechend der Prolog-Strategie*/

parsing_von_oben_links(Phrase,Kat) :-
			parse_von_oben_links([Kat],Phrase).
			

parse_von_oben_links([],[]) :- !.

parse_von_oben_links([Kat|Rkat],L) :-
			regel(Kat,Kat_exp),
			append(Kat_exp,Rkat,Kats1),
			parse_von_oben_links(Kats1,L).
			
parse_von_oben_links([X|R],[Wort|Rs]) :-
			lex(X,[Wort]),
			parse_von_oben_links(R,Rs).
			
			
/* Parsing von oben nach unten, aber von rechts nach links*/

parsing_von_oben_rechts(Phrase,Kat) :-
			umdrehen(Phrase,Phrasu),
			parse_von_oben_rechts([Kat],Phrasu).
			

parse_von_oben_rechts([],[]) :- !.

parse_von_oben_rechts([Kat|Rkat],L) :-
			regel(Kat,Kat_exp),
			umdrehen(Kat_exp,Kat_expu),
			append(Kat_expu,Rkat,Kats1),
			parse_von_oben_rechts(Kats1,L).
			

parse_von_oben_rechts([Kat|Rkats],[Wort|Rs]) :-
			lex(Kat,[Wort]),
			parse_von_oben_rechts(Rkats,Rs).



/*Von unten nach oben (bottom up), links nach rechts
Hier wird auch der Baum erzeugt*/

parsing_von_unten_links([Wort|Restsatz],Baum) :-
			parse_von_unten_links(Restsatz,[Wort],Baum).
			

parse_von_unten_links([],Stapel,S) :-
			reduziere(Stapel,[S]).

parse_von_unten_links([Wort|Restsatz],Stapel,SynBaum) :-
			reduziere(Stapel,Stapel_red),
			parse_von_unten_links(Restsatz,[Wort|Stapel_red],SynBaum).

reduziere(Stapel,Stapel2) :-
	reduziere1(Stapel,Stapel1), 
	reduziere(Stapel1,Stapel2).

%Keine Reduktion
reduziere(X,X).
	
reduziere1([Wort|Rest],[Baum|Rest]) :-
	lex(Kat,[Wort]),
	Kat =.. [C|_],
	Baum =.. [C,Wort].



reduziere1([A|Y],[Baum|Y]) :-
		A=..[A1|_],
		regel(C,[A1]),
		C=..[C1|_],
		Baum=..[C1,A].

reduziere1([B,A|Y],[Baum|Y]) :-
		B =..[B1|_],
		A=..[A1|_],
		regel(C,[A1,B1]),
		C=..[C1|_],
		Baum=..[C1,A,B].

reduziere1([C,B,A|Y],[Baum|Y]) :-
		C =..[C1|_],
		B=..[B1|_],
		A=..[A1|_],
		regel(M,[A1,B1,C1]),
		M=..[M1|_],
		Baum=..[M1,A,B,C].



		

%Hilfsprädikat; dreht eine Liste um
umdrehen(L,Lu) :- umdrehen(L,[],Lu).

umdrehen([],L,L).

umdrehen([K|R],L1,L) :-
	umdrehen(R,[K|L1],L).