// written by André Betz 
// http://www.andrebetz.de

#include <stdio.h>
#include <stdlib.h>
#define  EPSILON '&'

/*
	LL(1)-Parser-Generator - keine Linksrekursion erlaubt
	A->AB; => 
	Umformen von EBNF -> BNF
	A->a(b)c => A->aBc,B->b
	A->a[b]c => A->aBc,B->b,B->&
	A->a{b}c => A->aBc,B->bB,B->&
	A->a|b   => A->a,A->b
	A->UV&   => A->UVX,X->&
*/

/* Baumstruktur */
typedef struct node
{
	struct node *suc;
	struct node *next;
	struct node *First;
	struct node *Follow;
	int			Nr;
	int			term;
	int			Epsfrei;
	char		sym;
	char		mark;
} *pnode;

/* erzeugt neuen Knoten */
pnode NewNode()
{
  pnode neu;
  char *point;
  int cnt;

  neu = (pnode)malloc(sizeof(struct node));
  point = (char*)neu;
  for(cnt=0;cnt<sizeof(struct node);cnt++)
  {
	  point[cnt] = 0;
  }

  return neu;
}

/* schaut ob Zeichen im Baum schon vorhanden ist */
int isThere(pnode gram,char Sym)
{
	pnode HTrans = gram;
	pnode Suc;

	while(HTrans)
	{
		Suc = HTrans;
		while(Suc)
		{
			if(Sym==Suc->sym) return 1;
			Suc = Suc->suc;
		}
		HTrans = HTrans->next;
	}
	return 0;
}

/* gibt Zeiger auf Element mit der Produktion zurück */
pnode getTransBegin(pnode gram,char Sym)
{
	pnode HTrans = gram;

	while(HTrans)
	{
		if(Sym==HTrans->sym) return HTrans;
		HTrans = HTrans->next;
	}
	return NULL;
}

/* gibt Zeiger auf Produktion in der sich das Symbol befindet */
pnode getTransInside(pnode suc,char Sym)
{
	pnode Suc = suc;

	while(Suc)
	{
		if(Sym==Suc->sym) return Suc;
		Suc = Suc->suc;
	}
	return NULL;
}

/* erzeugt aus der BNF-Grammatik einen Baum */
pnode Transform(char* Gram)
{
	pnode tree = NULL;
	pnode next;
	pnode help;
	pnode NTrans;
	int   GPtr = 0;
	int   NTr = 2;
	int	  T = 0;
	int   NT = 0;
	char  Sym;

	while(Gram[GPtr]!=0)
	{
		Sym = Gram[GPtr];

		if(Sym!='=')
		{
			if(Sym!='.')
			{
				help = NewNode();

				if(Sym>='A'&&Sym<='Z') 
				{
					help->Nr =NT;
					if(!isThere(tree,Sym)) NT++;
				}
				else
				{
					if(Sym!=EPSILON)
					{
  						help->term = 1;
						help->Nr = T;
						if(!isThere(tree,Sym)) T++;
					}
					else 
					{
						help->term = 2;
						Sym = 0;
					}
				}
				help->sym     = Sym;

		        switch(NTr) 
				{
				case 2:
					tree   = help;
					NTrans = help;
					NTr = 0;
					break;
				case 1:
					NTrans->next = help;
					NTrans = help;
					NTr = 0;
					break;
				default:
					next->suc = help;
					break;
				}
				next = help;
			}
			else NTr = 1;
		}
		GPtr++;
	}
	return tree;
}

