Untitled

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

// for lex
#define MAXLEN 256
// Token types
typedef enum {
    UNKNOWN,
    END,     // '\n'
    ENDFILE, // EOF
    INT,     // Integer Number
    ID,      // Variable
    ADDSUB,  // '+' or '-'
    MULDIV,  // '*' or '/'
    ASSIGN,  // '='
    LPAREN,  // '('
    RPAREN,  // ')'
    INCDEC,  // ++ or --
    AND,     // '&'
    OR,      // '|'
    XOR      // '^'
} 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);
TokenSet getToken(void);
TokenSet curToken = UNKNOWN;
char lexeme[MAXLEN];

// 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) \
    {                   \
        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;
// The symbol table
Symbol table[TBLSIZE];

/*
    we use a symbol table to record variables’ current values
    we use getval() and setval() to manipulate the symbol table
*/

// Initialize the symbol table with builtin variables

void initTable(void);
int calculate_reg(BTNode *root);
void Last_Move(void);
int not_used();
int get_memory_address(char *str);
int check_defined(char *str);
int Exist_Variable(BTNode *root);

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

// for codeGen
int reg[8][2];
// Evaluate the syntax tree
int evaluateTree(BTNode *root);

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

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

TokenSet getToken(void) {
    int i = 0;
    char c = '\0';

    while ((c = fgetc(stdin)) == ' ' || c == '\t') {
    };

    if (isdigit(c)) { // return INT
        lexeme[0] = c;
        c = fgetc(stdin);
        i = 1;
        while (isdigit(c) && i < MAXLEN) {
            lexeme[i++] = c;
            c = fgetc(stdin);
        }
        if (isalpha(c) || c == '_') {
            err(UNKNOWN);
        }
        ungetc(c, stdin);
        lexeme[i] = '\0';
        return INT;

    } else if (c == '+' || c == '-') { // return ADDSUB or INCDEC
        lexeme[0] = c;
        c = fgetc(stdin);
        if ((c == '+' || c == '-') && (c == lexeme[0])) {
            lexeme[1] = c;
            lexeme[2] = '\0';
            return INCDEC;
        } else {
            ungetc(c, stdin);
            lexeme[1] = '\0';
            return ADDSUB;
        }

    } else if (c == '*' || c == '/') { // return MULDIV
        lexeme[0] = c;
        lexeme[1] = '\0';
        return MULDIV;

    } else if (c == '\n') { // return END
        lexeme[0] = '\0';
        return END;

    } else if (c == '=') { // return ASSIGN
        strcpy(lexeme, "=");
        return ASSIGN;

    } else if (c == '(') { // return LPAREN
        strcpy(lexeme, "(");
        return LPAREN;

    } else if (c == ')') { // return RPAREN
        strcpy(lexeme, ")");
        return RPAREN;

    } else if (c == '&') { // return AND
        lexeme[0] = c;
        lexeme[1] = '\0';
        return AND;

    } else if (c == '|') { // return OR
        lexeme[0] = c;
        lexeme[1] = '\0';
        return OR;

    } else if (c == '^') { // return XOR
        lexeme[0] = c;
        lexeme[1] = '\0';
        return XOR;

    } else if (isalpha(c) || c == '_') {
        lexeme[0] = c;
        c = fgetc(stdin);
        i = 1;
        while ((isdigit(c) || isalpha(c) || c == '_')) {
            if (i >= MAXLEN) {
                printf("EXIT 1");
                exit(0);
            }
            lexeme[i] = c;
            ++i;
            c = fgetc(stdin);
        }

        ungetc(c, stdin);
        lexeme[i] = '\0';
        return ID;

    } else if (c == EOF) {
        return ENDFILE;

    } else {
        return UNKNOWN;
    }
}

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

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

char *getLexeme(void) {
    return lexeme;
}

/*============================================================================================
parser implementation
============================================================================================*/

int calculate_reg(BTNode *root) {
    int ans = 0;
    if (root->data == ID || root->data == INT) {
        ans++;
    }
    if (root->left != NULL) {
        ans += calculate_reg(root->left);
    }
    if (root->right != NULL) {
        ans += calculate_reg(root->right);
    }
    return ans;
}

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

    if (root->left != NULL) {
        if (Exist_Variable(root->left)) {
            return 1;
        }
    } else if (root->right != NULL) {
        if (Exist_Variable(root->right)) {
            return 1;
        }
    }

    return 0;
}

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 not_used() {
    int i;
    for (i = 0; i < 8; i++) {
        if (reg[i][1] == 0) {
            return i;
        }
    }
}

int get_memory_address(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 i * 4;
}

int check_defined(char *str) {
    for (int i = 0; i < sbcount; i++) {
        if (strcmp(table[i].name, str) == 0) {
            return 1;
        }
    }
    return 0;
}

int getval(char *str) { // Get the value of a variable
    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) { // Set the value of a variable
    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) { // Make a new node according to token type and lexeme
    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();
        return retp;

    } else if (match(ID)) {
        retp = makeNode(ID, getLexeme());
        advance();
        return retp;

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

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

// addsub_expr := muldiv_expr addsub_expr_tail
BTNode *addsub_expr(void) {
    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;
    }
}

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

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

// or_expr := xor_expr or_expr_tail
BTNode *or_expr(void) {
    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;
    }
}

// assign_expr := ID ASSIGN assign_expr | or_expr
BTNode *assign_expr(void) {
    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)) {
        advance();
    } else {
        retp = assign_expr();
        if (match(END)) {
            for (int i = 0; i < 8; i++) {
                reg[i][0] = 0;
                reg[i][1] = 0;
            }
            int ans = evaluateTree(retp);
            freeTree(retp);
            advance();
        } else {
            error(SYNTAXERR);
        }
    }
}

void err(ErrorType errorNum) {
    printf("EXIT 1");
    exit(0);
}

/*============================================================================================
codeGen implementation
============================================================================================*/
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 = not_used();
            printf("MOV r%d [%d]\n", nu, get_memory_address(root->lexeme));
            reg[nu][0] = getval(root->lexeme);
            reg[nu][1] = 1;
            return nu;
            break;

        case INT:
            nu = not_used();
            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", get_memory_address(root->left->lexeme), rv);
            setval(root->left->lexeme, reg[rv][0]);
            return rv;
            break;

        case ADDSUB:
            if (calculate_reg(root->left) > calculate_reg(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;
            }
            return lv;
            break;

        case MULDIV:
            if (calculate_reg(root->left) > calculate_reg(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("MUL r%d r%d\n", lv, rv);
                reg[lv][0] *= reg[rv][0];
                reg[rv][0] = 0;
                reg[rv][1] = 0;
                return lv;
            } else if (strcmp(root->lexeme, "/") == 0) {
                if (reg[rv][0] == 0 && Exist_Variable(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 = not_used();
            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", get_memory_address(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", get_memory_address(root->right->lexeme), rv);
                setval(root->right->lexeme, reg[rv][0]);
                return rv;
            }
            break;

        case AND:
            if (calculate_reg(root->left) > calculate_reg(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_reg(root->left) > calculate_reg(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_reg(root->left) > calculate_reg(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
============================================================================================*/

int main() {
    initTable();
    while (1) {
        statement();
    }
    return 0;
}

Raw Text