# h1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
// for lex
#define MAXLEN 256
// Token types
typedef enum {
    UNKNOWN, END, ENDFILE,
    INT, ID,
    ADDSUB, MULDIV,
    ASSIGN,
    LPAREN, RPAREN,
    INCDEC,
    OR,AND,XOR,
} TokenSet;

TokenSet getToken(void);
TokenSet curToken = UNKNOWN;
char lexeme[MAXLEN];

// 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 1

// Call this macro to print error message and exit the program
// This will also print where you called it in your program

// Error types

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

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

int sbcount = 0;
Symbol table[TBLSIZE];

// 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 *assign_expr(void);
BTNode *or_expr(void);
BTNode *xor_expr(void);
BTNode *or_expr_tail(BTNode *left);
BTNode *and_expr(void);
BTNode *xor_expr_tail(BTNode *left);
BTNode *and_expr_tail(BTNode *left);
BTNode *addsub_expr(void);
BTNode *addsub_expr_tail(BTNode *left);
BTNode *muldiv_expr(void);
BTNode *muldiv_expr_tail(BTNode *left);
BTNode *unary_expr(void);

/*
statement        := END | assign_expr END 
assign_expr      := ID ASSIGN assign_expr | or_expr 
or_expr          := xor_expr or_expr_tail 
or_expr_tail     := OR xor_expr or_expr_tail | NiL 
xor_expr         := and_expr xor_expr_tail 
xor_expr_tail    := XOR and_expr xor_expr_tail | NiL 
and_expr         := addsub_expr and_expr_tail | NiL 
and_expr_tail    := AND addsub_expr and_expr_tail | NiL 
addsub_expr      := muldiv_expr addsub_expr_tail 
addsub_expr_tail := ADDSUB muldiv_expr addsub_expr_tail | NiL 
muldiv_expr      := unary_expr muldiv_expr_tail 
muldiv_expr_tail := MULDIV unary_expr muldiv_expr_tail | NiL 
unary_expr       := ADDSUB unary_expr | factor 
factor           := INT. | ID. | INCDEC ID. | LPAREN assign_expr RPAREN. //finish?
*/


BTNode *term(void);
BTNode *term_tail(BTNode *left);
BTNode *expr(void);
BTNode *expr_tail(BTNode *left);
void printPrefix(BTNode *root);
void statement(void);
// Print error message and exit the program


// for codeGen
//remember register's position
int r=-1,ok = 0, newone, flag=0;
BTNode *check=NULL;
// Evaluate the syntax tree
void search_div(BTNode *root);
void search_id(BTNode *root);
int evaluate(BTNode *root);
int evaluateTree(BTNode *root,int r);
// Print the syntax tree in prefix


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

TokenSet getToken(void)
{
    int i = 0;
    char c = '\0', cc = '\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;
        cc=fgetc(stdin);
        if((c=='+'&&cc=='+')||(c=='-'&&cc=='-')){
            lexeme[1]=c;
            lexeme[2]='\0';
            return INCDEC;
        }
        else {
            ungetc(cc,stdin);
            lexeme[1] = '\0';
            return ADDSUB;
        }
    } else if (c == '*' || c == '/') {
        lexeme[0] = c;
        lexeme[1] = '\0';
        return MULDIV;
    } else if (c=='&'){
        lexeme[0]=c;
        lexeme[1]='\0';
        return AND;
    } else if (c=='^'){
        lexeme[0]=c;
        lexeme[1]='\0';
        return XOR;
    } else if (c=='|'){
        lexeme[0]=c;
        lexeme[1]='\0';
        return OR;
    } 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)) {
        lexeme[0] = c;
        c = fgetc(stdin);
        i = 1;
        while (( isalpha(c) || c=='_' ||isdigit(c) )&& i < MAXLEN) {
            lexeme[i] = c;
            ++i;
            c = fgetc(stdin);
        }
        ungetc(c, stdin);
        lexeme[i] = '\0';
        return ID;
    } 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;
    strcpy(table[1].name, "y");
    table[1].val = 0;
    strcpy(table[2].name, "z");
    table[2].val = 0;
    sbcount = 3;
}

