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

char lookahead;
enum TERMINAL {
	ID,
	ADD,
	MUL,
	LBR,
	RBR,
	END,
	ERR
};

enum NON_TERMINAL {
	E,
	T,
	F
};

enum ACTION_TYPE {
	SHIFT,
	REDUCE,
	ERROR,
	ACC
};

#define NUM_TERMINAL  6
#define NUM_NONTERMINAL  3
#define NUM_STATES  12

struct action{
	enum ACTION_TYPE type;
	int id;
}  actionTable[NUM_STATES][NUM_TERMINAL];

int gotoTable[NUM_STATES][NUM_NONTERMINAL];

int stackPtr;
int stack[1024];
void push(int state) {
	stack[stackPtr] = state;
	stackPtr ++;
}

void pop() {
	stackPtr --;
}

int top() {
	return stack[stackPtr - 1];
}

void init() {
	int i, j;

	//stack
	stackPtr = 0;
	push(0);

	//action and goto tables
	for(i = 0; i < NUM_STATES; i ++) {
		for(j = 0; j < NUM_TERMINAL; j ++) {
		actionTable[i][j].type = ERROR;
		}
		for(j = 0; j < NUM_NONTERMINAL; j ++) {
		gotoTable[i][j] = -1;
		}
	}

	//fill in the goto table
	gotoTable[0][E] = 1;
	gotoTable[0][T] = 2;
	gotoTable[0][F] = 3;
	//... your turn
	gotoTable[4][E] = 8;
	gotoTable[4][T] = 2;
	gotoTable[4][F] = 3;

	gotoTable[6][T] = 9;
	gotoTable[6][F] = 3;

	gotoTable[7][F] = 10;

	//fill in the action table
	actionTable[2][ADD].type = REDUCE;
	actionTable[2][ADD].id = 2;
	actionTable[2][MUL].type = SHIFT;
	actionTable[2][MUL].id = 7;
	actionTable[2][RBR].type = REDUCE;
	actionTable[2][RBR].id = 2;
	actionTable[2][END].type = REDUCE;
	actionTable[2][END].id = 2;
	//... your turn
	actionTable[0][ID].type = SHIFT;
	actionTable[0][ID].id = 5;
	actionTable[0][LBR].type = SHIFT;
	actionTable[0][LBR].id = 4;

	actionTable[1][ADD].type = SHIFT;
	actionTable[1][ADD].id = 6;
	actionTable[1][END].type = ACC;

	actionTable[2][ADD].type = REDUCE;
	actionTable[2][ADD].id = 2;
	actionTable[2][MUL].type = SHIFT;
	actionTable[2][MUL].id = 7;
	actionTable[2][RBR].type = REDUCE;
	actionTable[2][RBR].id = 2;
	actionTable[2][END].type = REDUCE;
	actionTable[2][END].id = 2;

	actionTable[3][ADD].type = REDUCE;
	actionTable[3][ADD].id = 4;
	actionTable[3][MUL].type = REDUCE;
	actionTable[3][MUL].id = 4;
	actionTable[3][RBR].type = REDUCE;
	actionTable[3][RBR].id = 4;
	actionTable[3][END].type = REDUCE;
	actionTable[3][END].id = 4;

	actionTable[4][ID].type = SHIFT;
	actionTable[4][ID].id = 5;
	actionTable[4][LBR].type = SHIFT;
	actionTable[4][LBR].id = 4;

	actionTable[5][ADD].type = REDUCE;
	actionTable[5][ADD].id = 6;
	actionTable[5][MUL].type = REDUCE;
	actionTable[5][MUL].id = 6;
	actionTable[5][RBR].type = REDUCE;
	actionTable[5][RBR].id = 6;
	actionTable[5][END].type = REDUCE;
	actionTable[5][END].id = 6;

	actionTable[6][ID].type = SHIFT;
	actionTable[6][ID].id = 5;
	actionTable[6][LBR].type = SHIFT;
	actionTable[6][LBR].id = 4;

	actionTable[7][ID].type = SHIFT;
	actionTable[7][ID].id = 5;
	actionTable[7][LBR].type = SHIFT;
	actionTable[7][LBR].id = 4;

	actionTable[8][ADD].type = SHIFT;
	actionTable[8][ADD].id = 6;
	actionTable[8][RBR].type = SHIFT;
	actionTable[8][RBR].id = 11;

	actionTable[9][ADD].type = REDUCE;
	actionTable[9][ADD].id = 1;
	actionTable[9][MUL].type = SHIFT;
	actionTable[9][MUL].id = 7;
	actionTable[9][RBR].type = REDUCE;
	actionTable[9][RBR].id = 1;
	actionTable[9][END].type = REDUCE;
	actionTable[9][END].id = 1;

	actionTable[10][ADD].type = REDUCE;
	actionTable[10][ADD].id = 3;
	actionTable[10][MUL].type = REDUCE;
	actionTable[10][MUL].id = 3;
	actionTable[10][RBR].type = REDUCE;
	actionTable[10][RBR].id = 3;
	actionTable[10][END].type = REDUCE;
	actionTable[10][END].id = 3;

	actionTable[11][ADD].type = REDUCE;
	actionTable[11][ADD].id = 5;
	actionTable[11][MUL].type = REDUCE;
	actionTable[11][MUL].id = 5;
	actionTable[11][RBR].type = REDUCE;
	actionTable[11][RBR].id = 5;
	actionTable[11][END].type = REDUCE;
	actionTable[11][END].id = 5;
}

