Untitled

                Never    
C
       
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
//lex.h
#define MAXLEN 256

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

// Test if a token matches the current token 
extern int match(TokenSet token);

// Get the next token
extern void advance(void);

// Get the lexeme of the current token
extern char *getLexeme(void);

//parser.h
#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;

// The symbol table
extern Symbol table[TBLSIZE];

// Initialize the symbol table with builtin variables
extern void initTable(void);

// Get the value of a variable
extern int getval(char *str);

int check_defined(char* str);

// Set the value of a variable
extern int setval(char *str, int val);

// Find the table idex;
extern int find_table_index(char* str);

// Make a new node according to token type and lexeme
extern BTNode *makeNode(TokenSet tok, const char *lexe);

// Free the syntax tree
extern void freeTree(BTNode *root);

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

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

//codeGen.h
int reg[8][2];//reg[][0] = data, reg[][1] = used(1) not used(0)

// Find empty register
extern int find_not_used_reg();
//
int check_ID(BTNode* root);
// Evaluate the syntax tree
extern int evaluateTree(BTNode *root);

// Print the syntax tree in prefix
extern void printPrefix(BTNode *root);

//lex.c
TokenSet getToken(void);
TokenSet curToken = UNKNOWN;
char lexeme[MAXLEN];

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 == '_'){
            err(UNKNOWN);
        }
        ungetc(c, stdin);
        lexeme[i] = '\0';
        return INT;
    } else if (c == '+' || c == '-') {
        char c2 = fgetc(stdin);
        if( c2 == c){
            lexeme[0] = lexeme[1] = c;
            lexeme[2] = '\0';
            return INCDEC;
        }
        else{
            ungetc(c2, stdin);
            lexeme[0] = c;
            lexeme[1] = '\0';
            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;
        c = fgetc(stdin);
        i = 1;
        while ((isalpha(c) || isdigit(c) || 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 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 {
        return UNKNOWN;
    }
}

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

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

char *getLexeme(void) {
    return lexeme;
}

//parser.c
int sbcount = 0;
Symbol table[TBLSIZE];

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 check_defined(char* str){
    int i;
    for(i = 0; i < sbcount; i ++){
        if(strcmp(table[i].name, str) == 0 )
            return 1;
    }
    return 0;
}

int find_table_index(char* str){
    int i;
    for(i = 0; i < sbcount; i ++){
        if(strcmp(table[i].name, str) == 0 )
            return i*4;
    }
    if(sbcount >= TBLSIZE)
        error(RUNOUT);
    strcpy(table[sbcount].name, str);
    table[sbcount].val = 0;
    i = sbcount;
    sbcount++;
    return 4 * i;
}

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

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

    if (match(INT)) {
        retp = makeNode(INT, getLexeme());
        advance();
        return retp;
    } else if (match(ID)) {
        retp = makeNode(ID, getLexeme());
        advance();
        return retp;
    } else if (match(INCDEC)) {
        int flag;
        if(strcmp(getLexeme(), "++") == 0)
            flag = 1;
        else
            flag = 0;
        retp = makeNode(ASSIGN, "=");
        advance();
        if (match(ID)){
            retp->left = makeNode(ID, getLexeme());
            if(flag == 1)
                retp->right = makeNode(ADDSUB, "+");
            else
                retp->right = makeNode(ADDSUB, "-");
            retp->right->left = makeNode(ID, getLexeme());
            retp->right->right = makeNode(INT, "1");
            advance();
            return retp;
        }
        else{
            error(NOTNUMID);
        }
    } else if (match(LPAREN)) {
        advance();
        retp = assign_expr();
        if (match(RPAREN)){
            advance();
            return retp;
        }
        else
            error(MISPAREN);
    } else {
        error(NOTNUMID);
    }
}

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

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

//muldiv_expr := unary_expr muldiv_expr_tail;
BTNode *muldiv_expr(void) {
    BTNode *node = unary_expr();
    return muldiv_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;
    }
}

//and_expr_tail:= AND addsub_expr andsub_expr_tail;
BTNode *addsub_expr(void) {
    BTNode *node = muldiv_expr();
    return addsub_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;
    }
}

