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


// for lex
#define MAXLEN 256
int eflag = 0;
// Token types
typedef enum {
    UNKNOWN, END, ENDFILE,
    INT, ID,
    ADDSUB, MULDIV,
    ASSIGN,
    LPAREN, RPAREN,
    INCDEC,AND,OR,XOR
} TokenSet;

TokenSet getToken(void); 
TokenSet curToken = UNKNOWN;
char lexeme[MAXLEN];
int i = -1;

// Test if a token matches the current token
int match(TokenSet token);
// Get the next token
void advance(void);
// Get the lexeme of the current token
char *getLexeme(void);


// for parser
#define TBLSIZE 64
// Set PRINTERR to 1 to print error message while calling error()
// Make sure you set PRINTERR to 0 before you submit your code
#define PRINTERR 0
int used[TBLSIZE]; //記錄這個register是否被用過
// Call this macro to print error message and exit the program
// This will also print where you called it in your program
#define error(errorNum) { \
    if (PRINTERR) \
        fprintf(stderr, "error() called at %s:%d: ", __FILE__, __LINE__); \
    err(errorNum); \
}

// Error types
typedef enum {
    UNDEFINED, MISPAREN, NOTNUMID, NOTFOUND, RUNOUT, NOTLVAL, DIVZERO, SYNTAXERR
} ErrorType;

// Structure of the symbol table
typedef struct {
    int val;
    char name[MAXLEN];
    int idx;
} Symbol;

// Structure of a tree node
typedef struct _Node {
    TokenSet data;
    int val;
    char lexeme[MAXLEN];
    struct _Node *left;
    struct _Node *right;
} BTNode;

int sbcount = 0;
Symbol table[TBLSIZE];
BTNode* reg[TBLSIZE]; //紀錄NODE屬於哪個register

// Initialize the symbol table with builtin variables
void initTable(void);
// Get the value of a variable
int getval(char *str);
// Set the value of a variable
int setval(char *str, int val);
// Make a new node according to token type and lexeme
BTNode *makeNode(TokenSet tok, const char *lexe);
// Free the syntax tree
void freeTree(BTNode *root);
BTNode *factor(void);
BTNode *unary_expr(void);
BTNode *muldiv_expr(void);
BTNode *muldiv_expr_tail(BTNode* left);
BTNode *addsub_expr(void);
BTNode *addsub_expr_tail(BTNode* left);
BTNode *and_expr(void);
BTNode *and_expr_tail(BTNode* left);
BTNode *or_expr(void);
BTNode *or_expr_tail(BTNode* left);
BTNode *xor_expr(void);
BTNode *xor_expr_tail(BTNode* left);
BTNode *assign_expr(void);
void statement(void);
// Print error message and exit the program
void err(ErrorType errorNum);


// for codeGen
// Evaluate the syntax tree
int evaluateTree(BTNode *root);
int check(BTNode* root);
// Print the syntax tree in prefix
void printPrefix(BTNode *root);


/*============================================================================================
lex implementation
============================================================================================*/