enum TERMINAL lexical(FILE *fp) 
{
	lookahead = getc(fp);

	while(lookahead == ' ' || lookahead == '\t' || lookahead == '\n') {
		lookahead = getc(fp);
	}

	if(isdigit(lookahead)) {
		while(isdigit(lookahead)) {
			lookahead = getc(fp);
		}
		ungetc(lookahead, fp);
		return ID;
	} else if (lookahead == '+') {
		return ADD;
	} else if (lookahead == '*') {
		return MUL;
	} else if(lookahead == EOF) {
		return END;
	}else if(lookahead == '(') {
		return LBR;
	} else if(lookahead == ')') {
		return RBR;
	} else {
		return ERR;
	}
}

void parse(enum TERMINAL *input) {
	int currentState = 0;
	int index = 0;

	while(1) {
		printf("currentState: %d\n", currentState);
		switch(actionTable[currentState][input[index]].type) 
		{
			case SHIFT:
				push(actionTable[currentState][input[index]].id);
				currentState = top();
				index++;
				break;
			case REDUCE:
				switch(actionTable[currentState][input[index]].id) 
				{
					case 1:
						pop();
						pop();
						pop();
						push(gotoTable[top()][E]);
						currentState = top();
						//reduce by production 1
						break;
					case 2:
						pop();
						push(gotoTable[top()][E]);
						currentState = top();
						//reduce by production 2
						break;
					case 3:
						pop();
						pop();
						pop();
						push(gotoTable[top()][T]);
						currentState = top();
						//reduce by production 3
						break;
					case 4:
						pop();
						push(gotoTable[top()][T]);
						currentState = top();
						//reduce by production 4
						break;
					case 5:
						pop();
						pop();
						pop();
						push(gotoTable[top()][F]);
						currentState = top();
						//reduce by production 5
						break;
					case 6:
						pop();
						push(gotoTable[top()][F]);
						currentState = top();
						//reduce by production 6
						break;
					default:
						printf("ERROR REDUCE\n");
						exit(-1);
						break;
				}
				break;
			case ERROR:
				printf("ERROR ACTION\n");
				exit(-1);
				break;
			case ACC:
				if(input[index] == END) {
					printf("ACC\n");
					return;
				} else {
					printf("ERROR ACC\n");
					exit(-1);
				}
				break;
		}
	}
}


int main(int argc, char **argv) {
	enum TERMINAL input[1024]; 
	int inputIndex = 0;
	FILE *fp;
	enum TERMINAL temp;
	if(argc < 2) {
		printf("insufficient arguments");
		return 1;
	}
	fp = fopen(argv[1], "r");
	while((temp = lexical(fp)) != END) {
		input[inputIndex++] = temp;
	}

	input[inputIndex] = END;
	fclose(fp);

	init();
	parse(input);

	return 0;
}