Infinity Calculator implementation for Assignment 2 in Computer Organization.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 

299 lines
6.9 KiB

#include "parse.h"
long fromhex(const char *s) {
char c = *s & ~(0x20);
if (c >= 'A') return c - 'A' + 10;
return c - '0';
}
expr_t *parse_hex_int() {
const char *ptr = token_str + 2; // Skip the initial "0x" part
expr_t *num = malloc(sizeof(expr_t));
num->opcode = EXPR_NULL;
num->flags = num->left.data = 0;
num->par = NULL;
num->right.data = fromhex(ptr);
for (int d = 0; d < 16; ++d) {
ptr++;
if (ptr == input_str) {
return num;
}
num->right.data = num->right.data * 16 + fromhex(ptr);
}
ptr++;
while(ptr != input_str) {
expr_t *more_num = malloc(sizeof(expr_t));
more_num->opcode = EXPR_CONCAT;
more_num->flags = EXFLAG_MOD | EXFLAG_HEX;
more_num->left.data = 0;
more_num->right.data = *ptr - '0';
for (int d = 0; d < 16; ++d) {
ptr++;
if (ptr == input_str) {
return bubble_expr(num, more_num);
}
more_num->right.data = more_num->right.data * 16 + fromhex(ptr);
}
ptr++;
num = bubble_expr(num, more_num);
}
return num;
}
expr_t *parse_decimal_int() {
const char *ptr = input_str - 1;
expr_t *num = malloc(sizeof(expr_t));
num->opcode = EXPR_NULL;
num->flags = num->left.data = 0;
num->par = NULL;
num->right.data = *ptr - '0';
ptr--;
if (ptr < token_str) return num;
num->right.data = num->right.data + 10 * (*ptr - '0');
ptr--;
while(ptr >= token_str) {
expr_t *more_num = malloc(sizeof(expr_t));
more_num->opcode = EXPR_CONCAT;
more_num->flags = EXFLAG_MOD;
more_num->left.data = 0;
more_num->right.data = *ptr - '0';
ptr--;
if (ptr < token_str) return bubble_expr(num, more_num);
more_num->right.data = more_num->right.data + 10 * (*ptr - '0');
ptr--;
num = bubble_expr(num, more_num);
}
return num;
}
expr_t *parse_operation(int opcode) {
expr_t *num_expr;
switch (tokenize()) {
case TOK_NULL:
fprintf(stderr, "Expected expression, found end of data.\n");
return NULL;
case TOK_ERR:
fprintf(stderr, "Invalid token \"%c\".\n", *token_str);
return NULL;
case TOK_NUMDEC:
num_expr = parse_decimal_int();
break;
case TOK_NUMHEX:
num_expr = parse_hex_int();
num_expr->flags |= num_expr->opcode ? EXFLAG_PAREN : 0;
break;
case TOK_LPAREN:
num_expr = parse(1);
num_expr->flags |= EXFLAG_PAREN;
break;
case TOK_RPAREN:
fprintf(stderr, "Expected expression, found \"(\".\n");
return NULL;
case TOK_MINUS: ;
token_t t = tokenize();
if (t == TOK_NUMDEC) {
num_expr = parse_decimal_int();
num_expr->flags |= EXFLAG_RNEG;
break;
}
else if (t == TOK_NUMHEX) {
num_expr = parse_hex_int();
num_expr->flags |= EXFLAG_RNEG;
break;
}
case TOK_PLUS:
case TOK_STAR:
case TOK_FSLASH:
case TOK_CARROT:
fprintf(stderr, "Expected expression, found operator.\n");
return NULL;
}
if (num_expr->opcode) {
expr_t *add_expr = malloc(sizeof(expr_t));
add_expr->opcode = opcode;
add_expr->par = NULL;
add_expr->left.data = 0;
add_expr->flags = EXFLAG_REXP;
add_expr->right.expr = num_expr;
num_expr->flags |= EXFLAG_PAREN;
return add_expr;
}
else {
num_expr->opcode = opcode;
return num_expr;
}
}
expr_t *parse(char expect_rparen) {
expr_t *expr_tree;
// Construct initial expression.
switch (tokenize()) {
case TOK_NULL:
fprintf(stderr, "Expected expression, found end of data.\n");
return NULL;
case TOK_ERR:
fprintf(stderr, "Invalid token \"%c\".\n", *token_str);
return NULL;
case TOK_NUMDEC:
expr_tree = parse_decimal_int();
expr_tree->flags |= expr_tree->opcode ? EXFLAG_PAREN : 0;
break;
case TOK_NUMHEX:
expr_tree = parse_hex_int();
expr_tree->flags |= expr_tree->opcode ? EXFLAG_PAREN : 0;
break;
case TOK_LPAREN:
expr_tree = parse(1);
expr_tree->flags |= EXFLAG_PAREN;
break;
case TOK_RPAREN:
fprintf(stderr, "Expected expression, found \")\".\n");
return NULL;
case TOK_MINUS: ;
token_t t = tokenize();
if (t == TOK_NUMDEC) {
expr_tree = parse_decimal_int();
expr_tree->flags |= EXFLAG_RNEG;
break;
}
else if (t == TOK_NUMHEX) {
expr_tree = parse_hex_int();
expr_tree->flags |= EXFLAG_RNEG;
break;
}
case TOK_PLUS:
case TOK_STAR:
case TOK_FSLASH:
case TOK_CARROT:
fprintf(stderr, "Expected expression, found operator.\n");
return NULL;
}
// Continual construction of the expression tree.
while (1) {
switch (tokenize()) {
case TOK_NULL:
if (expect_rparen) {
fprintf(stderr, "Expected \")\", found end of data.\n");
destroy_expr(expr_tree);
return NULL;
}
else {
return expr_tree;
}
case TOK_ERR:
fprintf(stderr, "Invalid token \"%c\".\n", *token_str);
destroy_expr(expr_tree);
return NULL;
case TOK_NUMDEC:
case TOK_NUMHEX:
fprintf(stderr, "Expected operator, found number.\n");
destroy_expr(expr_tree);
return NULL;
case TOK_LPAREN:
fprintf(stderr, "Expected operator, found \"(\".\n");
destroy_expr(expr_tree);
return NULL;
case TOK_RPAREN:
if (expect_rparen) {
expr_tree->flags |= expr_tree->opcode ? EXFLAG_PAREN : 0;
return expr_tree;
}
else {
fprintf(stderr, "Expected operator, found \")\".\n");
destroy_expr(expr_tree);
return NULL;
}
case TOK_PLUS: ;
expr_t *a = parse_operation(EXPR_ADD);
if (a) {
expr_tree = bubble_expr(expr_tree, a);
}
else {
destroy_expr(expr_tree);
return NULL;
}
break;
case TOK_MINUS: ;
expr_t *s = parse_operation(EXPR_SUB);
if (s) {
s->flags ^= EXFLAG_RNEG;
expr_tree = bubble_expr(expr_tree, s);
}
else {
destroy_expr(expr_tree);
return NULL;
}
break;
case TOK_STAR: ;
expr_t *m = parse_operation(EXPR_MULT);
if (m) {
expr_tree = bubble_expr(expr_tree, m);
}
else {
destroy_expr(expr_tree);
return NULL;
}
break;
case TOK_FSLASH: ;
expr_t *d = parse_operation(EXPR_DIV);
if (d) {
d->flags |= EXFLAG_MOD;
expr_tree = bubble_expr(expr_tree, d);
}
else {
destroy_expr(expr_tree);
return NULL;
}
break;
case TOK_CARROT: ;
expr_t *ex = parse_operation(EXPR_IPOW);
if (ex) {
expr_tree = bubble_expr(expr_tree, ex);
}
else {
destroy_expr(expr_tree);
return NULL;
}
break;
}
}
}
#ifdef UNIT_TESTS
void test_expr_and_parse() {
const char *test_input = "15^2*6000+20-400/2\0";
input_str = test_input;
expr_t *e = parse(0);
assert(e->flags == 0x3);
assert(e->left.expr->flags == 0x3);
assert(e->left.expr->left.expr->flags == 0);
assert(e->left.expr->left.expr->left.data == 15);
assert(e->left.expr->left.expr->right.data == 2);
assert(e->left.expr->right.expr->flags == 0x30);
assert(e->left.expr->right.expr->left.data == 0);
assert(e->left.expr->right.expr->right.data == 60);
assert(e->right.expr->flags == 0xA);
assert(e->right.expr->left.data == 20);
assert(e->right.expr->right.expr->flags == 0x21);
assert(e->right.expr->right.expr->left.expr->flags == 0x30);
assert(e->right.expr->right.expr->left.expr->left.data == 0);
assert(e->right.expr->right.expr->left.expr->right.data == 4);
assert(e->right.expr->right.expr->right.data == 2);
destroy_expr(e);
}
#endif