int getid(char *str){
    for(int i=0;i<sbcount;i++){
        if(strcmp(str,table[i].name)==0){
            return i;
        }
    }
    printf("EXIT 1\n");
    exit(0);
}

int getval(char *str) { //取得ID
    int i = 0;
    for (i = 0; i < sbcount; i++){
        if (strcmp(str, table[i].name) == 0) {
            return i*4;
        }//有找到的情況
    }
    if (sbcount >= TBLSIZE) {
        printf("EXIT 1\n");exit(0);
    }
    strcpy(table[sbcount].name, str);//沒找到的情況
    table[sbcount].val = 0;
    sbcount++;
    return sbcount*4-4;
}

int setval(char *str, int val) { //指派值給table
    int i = 0;
    for (i = 0; i < sbcount; i++) {
        if (strcmp(str, table[i].name) == 0) {
            table[i].val = val;
            return val;
        }
    }//有找到的情況
    if (sbcount >= TBLSIZE) {
        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);
    }
}

/*
statement        := END | assign_expr END 
assign_expr      := ID ASSIGN assign_expr | or_expr 
or_expr          := xor_expr or_expr_tail 
or_expr_tail     := OR xor_expr or_expr_tail | NiL 
xor_expr         := and_expr xor_expr_tail 
xor_expr_tail    := XOR and_expr xor_expr_tail | NiL 
and_expr         := addsub_expr and_expr_tail | NiL 
and_expr_tail    := AND addsub_expr and_expr_tail | NiL 
addsub_expr      := muldiv_expr addsub_expr_tail 
addsub_expr_tail := ADDSUB muldiv_expr addsub_expr_tail | NiL 
muldiv_expr      := unary_expr muldiv_expr_tail 
muldiv_expr_tail := MULDIV unary_expr muldiv_expr_tail | NiL 
unary_expr       := ADDSUB unary_expr | factor 
factor           := INT. | ID. | INCDEC ID. | LPAREN assign_expr RPAREN. //finish?
*/
//factor           := INT. | ID. | INCDEC ID. | LPAREN assign_expr RPAREN.
BTNode *factor(void) {
    BTNode *retp, *left;
    if (match(INT)) {
        retp = makeNode(INT, getLexeme());
        advance();
    } 
    else if (match(ID)) {
        left = makeNode(ID, getLexeme());
        advance();
        retp=left;
    } 
    else if (match(INCDEC)){
        retp = makeNode(INCDEC,getLexeme());
        advance();
        if(match(ID)){
            retp->left = makeNode(ID,getLexeme());
            advance();
            retp->right = makeNode(INT,"1");
        }
        else {
            printf("EXIT 1\n");
            exit(0);
        }
/////////////////////////////////////
//      node(maybe '+', maybe '-') //
//     /    \                      //
//    ID     1                     //
/////////////////////////////////////
    } 
    else if (match(LPAREN)) {
        advance();
        retp = assign_expr();
        if (match(RPAREN)) advance();
        else{
            printf("EXIT 1\n");exit(0);
        }
    } 
    else {
        printf("EXIT 1\n");exit(0);
    }
    return retp;
}
//assign_expr      := ID ASSIGN assign_expr | or_expr 
BTNode *assign_expr(void){
    BTNode *retp,*left;
    retp = or_expr();
    if(match(ASSIGN)&&retp->data==ID){
        left = retp;
        retp = makeNode(ASSIGN,getLexeme());
        advance();
        retp->left = left;
        retp->right = assign_expr();
    }
    return retp;
}
//or_expr          := xor_expr or_expr_tail 
BTNode *or_expr(void){
    BTNode *retp=xor_expr();
    return or_expr_tail(retp);
}
//xor_expr         := and_expr xor_expr_tail 
BTNode *xor_expr(void){
    BTNode *retp=and_expr();
    return xor_expr_tail(retp);
}
//or_expr_tail     := OR xor_expr or_expr_tail | NiL 
BTNode *or_expr_tail(BTNode *left){
    BTNode *retp=NULL;
    if(match(OR)){
        retp = makeNode(OR,getLexeme());
        advance();
        retp->left=left;
        retp->right=xor_expr();
        return or_expr_tail(retp);
    }else {
        return left;
    }
}
//xor_expr_tail    := XOR and_expr xor_expr_tail | NiL 
BTNode *xor_expr_tail(BTNode *left){
    BTNode *retp=NULL;
    if(match(XOR)){
        retp = makeNode(XOR,getLexeme());
        advance();
        retp->left=left;
        retp->right=and_expr();
        return xor_expr_tail(retp);
    }
    else {
        return left;
    }
}
//and_expr         := addsub_expr and_expr_tail
BTNode *and_expr(void){
    BTNode *retp=addsub_expr();
    return and_expr_tail(retp);
}
//and_expr_tail    := AND addsub_expr and_expr_tail | NiL 
BTNode *and_expr_tail(BTNode *left){
    BTNode *retp=NULL;
    if(match(AND)){
        retp = makeNode(AND,getLexeme());
        advance();
        retp->left=left;
        retp->right=addsub_expr();
        return and_expr_tail(retp);
    }
    else{
        return left;
    }
}
//addsub_expr      := muldiv_expr addsub_expr_tail 
BTNode *addsub_expr(void){
    BTNode *retp=muldiv_expr();
    return addsub_expr_tail(retp);
}
//addsub_expr_tail := ADDSUB muldiv_expr addsub_expr_tail | NiL 
BTNode *addsub_expr_tail(BTNode *left){
    BTNode *retp=NULL;
    if(match(ADDSUB)){
        retp = makeNode(ADDSUB,getLexeme());
        advance();
        retp->left=left;
        retp->right=muldiv_expr();
        return addsub_expr_tail(retp);
    }
    else{
        return left;
    }
}
//muldiv_expr      := unary_expr muldiv_expr_tail 
BTNode *muldiv_expr(void){
    BTNode *retp=unary_expr();
    return muldiv_expr_tail(retp);
}
//muldiv_expr_tail := MULDIV unary_expr muldiv_expr_tail | NiL 
BTNode *muldiv_expr_tail(BTNode *left){
    BTNode *retp=NULL;
    if(match(MULDIV)){
        retp = makeNode(MULDIV,getLexeme());
        advance();
        retp->left=left;
        retp->right=unary_expr();
        return muldiv_expr_tail(retp);
    }
    else{
        return left;
    }
}
//unary_expr       := ADDSUB unary_expr | factor 
BTNode *unary_expr(void){
    BTNode *retp;
    if(match(ADDSUB)){
        retp = makeNode(ADDSUB,getLexeme());
        advance();
        retp->left = makeNode(INT,"0");
        retp->right = unary_expr();
/////////////////////////////////////
//      node(maybe '+', maybe '-') //
//     /    \                      //
//    0     unary_expr()           //
/////////////////////////////////////
    }
    else{
        retp = factor();
    }
    return retp;
}
//statement        := END | assign_expr END 
void statement(void) {
    BTNode *retp = NULL,*tmp;
    advance();
    if(match(ENDFILE)){
        printf("MOV r0 [0]\nMOV r1 [4]\nMOV r2 [8]\nEXIT 0\n");
        exit(0);
    }
    else if (match(END)) {
        advance();
    } else {
        retp = assign_expr();
        if (match(END)) {
            //printPrefix(retp);
            evaluateTree(retp,0);
        }
        else {
            printf("EXIT 1\n");
            exit(0);
        }
        
    }
}


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

