/*
 * 	1. Konstruirati NKA (nedeterministicki konacni automat) koji ce
 * 	prihvacati sve moguce zapise cijelih i realnih brojeva te ga
 * 	programski realizirati. Program iz datoteke cita pojedine zapise koji
 * 	mogu biti odvojeni prazninama, tabulatorima te znakovima za novi red.
 * 	Za svaki zapis program treba provjeriti pripada li u zadanu klasu te
 * 	to ispisati u posebnu datoteku.
 * PRIMJER:
 * 	Cijeli brojevi:		22	0	8	-112	+0
 *	Realni brojevi:		2.5	.5	0.0	2e-8	+3.E+4	55.
 *	Ne prihvaca:		.	023	.e4	2e-8.2
 */

/*
 * Program pisao: Dinko Korunic; 36355514; e-mail: kreator@fly.srk.fer.hr 
 * Koristena literatura
 * 	prof. Srbljic: AFJJP1
 * 	Art of Assembly Programming, Chapter 16
 * 	razliciti `finite-state automaton' tekstovi
 * 	comp.compilers, comp.compilers FAQ, ...
 *
 * $Id: afjjp1-1.c,v 2.26 2000/10/05 14:56:50 kreator Exp $
 */

#include <errno.h>
#include <fcntl.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
#include <string.h>

#include <gc.h>
#define malloc(n) GC_malloc(n) /* GC za malloc */
#define free(n) 0 /* nije preporucljiva upotreba GC_free() */

/* Datoteke */
#define OUTPUTFILE "izlaz.txt" /* Izlazna dadoteka */
#define INPUTSTATE "stanja.txt" /* Tablica stanja */
#define INPUTTRANS "trans.txt" /* Transliteracijski niz */
#define INPUTLABEL "oznake.txt" /* Oznake trans. stanja */

/* Macro za detekciju delimitera koji su navedeni u opisu zadatka; buduci da
 * input file moze biti i DOS [tm] based, neka bude i cr/lf par. */
#define ismydelim(x) ((x==' ') || (x=='\n') || (x=='\t') || (x=='\r'))

/* Misc defineovi potrebni za daljnji rad */
#define EPSI '*' /* Ako je doticno definirano, automat moze simulirati i
		    epsilon prijelaze, dakle bez ulaznih znakova; meni je
		    dodati u NFA simulator bio zapravo programerski izazov,
		    tako da sam napravio i vishe nego sto je trebalo.. */
#define BLANK 'x'/* Nema vishe slijedecih stanja */

/* Struktura koja se nalazi u polju stanja za svako individualno stanje i
 * pokazuje na slijedeca stanja iz doticnog. */
typedef struct state_struct
{
  char *nextstate; /* Niz znakova odijeljenih ',', NFA! */
  int isfinal; /* Doticno stanje je prihvatljivo ili ne, 0/!0 Takodjer, 1
		  oznacava prvu klasu, 10 drugu, 100 trecu.. radi koristenja
		  OR */
}
state_type;

/* Tablica stanja (string koji se kasnije prebacuje u strukturu) */
char *stanja;
/* (Optimizirana) tablica transliteracije (string) */
char *znakovi;
/* String koji sluzi za pozicioniranje unutar tablice stanja, to su oznake
 * stanja koje smo rabili u tablici stanja sa identicnim redoslijedom */
char *oznake_stanja;
/* Duzina tablice stanje, sirina tablice stanja */
int tabell, tabelw;

/* Prototipovi */
void misc_simul (int, char **);
char *misc_input (char *);
char *purify (char *);
state_type *init_simul (void);
void trans_string (char *);
int simul_nfa (const state_type *, const char *, int);
char *strtoken (char **, char *, char *);
char *index (const char *, int);
char *mystrdup(const char *);

/* Glavni program :-) */
int main(int argc, char **argv)
{
  misc_simul(argc, argv);
  return(EXIT_SUCCESS);
}

/* Funkcija za inicijalizaciju i punjenje razlicitih struktura, razlicite
 * pre-simulator funkcije */
