Untitled

#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,
    AND, OR, XOR,
    INCDEC
} TokenSet;

TokenSet getToken(void);
TokenSet curToken = UNKNOWN;
char lexeme[MAXLEN];
int match(TokenSet token);
void advance(void);
char *getLexeme(void);
#define TBLSIZE 64
#define PRINTERR 1
#define error(errorNum) { \
    if (PRINTERR) \
        fprintf(stderr, "error() called at %s:%d: ", __FILE__, __LINE__); \
    err(errorNum); \
}
typedef enum {
    UNDEFINED, MISPAREN, NOTNUMID, NOTFOUND, RUNOUT, NOTLVAL, DIVZERO, SYNTAXERR, NOVALUE, WRONGNAME
} ErrorType;

typedef struct {
    int val;
    char name[MAXLEN];
} Symbol;

typedef struct _Node {
    TokenSet data;
    int val;
    char lexeme[MAXLEN];
    struct _Node *left;
    struct _Node *right;
} BTNode;


void look(BTNode *root);
int sbcount = 0;
Symbol table[TBLSIZE];

void initTable(void);
int getval(char *str);
int setval(char *str, int val);
BTNode *makeNode(TokenSet tok, const char *lexe);
void freeTree(BTNode *root);
BTNode *factor(void);
BTNode *term(void);
BTNode *term_tail(BTNode *left);
BTNode *expr(void);
BTNode *expr_tail(BTNode *left);
void statement(void);


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

int evaluateTree(BTNode *root);
void printPrefix(BTNode *root);

int look_value=0;
int r[8];
int number;
int flag;


/*============================================================================================
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);
        }
 
        if (isalpha(c) || c == '_') {
            error(NOVALUE);
        }
        ungetc(c, stdin);
        lexeme[i] = '\0';
        return INT;
    } 
    else if (c == '+' || c == '-') {
        char d = fgetc(stdin);
 
        if (c == d) {
            lexeme[0] = c;
            lexeme[1] = '\0';
            return INCDEC;
        }
        else {
            ungetc(d, stdin);
            lexeme[0] = c;
            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 OR;
    }
    else if (c == '^') {
        lexeme[0] = c;
        lexeme[1] = '\0';
        return XOR;
    }
    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;
        c = fgetc(stdin);
        i = 1;
 
        while ((isdigit(c) || isalpha(c) || c == '_') && i < MAXLEN) {
            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;

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

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

    error(NOVALUE);
    /*strcpy(table[sbcount].name, str);
    table[sbcount].val = 0;
    sbcount++;*/
    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);
    }
}


BTNode *factor(void) {
    BTNode *retp = NULL, *left = NULL;

    if (match(INT)) {
        retp = makeNode(INT, getLexeme());
        advance();
    } else if (match(ID)) {
        left = makeNode(ID, getLexeme());
        advance();
        /*if (!match(ASSIGN)) {
            retp = left;
        } else {
            retp = makeNode(ASSIGN, getLexeme());
            advance();
            retp->left = left;
            retp->right = assign_expr();
        }*/
    } else if (match(INCDEC)) {                      
        retp = makeNode(ASSIGN, "='\0");
        retp -> right = makeNode(ADDSUB, getLexeme());
        advance();
 
        retp -> left = factor();
        retp -> right -> right = makeNode(INT, "1'\0");
        retp -> right -> left = (BTNode*) calloc (sizeof(BTNode), 1);
        strcpy(retp -> right -> left -> lexeme, retp -> left -> lexeme);
        retp -> right -> left -> data = ID;                         
    } else if (match(LPAREN)) {
        advance();
        retp = assign_expr();
        if (match(RPAREN))
            advance();
        else
            error(MISPAREN);
    } else {
        error(NOTNUMID);
    }
    return retp;
}





extern BTNode *assign_expr(void){
    BTNode *node=NULL;  BTNode *left=or_expr();

    if(left->data == ID && match(ASSIGN))
    { 
        node=makeNode(ASSIGN,getLexeme());
        advance();
        node->left=left;
        node->right=assign_expr();
        
    }else{
        return left;
    }

    return node;

}

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

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

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

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

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

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

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

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

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

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

extern BTNode *unary_expr(void){                            //return再看看
    BTNode *node = NULL;
    if (match(ADDSUB)) {
        node = makeNode(ADDSUB, getLexeme());
        advance();
        node->left = makeNode(INT,"0'\0");
        node->right = unary_expr();
    } else {
        node = factor();
    }

    return node;
}


void statement(void) {
    BTNode *retp = NULL;

    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 {
        retp = assign_expr();
        if ( match(END) ) {
            number=0;
            evaluateTree(retp);
            freeTree(retp);
            advance();
        } 
        else {
            error(SYNTAXERR);
        }
    }
}

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;
            case NOVALUE:
                //fprintf(stderr, "syntax error\n");
                break;
            case WRONGNAME:
                //fprintf(stderr, "wrong name\n");
                break;
            default:
                //fprintf(stderr, "undefined error\n");
                break;
        }
    }
    printf("EXIT 1\n");
    exit(0);
}


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

