Untitled

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

#define MAXLEN 256

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

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

#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, ILLEGAL_VAR
} 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];
static int in = 0;
static BTNode *innode;
// Initialize the symbol table with builtin variables
extern void initTable(void);

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

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

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

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

extern int evaluateTree(BTNode *root);

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

int count=0;
int inc,dec,indiv,have_v;
int have_val(BTNode* root);
//int reg_value[1] = {0};
//int regs[8];

int main() {
    freopen("input.txt", "w", stdout);
    initTable();
    //printf(">> ");
    //printf("MOV r%d [0]\n", count++);
    //printf("MOV r%d [4]\n", count++);
    //printf("MOV r%d [8]\n", count++);
    count = 0;
    while (1) {
        statement();
    }
    printf("EXIT 0\n");
    return 0;
}

static TokenSet getToken(void);
static TokenSet curToken = UNKNOWN;
static 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 == '_')
        {
            error(ILLEGAL_VAR);
        }
        if(i >= MAXLEN)
            error(RUNOUT);
        ungetc(c, stdin);
        lexeme[i] = '\0';
        return INT;
    } else if (c == '+' || c == '-') {
        lexeme[0] = c;
        c = fgetc(stdin);
        if(c == '+' && lexeme[0] == '+')
        {
            lexeme[1] = c;
            lexeme[2] = '\0';
            return INCDEC;
        }
        else if(c == '-' && lexeme[0] == '-')
        {
            lexeme[1] = c;
            lexeme[2] = '\0';
            return INCDEC;
        }
        ungetc(c, stdin);
        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 (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;
        c = fgetc(stdin);
        i=1;
        while((isalpha(c) || c == '_' || isdigit(c)) && i<MAXLEN){
            lexeme[i] = c;
            ++i;
            c = fgetc(stdin);
        }
        if(i >= MAXLEN)
            error(RUNOUT);
        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;
}


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 getval(char *str) {
    int i = 0;

    for (i = 0; i < sbcount; i++){
        if (strcmp(str, table[i].name) == 0)
        {
            /*for(int j=0; j<8; j++)
            {
                if(reg_value[j] == table[i].val && table[i].val != 0)
                {
                    printf("MOV r%d r%d\n", count, j);
                    //printf("MOV r%d %d\n", count, table[i].val);
                    reg_value[count] = table[i].val;
                    return table[i].val;
                }
            }*/
            if(count>7)
                exit(1);
            printf("MOV r%d [%d]\n", count, i*4);
            //reg_value[count] = table[i].val;
            return table[i].val;
        }
    }

    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) {
            if(count>7)
                exit(1);
            printf("MOV [%d] r%d\n", i*4, count);
            table[i].val = val;
            return val;
        }
    }

    if (sbcount >= TBLSIZE)
        error(RUNOUT);
    
    strcpy(table[sbcount].name, str);
    table[sbcount].val = val;
    if(count>7)
        exit(1);
    printf("MOV [%d] r%d\n", sbcount*4, count);
    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 | INCDEC ID | LPAREN assign_expr RPAREN

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

    if (match(INT)) {
        retp = makeNode(INT, getLexeme());
        advance();
    } else if (match(ID)) {
        retp = makeNode(ID, getLexeme());
        advance();
    } else if (match(INCDEC)){
        retp = makeNode(INCDEC, getLexeme());
        advance();
        
        if(match(ID)){
            retp->right = makeNode(ID, getLexeme());
            advance();
        }
        else{
            error(NOTLVAL);
        }
    } else if (match(LPAREN)) {
        //retp = makeNode(LPAREN, getLexeme());
        advance();
        //retp->right = assign_expr();
        retp = assign_expr();
        if (match(RPAREN))
            advance();
        else
            error(MISPAREN);
    } else {
        error(NOTNUMID);
    }
    return retp;
}

//unary_expr := ADDSUB unary_expr | factor 
BTNode *unary_expr() {
    BTNode *node = NULL;

    if(innode != NULL) {
        node = innode;
        innode = NULL;
        return node;
    }
    if(match(ADDSUB)) {
        node = makeNode(ADDSUB, getLexeme());
        node->left = makeNode(INT, "0");
        advance();
        node->right = unary_expr();
        return node;
    } else {
        node = factor();
        return 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;
    }
}


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