TokenSet getToken(void)
{
    int i = 0;
    char c = '\0';

    while ((c = fgetc(stdin)) == ' ' || c == '\t');

    if (isdigit(c)) {
        lexeme[0] = c;
        c = fgetc(stdin);
        i = 1;
        while (isdigit(c) && i < MAXLEN) {
            lexeme[i] = c;
            ++i;
            c = fgetc(stdin);
        }
        ungetc(c, stdin);
        lexeme[i] = '\0';
        return INT;
    } else if (c == '+' || c == '-') {
        lexeme[0] = c;
        lexeme[1] = '\0';
        c = fgetc(stdin);
        if(c == lexeme[0]){
            lexeme[1] = c;
            lexeme[2] = '\0';
            return INCDEC;
        } else{
         ungetc(c,stdin);
         return ADDSUB;
        }
    } else if (c == '*' || c == '/') {
        lexeme[0] = c;
        lexeme[1] = '\0';
        return MULDIV;
    } else if (c == '\n') {
        lexeme[0] = '\0';
        return END;
    } else if (c == '=') {
        strcpy(lexeme, "=");
        return ASSIGN;
    } else if (c == '(') {
        strcpy(lexeme, "(");
        return LPAREN;
    } else if (c == ')') {
        strcpy(lexeme, ")");
        return RPAREN;
    } else if (isalpha(c) || c == '_') {
        lexeme[0] = c;
        i = 1;
        c = fgetc(stdin);
        while(isdigit(c) || isalpha(c) || c == '_' ){
            lexeme[i] = c;
            ++i;
            c = fgetc(stdin);
        }
        if(c != ' ')
        ungetc(c,stdin);
        lexeme[i] = '\0';
        return ID;
    } else if(c == '&'){
        lexeme[0] = c;
        lexeme[1] = '\0';
        return AND;
    } else if(c == '|'){
        lexeme[0] = c;
        lexeme[1] = '\0';
        return OR;
    } else if(c == '^'){
        lexeme[0] = c;
        lexeme[1] = '\0';
        return XOR;
    }
     else if (c == EOF) {
        return ENDFILE;
    } else {
        return UNKNOWN;
    }
}

void advance(void) {
    curToken = getToken();
}

int match(TokenSet token) {
    if (curToken == UNKNOWN)
        advance();
    return token == curToken;
}

char *getLexeme(void) {
    return lexeme;
}


/*============================================================================================
parser implementation
============================================================================================*/

void initTable(void) {
    strcpy(table[0].name, "x");
    table[0].val = 0;
    table[0].idx = 0;
    strcpy(table[1].name, "y");
    table[1].val = 0;
    table[1].idx = 1;
    strcpy(table[2].name, "z");
    table[2].val = 0;
    table[2].idx = 2;
    sbcount = 3;
}

int getval(char *str) {
    int a = 0;

    for (a = 0; a < sbcount; a++)
        if (strcmp(str, table[a].name) == 0){
            ++i;
            printf("MOV r%d [%d]\n",i,a*4);
            return table[a].val;
        }
    /*if(a>=sbcount){
        strcpy(table[sbcount].name,str);
        table[sbcount].val = 0;
        table[sbcount].idx = sbcount;
        sbcount++;
    }*/
    if (sbcount >= TBLSIZE){
        error(RUNOUT);
        eflag = 1;
        printf("EXIT 1\n");
        exit(0);
    }

    if(a>=sbcount){
        error(UNDEFINED)
        eflag = 1;
        printf("EXIT 1\n");
        exit(0);
    }
}

int setval(char *str, int val) {

    for (int a = 0; a < sbcount; a++) {
        if (strcmp(str, table[a].name) == 0) {
            table[a].val = val;
            return val;
        }
    }

    if (sbcount >= TBLSIZE){
        error(RUNOUT);
        eflag = 1;
        printf("EXIT 1\n");
        exit(0);
    }

    strcpy(table[sbcount].name, str);
    table[sbcount].val = val;
    sbcount++;
    return val;
}