int evaluateTree(BTNode *root) {
    int retval = 0, lv = 0, rv = 0;
    int i,j;
    int left,right;

    if (root != NULL) {
        switch (root->data) {
            case ID:
                retval = getval(root->lexeme);
                r[number]=retval;

                for(i=0;i<sbcount;i++)
                {
                    if( strcmp(table[i].name,root->lexeme)==0 )
                    {
                        printf("MOV r%d [%d]\n",number,i*4);
                        break;
                    }
                }


                number++;
                break;
            case INT:
                retval = atoi(root->lexeme);
                r[number]=retval;
                printf("MOV r%d %d\n",number,r[number]);
                number++;
                break;
            case ASSIGN:
            if(root->left->data != ID)     error(NOVALUE);
            
                rv = evaluateTree(root->right);
                retval = setval(root->left->lexeme, rv);

                for(i=0;i<sbcount;i++)
                {
                    if( strcmp(table[i].name,root->left->lexeme)==0)
                    {
                        for(j=number-1;j>=0;j--)
                        {
                            if(rv==r[j])
                            {
                                printf("MOV [%d] r%d\n",i*4,j);
                                break;
                            }
                            
                        }
                        break;
                    }
                }

                break;
            case ADDSUB:
            case MULDIV:
            if (root -> left == NULL || root -> right == NULL ) {
                    error(NOVALUE);
                }


                lv = evaluateTree(root->left);
                rv = evaluateTree(root->right);
                right = --number;
                left  = --number;
                number++;
                
                if (strcmp(root->lexeme, "+") == 0) {
                    retval = lv + rv;
                    r[left]=retval; r[right]=0;
                    printf("ADD r%d r%d\n",left,right);
                } else if (strcmp(root->lexeme, "-") == 0) {
                    retval = lv - rv;
                    r[left]=retval; r[right]=0;
                    printf("SUB r%d r%d\n",left,right);
                } else if (strcmp(root->lexeme, "*") == 0) {
                    retval = lv * rv;
                    r[left]=retval; r[right]=0;
                    printf("MUL r%d r%d\n",left,right);
                } else if (strcmp(root->lexeme, "/") == 0) {
                    if (rv == 0){
                        look_value=0;
                        look(root->right);
                        if(look_value)
                        retval = 0;                              
                        else
                        error(DIVZERO);
                    }
                    else retval = lv / rv;

                    r[left]=retval; r[right]=0;
                    printf("DIV r%d r%d\n",left,right);
                }
                break;
            /*case INCDEC:        
                if (root -> left == NULL || root -> right == NULL  ) {
                    err(NOVALUE);
                }
                if(root->right->data != ID)
                    err(NOVALUE);
                lv = evaluateTree(root->left);                 
                rv = evaluateTree(root->right);
                right = --number;
                left  = --number;
                number++;
                number++;          

                if (strcmp(root->lexeme, "++") == 0) {
                    retval=lv+rv;
                    setval(root->right->lexeme, retval);
                    r[left]=1; r[right]=retval;
                    printf("ADD r%d r%d\n",right,left);
                } else if (strcmp(root->lexeme, "--") == 0) {
                    retval=rv-lv;
                    setval(root->right->lexeme, retval);
                    r[left]=1; r[right]=retval;
                    printf("SUB r%d r%d\n",right,left);
                }
                break;*/
            case AND:
            case OR:
            case XOR:
            if (root -> left == NULL || root -> right == NULL) {
                    error(NOVALUE);
                }

                lv = evaluateTree(root->left);                 
                rv = evaluateTree(root->right);
                right = --number;
                left  = --number;
                number++;
                
                if (strcmp(root->lexeme, "&") == 0) {
                    retval = lv & rv;
                    r[left]=retval; r[right]=0;
                    printf("AND r%d r%d\n",left,right);
                } else if (strcmp(root->lexeme, "|") == 0) {
                    retval = lv | rv;
                    r[left]=retval; r[right]=0;
                    printf("OR r%d r%d\n",left,right);
                } else if (strcmp(root->lexeme, "^") == 0) {
                    retval = lv ^ rv;
                    r[left]=retval; r[right]=0;
                    printf("XOR r%d r%d\n",left,right);
                }
                break;
            default:
                retval = 0;
        }
    }
    return retval;
}



void look(BTNode *root){

    if(look_value)  return;

    if(root->left!=NULL)
    look(root->left);

    if(root->right!=NULL)
    look(root->right);

    if(root->data == ID) {
        look_value=1;
        return;
    }

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


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

int main() {
    initTable();

    while (1) {
        statement();
    }
    return 0;
}