%{
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

extern int yylineno;
extern char *yytext;
extern FILE *yyin;

struct transFn {
	char *state;
	char *input;
	char *result;
	struct transFn *nextPtr;
};
struct stringNode {
	char *value;
	struct stringNode *nextPtr;
};

typedef struct transFn TRANSFN;
typedef struct stringNode STRING_NODE;

char statesVar[256];
char alphabetVar[256];
char functionVar[256];
char acceptingVar[256];
char startState[256];

char TEMPSTATE[20][256];
char TEMPINPUT[20][256];
char TEMPRESULT[256];

TRANSFN *firstTransPtr;
TRANSFN *lastTransPtr;
TRANSFN *newTransPtr;
TRANSFN *currentTransPtr;

STRING_NODE *firstInputPtr;
STRING_NODE *lastInputPtr;
STRING_NODE *currentInputPtr;

STRING_NODE *firstStatePtr=NULL;
STRING_NODE *lastStatePtr;
STRING_NODE *currentStatePtr;

STRING_NODE *firstAcceptPtr= NULL;
STRING_NODE *lastAcceptPtr;
STRING_NODE *currentAcceptPtr;

STRING_NODE *newListPtr;
STRING_NODE *lastListPtr;
STRING_NODE *firstListPtr;
STRING_NODE *currentListPtr;
STRING_NODE *tmpPtr;

int deltaCount=0;
int stateCount=0;
int inputCount=0;
int acceptCount=0;
int listCount=0;
int recurse=0;
int inputBool, stateBool[20], listBool;

/* prototypes */

void displayFn();


%}
%union {
   char string[256];
   }
%token <string> WHITESPACE
%token <string> EQUALS
%token <string> OPENBRACKET
%token <string> CLOSEBRACKET
%token <string> OPENBRACE
%token <string> CLOSEBRACE
%token <string> IN
%token <string> SYMBOL
%token <string> COMMA
%token <string> SEMICOLON
%token <string> COLON
%token <string> EMPTYSET
%token <string> UNKNOWN

%%  

statements:
   statement SEMICOLON statements
   {
   } |
   {
   };
statement:
   language     {  }
   | defn  	{  }
   | function 	{  };
language:
   SYMBOL EQUALS OPENBRACKET SYMBOL COMMA SYMBOL COMMA SYMBOL COMMA SYMBOL COMMA SYMBOL CLOSEBRACKET
   {
	strcpy(statesVar,$4);
	strcpy(alphabetVar,$6);
	strcpy(functionVar,$8);
	strcpy(startState, $10);
	strcpy(acceptingVar,$12);
	printf("found language definition\n");
   };
defn:
   SYMBOL EQUALS OPENBRACE list CLOSEBRACE
   {	
		if(strcmp($1,statesVar)==0) {
   		printf("found state definition - %s\n",$1);
     		firstStatePtr = firstListPtr;
      	lastStatePtr = lastListPtr;
	   	stateCount = listCount;
      	listCount = 0;
   	}    
		else if(strcmp($1,alphabetVar)==0) {
	   	printf("found alphabet definiton - %s\n",$1);
	   	firstInputPtr = firstListPtr;
	   	lastInputPtr = lastListPtr;
	   	inputCount = listCount;
	   	listCount = 0;
	   }
	  	else if(strcmp($1,acceptingVar)==0) {
	   	printf("found accepting state definition - %s\n",$1);
			firstAcceptPtr = firstListPtr;
			lastAcceptPtr = lastListPtr;
			acceptCount = listCount;
			listCount = 0;
	   }
		else
           printf("found unknown symbol - %s\n",$1);
   } |
   SYMBOL EQUALS EMPTYSET
   {
		if(strcmp($1,statesVar)==0) { 
           printf("ERROR -- found EMPTY state definition - %s\n",$1);
           exit(0);
   	}
      else if(strcmp($1,alphabetVar)==0) {
	   	printf("ERROR -- found EMPTY alphabet definiton - %s\n",$1);
	   	exit(0);
	   }
      else if(strcmp($1,acceptingVar)==0)
	   	printf("found EMPTY accepting state definition - %s\n",$1);
		else
         printf("found unknown symbol - %s\n",$1);
   } |
   SYMBOL EQUALS SYMBOL
   {
   	if(strcmp($3,"0")==0) 
   	{
	   	if(strcmp($1,statesVar)==0) { 
              printf("ERROR -- found EMPTY state definition - %s\n",$1);
              exit(0);
         }
         else if(strcmp($1,alphabetVar)==0) {
	      	printf("ERROR -- found EMPTY alphabet definiton - %s\n",$1);
	      	exit(0);
	      }
         else if(strcmp($1,acceptingVar)==0)
	      	printf("found EMPTY accepting state definition - %s\n",$1);
	   	else
              printf("found unknown symbol - %s\n",$1);
      }   
   	else
           printf("found unknown symbol - %s\n",$1);
   };
