#include <stdio.h>

int get_state(char input[256]); /* Gets what type of information the
                                   program is looking for */

int verify_ndpda(char input[256]); /* Verifies that the data in the
                                      specified file is for a
                                      non-deterministic pushdown
                                      automata */

int retrieve_mach_states(char input[256], char states[100][256], int
                         *stnum); /* Gets the states for the automaton */

int retrieve_symbols(char input[256], char symbols[100][256], int
                     *symbnm); /* Gets the symbols for the automaton */

/* The following verifies that the transitions stated in the file are
   legal. */

int verify_transitions(char input[256], int statenum,
                       int symnum, int stacknum, char states[100][256],
                       char symbols[100][256], char stack[100][256],
                       char transitions[100][256], int *trans);

/* The following verifies that the stated start state is legal */
int verify_start_state(char input[256], char states[100][256], int num);

/* The following verifies that the stated final state is legal */
int verify_final_states(char input[256], char states[100][256], char
                        final_states[100][256], int num, int *fstates);

/* The following gets the stack symbols for the automaton */
int retrieve_stack_symbols(char input[256], char stack[100][256], int
                           *stacknum);

/* The following finds a particular string in a list of strings. It
   returns the index of the string if it is found, and -1 if it is not. */
int find_string(char input[256], char index[100][256], int num);

/* The following removes all but one space between characters in a
   string */
void remove_space(char input[256], char output[256]);

/* The following is used to print certain string indexes for debugging
   purposes. It is not used in this program unless the program is in debug
   mode. */
void print_stuff(char input[100][256], int num);