/* untersucht auf Epsilonfreiheit */
void EpsilonTable(pnode Gram)
{
	pnode HTrans = Gram;
	pnode Suc;
	pnode help;
	int cntEps;
	int cntT;
	int cntNT;
	int cntSum;
	int cntFrei1;
	int cntNFrei1;
	int cntUnent1;
	int cntFrei2;
	int cntNFrei2;
	int cntUnent2;
	int Unent = 0;

	while(HTrans)
	{
		Suc = HTrans->suc;
		cntEps = 0;
		cntT   = 0;
		cntNT  = 0;
		if(HTrans->Epsfrei==0)
		{
			while(Suc)
			{
				if(Suc->term==2)  cntEps++;
				if(Suc->term==1)  cntT++;
				if(Suc->term==0)  cntNT++;
				Suc = Suc->suc;
			}
			cntSum = cntEps + cntT + cntNT;
			if(cntT)           HTrans->Epsfrei = 2; /* Nein */ 
			if(cntSum==cntEps) HTrans->Epsfrei = 1; /* Ja */
			if(cntNT)          Unent = 1;
		}
		HTrans = HTrans->next;
	}

	while(Unent)
	{
		Unent = 0;
		HTrans = Gram;
    
		while(HTrans)
		{
			if(HTrans->Epsfrei==0)
			{
				Suc = HTrans->suc;

				cntFrei2   = 0; 
				cntNFrei2  = 0; 
				cntUnent2  = 0;

				while(Suc)
				{
					help = Gram;
					cntFrei1   = 0; 
					cntNFrei1  = 0; 
					cntUnent1  = 0; 
		  
					while(help)
					{
						help = getTransBegin(help,Suc->sym);

						if(help!=NULL)
						{
   							if(help->Epsfrei==0) cntUnent1++;
							if(help->Epsfrei==1) cntNFrei1++;
							if(help->Epsfrei==2) cntFrei1++;
							help = help->next;
						}
					}
		
					cntSum = cntUnent1 + cntFrei1 + cntNFrei1;
					if(cntUnent1)         cntUnent2++;
					if(cntSum==cntNFrei1) cntNFrei2++;
					if(cntFrei1)          cntFrei2++;
					Suc = Suc->suc;
				}

				cntSum = cntUnent2 + cntFrei2 + cntNFrei2;
				if(cntUnent2)         Unent = 1;
				if(cntSum==cntNFrei2) HTrans->Epsfrei = 1;
				if(cntFrei2)          HTrans->Epsfrei = 2;
		  
			}
			HTrans = HTrans->next;
		}
	}

}

/* erzeugt First-Menge */
void FirstSet(pnode Gram)
{
	pnode HTrans = Gram;
	pnode Suc;
	pnode help;
	pnode help2;
	pnode HFst;
	int Unent = 1;
	int Epsfrei;
	int SchoHier;

	while(Unent)
	{
		HTrans = Gram;
		Unent = 0;
		while(HTrans)
		{
			Suc = HTrans->suc;
			Epsfrei = 1;	
	  
			while((Epsfrei)&&(HTrans->Epsfrei==2)&&(Suc))
			{
				Epsfrei = 0;
  				help = Gram;

				if(Suc->term==0)
				{
					while(help)
					{
 						help = getTransBegin(help,Suc->sym);

						if(help!=NULL)
						{
							if(help->Epsfrei==1) Epsfrei = 1;
							help2 = help->First;

							while(help2)
							{
	 							HFst = HTrans;
 								SchoHier = 1;
								while((HFst->First)&&(SchoHier==1)) 
								{
 									HFst = HFst->First;
 									if(help2->sym==HFst->sym) SchoHier = 0;
								}

								if(SchoHier==1)
								{
									HFst->First = NewNode();
									HFst = HFst->First;
									HFst->sym = help2->sym;
									Unent = 1;
								}
								help2 = help2->First;
							}
  							help = help->next;
						}
					}
				}
				else
				{
					HFst = HTrans;
					SchoHier = 1;
					while((HFst->First)&&(SchoHier==1)) 
					{
						HFst = HFst->First;
						if(Suc->sym==HFst->sym) SchoHier = 0;
					}

					if(SchoHier==1)
					{
						HFst->First = NewNode();
						HFst = HFst->First;
						HFst->sym = Suc->sym;
						Unent = 1;
					}
				}
				Suc = Suc->suc;
			}
			HTrans = HTrans->next;
		}
	}
}