//and_expr := addsub_expr and_expr_tail;
BTNode *and_expr(void) {
    BTNode *node = addsub_expr();
    return and_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;
    }
}

//xor_expr := and_expr xor_expr_tail;
BTNode *xor_expr(void) {
    BTNode *node = and_expr();
    return xor_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;
    }
}

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

//assign_expr := ID ASSIGN assgin_expr | or_expr;
BTNode* assign_expr(){
    int flag = match(ID);
    BTNode *left = or_expr(), *node = NULL;
    if(match(ASSIGN)){
        if(flag){
            node = makeNode(ASSIGN, getLexeme());
            advance();
            node->left = left;
            node->right = assign_expr();
            return node;
        }
        else{
            err(NOTNUMID);
        }
    }
    else{
        return left;
    }
}

// statement := ENDFILE | END | assign_expr END
void statement(void) {
    BTNode *retp = NULL;

    if (match(ENDFILE)) {
        for(int i = 0; i < 8; i ++){
                reg[i][0] = 0;
                reg[i][1] = 0;
        }
        for(int i = 0; i < 3; i ++){
            printf("MOV r%d [%d]\n", i, 4*i);
        }
        printf("EXIT 0");
        exit(0);
    } else if (match(END)) {
        //printf(">> ");
        advance();
    } else {
        retp = assign_expr();
        //printPrefix(retp);
        //printf("\n");
        if (match(END)) {
            for(int i = 0; i < 8; i ++){
                reg[i][0] = 0;
                reg[i][1] = 0;
            }
            /*
            for(int i = 0; i < sbcount; i ++){
                printf("%s ", table[i].name);
            }
            printf("\n");
            */
            int answer = evaluateTree(retp);
            /*
            for(int i = 0; i < sbcount; i ++){
                printf("%s ", table[i].name);
            }
            printf("\n");
            */
            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;
            default:
                fprintf(stderr, "undefined error\n");
                break;
        }
    }
    printf("EXIT 1");
    exit(0);
}

//codeGen.c
int find_not_used_reg(){
    int i;
    for(i = 0; i < 8; i ++){
        if(reg[i][1] == 0)
            return i;
    }
    //no empty reg error?
}
int check_ID(BTNode* root){
    if(root == NULL) return 0;
    if(root->data == ID)
        return 1;
    if(root->left != NULL){
        if (check_ID(root->left))
            return 1;
    }
    if(root->right != NULL){
        if (check_ID(root->right))
            return 1;
    }
    return 0;
}