void main(int argc, char *argv[]) {
    char filename[100]; /* Holds the name of the file to be read from */

    /* For the following: state holds the integer corresponding to the
       current type of information the program is looking for, mst is
       the number of states in the automaton, sym is the number of
       symbols in the automaton, ver, start, final, STATE_ERR,
       SYMBOL_ERR, STACK_ERR, TYPE_ERROR, and NDPDA all take return values
       and produce error messages accordingly, stack holds the number of
       stack symbols in the automaton, trans holds the number of
       transition functions in the automaton, and fstates holds the
       number of final states in the automaton */
    int state, mst = 0, sym = 0, ver = 0, start = 0, final = 0;
    int stack = 0, trans = 0, fstates = 0;
    int TYPE_ERROR = 0, NDPDA = 0;
    int STATE_ERR = 0, SYMBOL_ERR = 0, STACK_ERR = 0;

    char input[256] = "\0"; /* Holds the input from the file */

    /* Symbols holds the symbols for the automaton, while stack_symbols
       holds the stack symbols for the automaton */
    char symbols[100][256], stack_symbols[100][256];
    char mach_states[100][256]; /* Holds the states for the automaton */
    char transitions[100][256]; /* Holds the transitions for the
                                   automaton */
    char final_states[100][256]; /* Holds the final states for the
                                    automaton */
    int i, j; /* Counters */
    FILE *infile; /* Points to the file to be read from */

    /* Make certain that the proper amount of command line parameters have
       been entered */
    if(argc < 2) {
        printf("Usage: pda_regoc <filename>\n");
        exit(0);
    }

    /* Get the name of the file to be read from */
    strcpy(filename, argv[1]);
    
    /* Open the file */
    if((infile = fopen(filename, "r")) == NULL) {
        printf("Error opening file.\n");
        exit(0);
    }

    /* Loop until the line .end is read */
    while(strcmp(input, ".end\n")) {
        /* Read a string from the file and store it in input. If the end
           of the file is reached, print an error message and break out
           of the loop. */
        if(fgets(input, sizeof(input), infile) == NULL) {
            printf("Error: End of file reached.\n");
            break;
        }
        if(input[0] != '!') {  /* This line allows comments */
        if(input[0] == '.') state = 0; /* If the first character of the
                                          line is a period, look for the
                                          input type */

        /* In the following, we get a state from the get_state()
           function, and then according to the value returned from that
           function we search for particular data */
        switch(state) {
            case 0: printf("Getting input type.\n");
                    state = get_state(input); break;
            case 1: printf("Verifying automaton specifications.\n");
                    NDPDA = verify_ndpda(input);
                    if(!NDPDA) {
                        printf("This program can only verify ");
                        printf("non-deterministic pushdown automata.\n");
                        exit(0);
                    }
                    break;
            case 2: printf("Retrieving states.\n");
                    if(STATE_ERR != -1)
                        STATE_ERR = retrieve_mach_states(input,
                                             mach_states, &mst); 
                    else retrieve_mach_states(input, mach_states, &mst);
                    break;
            case 3: printf("Retrieving symbols.\n");
                    if(SYMBOL_ERR >= 0) {
                        SYMBOL_ERR = retrieve_symbols(input, symbols,
                                                     &sym);
                    }
                    else retrieve_symbols(input, symbols, &sym);
                    break;
            case 4: printf("Verifying transitions.\n");
                    if(ver >= 0) {
                        if((!mst) || (!sym)) {
                            if(!mst) printf("Error: No states.\n");
                            if(!sym) printf("Error: No symbols.\n");
                        }
                        else {
                            ver = verify_transitions(input, mst, sym,
                                                     stack,
                                                     mach_states,
                                                     symbols,
                                                     stack_symbols,
                                                     transitions,
                                                     &trans);
                        }
                    }
                    break;
            case 5: printf("Verifying starting state.\n");
                    if(start != -1) {
                        if((!mst) || (start)) {
                            if(!mst) printf("Error: No states.\n");
                            if(start) {
                                printf("Error: More than one"); 
                                printf(" starting state.\n");
                                start++;
                            }
                        }
                        else start = verify_start_state(input,
                                                        mach_states,
                                                        mst);
                    }
                    break;
            case 6: printf("Verifying ending states.\n");
                    if(final >= 0) {
                        if(!mst) printf("Error: No states.\n");
                        else final = verify_final_states(input,
                                                         mach_states,
                                                         final_states,
                                                         mst, &fstates);
                    }
                    break;
            case 7: printf("End of automaton specs.\n"); break;
            case 8: if(STACK_ERR != -1)
                        STACK_ERR = retrieve_stack_symbols(input,
                                           stack_symbols, &stack);
                    else retrieve_stack_symbols(input,
                                stack_symbols, &stack);
                    break;
            default: printf("Error: Unidentified type.\n"); 
                     TYPE_ERROR = 1;
                     break;
        }
      }
    }
    
    /* Here we print any errors that may have been found */
    if((!mst) || (!sym) || (!ver) || (!start) || (start > 1) ||
       (!fstates) || (ver < 0) || (start == -1) || (final < 0) ||
       (STATE_ERR == -1) || (SYMBOL_ERR < 0) || (STACK_ERR == -1) ||
       (TYPE_ERROR)) {
        printf("\n\nFinal Error Output:\n");
        if(!mst) printf("No states.\n");
        if(!sym) printf("No symbols.\n");
        if(!ver) printf("Unable to verify transition function.\n");
        if(STACK_ERR == -1) printf("Repeated state.\n");
        if(SYMBOL_ERR == -1) printf("Repeated symbol.\n");
        if(SYMBOL_ERR == -2)
            printf("Illegal use of a reserved word as a symbol.\n");
        if(STACK_ERR == -1) printf("Repeated stack symbol.\n");
        if(!start) printf("No starting state.\n");
        if(start > 1) printf("Too many starting states. (%d)\n", start);
        if(!fstates) printf("No final states.\n");
        if(ver == -1) printf("Invalid symbol in transition function.\n");
        if(ver == -2) printf("Invalid state in transition function.\n");
        if(ver == -3) printf("Incomplete transition.\n");
        if(ver == -4)
            printf("Invalid stack symbol in transition function\n");
        if(ver == -5) printf("Repeated transition.\n");
        if(start == -1) printf("Invalid starting state.\n");
        if(final == -1) printf("Invalid final state.\n");
        if(final == -2) printf("Repeated final state.\n");
        if(TYPE_ERROR) printf("Invalid type in input file.\n");
    }

    /* The following gets printed if there are no errors. */
    else printf("\n\nNon-Deterministic Pushdown Automaton Verified.\n");

    /* Debugging messages */
    #ifdef debug
    printf("\nStates:\n");
    print_stuff(mach_states, mst);
    printf("\nSymbols:\n");
    print_stuff(symbols, sym);
    printf("\nStack Symbols:\n");
    print_stuff(stack_symbols, stack);
    printf("\nFinal States:\n");
    print_stuff(final_states, fstates);
    #endif

    /* Close the file and exit */
    fclose(infile);
    exit(0);
}

