Mini Project
unknown
plain_text
12 days ago
20 kB
7
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,
LPAREN, RPAREN,
AND, OR, XOR,
INC, DEC,
ADDSUB_ASSIGN
} TokenSet;
TokenSet getToken(void);
TokenSet curToken = UNKNOWN;
char lexeme[MAXLEN];
int inTable(char* str);
// 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) { \
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;
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);
// 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(void);
extern void statement(void);
// Print error message and exit the program
void err(ErrorType errorNum);
// for codeGen
// Evaluate the syntax tree
int evaluateTree(BTNode *root);
// Print the syntax tree in prefix
void printPrefix(BTNode *root);
// Get assembly code of syntax tree
int getAssembly(BTNode *root, int r);
int flag = 0;
/*============================================================================================
lex implementation
============================================================================================*/
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 == '-') {//modify
lexeme[0] = c;
c = fgetc(stdin);
if (c == '+') {
lexeme[1] = c;
lexeme[2] = '\0';
return INC;
} else if (c == '-') {
lexeme[1] = c;
lexeme[2] = '\0';
return DEC;
} else if (c == '=') {
lexeme[1] = c;
lexeme[2] = '\0';
return ADDSUB_ASSIGN;
} else{
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 (isalpha(c)) {
lexeme[0] = c;
c = fgetc(stdin);
i = 1;
while (isalpha(c) && i < MAXLEN) {
lexeme[i] = c;
++i;
c = fgetc(stdin);
}
ungetc(c, stdin);
lexeme[i] = '\0';
return ID;
} else if (c == '&') {//modify
lexeme[0] = c;
lexeme[1] = '\0';
return AND;
} else if (c == '|') {//modify
lexeme[0] = c;
lexeme[1] = '\0';
return OR;
} else if (c == '^') {//modify
lexeme[0] = c;
lexeme[1] = '\0';
return XOR;
} else if (c == EOF) {
return ENDFILE;
} else {
return UNKNOWN;
}
}
int inTable(char* str) {
for (int i = 0;i < sbcount;i++) {
if (strcmp(table[i].name, str) == 0)
return 1;
}
return 0;
}
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;
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);
error(SYNTAXERR);
}
int getidx(char* str) {
int i = 0;
for (i = 0; i < sbcount; i++) {
if (strcmp(str, table[i].name) == 0)
return 4 * i;
}
//printf("getidx : error\n");
error(SYNTAXERR);
return -1;
}
int setval(char *str, int val) {
int i = 0;
//printf("setval : %s , %d\n", str, val);
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 *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(INC)) {
retp = makeNode(INC, getLexeme());
advance();
retp->right = makeNode(INT, "1");
retp->left = factor();
} else if (match(DEC)) {
retp = makeNode(DEC, getLexeme());
advance();
retp->right = makeNode(INT, "1");
retp->left = factor();
} else if (match(LPAREN)) {
advance();
retp = assign_expr();
if (match(RPAREN))
advance();
else
error(MISPAREN);
} else {
error(NOTNUMID);
}
return retp;
}
//BTNode *term(void) {
// BTNode *node = factor();
// return term_tail(node);
//}
//BTNode *term_tail(BTNode *left) {
// BTNode *node = NULL;
//
// if (match(MULDIV)) {
// node = makeNode(MULDIV, getLexeme());
// advance();
// node->left = left;
// node->right = factor();
// return term_tail(node);
// } else {
// return left;
// }
//}
//BTNode *expr(void) {
// BTNode *node = term();
// return expr_tail(node);
//}
//BTNode *expr_tail(BTNode *left) {
// BTNode *node = NULL;
//
// if (match(ADDSUB)) {
// node = makeNode(ADDSUB, getLexeme());
// advance();
// node->left = left;
// node->right = term();
// return expr_tail(node);
// } else {
// return left;
// }
//}
BTNode* unary_expr(void) {
BTNode* node = NULL;
if (match(ADDSUB)) {
node = makeNode(ADDSUB, getLexeme());
advance();
node->left = makeNode(INT, "0");
node->right = unary_expr();
}
else {
node = factor();
}
return node;
}
BTNode* muldiv_expr(void) {
BTNode* node = unary_expr();
return muldiv_expr_tail(node);
}
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;
}
}
BTNode* addsub_expr(void) {
BTNode* node = muldiv_expr();
return addsub_expr_tail(node);
}
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;
}
}
BTNode* and_expr(void) {
BTNode* node = addsub_expr();
return and_expr_tail(node);
}
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;
}
}
BTNode* xor_expr(void) {
BTNode* node = and_expr();
return xor_expr_tail(node);
}
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;
}
}
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;
}
}
BTNode* assign_expr(void) {
BTNode* node = NULL, * left = NULL;
left = or_expr();
if (match(ASSIGN)) {
if (left->data != ID) error(SYNTAXERR);
node = makeNode(ASSIGN, getLexeme());
advance();
node->left = left;
node->right = assign_expr();
}
else if (match(ADDSUB_ASSIGN)) {
if (left->data != ID) error(SYNTAXERR);
node = makeNode(ADDSUB_ASSIGN, getLexeme());
advance();
node->left = left;
node->right = assign_expr();
}
else node = left;
return node;
}
void statement(void) {
BTNode *retp = NULL;
if (match(ENDFILE)) {
printf("MOV r0 [0]\nMOV r1 [4]\nMOV r2 [8]\n");
printf("EXIT 0\n");
exit(0);
} else if (match(END)) {
//printf(">> ");
advance();
} else {
retp = assign_expr();
if (match(END)) {
int k = evaluateTree(retp);
int d = getAssembly(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");
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 getAssembly(BTNode *root, int r) {
if (root != NULL) {
int num, reg1, reg2;
switch (root->data) {
case ID:
printf("MOV r%d [%d]\n", r, getidx(root->lexeme));
break;
case INT:
num = atoi(root->lexeme);
printf("MOV r%d %d\n", r, num);
break;
case ASSIGN:
reg1 = getAssembly(root->right, r);
printf("MOV [%d] r%d\n", getidx(root->left->lexeme), reg1);
break;
case AND:
reg1 = getAssembly(root->left, r);
reg2 = getAssembly(root->right, r + 1);
printf("AND r%d r%d\n", reg1, reg2);
break;
case OR:
reg1 = getAssembly(root->left, r);
reg2 = getAssembly(root->right, r + 1);
printf("OR r%d r%d\n", reg1, reg2);
break;
case XOR:
reg1 = getAssembly(root->left, r);
reg2 = getAssembly(root->right, r + 1);
printf("XOR r%d r%d\n", reg1, reg2);
break;
case INC:
reg1 = getAssembly(root->left, r);
reg2 = getAssembly(root->right, r + 1);
printf("ADD r%d r%d\n", reg1, reg2);
printf("MOV [%d] r%d\n", getidx(root->left->lexeme), r);
break;
case DEC:
reg1 = getAssembly(root->left, r);
reg2 = getAssembly(root->right, r + 1);
printf("SUB r%d r%d\n", reg1, reg2);
printf("MOV [%d] r%d\n", getidx(root->left->lexeme), r);
break;
case ADDSUB_ASSIGN:
if (strcmp(root->lexeme, "+=") == 0) {
reg1 = getAssembly(root->left, r);
reg2 = getAssembly(root->right, r+1);
printf("ADD r%d r%d\n", reg1, reg2);
printf("MOV [%d] r%d\n", getidx(root->left->lexeme), r);
break;
}else if (strcmp(root->lexeme, "-=") == 0) {
reg1 = getAssembly(root->left, r);
reg2 = getAssembly(root->right, r + 1);
printf("SUB r%d r%d\n", reg1, reg2);
printf("MOV [%d] r%d\n", getidx(root->left->lexeme), r);
break;
}
case ADDSUB:
case MULDIV:
if (strcmp(root->lexeme, "+") == 0) {
reg1 = getAssembly(root->left, r);
reg2 = getAssembly(root->right, r + 1);
printf("ADD r%d r%d\n", reg1, reg2);
break;
}else if (strcmp(root->lexeme, "-") == 0) {
reg1 = getAssembly(root->left, r);
reg2 = getAssembly(root->right, r + 1);
printf("SUB r%d r%d\n", reg1, reg2);
break;
}
else if (strcmp(root->lexeme, "*") == 0) {
reg1 = getAssembly(root->left, r);
reg2 = getAssembly(root->right, r + 1);
printf("MUL r%d r%d\n", reg1, reg2);
break;
}
else if (strcmp(root->lexeme, "/") == 0) {
reg1 = getAssembly(root->left, r);
reg2 = getAssembly(root->right, r + 1);
printf("DIV r%d r%d\n", reg1, reg2);
break;
}
default:
r = 0;
}
}
return r;
}
int evaluateTree(BTNode *root) {
int retval = 0, lv = 0, rv = 0;
if (root != NULL) {
switch (root->data) {
case ID:
flag = 1;
retval = getval(root->lexeme);
break;
case INT:
retval = atoi(root->lexeme);
break;
case ASSIGN:
flag = 1;
rv = evaluateTree(root->right);
retval = setval(root->left->lexeme, rv);
break;
case AND:
lv = evaluateTree(root->left);
rv = evaluateTree(root->right);
retval = lv & rv;
break;
case OR:
lv = evaluateTree(root->left);
rv = evaluateTree(root->right);
retval = lv | rv;
break;
case XOR:
lv = evaluateTree(root->left);
rv = evaluateTree(root->right);
retval = lv ^ rv;
break;
case INC:
flag = 1;
rv = evaluateTree(root->right);
retval = rv + 1;
break;
case DEC:
flag = 1;
rv = evaluateTree(root->right);
retval = rv - 1;
break;
case ADDSUB_ASSIGN:
lv = evaluateTree(root->left);
rv = evaluateTree(root->right);
retval = setval(root->left->lexeme, lv+rv);
break;
case ADDSUB:
case MULDIV:
lv = evaluateTree(root->left);
flag = 0;
rv = evaluateTree(root->right);
if (strcmp(root->lexeme, "+") == 0) {
retval = lv + rv;
} else if (strcmp(root->lexeme, "-") == 0) {
retval = lv - rv;
} else if (strcmp(root->lexeme, "*") == 0) {
retval = lv * rv;
} else if (strcmp(root->lexeme, "/") == 0) {
if (rv == 0){
//printf("flag : %d\n", flag);
if (flag) break;
else error(DIVZERO);
}else{
retval = lv / rv;
}
}
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...
Leave a Comment