function:
   SYMBOL OPENBRACKET pair CLOSEBRACKET EQUALS function
   {
   	/* create new TRANSFN node */
   	recurse--;
		if (strcmp($1,functionVar) != 0)
			printf("WARNING: unknown symbol name: %s\n",$1);
		else 
		{
 			if (stateBool[recurse] ==0) {
 				printf("ERROR1: Invalid state string: %s\n",TEMPSTATE[recurse]);
 				exit(0);
 			}

   		newTransPtr = malloc(sizeof(TRANSFN));
   		if (deltaCount==0) 
   		{ 
   	   	firstTransPtr = newTransPtr;
   	   	lastTransPtr = newTransPtr;
   		}
   		else 
   		{
   	   	(*lastTransPtr).nextPtr = newTransPtr;
   	   	lastTransPtr = newTransPtr;
   		}
   		deltaCount++;
   		(*newTransPtr).nextPtr = NULL;
   		(*newTransPtr).state = malloc(sizeof(strlen(TEMPSTATE[recurse])+1));
   		strcpy((*newTransPtr).state, TEMPSTATE[recurse]);
   		(*newTransPtr).input = malloc(sizeof(strlen(TEMPINPUT[recurse])+1));
   		strcpy((*newTransPtr).input, TEMPINPUT[recurse]);
   		(*newTransPtr).result = malloc(sizeof(strlen(TEMPRESULT)+1));
   		strcpy((*newTransPtr).result, TEMPRESULT);
		}
   } |
   SYMBOL OPENBRACKET pair CLOSEBRACKET EQUALS SYMBOL COLON SYMBOL IN OPENBRACE list CLOSEBRACE
   {
   	/* create new TRANSFN node */
   	recurse--;
      if (strcmp($1, functionVar) != 0)
      	printf("WARNING: unknown symbol name: %s\n",$1);
      else 
      {  
			if ((stateBool[recurse] ==0)&&(strcmp(TEMPSTATE[0],$6)!=0)) 
			{
  				printf("ERROR2: Invalid state string: %s\n",TEMPSTATE[recurse]);
  				exit(0);
  			}

			if ((strcmp(TEMPSTATE[0], $6)!=0) || (strcmp($6, $8)!=0)) 
			{
				printf("ERROR: Invalid transition function: %s(%s,%s)\n",$1,TEMPSTATE[0],TEMPINPUT[0]);
				exit(0);
			}
			currentListPtr = firstListPtr;

			while(currentListPtr != NULL) 
			{
				currentStatePtr=firstStatePtr;
				listBool=0;
				while(currentStatePtr!=NULL) {
					if(strcmp((*currentListPtr).value,(*currentStatePtr).value)==0) {
						listBool++;
					}
					currentStatePtr=(*currentStatePtr).nextPtr;
				}
				if(listBool==0) {
					printf("ERROR: Invalid state reference found in delta: %s\n",(*currentListPtr).value);
					exit(0); 
				}
        		newTransPtr = malloc(sizeof(TRANSFN));
				(*newTransPtr).nextPtr = NULL;
 
   	     	if (deltaCount==0) 
   	     	{
      	  	   firstTransPtr = newTransPtr;
        		   lastTransPtr = newTransPtr;
        		}
        		else 
        		{
           		(*lastTransPtr).nextPtr = newTransPtr;
           		lastTransPtr = newTransPtr;
        		}
        		deltaCount++;
 
				(*newTransPtr).state = (*currentListPtr).value;
				(*newTransPtr).input = TEMPINPUT[0];
				(*newTransPtr).result = (*currentListPtr).value;
				
				currentListPtr = (*currentListPtr).nextPtr;

			}
		}					
   } |
   SYMBOL
   {
   	/* Store $1 as TEMPRESULT */
		printf("recurse: %d\n",recurse);
		stateBool[recurse]=0;
		currentStatePtr=firstStatePtr;
		while(currentStatePtr!=NULL) {
			if(strcmp($1,(*currentStatePtr).value)==0) {
				stateBool[recurse]++;
			}
			currentStatePtr=(*currentStatePtr).nextPtr;
		}
		if(stateBool[recurse] == 0) {
			printf("ERROR: Invalid member of state set: %s\n",$1);
			exit(0);
		}		
   	strcpy(TEMPRESULT, $1);
   };

