#include <stdio.h>
#include <malloc.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

#define WORLEN 12

typedef struct
{
  char changed;
  int next;
  char LNR;
} Rule;

typedef struct
{
   char name[WORLEN];
   Rule *rules;
} Stanje;

//globalne promenljive
int lineNo =1;    //rednbi broj linije do kog smo stigli u parsiranju
FILE *fp;         //ulazni fajl
Stanje *stanja;   //ova struktura opisuje tjuringovu masinu
char c;           //tekuci karakter pri parsiranju
char L[30];          //jezik koji prima tjuringova masina
char tape[1000];       //"beskonacna" traka tjuringove masine
int brStanja = 0;   //broj stanja Tjuringove masine
int brSlova = 0;  //broj slova azbuke nad kojom radi tjuringova masina
int tapeLen = 0;  //zauzeta duzina trake
int pocetno;      //stanje iz kog masina pocinje da radi;
int *zavrsna;     //zavrsna stanja
int brZavrsnih = 0;

void Err(int,char*);
//funkcija koja obradjuje greske, svaka greska ima svoj celobrojni kod
//info daje dodatne informacije o nastaloj gresci
void Err(int code,char *info)
{
   switch(code)
   {
      case 1:
         ("\nPogresan broj argumenata komandne linije!");
         printf("\nSyntax : Tjuring <source file>\n");
         exit(-1);
         break;
      case 2:
         printf("\nGreska pri otvranju datoteke %s!\n",info);
         exit(-2);
         break;
      case 3:
         printf("\nNepoznata direktiva #%s# na liniji %d\n",info,lineNo);
         exit(-3);
         break;
      case 4:
         printf("\nGreska na liniji %d.",lineNo);
         printf("\nDirektive ne mogu biti duze od 10 karaktera!\n");
         exit(-4);
         break;
      case 5:
         printf("\nPopunjena sva raspoloziva memorija za vreme");
         printf(" parsiranja linije %d!\n",lineNo);
         exit(-5);
         break;
      case 6:
         printf("\nGreska na liniji %d.",lineNo);
         printf("\nImena stanja ne mogu biti duza od 10 karaktera!\n");
         exit(-6);
         break;
      case 7:
         printf("\nLinija %d:Neocekivani kraj datoteke\n",lineNo);
         exit(-7);
         break;
      case 8:
         printf("\nGreska na liniji %d:",lineNo);
         printf("\nOcekivano \'%s\'\n",info);
         exit(-8);
         break;
      case 9:
         printf("\nGreska na liniji %d:",lineNo);
         printf("\nNedfinisano stanje \"%s\"\n",info);
         exit(-9);
         break;
      case 10:
         printf("\nGreska na liniji %d:",lineNo);
         printf("\nSlova \"%c\" nema u azbuci definisanoj direktivom",c);
         printf(" #azbuka#\n");
         exit(-10);
         break;
      case 11:
         printf("\nGreska na liniji %d:",lineNo);
         printf("\nOcekivano L,N ili R (left,neutral,right)\n");
         exit(-11);
         break;
   }
}

//funkcija SkipWs vraca prvi karakter nakon blanko znakova u fajlu fp
void SkipWs()
{
   while(((c=getc(fp))==' ') || (c=='\n') || (c=='\t'))
      if(c=='\n')
		lineNo++;
   if(c==EOF)
      Err(7,NULL);

}

//proverava za dirketivu *directive racunajuci da je c='#' s
void CheckDirective(char *directive)
{
   char word[WORLEN],i=0;
   while((c = getc(fp)) != '#')
   {
      word[i++] = c;
      if(c==EOF)
         Err(7,NULL);
      if(i==WORLEN-2)
         Err(4,NULL);
   }

   word[i] = '\0';
   if(strcmp(word,directive))
      Err(3,word);
}

//cita stanja tjuringove masine,
void ReadStates()
{
   int i;		
   SkipWs();
   stanja = (Stanje*)malloc(sizeof(Stanje));
   while(c!='#')
   {
      brStanja++;i=0;
      realloc(stanja,brStanja*sizeof(Stanje));
      if(stanja == NULL)
         Err(5,NULL);
      while(c!=';')
      {
         stanja[brStanja-1].name[i++] = c;
         if(i==WORLEN-2)
            Err(6,NULL);
         c = getc(fp);
      }
		stanja[brStanja-1].name[i]='\0';
      SkipWs();
   }
}