/* erzeugt Follow-Menge */
void FollowSet(pnode Gram)
{
	pnode HTrans = Gram;
	pnode HTrans2;
	pnode HFlw;
	pnode HFst;
	pnode Suc;
	pnode help;
	int SchoHier;
	int Unent = 1;
	int Epsfrei;

	while(Unent)
	{
		Unent = 0;
		while(HTrans) /* HTrans entspricht dem A */ 
		{
			HTrans2 = Gram;
			while(HTrans2) /* sucht nach dem Zeichen von HTrans in den Produktionen */
			{
				help = HTrans2->suc; /* HTrans2 entspricht dem B */
				while(help)
				{
					help = getTransInside(help,HTrans->sym);
					if(help!=NULL)
					{
						help = help->suc; /* help entspricht dem Beta */
						Epsfrei = 1;
						while(Epsfrei)
						{
							Epsfrei = 0;
							if(help==NULL)
							{
								Suc = HTrans2->Follow;

								while(Suc)
								{
									HFlw = HTrans;
									SchoHier = 1;

									while((HFlw->Follow)&&(SchoHier==1)) 
									{
										HFlw = HFlw->Follow;
										if(Suc->sym==HFlw->sym) SchoHier = 0;
									}
		
									if(SchoHier==1)
									{
										HFlw->Follow = NewNode();
										HFlw = HFlw->Follow;
										HFlw->sym = Suc->sym;
										Unent = 1;
									}

									Suc = Suc->Follow;
								}
							}
							else
							{
								if(help->term==1)
								{
									HFlw = HTrans;
									SchoHier = 1;
									while((HFlw->Follow)&&(SchoHier==1)) 
									{
										HFlw = HFlw->Follow;
										if(help->sym==HFlw->sym) SchoHier = 0;
									}

									if(SchoHier==1)
									{
										HFlw->Follow = NewNode();
										HFlw = HFlw->Follow;
										HFlw->sym = help->sym;
										Unent = 1;
									}
								}
								if(help->term==0)
								{
									Suc = Gram;
		
									while(Suc)
									{
										Suc = getTransBegin(Suc,help->sym);
										if(Suc!=NULL)
										{
											HFst = Suc->First;
											while(HFst)
											{
												HFlw = HTrans;
												SchoHier = 1;
						
												while((HFlw->Follow)&&(SchoHier==1)) 
												{
													HFlw = HFlw->Follow;
													if(HFst->sym==HFlw->sym) SchoHier = 0;
												}

												if(SchoHier==1)
												{
													HFlw->Follow = NewNode();
													HFlw = HFlw->Follow;
													HFlw->sym = HFst->sym;
													Unent = 1;
												}
												HFst = HFst->First;
											}
											if(Suc->Epsfrei==1)	Epsfrei = 1;
											Suc = Suc->next;
										}
									}
								}
							}
							if(Epsfrei==1) help = help->suc;
						}
					}
				}
				HTrans2 = HTrans2->next;
			}
			HTrans = HTrans->next;
		}
	}
}

void ShowTables(pnode Gram)
{
	pnode HTrans = Gram;
	pnode Suc;
	pnode HFst;
	pnode HFlw;
	int count = 0;

	printf("Num\tTrans\tEps\tFirst\tFollow\n");
	while(HTrans)
	{
		printf("%d\t%c->",count,HTrans->sym);
		Suc  = HTrans->suc;
		HFst = HTrans->First;
		HFlw = HTrans->Follow;
		while(Suc)
		{
			printf("%c",Suc->sym);
			Suc = Suc->suc;
		}

		if(HTrans->Epsfrei==1)	printf("\tj");
		else					printf("\tn");

		printf("\t{");
		while(HFst)
		{
			printf("%c",HFst->sym);
			HFst = HFst->First;
			if(HFst!=NULL) printf(",");
		}
		printf("}\t{");
		while(HFlw)
		{
			printf("%c",HFlw->sym);
			HFlw = HFlw->Follow;
			if(HFlw!=NULL) printf(",");
		}
		printf("}\n");
		count++;
		HTrans = HTrans->next;
	}
	printf("\n");
}

void ShowStack(pnode FrstEl)
{
	pnode help = FrstEl;
	while(help)
	{
		printf("%c",help->sym);
		help = help->next;
	}
	printf("\n");
}