void misc_simul(int argc, char **argv)
{
  char *buffptr, *posp, *charp;
  state_type *state_table;
  int retval;
  FILE *izlaz;

  /* Pozovi ucitavanje */
  if (argc==2)
    posp=buffptr=misc_input(argv[1]);
  else
    {
      fprintf(stderr, "Krivi parametri\n");
      exit(EXIT_FAILURE);
    }

  /* Napunimo potrebne varijable */
  stanja=misc_input(INPUTSTATE);
  znakovi=misc_input(INPUTTRANS);
  oznake_stanja=misc_input(INPUTLABEL);

  /* Ocistimo doticne od mogucih delimitera */
  purify(stanja);
  purify(znakovi);
  purify(oznake_stanja);

#ifdef DEBUG
  fprintf(stderr, "%s\n%s\n%s\n", stanja, znakovi, oznake_stanja);
#endif

  /* Pozovemo inicijalizaciju (epsi) NFA simulatora */
  state_table=init_simul();

  /* Otvorimo izlaznu dadoteku za fprintf() */
  if ((izlaz=fopen(OUTPUTFILE, "w"))==NULL)
    {
      perror("Ne mogu otvoriti izlaznu datoteku");
      exit(EXIT_FAILURE);
    }

  /* Alociramo memoriju za najgori slucaj! */
  charp=malloc((strlen(buffptr)+1));
  for (;;)
    {
      for (;ismydelim(*posp); ++posp);
      /* Baah. Naime, trebalo bi staviti width.. rado bih koristio a
       * flag koji nazalost nije u ANSI-C specifikacijama :-( */
      if (sscanf(posp, "%s", charp)==EOF)
	break;
      fprintf(izlaz, "%s\t", charp);
      /* Provjeravamo pojedine zapise */
      trans_string(charp); /* Transliteriraj doticni */
      fprintf(izlaz, "%s\t", charp);
      if ((retval=simul_nfa(state_table, charp, 0)))
	fprintf(izlaz, "se prihvaca sa %d\n", retval);
      else
	fprintf(izlaz, "se ne prihvaca\n");
      posp+=strlen(charp);
    }

  if (fclose(izlaz)==EOF)
    {
      perror("Ne mogu zatvoriti izlaznu datoteku");
      exit(EXIT_FAILURE);
    }
}

/* F-ja za obavljanje misc operacija nad ulaznom datotekom */
char *misc_input(char *inputfile)
{
  int fd; /* File descriptor */
  struct stat statbuf; /* Saznamo velicinu ulaznog teksta */
  char *buffptr;

  /* Otvori ulaznu datoteku i kopiraj u memoriju */
  if ((fd=open(inputfile, O_RDONLY, S_IRUSR|S_IWUSR))==-1)
    {
      perror("Ne mogu otvoriti datoteku s ulaznim podacima");
      exit(EXIT_FAILURE);
    }
  if (fstat(fd, &statbuf)==-1)
    {
      perror("Ne mogu dobiti podatke o ulaznoj datoteci");
      exit(EXIT_FAILURE);
    }
  if ((buffptr=malloc(statbuf.st_size))==NULL)
    {
      perror("Ne mogu alocirati memoriju za ulazne podatke");
      exit(EXIT_FAILURE);
    }
  if (read(fd, buffptr, statbuf.st_size)==-1)
    {
      perror("Ne mogu procitati podatke iz ulazne datoteke");
      exit(EXIT_FAILURE);
    }
  if (close(fd)==-1)
    {
      perror("Ne mogu zatvoriti ulaznu datoteku");
      exit(EXIT_FAILURE);
    }

  /* Terminiraj doticni */
  *(buffptr+statbuf.st_size-1)=0;
  return buffptr;
}

/* Funkcija za brzo pretrazivanje po nizu i zamjenu znakova, sto je zapravo
 * _transliteriranje_ u ovom slucaju */
void trans_string(char *oldstring)
{
  char *posp, *charp, *pos, *stringp, *tmp=mystrdup(znakovi);

  /* Polako scanniraj ulazni niz i transliteriraj, s time sto se ide po
   * razlicitim klasama za transliteriranje i zamjenjuje svaki znak koji
   * se pojavljuje */
  for (stringp=strtoken(&posp, tmp, ";"); stringp!=NULL;
       stringp=strtoken(&posp, NULL, ";"))
    for (charp=stringp+1; *charp; ++charp)
      for (pos=oldstring; (pos=index(pos, *charp))!=NULL;
	   *(pos++)=*stringp);
  free(tmp);
}