//cita jezik sa kojim radi tjuringova masina
void ReadLang()
{
   SkipWs();
 //  L = (char*)malloc(sizeof(char));
   while(c!='#')
   {
      brSlova++;
    //  realloc(L,brSlova*sizeof(char));
   //   if(L == NULL)
    //     Err(5,NULL);
      L[brSlova-1] = c;
      SkipWs();
      if(c!=';'){
      	int i;for(i=0;i<brSlova;i++) printf("\n %c",L[i]);
      	putchar(c);
         Err(8,";");}
      SkipWs();
      putchar(L[brSlova-1]);
    }
	brSlova++;
	//realloc((void*)L,(size_t)brSlova*sizeof(char));
	L[brSlova-1] = '*';
}

//poomcna funkcija za parsiranje proverava za regularni izraz tipa  " [space]* , [space]*
void CheckComma()
{
	SkipWs();
	if(c!=',')
		Err(8,",");
	SkipWs();
}

//ovu funkciju koristi funkcija ReadRules, proverava da li simbol zadat u
//pravilu za neko stanje uopste posotji u definisanoj azbuci
int CheckLetter()
{
	int i=0;
	for(i=0;i<brSlova;i++)
		if(L[i]==c)
		{
			return i;
			i = brSlova+1;
		}
	if(i==(brSlova+1))
		Err(10,NULL);
}

//proverava da li string pripada skupu stanja, nakon stringa se ocekuje karakter next
int CheckAndGetState(char next)
{
	char sname[WORLEN],i=0;
	while(c!=next)
	{
		sname[i++] = c;
		c=getc(fp);
		if(c == EOF)
			Err(7,NULL);
		if(i==WORLEN-2)
			Err(6,NULL);
	}
	sname[i]='\0';
	for(i=0;i<brStanja;i++)
		if(!strcmp(sname,stanja[i].name))
			{
				return i;
				i=brStanja+1;
			}
	if(i==(brStanja+1))
		Err(9,sname);
}

//cita pravila, tj algoritam tjuringove masine u formatu:
// <stanje>:(<a>,<b>,<LNR>,<stanje2>)
//gde je <stanje> stanje za koje definisemo pravila, <a> karakter koji se
//cita sa trake, <b> karakter koji se pise na traku, <LNR> pravac pomeranja trake
//i <stanje2> sledece stanje tjuringove masine
void ReadRules()
{
   int i,state,letter,change,next;
   for(i=0;i<brStanja;i++)
      stanja[i].rules = (Rule*)calloc(brSlova,sizeof(Rule));
   SkipWs();
   while(c!='#')
   {
      state = CheckAndGetState(':');
      if(c!=':')
         Err(8,":");
      SkipWs();
      if(c!='(')
       Err(8,"(");
      SkipWs();
      letter = CheckLetter();
      CheckComma();
      change = CheckLetter();
      stanja[state].rules[letter].changed = L[change];
      CheckComma();
      if(c!='L' && c!='N' && c!='R')
         Err(11,NULL);
      stanja[state].rules[letter].LNR = c;
      CheckComma();
      next = CheckAndGetState(')');
      stanja[state].rules[letter].next = next;
      SkipWs();
      if(c!=';')
         Err(8,";");
      SkipWs();
   }
}

//proverava da li karaketer na traci pripada definisanoj azbuci
int CheckTapeL()
{
   int i;
   for(i=0;i<brSlova;i++)
		if(c==L[i])
			return 1;
   if(c == ';')
	return 0;
   if(c == EOF)
	Err(7,NULL);
   else 
	Err(10,NULL);
}

//funkcija koja cita traku definisanu direktivom #traka# i
//smesta  je u niz tape*
void ReadTape()
{
   SkipWs();
//   tape = (char*)malloc(sizeof(char));
   while(CheckTapeL())
   {
   //   realloc(tape,sizeof(char)*(tapeLen));
	//  if(tape == NULL)
   //      Err(5,NULL);
      tape[tapeLen++]=c;
      c = getc(fp);
   }
   SkipWs();
}

//funkcija koja vraca indeks zavrsnog stanja definisanog direktiivom #zavrsna#
int GetEndState()
{
   char sname[WORLEN],i=0;
   while(((c=getc(fp))==' ') || (c=='\n'))
      if(c=='\n')
		lineNo++;
   if(c==EOF)
      return -1;
   while(c!=';')
   {
      sname[i++] = c;
      c=getc(fp);
      if(c == EOF)
	  {
         Err(8,";");
		 Err(7,NULL);
	  }
      if(i==WORLEN-2)
         Err(6,NULL);
   }
   sname[i]='\0';
   for(i=0;i<brStanja;i++)
      if(!strcmp(sname,stanja[i].name))
         return i;
   Err(9,sname);
}