list:
	list COMMA SYMBOL
	{

		/* Store $3 as STRING_NODE */
		newListPtr = malloc(sizeof(STRING_NODE));
		if(listCount==0) {
			firstListPtr = newListPtr;
			lastListPtr = newListPtr;
		}
		else {
			(*lastListPtr).nextPtr = newListPtr;
			lastListPtr = newListPtr;
		}
		listCount++;
		(*newListPtr).nextPtr = NULL;
		(*newListPtr).value = malloc(sizeof(strlen($3)+1));
		strcpy((*newListPtr).value, $3);

		
	} |
	SYMBOL
	{
		/* Store $1 as STRING_NODE */
		newListPtr = malloc(sizeof(STRING_NODE));
		if(listCount==0) {
			firstListPtr = newListPtr;
			lastListPtr = newListPtr;
		}
		else {
			(*lastListPtr).nextPtr = newListPtr;
			lastListPtr = newListPtr;
		}
		listCount++;
		(*newListPtr).nextPtr = NULL;
		(*newListPtr).value = malloc(sizeof(strlen($1)+1));
		strcpy((*newListPtr).value, $1);

	

	};   
pair:
   SYMBOL COMMA SYMBOL
   {
   	/* Store $1 as TEMPSTATE and $3 as TEMPINPUT */
		strcpy(TEMPSTATE[recurse], $1);
		strcpy(TEMPINPUT[recurse], $3);
      
      currentStatePtr=firstStatePtr;
   	stateBool[recurse]=0;

  		while(currentStatePtr!=NULL) {
  			if(!strcmp($1,(*currentStatePtr).value)) {
  				stateBool[recurse]++;
  			}
  			currentStatePtr=(*currentStatePtr).nextPtr;
  		}
  		printf("stateBool: %d[%d]\n",stateBool[recurse], recurse);
   	inputBool=0;
   	currentInputPtr=firstInputPtr;
  		while(currentInputPtr!=NULL) {
  			if(!strcmp($3,(*currentInputPtr).value)) {
  				inputBool++;
  			}
  			currentInputPtr=(*currentInputPtr).nextPtr;
  		}
  		if (inputBool ==0) {
  			printf("ERROR2: Invalid input string: %s\n",$3);
  			exit(0);
  		}
   	recurse++;
  		
};
%%
   int yyerror (char *s)
   {
     fprintf (stderr, "line %d: %s at \"%s\"\n",yylineno,s,yytext);
     return 0;
   }
   int main (int argc, char **argv)
   {
       FILE *datain;
       char currentState[256];
       char alpha;
       char inputstr[256];
       TRANSFN *currentPtr;
       STRING_NODE *acceptPtr;
       int FinQ=0;
       STRING_NODE *accPtr, *QPtr;
       
       if(argc!=3)
       {
           printf("Incorrect number of arguments\n");
           exit(0);
       }

      yyin = fopen(argv[1],"r");
      if(!yyin)
      {
           printf("Unable to open automaton file");
           exit(0);
      }
      yyparse();
      fclose(yyin);
      displayFn();
      
      currentListPtr=firstStatePtr;
      while((*currentListPtr).nextPtr!=NULL) {      
      	currentStatePtr=(*currentListPtr).nextPtr;
			while(currentStatePtr!=NULL) {
				if(strcmp((*currentListPtr).value,(*currentStatePtr).value)==0) {
					printf("WARNING: Duplicate states found in Q: %s\n",(*currentListPtr).value);
				}
				currentStatePtr=(*currentStatePtr).nextPtr;
			}
			currentListPtr=(*currentListPtr).nextPtr;
		}
		if(listBool==0) {
			printf("ERROR: Invalid state reference found in delta: %s\n",(*currentListPtr).value);
			exit(0); 
		}


      /* CHECK FOR MISSING TRANSITION TABLE ENTRIES */
      currentStatePtr = firstStatePtr;
      while(currentStatePtr != NULL) {
			currentInputPtr=firstInputPtr;
      	while(currentInputPtr != NULL) {
      		inputBool=0;
      		currentTransPtr=firstTransPtr;      		     			
      		while(currentTransPtr != NULL) {
      			if( (strcmp((*currentTransPtr).state,(*currentStatePtr).value)==0) && (strcmp((*currentTransPtr).input, (*currentInputPtr).value)==0))
      				inputBool++;
					currentTransPtr = (*currentTransPtr).nextPtr;
      		}

      		if(inputBool==0) {
      			printf("WARNING: There are empty transition table entries: delta(%s,%s)\n",(*currentStatePtr).value, (*currentInputPtr).value);
      		}
      		if(inputBool>1) {
					printf("WARNING: There are duplicate transition table entries: delta(%s,%s)\n",(*currentStatePtr).value, (*currentInputPtr).value);
				}
				currentInputPtr = (*currentInputPtr).nextPtr;					    		
			}
			currentStatePtr=(*currentStatePtr).nextPtr;
		}
			      
      datain = fopen(argv[2],"r");
      if(!datain)
      {
           printf("Unable to open data input file");
           exit(0);
      }
      strcpy(currentState, startState);
      fscanf(datain, "%c", &alpha);
      while (!feof(datain)) {
         if (!isspace(alpha))
            strncat(inputstr, &alpha, 1);
         else{
         	printf("%s ",inputstr);
         	currentPtr = firstTransPtr;
            if (strcmp("epsilon",inputstr)!=0) {
               while(((strcmp(inputstr,(*currentPtr).input))||(strcmp(currentState,(*currentPtr).state)))&&((*currentPtr).nextPtr != NULL))
               {
               	currentPtr = (*currentPtr).nextPtr;
               }	
               if(((strcmp(inputstr,(*currentPtr).input))||(strcmp(currentState,(*currentPtr).state)))&&(strcmp(inputstr,"\0")))
               {
                  printf("\nERROR: Non-deterministic input found: %s\n",inputstr);
                  exit(0);
               }
               strcpy(currentState, (*currentPtr).result); 
            }
            if(alpha=='\n'){
               /* check currentState with accepting states and print accept/reject */
            	acceptPtr = firstAcceptPtr;
            	if(acceptPtr != NULL)
            	{
            		while((strcmp(currentState,(*acceptPtr).value))&&((*acceptPtr).nextPtr!=NULL))
            		{
            	   	acceptPtr = (*acceptPtr).nextPtr;
           			}
           			if(strcmp(inputstr,"\0"))
           			{   
            			if(strcmp(currentState,(*acceptPtr).value))
            				printf(" - REJECT\n");
            			else
            	 			printf(" - ACCEPT\n");
            	 	}
            	}
            	else
            	{
            		printf(" - REJECT\n");
            	}
	       		strcpy(currentState, startState);
            }
            strcpy(inputstr, "\0");

         }               	
         fscanf(datain, "%c", &alpha);
      }
      fclose(datain);    
      return 0;
   }