BTNode *makeNode(TokenSet tok, const char *lexe) {
    BTNode *node = (BTNode*)malloc(sizeof(BTNode));
    strcpy(node->lexeme, lexe);
    node->data = tok;
    node->val = 0;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void freeTree(BTNode *root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

// factor := INT|
//		   	 ID|
//		   	 LPAREN expr RPAREN |
//		   	 INCDEC ID
//           
BTNode *factor(void) {
    BTNode *retp = NULL, *left = NULL;

    if (match(INT)) {
        retp = makeNode(INT, getLexeme());
        advance();
    } else if (match(ID)) {
        retp = makeNode(ID, getLexeme());
        advance();
    }
      else if(match(INCDEC)){  //記法:root = ++ root->right = ID root->left = 0
        retp = makeNode(INCDEC,getLexeme());
        advance();
        retp->left = makeNode(INT,"0");
        if(match(ID)){
            retp->right = makeNode(ID,getLexeme());
        }
        else{
            error(SYNTAXERR);
            eflag = 1;
            printf("EXIT 1\n");
            exit(0);
        }
        advance();
        if(retp->right->data != ID){
            error(SYNTAXERR);
            eflag = 1;
            printf("EXIT 1\n");
            exit(0);
        }
    }
    else if (match(LPAREN)) {
        advance();
        retp = assign_expr();
        if (match(RPAREN))
            advance();
        else{
            error(MISPAREN);
            eflag = 1;
            printf("EXIT 1\n");
            exit(0);
        }
    } else {
        error(NOTNUMID);
        eflag = 1;
        printf("EXIT 1\n");
        exit(0);
    }
    return retp;
}


BTNode *unary_expr(void){
    BTNode* node = NULL;
    if(match(ADDSUB)){
       node = makeNode(ADDSUB,getLexeme());
       advance();
       node->left = makeNode(INT,"0");
       node->right = unary_expr();
    }
    else if(match(AND) || match(OR) || match(XOR)){
        error(SYNTAXERR);
        eflag = 1;
        printf("EXIT 1\n");
    }
    else{
       node = factor();
    }
    return node;
}

BTNode* muldiv_expr(void){
    BTNode* Node = unary_expr();
    return muldiv_expr_tail(Node);
}

BTNode *muldiv_expr_tail(BTNode* left){
    BTNode *node = NULL;
    if(match(MULDIV)){
        node = makeNode(MULDIV,getLexeme());
        advance();
        node->left = left;
        node->right = unary_expr();
        if(node->right == NULL){
            error(SYNTAXERR);
            eflag = 1;
            printf("EXIT 1\n");
            exit(0);
        }
        return muldiv_expr_tail(node);
    }
    else{
        return left;
    }
    
}

BTNode* addsub_expr(void){
    BTNode* node = muldiv_expr();
    return addsub_expr_tail(node);
}

BTNode* addsub_expr_tail(BTNode* left){
    BTNode* node = NULL;
    if(match(ADDSUB)){
        node = makeNode(ADDSUB,getLexeme());
        advance();
        node->left = left;
        node->right = muldiv_expr();
        if(node->right == NULL){
            error(SYNTAXERR);
            eflag = 1;
            printf("EXIT 1\n");
            exit(0);
        }
        return addsub_expr_tail(node);
    }
    else{
        return left;
    }
}

BTNode* and_expr(void){
    BTNode* node = addsub_expr();
    return and_expr_tail(node);
}

BTNode* and_expr_tail(BTNode* left){
    BTNode* node = NULL;
    if(match(AND)){
        node = makeNode(AND,getLexeme());
        advance();
        node->left = left;
        node->right = addsub_expr();
        if(node->right == NULL){
            error(SYNTAXERR);
            eflag = 1;
            printf("EXIT 1\n");
            exit(0);
        }
        return and_expr_tail(node);
    }
    else{
        return left;
    }
}

BTNode* or_expr(void){
    BTNode* node = and_expr();
    return or_expr_tail(node);
}

BTNode* or_expr_tail(BTNode *left){
    if(match(OR)){
        BTNode *node = makeNode(OR,getLexeme());
        advance();
        node->left = left;
        node->right = and_expr();
        if(node->right == NULL){
            error(SYNTAXERR);
            eflag = 1;
            printf("EXIT 1\n");
            exit(0);
        }
        return or_expr_tail(node);
    }
    else{
        return left;
    }
}

BTNode* xor_expr(void){
    BTNode* node = or_expr();
    return xor_expr_tail(node);
}

BTNode* xor_expr_tail(BTNode* left){
    if(match(XOR)){
        BTNode* node = makeNode(XOR,getLexeme());
        advance();
        node->left = left;
        node->right = or_expr();
        if(node->right == NULL){
            error(SYNTAXERR);
            eflag = 1;
            printf("EXIT 1\n");
            exit(0);
        }
        return xor_expr_tail(node);
    }
    else{
        return left;
    }
}

BTNode* assign_expr(void){
    if(match(ID)){
        BTNode* left = makeNode(ID,getLexeme());
        advance();
        if(match(ASSIGN)){
            BTNode* node = makeNode(ASSIGN,getLexeme());
            advance();
            node->left = left;
            node->right = xor_expr();
            return node;
        }
        else{
            BTNode* node = xor_expr();
            /*node->left = left;*/
            return node;
        }
    }
    else{
        return xor_expr();
    }
}
void statement(void) {
    BTNode *retp = NULL;

    if (match(ENDFILE)) {
        if(eflag!=1){
        printf("MOV r0 [0]\n");
        printf("MOV r1 [4]\n");
        printf("MOV r2 [8]\n");
        }
        printf("EXIT %d\n",eflag);
        exit(0);
    } else if (match(END)) {
        //printf(">> ");
        advance();
    } else {
        retp = assign_expr();
        if (match(END)) {
            printf("%d\n", evaluateTree(retp));
            //evaluateTree(retp);
            //printf("Prefix traversal: ");
            //printPrefix(retp);
            //printf("\n");
            freeTree(retp);
            //printf(">> ");
            advance();
        } else {
            error(SYNTAXERR);
            eflag = 1;
            printf("EXIT 1\n");
            exit(0);
        }
    }
}

void err(ErrorType errorNum) {
    if (PRINTERR) {
        fprintf(stderr, "error: ");
        switch (errorNum) {
            case MISPAREN:
                fprintf(stderr, "mismatched parenthesis\n");
                break;
            case NOTNUMID:
                fprintf(stderr, "number or identifier expected\n");
                break;
            case NOTFOUND:
                fprintf(stderr, "variable not defined\n");
                break;
            case RUNOUT:
                fprintf(stderr, "out of memory\n");
                break;
            case NOTLVAL:
                fprintf(stderr, "lvalue required as an operand\n");
                break;
            case DIVZERO:
                fprintf(stderr, "divide by constant zero\n");
                break;
            case SYNTAXERR:
                fprintf(stderr, "syntax error\n");
                break;
            default:
                fprintf(stderr, "undefined error\n");
                break;
        }
    }
    //exit(0);
}


/*============================================================================================
codeGen implementation
============================================================================================*/

int evaluateTree(BTNode *root) {
    int retval = 0, lv = 0, rv = 0;
    int l,r;
    if (root != NULL) {
        switch (root->data) {
            case ID:
                retval = getval(root->lexeme);
                reg[i] = root;
                break;
            case INT:
                retval = atoi(root->lexeme);
                i++;
                printf("MOV r%d %d\n",i,retval);
                reg[i] = root;   
                break;
            case ASSIGN:
                rv = evaluateTree(root->right);
                retval = setval(root->left->lexeme, rv);
                for(int a=0;a<=sbcount;a++){
                if(strcmp(root->left->lexeme,table[a].name)==0){
                   for(int j=0;j<=i;j++){
                       if(reg[j] == root->right){
                           printf("MOV [%d] r%d\n",4*a,j);
                           break;
                       }
                   }
                    
                }
            }
            while(i>-1){
                reg[i] = NULL;
                used[i] = 0;
                i--;
            }
                break;
            case ADDSUB:
            case MULDIV:
                lv = evaluateTree(root->left);
                rv = evaluateTree(root->right);
                
                for(l=0;l<=i;l++){
                    if(strcmp(reg[l]->lexeme,root->left->lexeme)==0 && used[l]==0){break;}
                }
                for(r=0;r<=i;r++){
                    if(strcmp(reg[r]->lexeme,root->right->lexeme)==0 && used[r]==0 && l!=r){break;}
                }
                if (strcmp(root->lexeme, "+") == 0) {
                    printf("ADD r%d r%d\n",l,r);
                    retval = lv + rv;
                    reg[l] = root;
                    used[r] = 1;
                } else if (strcmp(root->lexeme, "-") == 0) {
                    printf("SUB r%d r%d\n",l,r);
                    retval = lv - rv;
                    reg[l] = root;
                    used[r] = 1;
                } else if (strcmp(root->lexeme, "*") == 0) {
                    printf("MUL r%d r%d\n",l,r);
                    retval = lv * rv;
                    reg[l] = root;
                    used[r] = 1;
                } else if (strcmp(root->lexeme, "/") == 0) {
                    if (rv == 0){
                        if(!check(root->right)){
                        error(DIVZERO);
                        printf("EXIT 1\n");
                        exit(0);
                        }
                        else{
                            retval = 0;
                            reg[l] = root;
                            used[r] = 1;
                        }
                    }
                    else {
                    printf("DIV r%d r%d\n",l,r);
                    retval = lv / rv;
                    reg[l] = root;
                    used[r] = 1;
                    }
                }
                break;
            case AND:
            case OR:
            case XOR:
                lv = evaluateTree(root->left);
                rv = evaluateTree(root->right);
                
                for(l=0;l<=i;l++){
                    if(strcmp(reg[l]->lexeme,root->left->lexeme)==0){break;}
                }
                for(r=0;r<=i;r++){
                    if(strcmp(reg[r]->lexeme,root->right->lexeme)==0 && l!=r){break;}
                }
                if(strcmp(root->lexeme,"&")==0){
                    printf("AND r%d r%d\n",l,r);
                    reg[l] = root;
                    used[r] = 1;
                    return(lv & rv);
                }
                else if(strcmp(root->lexeme,"|")==0){
                    printf("OR r%d r%d\n",l,r);
                    reg[l] = root;
                    used[r] = 1;
                    return(lv | rv);
                }
                else if(strcmp(root->lexeme,"^")==0){
                    printf("XOR r%d r%d\n",l,r);
                    reg[l] = root;
                    used[r] = 1;
                    return(lv ^ rv);
                }
                break;
            case INCDEC:
            if(strcmp(root->lexeme,"++")==0){
                retval = evaluateTree(root->right)+1;
                for(int a=0;a<sbcount;a++){
                    if(strcmp(root->right->lexeme,table[a].name)==0){
                        printf("MOV r%d 1\n",++i);
                        printf("ADD r%d r%d\n",i--,i--);
                        reg[++i] = root;
                        used[++i] = 1;
                        table[a].val++;
                    }
                }
            }
            else if(strcmp(root->lexeme,"--")==0){
                retval = evaluateTree(root->right)-1;
                for(int a=0;a<sbcount;a++){
                    if(strcmp(root->right->lexeme,table[a].name)==0){
                        printf("MOV r%d 1\n",++i);
                        printf("SUB r%d r%d\n",i--,i--);
                        reg[++i] = root;
                        used[++i] = 1;
                        table[a].val--;
                    }
                }
            }
                break;
            default:
                retval = 0;
        }
    }
    return retval;
}

void printPrefix(BTNode *root) {
    if (root != NULL) {
        printf("%s ", root->lexeme);
        printPrefix(root->left);
        printPrefix(root->right);
    }
}

int check(BTNode* root){
    int ans = 0;
    if(root->data = ID){
        ans = 1;
    }

    else{
        ans = check(root->left);
        ans = check(root->right);
    }
    return 0;

}


/*============================================================================================
main
============================================================================================*/

// This package is a calculator
// It works like a Python interpretor
// Example:
// >> y = 2
// >> z = 2
// >> x = 3 * y + 4 / (2 * z)
// It will print the answer of every line
// You should turn it into an expression compiler
// And print the assembly code according to the input

// This is the grammar used in this package
// You can modify it according to the spec and the slide
// statement  :=  ENDFILE | END | expr END
// expr    	  :=  term expr_tail
// expr_tail  :=  ADDSUB term expr_tail | NiL
// term 	  :=  factor term_tail
// term_tail  :=  MULDIV factor term_tail| NiL
// factor	  :=  INT | ADDSUB INT |
//		   	      ID  | ADDSUB ID  |
//		   	      ID ASSIGN expr |
//		   	      LPAREN expr RPAREN |
//		   	      ADDSUB LPAREN expr RPAREN

int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    initTable();
    //printf(">> ");
    while (1) {
        statement();
    }
    return 0;
}