# mini project 1
## len.h
* 新增 tokenSet

typedef enum {
    UNKNOWN, END, ENDFILE,
    INT, ID,
    ADDSUB, MULDIV,
    ASSIGN, ADDSUB_ASSIGN, INCDEC,
    AND, OR, XOR,
    LPAREN, RPAREN
} TokenSet;

## len.c
* getToken 負責拿到當前的 Token
* 協助之後判斷 expr 語法 找出 if match(Token)

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 == '+' || c == '-'){
            lexeme[1] = c;
            lexeme[2] = '\0';
            return INCDEC;
        }
        else if(c == '='){
            lexeme[1] = c;
            lexeme[2] = '\0';
            return ADDSUB_ASSIGN;
        }
        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(c == '&'){
        strcpy(lexeme, "&");
        return AND;
    } else if(c == '|'){
        strcpy(lexeme, "|");
        return OR;
    } else if(c == '^'){
        strcpy(lexeme, "^");
        return XOR;
    } else if (isalpha(c) || c == '_') {
        lexeme[0] = c;
        int i = 1;
        c = fgetc(stdin);
        while(isalnum(c) || c == '_' && i < MAXLEN-1){
            lexeme[i++] = c;
            c = fgetc(stdin);
        }
        ungetc(c, stdin);
        lexeme[i] = '\0';
        return ID;
    } else if (c == EOF) {
        return ENDFILE;
    } else {
        return UNKNOWN;
    }
}

## paser.h
* 根據語法創建語法樹的函式

// statement           := ENDFILE | END | assign_expr END
// assign_expr         := ID ASSIGN assign_expr | ID ADDSUB_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
// 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

extern void statement();
extern BTNode *assign_expr();
extern BTNode *or_expr();
extern BTNode *or_expr_tail(BTNode *left);
extern BTNode *xor_expr();
extern BTNode *xor_expr_tail(BTNode *left);
extern BTNode *and_expr();
extern BTNode *and_expr_tail(BTNode *left);
extern BTNode *addsub_expr();
extern BTNode *addsub_expr_tail(BTNode *left);
extern BTNode *muldiv_expr();
extern BTNode *muldiv_expr_tail(BTNode *left);
extern BTNode *unary_expr();
extern BTNode *factor();

## paser.c
* getval 負責找到該 varible 的值 沒找到 error(NOTFOUND)
* setval 負責設定新的 varible 的值或者是更新 varible 的值 (不動)
:::warning
assign_expr 要先取or_expr 再判斷 ID
若先找 ID advance() 之後會getToken到下一個 若不是 = 或 +=,-= 就會出錯 (get之後就沒辦法往回)
:::

int getval(char *str) {
    int i = 0;
    int found = 0;

    for (i = 0; i < sbcount; i++)
        if (strcmp(str, table[i].name) == 0){
            found = 1;
            printf("MOV r%d [%d]\n", r_cnt++, i*4);
            return table[i].val;
        }

    if (sbcount >= TBLSIZE){
        error(RUNOUT);
    }

    if(!found){
        error(NOTFOUND);
    }

    return 0;
}

int setval(char *str, int val) {
    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){
        error(RUNOUT);
    }

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

void statement(){
    if(match(ENDFILE)){
        printf("MOV r0 [0]\n");
        printf("MOV r1 [4]\n");
        printf("MOV r2 [8]\n");
        printf("EXIT 0\n");
        exit(0);
    }
    else if(match(END)){
        advance();
    }
    else{
        BTNode *retp = assign_expr();
        if(match(END)){
            evaluateTree(retp);
            freeTree(retp);
            advance();
        }
        else{
            error(SYNTAXERR);
        }
    }
}

// assign_expr := ID ASSIGN assign_expr | ID ADDSUB_ASSIGN assign_expr | or_expr
BTNode *assign_expr(){
    BTNode *retp = NULL, *left = or_expr();
    if(left->data == ID){
        if(match(ASSIGN)){
            retp = makeNode(ASSIGN, getLexeme());
            advance();
            retp->left = left;
            retp->right = assign_expr();
            return retp;
        }
        else if(match(ADDSUB_ASSIGN)){
            retp = makeNode(ADDSUB_ASSIGN, getLexeme());
            advance();
            retp->left = left;
            retp->right = assign_expr();
            return retp;
        }
    }
    return left;
}

// or_expr := xor_expr or_expr_tail
BTNode *or_expr(){
    BTNode *node = xor_expr();
    return or_expr_tail(node);
}