/* Here we read the input, and according to what state it matches, we
   return a particular integer. */
int get_state(char input[256]) {
    if(strcmp(input, ".type\n") == 0) return 1;
    if(strcmp(input, ".states\n") == 0) return 2;
    if(strcmp(input, ".symbols\n") == 0) return 3;
    if(strcmp(input, ".transitions\n") == 0) return 4;
    if(strcmp(input, ".start-state\n") == 0) return 5;
    if(strcmp(input, ".final-states\n") == 0) return 6;
    if(strcmp(input, ".end\n") == 0) return 7;
    if(strcmp(input, ".stack-symbols\n") == 0) return 8;
    return -1;
}

/* Checks to make certain that the string listed underneath type is the
   symbol for a Non-Deterministic Pushdown Automaton */
int verify_ndpda(char input[256]) {
    if(strcmp(input, "NDPDA\n") == 0) return 1;
    else return 0;
}
/* This takes strings seperated by spaces and stores them in states[][].
   It also records the number of states found, and returns -1 if a
   state is repeated. */
int retrieve_mach_states(char input[256], char states[100][256], int
                         *stnum) {
    int i, j;
    char temp[256];
    int ERROR_VAL = 0;

    for(i = 0; i < strlen(input); i++) {
        j = 0;
        temp[0] = '\0';
        while((input[i] != ' ') && (input[i] != '\n')) {
            temp[j] = input[i];
            j++;
            i++;
        }
        temp[j] = '\0';
        if(temp[0] != '\0') {
            if(find_string(temp, states, *stnum) != -1) ERROR_VAL = -1;
            else {
                strcpy(states[(*stnum)], temp);
                (*stnum)++;
            }
        }
    }

    return ERROR_VAL;
}

/* This takes strings seperated by spaces and stores them under
   symbols[][]. It also records the number of symbols found, and
   returns -1 if a symbol is repeated, or -2 if the reserved
   string "NULL" is used as a symbol. */
int retrieve_symbols(char input[256], char symbols[100][256], int
                      *symbnm) {
    int i, j;
    char temp[256];
    int ERROR_VAL = 0;
            
    for(i = 0; i < strlen(input); i++) {
        j = 0;
        temp[0] = '\0';
        while((input[i] != ' ') && (input[i] != '\n')) {
            temp[j] = input[i];
            j++;
            i++;
        }
        temp[j] = '\0';
        if(temp[0] != '\0') {
            if(find_string(temp, symbols, *symbnm) != -1) ERROR_VAL = -1;
            else if(strcmp(temp, "NULL") == 0) ERROR_VAL = -2;
            else {
                strcpy(symbols[(*symbnm)], temp);
                (*symbnm)++;
            }
        }
    }
     
    return ERROR_VAL;
}