//addsub_expr := muldiv_expr addsub_expr_tail 
BTNode *addsub_expr() {
    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() {
    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() {
    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() {
    //printf("C");
    BTNode *node = xor_expr();
    return or_expr_tail(node);
}


// assign_expr := ID ASSIGN assign_expr | or_expr
BTNode *assign_expr() {
    BTNode *node = NULL, *left = NULL;

    if(match(ID)) {
        left = makeNode(ID, getLexeme());
        advance();
        if(match(ASSIGN)) {
            node = makeNode(ASSIGN, getLexeme());
            advance();
            node->left = left;
            node->right = assign_expr();
            return node;
        } else {
            //printf("c");
            in = 1;
            innode = left;
            node = or_expr();
            innode = NULL;
            in = 0;
            return node;
        }  
    } else {
        node = or_expr();
        return node;
    }
}


// statement := ENDFILE | END | expr END
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)) {
        //printf(">> ");
        advance();
    } else {
        retp = assign_expr();
        if (match(END)) {
            evaluateTree(retp);
            freeTree(retp);
            //printf("%d\n", evaluateTree(retp));
            //printf("Prefix traversal: ");
            //printPrefix(retp);
            //printf("\n");
            //freeTree(retp);
            //printf(">> ");
            advance();
            count = 0;
        } else {
            error(SYNTAXERR);
        }
    }
}

void err(ErrorType errorNum) {
    if (PRINTERR)  printf("EXIT 1\n");
    exit(0);
}