// or_expr_tail := OR xor_expr or_expr_tail | NiL
BTNode *or_expr_tail(BTNode *left){
    BTNode *node = NULL;
    if(match(OR)){
        node = makeNode(OR, getLexeme());
        advance();
        node->left = left;
        node->right = xor_expr();
        return or_expr_tail(node);
    }
    else{
        return left;
    }
}

// xor_expr := and_expr xor_expr_tail
BTNode *xor_expr(){
    BTNode *node = and_expr();
    return xor_expr_tail(node);
}

// xor_expr_tail := XOR and_expr xor_expr_tail | NiL
BTNode *xor_expr_tail(BTNode *left){
    BTNode *node = NULL;
    if(match(XOR)){
        node = makeNode(XOR, getLexeme());
        advance();
        node->left = left;
        node->right = and_expr();
        return xor_expr_tail(node);
    }
    else{
        return left;
    }
}

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

// and_expr_tail := AND addsub_expr and_expr_tail | NiL
BTNode *and_expr_tail(BTNode *left){
    BTNode *node = NULL;
    if(match(AND)){
        node = makeNode(AND, getLexeme());
        advance();
        node->left = left;
        node->right = addsub_expr();
        return and_expr_tail(node);
    }
    else{
        return left;
    }
}

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

// addsub_expr_tail := ADDSUB muldiv_expr addsub_expr_tail | NiL
BTNode *addsub_expr_tail(BTNode *left){
    BTNode *node = NULL;
    if(match(ADDSUB)){
        node = makeNode(ADDSUB, getLexeme());
        advance();
        node->left = left;
        node->right = muldiv_expr();
        return addsub_expr_tail(node);
    }
    else{
        return left;
    }
} 

// muldiv_expr := unary_expr muldiv_expr_tail
BTNode *muldiv_expr(){
    BTNode *node = unary_expr();
    return muldiv_expr_tail(node);
}

// muldiv_expr_tail := MULDIV unary_expr muldiv_expr_tail | NiL
BTNode *muldiv_expr_tail(BTNode *left){
    BTNode *node = NULL;
    if(match(MULDIV)){
        node = makeNode(MULDIV, getLexeme());
        advance();
        node->left = left;
        node->right = unary_expr();
        return muldiv_expr_tail(node);
    }
    else{
        return left;
    }
}

// unary_expr := ADDSUB unary_expr | factor
BTNode *unary_expr(){
    BTNode *node = NULL;
    if(match(ADDSUB)){
        node = makeNode(ADDSUB, getLexeme());
        advance();
        node->left = makeNode(INT, "0");
        node->right = unary_expr();
        return node;
    }
    else{
        node = factor();
        return node;
    }
}

// factor := INT | ID | INCDEC ID | LPAREN assign_expr RPAREN
BTNode *factor(){
    BTNode *node = NULL;
    if(match(INT)){
        node = makeNode(INT, getLexeme());
        advance();
    }
    else if(match(ID)){
        node = makeNode(ID, getLexeme());
        advance();
    }
    else if(match(INCDEC)){
        node = makeNode(INCDEC, getLexeme());
        advance();
        if(match(ID)){
            node->left = makeNode(ID, getLexeme());
            advance();
        }
        else{
            error(NOTNUMID);
        }
    }
    else if(match(LPAREN)){
        advance();
        node = assign_expr();
        if(match(RPAREN)){
            advance();
        }
        else{
            error(MISPAREN);
        }
    }
    else{
        error(NOTNUMID);
    }
    return node;
}

## codeGen.h
* 新增 r_cnt, pos_cnt, find_pos_cnt, findVar
* r_cnt 計算當下的 r 是第幾個
* pos_cnt 計算 varible 的位置 (第幾個 * 4)
* find_pos_cnt 找到該 varible 是第幾個 (x:0 y:1 z:2...)
* findVar 找 DIV 右邊是否至少有一個 varible

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

int find_pos_cnt(char *name);
int findVar(BTNode *root);

int r_cnt;
int pos_cnt;

## assembly code 概念
:::info
遇到 INT, iD 時 register 會 ++
做 operation 的時候 丟棄右子樹的 register 所以 register ---
:::
* basic
* advance
## codeGen.c
* 實作 assembly code
* 遇到 ID 時的 r_cnt++ 我寫在 getval裡面