/* This function verifies that the necessary transition variables (the
   two states and either a symbol or NULL) are present, and also that
   the states, symbols, and stack symbols are all legal. If a state is not
   found it returns -2, if a symbol is not found, it returns -1, and if a
   stack symbol is not found, it returns -4. It also stores the transition
   strings under transitions[][] and the number of transitions under
   *trans. If a transition function is repeated, it returns -5. Finally,
   if a transition function is incomplete (i.e., is missing either one
   of the states, or the (symbol)U(NULL)) then it returns -3. */
int verify_transitions(char input[256], int statenum, int symnum,
                       int stacknum, char states[100][256], char
                       symbols[100][256], char stack[100][256],
                       char transitions[100][256], int *trans) {
    int GET_STATE1 = 1;
    int GET_SYMBOL = 0;
    int GET_STATE2 = 0;
    int GET_STACK_SYMBOLS1 = 0;
    int GET_STACK_SYMBOLS2 = 0;
    int ALL_FOUND = 0;
    char temp[256];
    int state1, state2;
    int i, j;

    for(i = 0; i < strlen(input); i++) {
        j = 0;
        temp[0] = '\0';
        if(GET_STATE1) {
            if(input[i] != ' ') {
                while((input[i] != ' ') && (input[i] != '\n')) {
                    temp[j] = input[i];
                    i++;
                    j++;
                }
                temp[j] = '\0';
                if(temp[0] != '\0') {
                    if((state1 = find_string(temp, states, statenum))
                        == -1) return -2;
                    GET_STATE1 = 0;
                    GET_SYMBOL = 1;
                }
            }
        }
        else if(GET_SYMBOL) {
            if(input[i] != ' ') {
                while((input[i] != ' ') && (input[i] != '\n')) {
                    temp[j] = input[i];
                    i++;
                    j++;
                }
                temp[j] = '\0';
                if(temp[0] != '\0') {
                    if((find_string(temp, symbols, symnum) == -1) &&
                        (strcmp(temp, "NULL") != 0)) return -2;
                    GET_SYMBOL = 0;
                    GET_STACK_SYMBOLS1 = 1;
                }
            }
        }
        else if(GET_STACK_SYMBOLS1) {
            if(input[i] != ' ') {
                if(input[i] == ':') {
                    GET_STACK_SYMBOLS1 = 0;
                    GET_STATE2 = 1;
                }
                else {
                    while((input[i] != ' ') && (input[i] != '\n')) {
                        temp[j] = input[i];
                        i++;
                        j++;
                    }
                    temp[j] = '\0';
                    if(temp[0] != '\0') {
                        if(find_string(temp, stack, stacknum) == -1)
                            return -4;
                    }
                }
            }
        }
        else if(GET_STATE2) {
            if(input[i] != ' ') {
                while((input[i] != ' ') && (input[i] != '\n')) {
                    temp[j] = input[i];
                    i++;
                    j++;
                }
                temp[j] = '\0';
                if(temp[0] != '\0') {
                    if((state2 = find_string(temp, states, statenum))   
                        == -1) return -2;
                    GET_STATE2 = 0;
                    GET_STACK_SYMBOLS2 = 1;
                    ALL_FOUND = 1;
                }
            }
        }
        else if(GET_STACK_SYMBOLS2) {
            if(input[i] != ' ') {
                if((input[i] == '\n') || (input[i] == '\0')) {
                    if(temp[0] != '\0') {
                        if(find_string(temp, stack, stacknum) == -1)
                            return -4;
                    }
                    GET_STACK_SYMBOLS2 = 0;
                }
                else {
                    while((input[i] != ' ') && (input[i] != '\n')) {
                        temp[j] = input[i];
                        i++;
                        j++;
                    }
                    temp[j] = '\0';
                    if(temp[0] != '\0') {
                        if(find_string(temp, stack, stacknum) == -1)
                            return -4;
                    }
                }
            }
        }
    }
if(!ALL_FOUND) return -3;
if(find_string(input, transitions, *trans) != -1) return -5;
strcpy(transitions[(*trans)], input);
(*trans)++;
return 1;
}

