Untitled
unknown
c_cpp
2 years ago
20 kB
6
Indexable
#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, LPAREN, RPAREN, INCDEC, AND, OR, XOR } 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) err(errorNum); // Error types typedef enum { UNDEFINED, MISPAREN, NOTNUMID, NOTFOUND, RUNOUT, NOTLVAL, DIVZERO, SYNTAXERR } ErrorType; // Structure of the symbol table typedef struct { int val, addr; 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, int address); int getadd(char *str); // 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 *term(void); // extern BTNode *term_tail(BTNode *left); // extern BTNode *expr(void); // extern BTNode *expr_tail(BTNode *left); void statement(void); BTNode* assign_expr(void); BTNode* or_expr(void); BTNode* or_expr_tail(BTNode *left); BTNode* xor_expr(void); BTNode* xor_expr_tail(BTNode *left); BTNode* and_expr(void); BTNode* and_expr_tail(BTNode *left); BTNode* addsub_expr(void); BTNode* addsub_expr_tail(BTNode *left); BTNode* muldiv_expr(void); BTNode* muldiv_expr_tail(BTNode *left); BTNode* unary_expr(void); // Print error message and exit the program void err(ErrorType errorNum); // for codeGen // Evaluate the syntax tree int evaluateTree(BTNode *root, int reg); // Print the syntax tree in prefix void printPrefix(BTNode *root); int add; /*============================================================================================ lex implementation ============================================================================================*/ TokenSet getToken(void) { int i = 0; char c = '\0'; while ((c = fgetc(stdin)) == ' ' || c == '\t'); //printf("%c\n", c); 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 == '-') { int cnt = 0; lexeme[0] = c, lexeme[1] = '\0'; c = fgetc(stdin); if(c == lexeme[0]){ lexeme[1] = c, lexeme[2] = '\0'; //ungetc(c, stdin); return INCDEC; } if(c == '='){ lexeme[1] = '=', lexeme[2] = '\0'; //ungetc(c, stdin); 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 == '&'){ lexeme[0] = '&', lexeme[1] = '\0'; return AND; } else if(c == '|'){ lexeme[0] = '|', lexeme[1] = '\0'; return OR; } else if(c == '^'){ lexeme[0] = '^', lexeme[1] = '\0'; return XOR; } else if (c == '_' || isalpha(c)) { lexeme[0] = c, lexeme[1] = '\0'; 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 { 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; table[0].addr = 0; strcpy(table[1].name, "y"); table[1].val = 0; table[1].addr = 4; strcpy(table[2].name, "z"); table[2].val = 0; table[2].addr = 8; sbcount = 3; add = 12; } int getval(char *str) { int i = 0; for (i = 0; i < sbcount; i++) if (strcmp(str, table[i].name) == 0) return table[i].val; error(NOTLVAL); if (sbcount >= TBLSIZE) error(RUNOUT); //error(NOTLVAL); strcpy(table[sbcount].name, str); table[sbcount].val = 0; sbcount++; return 0; } int getadd(char *str){ int i = 0; for (i = 0; i < sbcount; i++){ if (strcmp(str, table[i].name) == 0) return table[i].addr; } error(NOTLVAL); if (sbcount >= TBLSIZE) error(RUNOUT); //error(NOTLVAL); return 0; } int setval(char *str, int val, int address) { 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; table[sbcount].addr = address; 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 | ADDSUB INT | // ID | ADDSUB ID | // ID ASSIGN expr | // LPAREN expr RPAREN | // ADDSUB LPAREN expr RPAREN 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 = expr(); // } } else if (match(INCDEC)) { retp = makeNode(INCDEC, getLexeme()); retp->left = makeNode(INT, "0"); advance(); if(match(ID)) retp -> right = makeNode(ID, getLexeme()); else error(SYNTAXERR); advance(); } else if (match(LPAREN)) { advance(); retp = assign_expr(); if (match(RPAREN)) advance(); else error(MISPAREN); } else { printf("%d\n", curToken); error(NOTNUMID); } return retp; } // or_expr := xor_expr or_expr_tail BTNode *or_expr(void){ BTNode *node = xor_expr(); return or_expr_tail(node); } 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(void){ BTNode *node = and_expr(); return xor_expr_tail(node); } //xor_expr_tail := XOR and_expr xor_expr_tail 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(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; } } //addsub_expr := muldiv_expr addsub_expr_tail BTNode *addsub_expr(void){ BTNode *node = muldiv_expr(); return addsub_expr_tail(node); } //adddsub_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(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; } } //unary_expr := ADDSUB unary_expr | factor BTNode *unary_expr(void){ BTNode *mid; if( !match(ADDSUB) ) return factor(); mid = makeNode(ADDSUB, getLexeme()); advance(); mid -> right = unary_expr(); mid -> left = makeNode(INT, "0"); return mid; } //assign_expr := ID ASSIGN assign_expr | ID ADDSUB_ASSIGN assign_expr | or_expr BTNode *assign_expr(void){ BTNode *mid, *r, *l; l = or_expr(); if(match(ASSIGN) || match(ADDSUB_ASSIGN)){ if(l -> data != ID){ error(SYNTAXERR); } if(match(ASSIGN)) mid = makeNode(ASSIGN, getLexeme()); else mid = makeNode(ADDSUB_ASSIGN, getLexeme()); advance(); r = assign_expr(); mid -> left = l, mid -> right = r; return mid; } return l; } // statement := ENDFILE | END | assign_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)) { int ans = evaluateTree(retp, 0); // printf("Prefix traversal: "); // printPrefix(retp); // printf("\n"); freeTree(retp); //printf(">> "); advance(); } else { error(SYNTAXERR); } } } void err(ErrorType errorNum) { if (PRINTERR) { printf("EXIT 1\n"); exit(0); 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; } } exit(0); } /*============================================================================================ codeGen implementation ============================================================================================*/ int evaluateTree(BTNode *root, int reg) { int retval = 0, lv = 0, rv = 0; if (root != NULL) { switch (root->data) { case ID: retval = getval(root->lexeme); //printf("%s %d\n", root -> lexeme, reg); printf("MOV r%d [%d]\n", reg, getadd(root -> lexeme)); break; case INT: retval = atoi(root -> lexeme); //retval = setval(root -> lexeme, root -> val, -1); printf("MOV r%d %d\n", reg, retval); break; case ADDSUB_ASSIGN : lv = evaluateTree(root -> left, reg); rv = evaluateTree(root->right, reg + 1); if( !strcmp(root -> lexeme, "+=") ){ retval = setval(root->left->lexeme, lv + rv, -1); printf("ADD r%d r%d\n", reg, reg + 1); } else if( !strcmp(root -> lexeme, "-=")){ retval = setval(root -> left -> lexeme, lv - rv, -1); printf("SUB r%d r%d\n", reg, reg + 1); } printf("MOV [%d] r%d\n", getadd(root -> left -> lexeme), reg); //printf("end%d\n", reg); break; case ASSIGN: rv = evaluateTree(root->right, reg); int x = strcmp(root -> left -> lexeme, "x"); int y = strcmp(root -> left -> lexeme, "y"); int z = strcmp(root -> left -> lexeme, "z"); if(!x || !y || !z){ //printf("%s\n", root -> left -> lexeme); retval = setval(root->left->lexeme, rv, -1); //printf("%s %d\n", root -> left -> lexeme, getadd(root -> left -> lexeme)); }else{ //printf("%s add %d\n", root -> left -> lexeme, add); retval = setval(root->left->lexeme, rv, add); add += 4; } printf("MOV [%d] r%d\n", getadd(root -> left -> lexeme), reg); break; case ADDSUB: case MULDIV: lv = evaluateTree(root->left, reg); rv = evaluateTree(root->right, reg + 1); if (strcmp(root->lexeme, "+") == 0) { retval = lv + rv; printf("ADD"); } else if (strcmp(root->lexeme, "-") == 0) { retval = lv - rv; printf("SUB"); } else if (strcmp(root->lexeme, "*") == 0) { retval = lv * rv; printf("MUL"); } else if (strcmp(root->lexeme, "/") == 0) { if (rv == 0) error(DIVZERO); retval = lv / rv; printf("DIV"); } printf(" r%d r%d\n", reg, reg + 1); break; case INCDEC : rv = evaluateTree(root -> right, reg); printf("MOV r%d 1\n", reg + 1); if(!strcmp(root -> lexeme, "--")){ retval = setval(root->right->lexeme, rv - 1, -1); printf("SUB"); } else if(!strcmp(root -> lexeme, "++")){ retval = setval(root->right->lexeme, rv + 1, -1); printf("ADD"); } printf(" r%d r%d\n", reg, reg + 1); printf("MOV [%d] r%d\n", getadd(root -> right -> lexeme), reg); break; case AND : lv = evaluateTree(root -> left, reg); rv = evaluateTree(root -> right, reg + 1); retval = (lv & rv); printf("AND r%d r%d\n", reg, reg + 1); break; case OR : lv = evaluateTree(root -> left, reg); rv = evaluateTree(root -> right, reg + 1); retval = (lv | rv); printf("OR r%d r%d\n", reg, reg + 1); break; case XOR : lv = evaluateTree(root -> left, reg); rv = evaluateTree(root -> right, reg + 1); retval = (lv ^ rv); printf("XOR r%d r%d\n", reg, reg + 1); break; default: retval = 0; } } return retval; } void printPrefix(BTNode *root) { if (root != NULL) { printf("%s ", root->lexeme); printPrefix(root->left); printPrefix(root->right); } } /*============================================================================================ main ============================================================================================*/ // This package is a calculator // It works like a Python interpretor // Example: // >> y = 2 // >> z = 2 // >> x = 3 * y + 4 / (2 * z) // It will print the answer of every line // You should turn it into an expression compiler // And print the assembly code according to the input // This is the grammar used in this package // You can modify it according to the spec and the slide // statement := ENDFILE | END | expr END // expr := term expr_tail // expr_tail := ADDSUB term expr_tail | NiL // term := factor term_tail // term_tail := MULDIV factor term_tail| NiL // factor := INT | ADDSUB INT | // ID | ADDSUB ID | // ID ASSIGN expr | // LPAREN expr RPAREN | // ADDSUB LPAREN expr RPAREN int main() { initTable(); //printf(">> "); while (1) { statement(); } return 0; }
Editor is loading...