//funkcija koja cita sva zavrsna stanja definsiana direktivom #zavrsna#
void ReadEndStates()
{
   int i;
   zavrsna = (int*)malloc(sizeof(int));
   SkipWs();
   i = CheckAndGetState(';');
   zavrsna[brZavrsnih] = i;
   while((i = GetEndState())!=-1)
   {
      realloc(zavrsna,((++brZavrsnih)+1)*sizeof(int));
	  zavrsna[brZavrsnih]=i;
   }
	brZavrsnih++;
}

//funkcija cita prvo stanje, tj,stanje od kojeg masina pocinje sa radom
//definisano direktivom #pocetno#
int ReadFirstState()
{
   SkipWs();
   pocetno = CheckAndGetState(';');
   SkipWs();
}

//funkcija shiftuje sadrzaj trake za jedno mesto udesno
void TapeShr()
{
	int i;
	for(i=tapeLen-1;i>0;i--)
		tape[i]=tape[i-1];
}

//vraca ne nula broj ako je stanje sa indexom state zavrsno stanje Tjuringove masine
int IsEndState(int state)
{
	int i;
	int f=0;
	for(i=0;i<brZavrsnih;i++)
		if(zavrsna[i]==state){
			printf("zavrsno");
			return 1;
		}	
		printf("\nnije zavrsno \n ");
	return 0;
}

//sve se onda zbiva tu ispod sheshira :)
//ova funkcija simulira rad tjuringove masine definisane
//globalnim promenljivama stanja,brStanja,tape,tapeLen,L,pocetno,zavrsna i brZavrsnih
void RunProgram()
{
	int curState = pocetno,curTapePos =0,curLetterIndex=0,j;
        printf("\nPocetno stanje: %s \n",stanja[curState].name);
	while(!IsEndState(curState))
	{
		printf("\nTM u stanju %s\n",stanja[curState].name);
		//trazim index tekuceg slova u nizu L
		for(j=0;j<brSlova;j++)
			if(L[j]==tape[curTapePos])
			{
				curLetterIndex = j;
				j = brSlova;
			}
	        //menjam tekuce slovo
		tape[curTapePos] = stanja[curState].rules[curLetterIndex].changed;

		//shiftujem traku levo, desno, odnsono ostavljam je u nepromenjenom polozaj
		//pritom se obradjuju slucajevi kad se dodje do ''kraja'', tj ''pocetka'' trake
		switch(stanja[curState].rules[curLetterIndex].LNR)
		{
			case 'N':
				break;
			case 'R':
				if(curTapePos == (tapeLen-1))
				{
				//	realloc(tape,++tapeLen*sizeof(char));
					tape[tapeLen]='*';
					tapeLen+=2;
				}
				curTapePos++;
				break;
			case 'L':
				if(curTapePos == 0)
				{
				//	realloc(tape,++tapeLen*sizeof(char));
					TapeShr();
					tape[0]='*';
					tapeLen++;
				}
				else
					curTapePos--;
				break;
		}
		//postavljam sledece stanje
		curState = stanja[curState].rules[curLetterIndex].next;
	}
}



int main(int argc,char *argv[])
{
   int i;

   if(argc!=2)
      Err(1,NULL);
   fp = fopen(argv[1],"rt");

   if(fp==NULL)
      Err(2,argv[1]);

  //ucitavam datoteku koja sadrzi specifikacije tjuringove masine
   SkipWs();
   CheckDirective("stanja");
   ReadStates();
   CheckDirective("azbuka");
   ReadLang();
   CheckDirective("pravila");
   ReadRules();
   CheckDirective("traka");
   ReadTape();
   CheckDirective("pocetno");
   ReadFirstState();
   CheckDirective("zavrsna");
   ReadEndStates();
   printf("\nDatoteka %s uspesno ucitana!",argv[1]);

   //stampam informacije sadrzane u zadatoj datoteci
   printf("\n\nDefinisana stanja: \n");
   for(i=0;i<brStanja;i++)
      printf(" %s",stanja[i].name);

   printf("\n\nJezik:");
   for(i=0;i<brSlova;i++)
	printf("%c ",L[i]);

   printf("\n\nTraka:\n");
   for(i=0;i<tapeLen;i++)
	 printf("%c ",tape[i]);

   printf("\n\nPocetno stanje: %s ",stanja[pocetno].name);
   printf("\n\nZavrsna stanja:");
   for(i=0;i<brZavrsnih;i++)
      printf(" %s ",stanja[zavrsna[i]].name);

   //simulacija TMa
   RunProgram();

   //rezultat izvrsenja TMa
   printf("\n\nTraka posle izvrsenja programa:\n");
   for(i=0;i<tapeLen;i++)
	printf("%c ",tape[i]);
   printf("\n\n");
   //oslobadjam zauzetu memoriju
 //  for(i=0;i<brStanja;i++)
//		free(stanja[i].rules);
//   free(stanja);
   //free(tape);

 //  fclose(fp);
}