int calculate_depth(BTNode* root){
    int ans = 0;
    if(root->data == ID || root->data == INT) ans++;
    if(root->left != NULL){
        ans += calculate_depth(root->left);
    }
    if(root->right != NULL){
        ans += calculate_depth(root->right);
    }
    return ans;
}
int evaluateTree(BTNode *root) {
    int lv = 0, rv = 0;
    int nu;
    if (root != NULL) {
        switch (root->data){
            case ID:
                if(!check_defined(root->lexeme)){
                    err(NOTFOUND);
                }
                nu = find_not_used_reg();
                printf("MOV r%d [%d]\n",nu, find_table_index(root->lexeme));
                reg[nu][0] = getval(root->lexeme);
                reg[nu][1] = 1;
                return nu;
                break;
            case INT:
                nu = find_not_used_reg();
                printf("MOV r%d %d\n",nu, atoi(root->lexeme));
                reg[nu][0] = atoi(root->lexeme);
                reg[nu][1] = 1;
                return nu;
                break;
            case ASSIGN:
                 rv = evaluateTree(root->right);
                if(root->left->data != ID){
                    err(SYNTAXERR);
                }
                printf("MOV [%d] r%d\n", find_table_index(root->left->lexeme), rv);
                setval(root->left->lexeme, reg[rv][0]);
                //reg[rv][0] = 0;
                //reg[rv][1] = 0;
                return rv; 
                break;
            case ADDSUB:
            case MULDIV:
                if(calculate_depth(root->left) > calculate_depth(root->right)){
                    lv = evaluateTree(root->left);
                    rv = evaluateTree(root->right);
                }
                else{
                    rv = evaluateTree(root->right);
                    lv = evaluateTree(root->left);
                }
               
                if (strcmp(root->lexeme, "+") == 0) {
                    printf("ADD r%d r%d\n", lv, rv);
                    reg[lv][0] += reg[rv][0];
                    reg[rv][0] = 0;
                    reg[rv][1] = 0; 
                } else if (strcmp(root->lexeme, "-") == 0) {
                    printf("SUB r%d r%d\n", lv, rv);
                    reg[lv][0] -= reg[rv][0];
                    reg[rv][0] = 0;
                    reg[rv][1] = 0; 
                } else if (strcmp(root->lexeme, "*") == 0) {
                    printf("MUL r%d r%d\n", lv, rv);
                    reg[lv][0] *= reg[rv][0];
                    reg[rv][0] = 0;
                    reg[rv][1] = 0; 
                } else if (strcmp(root->lexeme, "/") == 0) {
                    if (reg[rv][0] == 0 && check_ID(root->right) == 0)
                        err(DIVZERO);
                    printf("DIV r%d r%d\n", lv, rv);
                    if(reg[rv][0] != 0)
                        reg[lv][0] /= reg[rv][0];
                    reg[rv][0] = 0;
                    reg[rv][1] = 0; 
                }
                return lv;
                break;
            /*case INCDEC:
                rv = evaluateTree(root->right);
                nu = find_not_used_reg();
                if(strcmp(root->lexeme, "++") == 0){
                    printf("MOV r%d %d\n", nu, 1);
                    reg[nu][0] = 1;
                    reg[nu][1] = 1;
                    printf("ADD r%d r%d\n", rv, nu);
                    reg[rv][0] += reg[nu][0];
                    reg[nu][0] = 0;
                    reg[nu][1] = 0; 
                    printf("MOV [%d] r%d\n",find_table_index(root->right->lexeme), rv);
                    setval(root->right->lexeme, reg[rv][0]);
                    return rv;
                }
                else{
                    printf("MOV r%d %d\n", nu, 1);
                    reg[nu][0] = 1;
                    reg[nu][1] = 1;
                    printf("SUB r%d r%d\n", rv, nu);
                    reg[rv][0] -= reg[nu][0];
                    reg[nu][0] = 0;
                    reg[nu][1] = 0; 
                    printf("MOV [%d] r%d\n",find_table_index(root->right->lexeme), rv);
                    setval(root->right->lexeme, reg[rv][0]);
                    return rv;
                }
                break;
                */
            case AND:
                if(calculate_depth(root->left) > calculate_depth(root->right)){
                    lv = evaluateTree(root->left);
                    rv = evaluateTree(root->right);
                }
                else{
                    rv = evaluateTree(root->right);
                    lv = evaluateTree(root->left);
                }
                printf("AND r%d r%d\n", lv, rv);
                reg[lv][0] = reg[lv][0] && reg[rv][0];
                reg[rv][0] = 0;
                reg[rv][1] = 0; 
                return lv;
                break;
            case OR:
                if(calculate_depth(root->left) > calculate_depth(root->right)){
                    lv = evaluateTree(root->left);
                    rv = evaluateTree(root->right);
                }
                else{
                    rv = evaluateTree(root->right);
                    lv = evaluateTree(root->left);
                }
                printf("OR r%d r%d\n", lv, rv);
                reg[lv][0] = reg[lv][0] || reg[rv][0];
                reg[rv][0] = 0;
                reg[rv][1] = 0; 
                return lv;
                break;
            case XOR:
                if(calculate_depth(root->left) > calculate_depth(root->right)){
                    lv = evaluateTree(root->left);
                    rv = evaluateTree(root->right);
                }
                else{
                    rv = evaluateTree(root->right);
                    lv = evaluateTree(root->left);
                }
                printf("XOR r%d r%d\n", lv, rv);
                reg[lv][0] = reg[lv][0] ^ reg[rv][0];
                reg[rv][0] = 0;
                reg[rv][1] = 0; 
                return lv;
                break;
            default:
                rv = 0;
                break;
        }
    }
}

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

//main.c
int main() {
    //freopen("input.txt", "w", stdout);
    initTable();
    while (1) {
        statement();
    }
    return 0;
}



Raw Text