/* This function checks to make certain that there is only one start state
   listed, and that it is a legal state. It returns -1 if the state is not
   legal, and 2 if more than one state is found. */    
int verify_start_state(char input[256], char states[100][256], int num) {
    int i, j = 0;
    char temp[256];
    int FOUND_ONE = 0;
    int LOOKING = 0;

    temp[0] = '\0';
    for(i = 0; i < strlen(input); i++) {
        if((input[i] != ' ') && (input[i] != '\n')) {
            FOUND_ONE = 1;
            if(LOOKING) return 2;
            temp[j] = input[i];
            j++;
        }
        else if(FOUND_ONE) LOOKING = 1;
    }
    temp[j] = '\0';
    if(temp[0] == '\0') return 0;
    if(find_string(temp, states, num) == -1) return -1;
    return 1;
}

/* This function checks to make certain that the final states listed are
   all legal. It also stores the final states under final_states[][], and
   the number of final states under *fstates, and uses these to make
   certain that no final state is repeated. It returns -1 if a state is
   illegal, and -2 if a state is repeated. */
int verify_final_states(char input[256], char states[100][256], char
                        final_states[100][256], int num, int *fstates) { 
    int i, j;
    char temp[256];
    int ERROR_VAL = 0;

    for(i = 0; i < strlen(input); i++) {
        j = 0;
        temp[0] = '\0';
        while((input[i] != ' ') && (input[i] != '\n')) {
            temp[j] = input[i];
            j++;
            i++;
        }
        temp[j] = '\0';
        if(temp[0] != '\0') {
            if(find_string(temp, states, num) == -1) ERROR_VAL = -1;
            else if(find_string(temp, final_states, *fstates) != -1)
                ERROR_VAL = -2;
            else {
                strcpy(final_states[(*fstates)], temp);
                (*fstates)++;
            }
        }
    }
    return ERROR_VAL;
}

/* This function takes strings seperated by spaces and stores them under
   stack[][]. It also records the number of stack symbols found, and
   stores them under *stacknum. If a stack symbol is repeated, it returns
   -1. */
int retrieve_stack_symbols(char input[256], char stack[100][256], int
                           *stacknum) {
    int i, j;
    char temp[256];
    int ERROR_VAL = 0;
    
    for(i = 0; i < strlen(input); i++) {
        j = 0;
        temp[0] = '\0';
        while((input[i] != ' ') && (input[i] != '\n')) {
            temp[j] = input[i];
            j++;
            i++;
        }
        temp[j] = '\0';
        if(temp[0] != '\0') {
            if(find_string(temp, stack, *stacknum) != -1) ERROR_VAL = -1;
            else {
                strcpy(stack[(*stacknum)], temp);
                (*stacknum)++;
            }
        }
    }
            
    return ERROR_VAL;
}

/* This function searches through an index of strings for a particular
   string. If it finds the string, it returns the index number at which
   that particular string was found. Otherwise, it returns -1. */
int find_string(char input[256], char index[100][256], int num) {
    int i;
    char temp1[256], temp2[256];
    int FOUND = -1;

    remove_space(input, temp1);
    for(i = 0; i < num; i++) {
        remove_space(index[i], temp2);
        if(strcmp(temp1, temp2) == 0) FOUND = i;
    }

return FOUND;
}

/* This function removes all but one space that are between characters in
   a string. */
void remove_space(char input[256], char output[256]) {
    int i, j = 0;

    for(i = 0; i < strlen(input); i++) {
        if((input[i] == ' ') && (i-1 >= 0)) {
            if(input[i-1] != ' ') {
                output[j] = input[i];
                j++;
            }
        }
        if((input[i] != ' ')) {
            output[j] = input[i];
            j++;
        }
    }
    output[j] = '\0';
}

/* This prints indexes of strings. It's only used for debugging
   purposes. */
void print_stuff(char input[100][256], int num) {
    int i;

    for(i = 0; i < num; i++) {
        printf("%s\n", input[i]);
    }
}