/*  DISPLAY AUTOMATON DEFINITION */	

  void displayFn()
  {
      TRANSFN *fnPtr;
		STRING_NODE *tmpPtr;


		/* DISPLAY STATE SET */
		tmpPtr=firstStatePtr;
		printf("Q={");
		while(tmpPtr!=NULL){
			if(tmpPtr!=firstStatePtr)
				printf(",");
			printf("%s",(*tmpPtr).value);
			tmpPtr=(*tmpPtr).nextPtr;
		}

		/* DISPLAY INPUT SET */
		tmpPtr=firstInputPtr;
		printf("}\nSIGMA={");
		while(tmpPtr!=NULL){
			if(tmpPtr!=firstInputPtr)
				printf(",");
			printf("%s",(*tmpPtr).value);
			tmpPtr=(*tmpPtr).nextPtr;
		}
			
		
		/* DISPLAY ACCEPTING STATES */
		tmpPtr=firstAcceptPtr;
		printf("}\nF={");
		while(tmpPtr!=NULL){
			if(tmpPtr!=firstAcceptPtr)
				printf(",");
			printf("%s",(*tmpPtr).value);
			tmpPtr=(*tmpPtr).nextPtr;
		}
		printf("}\n");
				 
		/* DISPLAY TRANSITION FUNCTIONS */
      fnPtr=firstTransPtr;
      while(fnPtr!=NULL)
      {
        printf("DELTA(%s,%s)=%s\n",(*fnPtr).state,(*fnPtr).input,(*fnPtr).result);
        fnPtr=(*fnPtr).nextPtr;
      }

  }