int parcount;
int evaluateTree(BTNode *root) {
    int retval = 0, lv = 0, rv = 0;
    int recount;
    //int regs[1000][8];
    BTNode* temp = NULL;
    int tmp=0;

    if (root != NULL) {
        switch (root->data) {
            case ID:
                retval = getval(root->lexeme);
                break;
            case INT:
                retval = atoi(root->lexeme);
                if(count>7)
                    exit(1);
                printf("MOV r%d %d\n", count, retval);
                //reg_value[count] = retval;
                break;
            case ASSIGN:
                rv = evaluateTree(root->right);
                if(root->left->data!=ID) error(SYNTAXERR);
                retval = setval(root->left->lexeme, rv);
                break;
            case ADDSUB:
            if(strcmp(root->lexeme, "+") == 0)
            {
                if(root->left->data == ID || root->left->data == INT)
                {
                    temp = root->left;
                    root->left = root->right;
                    root->right = temp;
                }
                lv = evaluateTree(root->left);

                if(strcmp(root->right->lexeme, "+") == 0)
                {
                    rv = evaluateTree(root->right);
                    //printf("MOV r%d r%d\n", count-1,count);
                }
                else
                {
                    count++;
                    if(count>=8)
                        exit(1);
                    rv = evaluateTree(root->right);
                    printf("ADD r%d r%d\n", count-1, count);
                    count--;
                    //reg_value[count] = retval;
                }
                retval = lv + rv;
                //reg_value[count] = retval;
            }
            else if(strcmp(root->lexeme, "-") == 0)
            {
                /*if(root->left->data == ID || root->left->data == INT)
                {
                    temp = root->left;
                    root->left = root->right;
                    root->right = temp;
                }*/
                lv = evaluateTree(root->left);

                if(strcmp(root->right->lexeme, "-") == 0)
                {
                    rv = evaluateTree(root->right);
                    //printf("MOV r%d r%d\n", count-1,count);
                }
                else
                {
                    count++;
                    if(count>=8)
                        exit(1);
                    rv = evaluateTree(root->right);
                    /*if(root->right->data == ID || root->right->data == INT)
                    {
                        printf("SUB r%d r%d\n", count, count-1);
                        printf("MOV r%d r%d\n", count-1, count);
                    }
                    else*/
                        printf("SUB r%d r%d\n", count-1, count);
                    count--;
                    //reg_value[count] = retval;
                }
                if(root->right->data == ID || root->right->data == INT)
                {
                    //printf("%d\n", lv);
                    retval = rv-lv;
                }
                else
                    retval = lv - rv;
                //reg_value[count] = retval;
            }
            break;
            case MULDIV:
            if(strcmp(root->lexeme, "*") == 0)
            {
                if(root->left->data == ID || root->left->data == INT)
                {
                    temp = root->left;
                    root->left = root->right;
                    root->right = temp;
                }
                lv = evaluateTree(root->left);

                if(strcmp(root->right->lexeme, "*") == 0)
                {
                    rv = evaluateTree(root->right);
                    //printf("MOV r%d r%d\n", count-1,count);
                }
                else
                {
                    count++;
                    if(count>=8)
                        exit(1);
                    rv = evaluateTree(root->right);
                    printf("MUL r%d r%d\n", count-1, count);
                    //reg_value[count] = retval;
                    count--;
                }
                retval = lv * rv;
                //reg_value[count] = retval;
            }
            else if(strcmp(root->lexeme, "/") == 0)
            {
                /*if(root->left->data == ID || root->left->data == INT)
                {
                    temp = root->left;
                    root->left = root->right;
                    root->right = temp;
                }*/
                lv = evaluateTree(root->left);

                if(strcmp(root->right->lexeme, "/") == 0)
                {
                    //indiv = 1;
                    //have_v = 0;
                    rv = evaluateTree(root->right);
                    /*if(root->right->data == ID || root->right->data == INT)
                    {
                        tmp = lv;
                        lv = rv;
                        rv = tmp;
                    }*/
                    if(rv == 0)
                    {
                        if(have_val(root->right))
                        {
                            retval = 0;
                        }
                        else
                            error(DIVZERO);
                    }
                    else
                        retval = lv/rv;
                    //printf("MOV r%d r%d\n", count-1,count);
                }
                else
                {
                    //indiv = 1;
                    //have_v = 0;
                    count++;
                    if(count>=8)
                        exit(1);
                    rv = evaluateTree(root->right);
                    /*if(root->right->data == ID || root->right->data == INT)
                    {
                        tmp = lv;
                        lv = rv;
                        rv = tmp;
                    }*/
                    if(rv == 0)
                    {
                        if(have_val(root->right))
                        {
                            retval = 0;
                        }
                        else
                            error(DIVZERO);
                    
                    }
                    else
                        retval = lv/rv;

                    /*if(root->right->data == ID || root->right->data == INT)
                    {
                        printf("DIV r%d r%d\n", count, count-1);
                        printf("MOV r%d r%d\n", count-1, count);
                    }
                    else*/
                        printf("DIV r%d r%d\n", count-1, count);
                    count--;
                    //reg_value[count] = reg_value[count+1];
                }
                //reg_value[count] = retval;
            }
                break;
            case INCDEC:
                if(strcmp(root->lexeme, "++") == 0)
                {
                    //inc = 1;
                    //lv = evaluateTree(root->left);
                    printf("MOV r%d 1\n", count);
                    //reg_value[count] = 1;
                    count++;
                    if(count>=8)
                        exit(1);
                    rv = evaluateTree(root->right);
                    //reg_value[count] = rv;
                    printf("ADD r%d r%d\n", count-1, count);
                    count--;
                    retval = rv+1;
                    //reg_value[count] = retval;
                    //inc = 0;
                }
                else if(strcmp(root->lexeme, "--") == 0)
                {
                    //dec = 1;
                    //lv = evaluateTree(root->left);
                    printf("MOV r%d -1\n", count);
                    //reg_value[count] = -1;
                    count++;
                    if(count>=8)
                        exit(1);
                    rv = evaluateTree(root->right);
                    //reg_value[count] = rv;
                    printf("ADD r%d r%d\n", count-1, count);
                    count--;
                    retval = rv-1;
                    //reg_value[count] = retval;
                    //dec = 0;
                }
                setval(root->right->lexeme, retval);
                break;
            case AND:
            if(root->left->data == ID || root->left->data == INT)
                {
                    temp = root->left;
                    root->left = root->right;
                    root->right = temp;
                }
                lv = evaluateTree(root->left);
            
                if(root->right->data == AND)
                {
                    rv = evaluateTree(root->right);
                }
                else
                {
                    count++;
                    if(count>=8)
                        exit(1);
                    rv = evaluateTree(root->right);
                    printf("AND r%d r%d\n", count-1, count);
                    count--;
                    //reg_value[count] = retval;
                }
                retval = lv & rv;
                //reg_value[count] = retval;
                break;
            case OR:
            if(root->left->data == ID || root->left->data == INT)
                {
                    temp = root->left;
                    root->left = root->right;
                    root->right = temp;
                }
                lv = evaluateTree(root->left);
            
                if(root->right->data == OR)
                {
                    rv = evaluateTree(root->right);
                }
                else
                {
                    count++;
                    if(count>=8)
                        exit(1);
                    rv = evaluateTree(root->right);
                    printf("OR r%d r%d\n", count-1, count);
                    count--;
                    //reg_value[count] = retval;
                }
                retval = lv | rv;
                //reg_value[count] = retval;
                break;
            case XOR:
            if(root->left->data == ID || root->left->data == INT)
                {
                    temp = root->left;
                    root->left = root->right;
                    root->right = temp;
                }
                lv = evaluateTree(root->left);
            
                if(root->right->data == XOR)
                {
                    rv = evaluateTree(root->right);
                }
                else
                {
                    count++;
                    if(count>=8)
                        exit(1);
                    rv = evaluateTree(root->right);
                    printf("XOR r%d r%d\n", count-1, count);
                    count--;
                    //reg_value[count] = retval;
                }
                retval = lv ^ rv;
                //reg_value[count] = retval;
                break;
            default:
                retval = 0;
        }
    }
    return retval;
}

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

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