int find_pos_cnt(char *name){
    int i;
    pos_cnt = 0;
    for(i=0; i<sbcount; i++){
        if(strcmp(name, table[i].name) == 0) return i;
    }
    error(NOTFOUND);
}

int findVar(BTNode *root){
    if(root == NULL) return 0;
    else if(root->data == ID) return 1;
    else if(findVar(root->left)) return 1;
    else if(findVar(root->right)) return 1;
    else return 0;
}

int evaluateTree(BTNode *root) {
    int retval = 0, lv = 0, rv = 0;

    if (root != NULL) {
        switch (root->data) {
            case ID:
                retval = getval(root->lexeme);
                break;
            case INT:
                retval = atoi(root->lexeme);
                printf("MOV r%d %d\n", r_cnt++, retval);
                break;
            case ASSIGN: // x = 3
                rv = evaluateTree(root->right);
                retval = setval(root->left->lexeme, rv);
                
                if(root->right->data == ASSIGN || root->right->data == ADDSUB_ASSIGN || root->right->data == INCDEC){
                    pos_cnt = find_pos_cnt(root->right->left->lexeme);
                    printf("MOV r%d [%d]\n", r_cnt++, pos_cnt*4);
                }

                pos_cnt = find_pos_cnt(root->left->lexeme);
                printf("MOV [%d] r%d\n", pos_cnt*4, r_cnt-1);
                r_cnt--;
                break;
            case ADDSUB_ASSIGN: // x += 3
                lv = getval(root->left->lexeme);
                rv = evaluateTree(root->right);

                if(root->right->data == ASSIGN || root->right->data == ADDSUB_ASSIGN || root->right->data == INCDEC){
                    pos_cnt = find_pos_cnt(root->right->left->lexeme);
                    printf("MOV r%d [%d]\n", r_cnt++, pos_cnt*4);
                }

                if(strcmp(root->lexeme, "+=") == 0){
                    lv += rv;
                    retval = setval(root->left->lexeme, lv);
                    printf("ADD r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }
                else if(strcmp(root->lexeme, "-=") == 0){
                    lv -= rv;
                    retval = setval(root->left->lexeme, lv);
                    printf("SUB r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }

                pos_cnt = find_pos_cnt(root->left->lexeme);
                printf("MOV [%d] r%d\n", pos_cnt*4, r_cnt-1);
                r_cnt--;
                break;
            case INCDEC: // ++x
                lv = getval(root->left->lexeme);
                printf("MOV r%d 1\n", r_cnt);

                if(strcmp(root->lexeme, "++") == 0){
                    lv++;
                    retval = setval(root->left->lexeme, lv);
                    printf("ADD r%d r%d\n", r_cnt-1, r_cnt);
                    r_cnt--;
                }
                else if(strcmp(root->lexeme, "--") == 0){
                    lv--;
                    retval = setval(root->left->lexeme, lv);
                    printf("SUB r%d r%d\n", r_cnt-1, r_cnt);
                    r_cnt--;
                }

                pos_cnt = find_pos_cnt(root->left->lexeme);
                printf("MOV [%d] r%d\n", pos_cnt*4, r_cnt);
                break;
            case ADDSUB: // x + 3
            case MULDIV:
            case AND:
            case OR:
            case XOR:
                lv = evaluateTree(root->left);
                rv = evaluateTree(root->right);

                if(root->left->data == ASSIGN || root->left->data == ADDSUB_ASSIGN || root->left->data == INCDEC){
                    pos_cnt = find_pos_cnt(root->left->left->lexeme);
                    printf("MOV r%d [%d]\n", r_cnt++, pos_cnt*4);
                }

                if(root->right->data == ASSIGN || root->right->data == ADDSUB_ASSIGN || root->right->data == INCDEC){
                    pos_cnt = find_pos_cnt(root->right->left->lexeme);
                    printf("MOV r%d [%d]\n", r_cnt++, pos_cnt*4);
                }

                if(strcmp(root->lexeme, "+") == 0){
                    retval = lv + rv;
                    printf("ADD r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }
                else if(strcmp(root->lexeme, "-") == 0){
                    retval = lv - rv;
                    printf("SUB r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }
                else if(strcmp(root->lexeme, "*") == 0){
                    retval = lv * rv;
                    printf("MUL r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }   
                else if(strcmp(root->lexeme, "/") == 0){
                    if(rv == 0 && findVar(root) == 0) error(DIVZERO);
                    retval = 0;
                    printf("DIV r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }
                else if(strcmp(root->lexeme, "&") == 0){
                    retval = lv & rv;
                    printf("AND r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }
                else if(strcmp(root->lexeme, "|") == 0){
                    retval = lv | rv;
                    printf("OR r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }
                else if(strcmp(root->lexeme, "^") == 0){
                    retval = lv ^ rv;
                    printf("XOR r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }
                break;
            default:
                retval = 0;
        }
    }
    return retval;
}

## AC_merge_code.c

#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, ADDSUB_ASSIGN, INCDEC,
    AND, OR, XOR,
    LPAREN, RPAREN
} 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
#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];
} 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];

// 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);

extern void statement();
extern BTNode *assign_expr();
extern BTNode *or_expr();
extern BTNode *or_expr_tail(BTNode *left);
extern BTNode *xor_expr();
extern BTNode *xor_expr_tail(BTNode *left);
extern BTNode *and_expr();
extern BTNode *and_expr_tail(BTNode *left);
extern BTNode *addsub_expr();
extern BTNode *addsub_expr_tail(BTNode *left);
extern BTNode *muldiv_expr();
extern BTNode *muldiv_expr_tail(BTNode *left);
extern BTNode *unary_expr();
extern BTNode *factor();

// Print error message and exit the program
void err(ErrorType errorNum);


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

int find_pos_cnt(char *name);
int findVar(BTNode *root);

int r_cnt;
int pos_cnt;

/*============================================================================================
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 == '+' || c == '-'){
            lexeme[1] = c;
            lexeme[2] = '\0';
            return INCDEC;
        }
        else if(c == '='){
            lexeme[1] = c;
            lexeme[2] = '\0';
            return ADDSUB_ASSIGN;
        }
        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(c == '&'){
        strcpy(lexeme, "&");
        return AND;
    } else if(c == '|'){
        strcpy(lexeme, "|");
        return OR;
    } else if(c == '^'){
        strcpy(lexeme, "^");
        return XOR;
    } else if (isalpha(c) || c == '_') {
        lexeme[0] = c;
        int i = 1;
        c = fgetc(stdin);
        while(isalnum(c) || c == '_' && i < MAXLEN-1){
            lexeme[i++] = c;
            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 getval(char *str) {
    int i = 0;
    int found = 0;

    for (i = 0; i < sbcount; i++){
        if (strcmp(str, table[i].name) == 0){
            found = 1;
            printf("MOV r%d [%d]\n", r_cnt++, i*4);
            return table[i].val;
        }
    }

    if (sbcount >= TBLSIZE)
        error(RUNOUT);

    //printf("%s\n", table[0].name);
    if(!found) error(NOTFOUND);

    return 0;
}

int setval(char *str, int val) {
    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)
        error(RUNOUT);

    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);
    }
}

void statement(){
    if(match(ENDFILE)){
        printf("MOV r0 [0]\n");
        printf("MOV r1 [4]\n");
        printf("MOV r2 [8]\n");
        printf("EXIT 0\n");
        exit(0);
    }
    else if(match(END)){
        advance();
    }
    else{
        BTNode *retp = assign_expr();
        if(match(END)){
            evaluateTree(retp);
            freeTree(retp);
            advance();
        }
        else{
            error(SYNTAXERR);
        }
    }
}

// assign_expr := ID ASSIGN assign_expr | ID ADDSUB_ASSIGN assign_expr | or_expr
BTNode *assign_expr(){
    BTNode *retp = NULL, *left = or_expr();
    if(left->data == ID){
        if(match(ASSIGN)){
            retp = makeNode(ASSIGN, getLexeme());
            advance();
            retp->left = left;
            retp->right = assign_expr();
            return retp;
        }
        else if(match(ADDSUB_ASSIGN)){
            retp = makeNode(ADDSUB_ASSIGN, getLexeme());
            advance();
            retp->left = left;
            retp->right = assign_expr();
            return retp;
        }
    }
    return left;
}

// or_expr := xor_expr or_expr_tail
BTNode *or_expr(){
    BTNode *node = xor_expr();
    return or_expr_tail(node);
}

// or_expr_tail := OR xor_expr or_expr_tail | NiL
BTNode *or_expr_tail(BTNode *left){
    BTNode *node = NULL;
    if(match(OR)){
        node = makeNode(OR, getLexeme());
        advance();
        node->left = left;
        node->right = xor_expr();
        return or_expr_tail(node);
    }
    else{
        return left;
    }
}

// xor_expr := and_expr xor_expr_tail
BTNode *xor_expr(){
    BTNode *node = and_expr();
    return xor_expr_tail(node);
}

// xor_expr_tail := XOR and_expr xor_expr_tail | NiL
BTNode *xor_expr_tail(BTNode *left){
    BTNode *node = NULL;
    if(match(XOR)){
        node = makeNode(XOR, getLexeme());
        advance();
        node->left = left;
        node->right = and_expr();
        return xor_expr_tail(node);
    }
    else{
        return left;
    }
}

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

// and_expr_tail := AND addsub_expr and_expr_tail | NiL
BTNode *and_expr_tail(BTNode *left){
    BTNode *node = NULL;
    if(match(AND)){
        node = makeNode(AND, getLexeme());
        advance();
        node->left = left;
        node->right = addsub_expr();
        return and_expr_tail(node);
    }
    else{
        return left;
    }
}

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

// addsub_expr_tail := ADDSUB muldiv_expr addsub_expr_tail | NiL
BTNode *addsub_expr_tail(BTNode *left){
    BTNode *node = NULL;
    if(match(ADDSUB)){
        node = makeNode(ADDSUB, getLexeme());
        advance();
        node->left = left;
        node->right = muldiv_expr();
        return addsub_expr_tail(node);
    }
    else{
        return left;
    }
} 

// muldiv_expr := unary_expr muldiv_expr_tail
BTNode *muldiv_expr(){
    BTNode *node = unary_expr();
    return muldiv_expr_tail(node);
}

// muldiv_expr_tail := MULDIV unary_expr muldiv_expr_tail | NiL
BTNode *muldiv_expr_tail(BTNode *left){
    BTNode *node = NULL;
    if(match(MULDIV)){
        node = makeNode(MULDIV, getLexeme());
        advance();
        node->left = left;
        node->right = unary_expr();
        return muldiv_expr_tail(node);
    }
    else{
        return left;
    }
}

// unary_expr := ADDSUB unary_expr | factor
BTNode *unary_expr(){
    BTNode *node = NULL;
    if(match(ADDSUB)){
        node = makeNode(ADDSUB, getLexeme());
        advance();
        node->left = makeNode(INT, "0");
        node->right = unary_expr();
        return node;
    }
    else{
        node = factor();
        return node;
    }
}

// factor := INT | ID | INCDEC ID | LPAREN assign_expr RPAREN
BTNode *factor(){
    BTNode *node = NULL;
    if(match(INT)){
        node = makeNode(INT, getLexeme());
        advance();
    }
    else if(match(ID)){
        node = makeNode(ID, getLexeme());
        advance();
    }
    else if(match(INCDEC)){
        node = makeNode(INCDEC, getLexeme());
        advance();
        if(match(ID)){
            node->left = makeNode(ID, getLexeme());
            advance();
        }
        else{
            error(NOTNUMID);
        }
    }
    else if(match(LPAREN)){
        advance();
        node = assign_expr();
        if(match(RPAREN)){
            advance();
        }
        else{
            error(MISPAREN);
        }
    }
    else{
        error(NOTNUMID);
    }
    return node;
}

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;
        }
        printf("EXIT 1\n");
    }
    exit(0);
}

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

int find_pos_cnt(char *name){
    for(int i=0; i<sbcount; i++){
        if(strcmp(name, table[i].name) == 0) return i;
    }
    //error(NOTFOUND);
}

int findVar(BTNode *root){
    if(root == NULL) return 0;
    if(root->data == ID) return 1;
    if(findVar(root->left)) return 1;
    if(findVar(root->right)) return 1;
    return 0;
}

int evaluateTree(BTNode *root) {
    int retval = 0, lv = 0, rv = 0;

    if (root != NULL) {
        switch (root->data) {
            case ID:
                retval = getval(root->lexeme);
                break;
            case INT:
                retval = atoi(root->lexeme);
                printf("MOV r%d %d\n", r_cnt++, retval);
                break;
            case ASSIGN: // x = 3
                rv = evaluateTree(root->right);
                retval = setval(root->left->lexeme, rv);
                
                if(root->right->data == ASSIGN || root->right->data == ADDSUB_ASSIGN || root->right->data == INCDEC){
                    pos_cnt = find_pos_cnt(root->right->left->lexeme);
                    printf("MOV r%d [%d]\n", r_cnt++, pos_cnt*4);
                }

                pos_cnt = find_pos_cnt(root->left->lexeme);
                printf("MOV [%d] r%d\n", pos_cnt*4, r_cnt-1);
                r_cnt--;
                break;
            case ADDSUB_ASSIGN: // x += 3
                lv = getval(root->left->lexeme);
                rv = evaluateTree(root->right);

                if(root->right->data == ASSIGN || root->right->data == ADDSUB_ASSIGN || root->right->data == INCDEC){
                    pos_cnt = find_pos_cnt(root->right->left->lexeme);
                    printf("MOV r%d [%d]\n", r_cnt++, pos_cnt*4);
                }

                if(strcmp(root->lexeme, "+=") == 0){
                    lv += rv;
                    retval = setval(root->left->lexeme, lv);
                    printf("ADD r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }
                else if(strcmp(root->lexeme, "-=") == 0){
                    lv -= rv;
                    retval = setval(root->left->lexeme, lv);
                    printf("SUB r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }

                pos_cnt = find_pos_cnt(root->left->lexeme);
                printf("MOV [%d] r%d\n", pos_cnt*4, r_cnt-1);
                r_cnt--;
                break;
            case INCDEC: // ++x
                lv = getval(root->left->lexeme);
                printf("MOV r%d 1\n", r_cnt);

                if(strcmp(root->lexeme, "++") == 0){
                    lv++;
                    retval = setval(root->left->lexeme, lv);
                    printf("ADD r%d r%d\n", r_cnt-1, r_cnt);
                    r_cnt--;
                }
                else if(strcmp(root->lexeme, "--") == 0){
                    lv--;
                    retval = setval(root->left->lexeme, lv);
                    printf("SUB r%d r%d\n", r_cnt-1, r_cnt);
                    r_cnt--;
                }

                pos_cnt = find_pos_cnt(root->left->lexeme);
                printf("MOV [%d] r%d\n", pos_cnt*4, r_cnt);
                break;
            case ADDSUB: // x + 3
            case MULDIV:
            case AND:
            case OR:
            case XOR:
                lv = evaluateTree(root->left);
                rv = evaluateTree(root->right);

                if(root->left->data == ASSIGN || root->left->data == ADDSUB_ASSIGN || root->left->data == INCDEC){
                    pos_cnt = find_pos_cnt(root->left->left->lexeme);
                    printf("MOV r%d [%d]\n", r_cnt++, pos_cnt*4);
                }

                if(root->right->data == ASSIGN || root->right->data == ADDSUB_ASSIGN || root->right->data == INCDEC){
                    pos_cnt = find_pos_cnt(root->right->left->lexeme);
                    printf("MOV r%d [%d]\n", r_cnt++, pos_cnt*4);
                }

                if(strcmp(root->lexeme, "+") == 0){
                    retval = lv + rv;
                    printf("ADD r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }
                else if(strcmp(root->lexeme, "-") == 0){
                    retval = lv - rv;
                    printf("SUB r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }
                else if(strcmp(root->lexeme, "*") == 0){
                    retval = lv * rv;
                    printf("MUL r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }   
                else if(strcmp(root->lexeme, "/") == 0){
                    if(rv == 0 && findVar(root) == 0) error(DIVZERO);
                    retval = 0;
                    printf("DIV r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }
                else if(strcmp(root->lexeme, "&") == 0){
                    retval = lv & rv;
                    printf("AND r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }
                else if(strcmp(root->lexeme, "|") == 0){
                    retval = lv | rv;
                    printf("OR r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }
                else if(strcmp(root->lexeme, "^") == 0){
                    retval = lv ^ rv;
                    printf("XOR r%d r%d\n", r_cnt-2, r_cnt-1);
                    r_cnt--;
                }
                break;
            default:
                retval = 0;
        }
    }
    return retval;
}

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

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

int main() {
    initTable();
    //printf(">> ");
    while (1) {
        statement();
    }
    return 0;
}

## 要感謝的人
1.陳廷恩 我不會就可以直接下去找他 debug 然後 expr 我們一起討論
2.許志希 assign_expr 卡爛 嘻嘻直接教我 code 點醒我
3.李君威 問 8 9 10測資錯誤的地方 果然是 ADDSUB_ASSIGN 的地方寫錯 我沒加\n
4.清大資工 大家 yoyoyooyoyoyoyooy

我超爛你們應該可以優化不少