/* Funkcija za simuliranje rada NFA automata (a moze i epsi-NFA) */
int simul_nfa(const state_type *state_table, const char *charp, int currstate)
{
  int retval=0;
  char *nextstate, *stringp, *posp=NULL, *pos, *poseth;

#ifdef DEBUG
  fprintf(stderr, "Sad sam u stanju %d.\n", currstate);
#endif

#ifdef EPSI
  /* Dodaj i epsi prijelaz u listu prijelaza */
  if ((poseth=index(oznake_stanja, EPSI))!=NULL)
    {
      nextstate=mystrdup(state_table[currstate*tabelw
				   +poseth-oznake_stanja].nextstate);
#ifdef DEBUG
      fprintf(stderr, "[%d] (eth) I mogu ici iz %d u %s\n", retval,
	      currstate, nextstate);
#endif
      for (stringp=strtoken(&posp, nextstate, ",");
	   stringp!=NULL; stringp=strtoken(&posp, NULL, ","))
	{
	  if (*stringp==BLANK)
	    {
	      if (!(*charp))
		retval|=state_table[currstate*tabelw].isfinal;
	    }
	  else
	    retval|=simul_nfa(state_table, charp, atoi(stringp));
	}
      free(nextstate);
    }
#endif /* EPSI */

  /* Trenutni ucitani znak nije kraj */
  if (*charp)
    {
      /* Uupsie. ucitali smo znak koji nije dozvoljen! */
      if ((pos=index(oznake_stanja, *charp))==NULL)
	return 0;
      
      /* Ptr. na niz u kojem su sadrzana stanja koja treba obici */
      nextstate=mystrdup(state_table[currstate*tabelw
				   +pos-oznake_stanja].nextstate);
#ifdef DEBUG
      fprintf(stderr, "[%d] I mogu ici u iz %d u %s za %c\n",
	      retval, currstate, nextstate, *charp);
#endif
      /* Napravi rekurzivno pozivanje */
      for (posp=NULL, stringp=strtoken(&posp, nextstate, ",");
	   stringp!=NULL; stringp=strtoken(&posp, NULL, ","))
	{
	  if (*stringp!=BLANK)
	    retval|=simul_nfa(state_table, charp+1, atoi(stringp));
	}
      free(nextstate);
    }
  else
    /* Oho, dosli smo do kraja niza! */
    retval|=state_table[currstate*tabelw].isfinal;
  
  return retval;
}

/* Funkcija za inicijalizaciju dinamickih struktura i parsiranje definiranih
 * stanja iz hardcoded tablice stanja */
state_type *init_simul(void)
{
  char *stringp, *posp, *tmpstanja=mystrdup(stanja);
  int i, j, k;
  state_type *root;

  tabelw=strlen(oznake_stanja);
  for (i=0, posp=tmpstanja; *posp; posp++)
    if (*posp==';')
      i++;

  if (i%(tabelw+1))
    {
      fprintf(stderr, "Krivo zadana tablica stanja\n");
      exit(EXIT_FAILURE);
    }
  tabell=i/tabelw;

  root=malloc(sizeof(state_type)*tabelw*tabell);

  /* Razdvojimo ih po ';' delimiteru */
  for (i=1,j=0,stringp=strtoken(&posp, tmpstanja, ";"); stringp!=NULL;
       stringp=strtoken(&posp, NULL, ";"), ++i)
    {
      if (i%(tabelw+1))
	{
#ifdef DEBUG
	  fprintf(stderr, "%-5s ", stringp);
#endif
	  root[j++].nextstate=mystrdup(stringp);
	}

      /* Oho, treba upisati isfinal flag */
      else
	{
#ifdef DEBUG
	  fprintf(stderr, "\t\t%s\n", stringp);
#endif
	  for (k=j; k>=j-tabelw; k--)
	    root[k].isfinal=atoi(stringp);
	  /* Bitno je primijetiti kako sam kasnije u kodu
	   * koristio |= moguce je onda razlikovati vishe i
	   * nizhe upaljenje bitove kod isfinal i time
	   * razlikovati _vishe_ prihvatljivih stanja! */
	}
    }
  free(tmpstanja);
  
  return root;
}

/* Naime, strsep je tek BSD 4.4 specific. A strtok _je_ ANSI-C, medjutim ne
 * funkcionira kad su prazna polja prisutna. */
char *strtoken(char **save, char *str, char *fs)
{
  char *pos=*save, /* Zadnja pozicija (kod zadnjeg poziva) */
    *tmp;
  if (str!=NULL) pos=str; /* Uu.. scanniramo novi string */
  for (;pos && *pos &&
	 index(fs, *pos)!=NULL; ++pos); /* Izbjegni vodece sep. */
  if (!pos || !*pos)
    return (pos=*save=NULL); /* Baah. String ima samo separatore */
  tmp=pos; /* OK. Zadrzi poziciju tokena */
  for (;*pos && index(fs, *pos)==NULL; ++pos); /* Izbjegni sadrzaj tokena */
  if (*pos) *pos++=0; /* Makni prvi separator poslije tokena */
  else pos=NULL; /* Gle! Kraj stringa :-) */
  *save=pos;
  return(tmp);
}

/* Funkcija za ciscenje razlicitih delimitera koji `mozda' mogu uletjeti u
 * inicijalizacijske dadoteke */
char *purify(char *string)
{
  char *tmp;
 
  for (tmp=string; *tmp; ++tmp)
    if (ismydelim(*tmp))
      strcpy(tmp, tmp+1);
  /* Kazu za strcpy `may not overlap', no kako je prvi parametar
   * ispod, onda ce raditi, bio bi bolji memmove() */
  return string;
}

/* Vlastita verzija mystrdup() da bi mogli implementirati GC nad istom */
char *mystrdup(const char *oldstr)
{
  char *newstr=malloc(strlen(oldstr)+1);
  return strcpy(newstr, oldstr);
}