void ParseLL1(pnode Gram,char* Text)
{
	pnode FrstEl  = NULL;
	pnode help   = NULL;
	pnode FSym;
	pnode HTrans;
	pnode Ersetz;
	pnode Next;
	int   count = 0;
	char  Sym;

	FrstEl = NewNode();
	Sym = Text[count];
	FrstEl->sym  = Gram->sym;
	FrstEl->term = Gram->term;

	while((Sym!=0)&&(FrstEl!=NULL))
	{

		printf("%c\t",Sym);
		ShowStack(FrstEl);

		if(FrstEl->term==1)
		{
			FSym = FrstEl->next;
			free(FrstEl);
			FrstEl = FSym;
			count++;
			Sym = Text[count];
		}
		else
		{
			HTrans = Gram;
			Ersetz = NULL;
			while(HTrans) /* sucht nach der zu ersetzenden Regel */
			{
				HTrans = getTransBegin(HTrans,FrstEl->sym); /* Geht dei Regeln durch */
				if(HTrans!=NULL)
				{
					/* FSym enthält die zu vergleichenden Zeichen */
					if(HTrans->Epsfrei==1)	FSym = HTrans->Follow;
					else					FSym = HTrans->First;

					while(FSym!=NULL) /* sucht nach dem Zeichen */
					{
						if(FSym->sym==Sym)		Ersetz = HTrans;
						if(HTrans->Epsfrei==1)	FSym = FSym->Follow;
						else					FSym = FSym->First;
					}
					HTrans = HTrans->next;
				}
			}
	
			Ersetz = Ersetz->suc;
			FSym = FrstEl->next;
			free(FrstEl);
			FrstEl = NULL;

			if(Ersetz->term==2)
			{
				FrstEl = FSym;
			}
			else
			{
				while(Ersetz!=NULL)
				{
					help = NewNode();
					help->sym  = Ersetz->sym;
					help->term = Ersetz->term;
					Ersetz = Ersetz->suc;

					if(FrstEl==NULL)	FrstEl = help;
					else				Next->next = help;
					Next = help;
				}
				Next->next = FSym;
			}
		}
	}
}

void DeleteTables(pnode Gram)
{
	pnode HTrans = Gram;
	pnode Suc;
	pnode HFst;
	pnode HFlw;
	pnode help;

	while(HTrans)
	{
		Suc  = HTrans->suc;
		HFst = HTrans->First;
		HFlw = HTrans->Follow;
		while(Suc)
		{
			help = Suc;
			Suc = Suc->suc;
			free(help);
		}
		while(HFst)
		{
			help = HFst;
			HFst = HFst->First;
			free(help);
		}
		while(HFlw)
		{
			help = HFlw;
			HFlw = HFlw->Follow;
			free(help);
		}
		help = HTrans;
		HTrans = HTrans->next;
		free(help);
	}
}

pnode LL0Table(pnode Gram)
{
	return NULL;
}

int LL1Analyse(char* BNF,char* Text)
{
	pnode Gram = Transform(BNF);
	EpsilonTable(Gram);
	FirstSet(Gram);
	FollowSet(Gram);
	ShowTables(Gram);
	ParseLL1(Gram,Text);
	DeleteTables(Gram);
	return 0;
}

int SLR1Analyse(char* BNF,char* Text)
{
	pnode Gram = Transform(BNF);
	EpsilonTable(Gram);
	FirstSet(Gram);
	FollowSet(Gram);
	ShowTables(Gram);
	LL0Table(Gram);
	DeleteTables(Gram);
	return 0;
}

int main(int argc,char **argv)
{
	char BspBNF[] = "S=E#.E=TU.U=+TU.U=&.T=FV.V=*FV.V=&.F=z.F=(E).";
	char BspText[] = "z+(z+z)*z#";
	if(argc!=3)
	{
		printf("Aufruf: %s '%s' '%s'\n",argv[0],BspBNF,BspText);
		LL1Analyse(BspBNF,BspText);
	}
	else
	{
		LL1Analyse(argv[1],argv[2]);
	}
	return 0;
}