//mark my  idea:
//if(ID):= print(MOV reg[k] ID([k]))
//if(int):= print(MOV reg[k] INT([k]))
//if(strcmp(root->lexeme,'+')==0) := print(ADD reg[ki] reg[kj])
//if(strcmp(root->lexeme,'-')==0) := print(SUB reg[ki] reg[kj])
//if(strcmp(root->lexeme,'*')==0) := print(MUL reg[ki] reg[kj])
//if(strcmp(root->lexeme,'/')==0) := print(DIV reg[ki] reg[kj])

//現在我需要的東西：
//利用evaluateTree(root)去把東西印出來
//簡而言之，可以說是不需要把值算出來
/*
void search_div(BTNode *root){
    if(root!=NULL){
        if(strcmp(root->lexeme,"/")==0) check = root;
        else search_div(root->left),search_div(root->right);
    }
    return;
}

void search_id(BTNode *root){
    if(root!=NULL){
        if(root->data == ID) ok = 1;
        else search_id(root->left),search_id(root->right);
    }
    return;
}

int evaluate(BTNode *root){
    int retval = 0, lv = 0, rv = 0;
    if (root != NULL) {
        switch (root->data) {
            case ID:
                for (int i = 0; i < sbcount; i++){
                    if (strcmp(root->lexeme, table[i].name) == 0) retval = table[i].val;
                }
                break;
            case INT:
                retval = atoi(root->lexeme);
                break;
            case ASSIGN:
                rv = evaluate(root->right);
                retval = setval(root->left->lexeme, rv);
                break;
            case ADDSUB:
            case MULDIV:
            case OR: 
            case XOR: 
            case AND: 
            case INCDEC: 
                lv = evaluate(root->left);
                rv = evaluate(root->right);
                if (strcmp(root->lexeme, "+") == 0) {retval = lv + rv;} 
                else if (strcmp(root->lexeme, "-") == 0) {retval = lv - rv;}
                else if (strcmp(root->lexeme, "*") == 0) {retval = lv * rv;}
                else if (strcmp(root->lexeme, "|") == 0) {retval = lv | rv;}
                else if (strcmp(root->lexeme, "&") == 0) {retval = lv & rv;}
                else if (strcmp(root->lexeme, "^") == 0) {retval = lv ^ rv;}
                else if (strcmp(root->lexeme, "++") == 0) {retval = lv + 1;}
                else if (strcmp(root->lexeme, "--") == 0) {retval = lv - 1;}
                else if (strcmp(root->lexeme, "/") == 0) {
                    retval = lv / rv;
                }
                break;
            default:
                retval = 0;
        }
    }
    return retval;
}
*/

