Untitled
unknown
c_cpp
2 years ago
22 kB
3
Indexable
#define MAXLEN 256 // Token types typedef enum { UNKNOWN, END, ENDFILE, INT, ID, ADDSUB, MULDIV, ASSIGN, LPAREN, RPAREN, /*I add*/ INCDEC, AND, OR, XOR, ADDSUB_ASSIGN, } 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); #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 0 // 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); // 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(BTNode* tmp); //extern BTNode *term(void); //extern BTNode *term_tail(BTNode *left); extern BTNode *assign_expr(void); extern BTNode *assign_expr_tail(BTNode *left, BTNode* tmp); extern BTNode* and_expr(BTNode* tmp); extern BTNode* and_expr_tail(BTNode* left, BTNode* tmp); extern BTNode* or_expr(BTNode* tmp); extern BTNode* or_expr_tail(BTNode* left, BTNode* tmp); extern BTNode* xor_expr(BTNode* tmp); extern BTNode* xor_expr_tail(BTNode* left, BTNode* tmp); extern BTNode* addsub_expr(BTNode* tmp); extern BTNode* addsub_expr_tail(BTNode* left, BTNode* tmp); extern BTNode* muldiv_expr(BTNode* tmp); extern BTNode* muldiv_expr_tail(BTNode* left, BTNode* tmp); extern void statement(void); // Print error message and exit the program extern void err(ErrorType errorNum); // Evaluate the syntax tree extern int evaluateTree(BTNode *root); // Print the syntax tree in prefix extern void printPrefix(BTNode *root); #include <stdio.h> #include <string.h> #include <ctype.h> static TokenSet getToken(void); static TokenSet curToken = UNKNOWN; extern 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); } ungetc(c, stdin); lexeme[i] = '\0'; return INT; } else if (c == '+' || c == '-') { lexeme[0] = c; char cnext = fgetc(stdin); // I add if((c == '+' && cnext =='+') || (c == '-' && cnext == '-')){ lexeme[1] = c; lexeme[2] = '\0'; return INCDEC; } else if (cnext == '='){ lexeme[1]=cnext; lexeme[2]='\0'; return ADDSUB_ASSIGN; } else{ ungetc(cnext, 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 (('A'<=c && c<='Z') || ('a'<=c && c<='z') || c=='_') { // I add lexeme[0] = c; c = fgetc(stdin); i = 1; while ((('A'<=c && c<='Z') || ('a'<=c && c<='z') || c == '_' || isdigit(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 == '&'){ // I add 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; } #include <stdio.h> #include <stdlib.h> #include <string.h> int err_flag; int reg[8]; int check_begin; int divide_by_zero; static int Flag = 0; int sbcount = 0; extern Symbol table[TBLSIZE]; char lexeme[MAXLEN]; 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); } else { error(NOTFOUND); // undefined variable } 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* and_expr(BTNode* tmp) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); node = addsub_expr(tmp); return and_expr_tail(node, tmp); } BTNode* and_expr_tail(BTNode* left, BTNode* tmp) { BTNode* node = NULL; if(match(AND)){ node = makeNode(AND, getLexeme()); advance(); node->left = left; node->right = addsub_expr(tmp); return and_expr_tail(node, tmp); } else { return left; } } BTNode* or_expr(BTNode* tmp) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); node = xor_expr(tmp); return or_expr_tail(node, tmp); } BTNode* or_expr_tail(BTNode* left, BTNode* tmp) { BTNode* node = NULL; if(match(OR)){ node = makeNode(OR, getLexeme()); advance(); node->left = left; node->right = xor_expr(tmp); return or_expr_tail(node, tmp); } else { return left; } } BTNode* xor_expr(BTNode* tmp) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); node = and_expr(tmp); return xor_expr_tail(node, tmp); } BTNode* xor_expr_tail(BTNode* left, BTNode* tmp) { BTNode* node = NULL; if(match(XOR)){ node = makeNode(XOR, getLexeme()); advance(); node->left = left; node->right = and_expr(tmp); return xor_expr_tail(node, tmp); } else { return left; } } BTNode* addsub_expr(BTNode* tmp) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); node = muldiv_expr(tmp); return addsub_expr_tail(node, tmp); } BTNode* addsub_expr_tail(BTNode* left, BTNode* tmp) { BTNode* node = NULL; if(match(ADDSUB)){ // deal with 2 addsub node = makeNode(ADDSUB, getLexeme()); advance(); node->left = left; node->right = muldiv_expr(tmp); return addsub_expr_tail(node, tmp); } else { return left; } } BTNode* unary_expr(BTNode* tmp) { BTNode *retp = NULL, *left=NULL; if(match(ADDSUB) && !Flag){ retp = makeNode(ADDSUB, getLexeme()); advance(); retp->left = makeNode(INT, "0"); retp->right = unary_expr(tmp); //advance(); } else { retp=factor(tmp); } return retp; } BTNode* muldiv_expr(BTNode* tmp) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); node = unary_expr(tmp); return muldiv_expr_tail(node, tmp); } BTNode* muldiv_expr_tail(BTNode* left, BTNode* tmp) { BTNode* node = NULL; if(match(MULDIV)){ node = makeNode(MULDIV, getLexeme()); advance(); node->left = left; node->right = unary_expr(tmp); return muldiv_expr_tail(node, tmp); } else { return left; } } // + + x ??? // factor := INT | ADDSUB INT | // ID | ADDSUB ID | // ID ASSIGN expr | // LPAREN expr RPAREN | // ADDSUB LPAREN expr RPAREN BTNode *factor(BTNode* tmp) { BTNode *retp = NULL, *left = NULL; if(Flag) { retp = tmp; Flag = 0; } else 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()); retp->left = makeNode(INT, "0"); advance(); if (match(ID)) { retp->right = makeNode(ID, getLexeme()); advance(); } else if (match(LPAREN)) { advance(); if(match(ID)){ retp->right = makeNode(ID, getLexeme()); advance(); if(match(RPAREN)) advance(); else error(MISPAREN); // modify } } else { error(NOTNUMID); } } else if (match(LPAREN)) { advance(); retp = assign_expr(); if (match(RPAREN)) advance(); else error(MISPAREN); } else { error(NOTNUMID); } return retp; } // assign_expr := ID ASSIGN assign_expr // | ID ADDSUB_ASSIGN assign_expr // | or_expr BTNode *assign_expr(void) { BTNode *retp = NULL, *left = NULL; if(match(ID)) { left = makeNode(ID, getLexeme()); advance(); if (match(ASSIGN)) { retp = makeNode(ASSIGN, getLexeme()); advance(); retp->left = left; retp->right = assign_expr(); } else if(match(ADDSUB_ASSIGN)) { retp = makeNode(ADDSUB_ASSIGN, getLexeme()); advance(); retp->left = left; retp->right = assign_expr(); } else { Flag = 1; retp = or_expr(left); } } else { retp = or_expr(NULL); } return retp; } // statement := ENDFILE | END | expr END void statement(void) { err_flag = 0; check_begin = 0; divide_by_zero = 0; for(int i = 0; i < 8; i++) reg[i] = 0; 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)) { if(!err_flag) evaluateTree(retp); else { printf("EXIT 1\n"); exit(0); } //printf("%d\n", evaluateTree(retp)); //printf("Prefix traversal: "); //printPrefix(retp); //printf("\n"); freeTree(retp); //printf(">> "); advance(); } else { error(SYNTAXERR); } } } void err(ErrorType errorNum) { printf("EXIT 1\n"); 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; } } exit(0); } #include <stdio.h> #include <stdlib.h> #include <string.h> int n; int divide_by_zero; extern int reg[8]; extern int sbcount; Symbol table[TBLSIZE]; void check(BTNode *root) { if(root){ if(root->data==ID) n = 1; check(root->right); check(root->left); } } int evaluateTree(BTNode *root) { int retval = 0, lv = 0, rv = 0, i, j; if (root != NULL) { switch (root->data) { case ID: retval = getval(root->lexeme); for(i=0; i<8; i++){ if(!reg[i]){ reg[i]=1; break; } } for(j=0; j<sbcount; j++) if(!strcmp(root->lexeme, table[j].name)) break; printf("MOV r%d [%d]\n", i, 4*j); break; case INT: retval = atoi(root->lexeme); for(i=0; i<8; i++){ if(!reg[i]){ reg[i]=1; break; } } printf("MOV r%d %d\n", i, retval); break; case ASSIGN: // problem ??? rv = evaluateTree(root->right); retval = setval(root->left->lexeme, rv); for(i=7; i>=0; i--){ if(reg[i]){ break; } } if(i==-1) i=0; for(j=0; j<sbcount; j++) if(!strcmp(root->left->lexeme, table[j].name)) break; printf("MOV [%d] r%d\n", 4*j, i); break; case ADDSUB: case MULDIV: if (strcmp(root->lexeme, "+") == 0) { lv = evaluateTree(root->left); rv = evaluateTree(root->right); retval = lv + rv; for(i=7; i>=0; i--){ if(reg[i]){ reg[i]=0; break; } } printf("ADD r%d r%d\n", i-1, i); } else if (strcmp(root->lexeme, "-") == 0) { lv = evaluateTree(root->left); rv = evaluateTree(root->right); retval = lv - rv; for(i=7; i>=0; i--){ if(reg[i]){ reg[i]=0; break; } } printf("SUB r%d r%d\n", i-1, i); } else if (strcmp(root->lexeme, "*") == 0) { lv = evaluateTree(root->left); rv = evaluateTree(root->right); retval = lv * rv; for(i=7; i>=0; i--){ if(reg[i]){ reg[i]=0; break; } } printf("MUL r%d r%d\n", i-1, i); } else if (strcmp(root->lexeme, "/") == 0) { rv = evaluateTree(root->right); n = 0; check(root->right); if(rv == 0 && !n) err(DIVZERO); else if(rv==0) rv=1; lv = evaluateTree(root->left); retval = lv / rv; for(i=7; i>=0; i--){ if(reg[i]){ reg[i]=0; break; } } printf("DIV r%d r%d\n", i, i-1); printf("MOV r%d r%d\n", i-1, i); } break; case INCDEC: rv = evaluateTree(root->right); rv = (!strcmp(root->lexeme, "++"))?(rv+1):(rv-1); setval(root->right->lexeme, rv); retval = rv; for(i=0; i<8; i++){ if(!reg[i]){ reg[i]=1; break; } } printf("MOV r%d 1\n", i); for(j=0; j<sbcount; j++) if(!strcmp(root->right->lexeme, table[j].name)) break; if(!strcmp(root->lexeme, "++")) printf("ADD r%d r%d\n", i-1, i); else printf("SUB r%d r%d\n", i-1, i); printf("MOV [%d] r%d\n", 4*j, i-1); reg[i]=0; break; case AND: lv = evaluateTree(root->left); rv = evaluateTree(root->right); retval = lv & rv; for(i=7; i>=0; i--){ if(reg[i]){ reg[i]=0; break; } } printf("AND r%d r%d\n", i-1, i); break; case OR: lv = evaluateTree(root->left); rv = evaluateTree(root->right); retval = lv | rv; for(i=7; i>=0; i--){ if(reg[i]){ reg[i]=0; break; } } printf("OR r%d r%d\n", i-1, i); break; case XOR: lv = evaluateTree(root->left); rv = evaluateTree(root->right); retval = lv ^ rv; for(i=7; i>=0; i--){ if(reg[i]){ reg[i]=0; break; } } printf("XOR r%d r%d\n", i-1, i); break; case ADDSUB_ASSIGN: lv = evaluateTree(root->left); rv = evaluateTree(root->right); retval = (!strcmp(root->lexeme, "+="))?(lv+rv):(lv-rv); setval(root->left->lexeme, retval); for(i=7; i>=0; i--){ if(reg[i]){ break; } } for(j=0; j<sbcount; j++) if(!strcmp(root->left->lexeme, table[j].name)) break; if(!strcmp(root->lexeme, "+=")) printf("ADD r%d r%d\n", i-1, i); else printf("SUB r%d r%d\n", i-1, i); printf("MOV [%d] r%d\n", 4*j, i-1); reg[i]=0; break; default: retval = 0; } } return retval; } void printPrefix(BTNode *root) { if (root != NULL) { printf("%s ", root->lexeme); printPrefix(root->left); printPrefix(root->right); } } #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> // 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() { //freopen("input.txt", "w", stdout); initTable(); //printf(">> "); while (1) { statement(); } return 0; }
Editor is loading...