int evaluateTree(BTNode *root, int r) {
    int retval = 0, ne, tmp, rr, ll;
    if (root != NULL) {
        switch (root->data) {
            case ID:
                //找table裡面有沒有存過root->lexeme,如果有就直接用,沒有就創一個新的
                //有用過->1,沒出現過->0    //之前印過的就不印了！
                newone=getid(root->lexeme);
                ne = getval(root->lexeme);
                flag=1;
                if(r>=8){
                    strcpy(table[sbcount].name, "\0");//沒找到的情況
                    table[sbcount].val = 0;
                    sbcount++;root->ever = sbcount*4-4;
                    printf("MOV [%d] r%d\n",root->ever,r%8);
                }
                else root->ever = 0;
                printf("MOV r%d [%d]\n",r%8,ne);
                break;
            case INT:
                retval = atoi(root->lexeme);
                if(r>=8){
                    strcpy(table[sbcount].name, "\0");//沒找到的情況
                    table[sbcount].val = 0;
                    sbcount++;root->ever = sbcount*4-4;
                    printf("MOV [%d] r%d\n",root->ever,r%8);
                }
                else root->ever = 0;
                printf("MOV r%d %d\n",r%8,retval);
                //把root->lexeme的char值強制轉換成int
                break;
            case ASSIGN:
                rr = evaluateTree(root->right,r);
                //利用遞迴,搜尋root右邊的值
                retval = setval(root->left->lexeme, rr);
                newone=getid(root->left->lexeme);
                tmp = getval(root->left->lexeme);
                //把左邊的值,交給右邊
                root->ever = 0;
                printf("MOV [%d] r%d\n",tmp,r%8);
                break;
            case ADDSUB:
            case MULDIV:
            case OR:
            case XOR:
            case AND:
            case INCDEC:
                ll = evaluateTree(root->left, r);
                //先遞迴找左邊
                if(strcmp(root->lexeme,"/")==0) flag=0;
                rr = evaluateTree(root->right, r+1);
                //再遞迴找右邊
                if (strcmp(root->lexeme, "+") == 0)  {
                    printf("ADD r%d r%d\n",r%8,(r+1)%8);retval = ll + rr;
                    if(root->right->ever != 0) printf("MOV r%d [%d]\n",(r+1)%8,root->right->ever),root->ever = root->left->ever;}
                else if (strcmp(root->lexeme,"++") == 0){
                    printf("ADD r%d r%d\n",r%8,(r+1)%8);
                    printf("MOV [%d] r%d\n",getid(root->left->lexeme)*4,r%8);
                    retval = ll + 1;
                    if(root->right->ever != 0) printf("MOV r%d [%d]\n",(r+1)%8,root->right->ever),root->ever = root->left->ever;}
                else if (strcmp(root->lexeme, "-") == 0) {
                    printf("SUB r%d r%d\n",r%8,(r+1)%8);retval = ll - rr;
                    if(root->right->ever != 0) printf("MOV r%d [%d]\n",(r+1)%8,root->right->ever),root->ever = root->left->ever;}
                else if (strcmp(root->lexeme,"--") == 0){
                    printf("SUB r%d r%d\n",r%8,(r+1)%8);
                    printf("MOV [%d] r%d\n",getid(root->left->lexeme)*4,r%8);
                    retval = ll -1;
                    if(root->right->ever != 0) printf("MOV r%d [%d]\n",(r+1)%8,root->right->ever),root->ever = root->left->ever;}
                else if (strcmp(root->lexeme, "*") == 0) {
                    printf("MUL r%d r%d\n",r%8,(r+1)%8);retval = ll * rr;
                    if(root->right->ever != 0) printf("MOV r%d [%d]\n",(r+1)%8,root->right->ever),root->ever = root->left->ever;}
                else if (strcmp(root->lexeme, "/") == 0) {
                    if(rr==0&&!flag){printf("EXIT 1\n");exit(0);}
                    printf("DIV r%d r%d\n",r%8,(r+1)%8);
                    if(root->right->ever != 0) printf("MOV r%d [%d]\n",(r+1)%8,root->right->ever),root->ever = root->left->ever;}
                else if (strcmp(root->lexeme, "|") == 0 ){
                    printf("OR r%d r%d\n",r%8,(r+1)%8);retval = ll | rr;
                    if(root->right->ever != 0) printf("MOV r%d [%d]\n",(r+1)%8,root->right->ever),root->ever = root->left->ever;}
                else if (strcmp(root->lexeme, "^") == 0 ){
                    printf("XOR r%d r%d\n",r%8,(r+1)%8);retval = ll ^ rr;
                    if(root->right->ever != 0) printf("MOV r%d [%d]\n",(r+1)%8,root->right->ever),root->ever = root->left->ever;}
                else if (strcmp(root->lexeme, "&") == 0){
                    printf("AND r%d r%d\n",r%8,(r+1)%8);retval = ll & rr;
                    if(root->right->ever != 0) printf("MOV r%d [%d]\n",(r+1)%8,root->right->ever),root->ever = root->left->ever;}
                break;
            default:
                retval = 0;
                break;
        }
    }
    return retval;
}

void printPrefix(BTNode *root) {
    if (root != NULL) {
        printf("%s ", root->lexeme);
        printPrefix(root->left);
        printPrefix(root->right);
    }
}
/*============================================================================================
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() {
    initTable();
    while (1) {
        statement();
    }
    return 0;
}