From eb0bde2d4dc1bdb6653ee216764c373066222b79 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Wed, 4 Nov 2009 22:19:29 -0500 Subject: Parse arithmetic expressions. --- dimension/parse.c | 291 ++++++++++++++++++++++++++++++++++++++--------- dimension/parse.h | 5 + dimension/realize.c | 43 +++++-- tests/dimension/demo.pov | 4 +- tests/dimension/demo.sh | 4 +- 5 files changed, 280 insertions(+), 67 deletions(-) diff --git a/dimension/parse.c b/dimension/parse.c index 51203c5..25d983c 100644 --- a/dimension/parse.c +++ b/dimension/parse.c @@ -50,8 +50,8 @@ dmnsn_parse_expect(dmnsn_token_type type, const dmnsn_array *tokens, } static int -dmnsn_parse_float(const dmnsn_array *tokens, unsigned int *ip, - dmnsn_array *astree) +dmnsn_parse_number(const dmnsn_array *tokens, unsigned int *ip, + dmnsn_array *astree) { unsigned int i = *ip; @@ -62,55 +62,233 @@ dmnsn_parse_float(const dmnsn_array *tokens, unsigned int *ip, return 1; } - int negative = 0; dmnsn_token token; dmnsn_array_get(tokens, i, &token); - if (token.type == DMNSN_T_MINUS) { - negative = 1; + dmnsn_astnode astnode; + astnode.children = NULL; + + if (token.type == DMNSN_T_INTEGER) { + astnode.type = DMNSN_AST_INTEGER; + long *value = malloc(sizeof(double)); + if (!value) + dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate room for integer."); + + *value = strtol(token.value, NULL, 0); + astnode.ptr = value; ++i; - if (i >= dmnsn_array_size(tokens)) { - fprintf(stderr, "Expected '%s' or '%s', found end of file\n", - dmnsn_token_string(DMNSN_T_INTEGER), - dmnsn_token_string(DMNSN_T_FLOAT)); - return 1; - } - dmnsn_array_get(tokens, i, &token); - } + } else if (token.type == DMNSN_T_FLOAT) { + astnode.type = DMNSN_AST_FLOAT; - double *value = malloc(sizeof(double)); - if (!value) - dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate room for float."); + double *value = malloc(sizeof(double)); + if (!value) + dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate room for float."); - if (token.type == DMNSN_T_INTEGER || token.type == DMNSN_T_FLOAT) { *value = strtod(token.value, NULL); + astnode.ptr = value; ++i; } else { - fprintf(stderr, "Expected '%s' or '%s', found '%s'\n", - dmnsn_token_string(DMNSN_T_INTEGER), - dmnsn_token_string(DMNSN_T_FLOAT), - dmnsn_token_string(token.type)); + dmnsn_diagnostic(token.filename, token.line, token.col, + "Expected '%s' or '%s', found '%s'", + dmnsn_token_string(DMNSN_T_INTEGER), + dmnsn_token_string(DMNSN_T_FLOAT), + dmnsn_token_string(token.type)); + goto bailout; + } + + dmnsn_array_push(astree, &astnode); + *ip = i; + return 0; + + bailout: + dmnsn_delete_astree(astnode.children); + return 1; +} + +static dmnsn_astnode_type +dmnsn_op_map(dmnsn_token_type type) +{ + switch (type) { + case DMNSN_T_PLUS: + return DMNSN_AST_ADD; + + case DMNSN_T_MINUS: + return DMNSN_AST_SUB; + + case DMNSN_T_STAR: + return DMNSN_AST_MUL; + + case DMNSN_T_SLASH: + return DMNSN_AST_DIV; + + default: + dmnsn_error(DMNSN_SEVERITY_HIGH, "Invalid token mapped to operator."); + return 0; /* Silence compiler warning */ + } +} + +static int +dmnsn_op_precedence(dmnsn_astnode_type type) +{ + switch(type) { + case DMNSN_AST_ADD: + case DMNSN_AST_SUB: + return 0; + + case DMNSN_AST_MUL: + case DMNSN_AST_DIV: return 1; + + default: + dmnsn_error(DMNSN_SEVERITY_HIGH, + "Precedence asked of invalid operator."); + return 0; /* Silence compiler warning */ } +} - if (negative) - *value *= -1.0; +static int dmnsn_parse_arithexp(const dmnsn_array *tokens, unsigned int *ip, + dmnsn_array *astree); - dmnsn_astnode astnode; - astnode.type = DMNSN_AST_FLOAT; - astnode.children = NULL; - astnode.ptr = value; +static int +dmnsn_parse_arithexp(const dmnsn_array *tokens, unsigned int *ip, + dmnsn_array *astree) +{ + dmnsn_token token; + unsigned int i = *ip; - dmnsn_array_push(astree, &astnode); + if (i >= dmnsn_array_size(tokens)) { + fprintf(stderr, "Expected arithmetic expression, found end of file\n"); + return 1; + } + + dmnsn_array *numstack = dmnsn_new_array(sizeof(dmnsn_astnode)), + *opstack = dmnsn_new_array(sizeof(dmnsn_astnode_type)); + + while (i < dmnsn_array_size(tokens)) { + dmnsn_array_get(tokens, i, &token); + + if (token.type == DMNSN_T_INTEGER || token.type == DMNSN_T_FLOAT) { + dmnsn_parse_number(tokens, &i, numstack); + } else if (token.type == DMNSN_T_LPAREN) { + ++i; + + if (dmnsn_parse_arithexp(tokens, &i, numstack) != 0) + goto bailout; + + if (dmnsn_parse_expect(DMNSN_T_RPAREN, tokens, &i) != 0) + goto bailout; + } else if (token.type == DMNSN_T_PLUS + || token.type == DMNSN_T_MINUS + || token.type == DMNSN_T_STAR + || token.type == DMNSN_T_SLASH) + + { + if (dmnsn_array_size(opstack) == dmnsn_array_size(numstack)) { + if (token.type == DMNSN_T_MINUS) { + /* Unary '-' -- negation */ + dmnsn_astnode astnode; + astnode.type = DMNSN_AST_NEGATE; + astnode.children = dmnsn_new_array(sizeof(dmnsn_astnode)); + astnode.ptr = NULL; + + ++i; + dmnsn_array_get(tokens, i, &token); + if (token.type == DMNSN_T_LPAREN) { + if (dmnsn_parse_arithexp(tokens, &i, astnode.children) != 0) + goto bailout; + } else { + if (dmnsn_parse_number(tokens, &i, astnode.children) != 0) + goto bailout; + } + + dmnsn_array_push(numstack, &astnode); + } else { + dmnsn_diagnostic(token.filename, token.line, token.col, + "Unexpected '%s' when parsing arithmetic expression", + dmnsn_token_string(token.type)); + return 1; + } + } else if (dmnsn_array_size(opstack) == 0) { + dmnsn_astnode_type type = dmnsn_op_map(token.type); + dmnsn_array_push(opstack, &type); + ++i; + } else { + dmnsn_astnode_type type = dmnsn_op_map(token.type), last_type; + dmnsn_array_get(opstack, dmnsn_array_size(opstack) - 1, &last_type); + + while (dmnsn_op_precedence(type) <= dmnsn_op_precedence(last_type)) { + dmnsn_astnode astnode, lhs, rhs; + astnode.type = last_type; + astnode.children = dmnsn_new_array(sizeof(dmnsn_astnode)); + astnode.ptr = NULL; + + dmnsn_array_pop(numstack, &rhs); + dmnsn_array_pop(numstack, &lhs); + + dmnsn_array_push(astnode.children, &lhs); + dmnsn_array_push(astnode.children, &rhs); + + dmnsn_array_push(numstack, &astnode); + dmnsn_array_resize(opstack, dmnsn_array_size(opstack) - 1); + + if (dmnsn_array_size(opstack) > 0) { + dmnsn_array_get(opstack, dmnsn_array_size(opstack) - 1, &last_type); + } else { + break; + } + } + + dmnsn_array_push(opstack, &type); + ++i; + } + } else { + break; + } + } + + if (dmnsn_array_size(numstack) == 0) { + dmnsn_diagnostic(token.filename, token.line, token.col, + "Expected arithmetic expression, found '%s'", + dmnsn_token_string(token.type)); + goto bailout; + } + + while (dmnsn_array_size(numstack) > 1) { + dmnsn_astnode_type type; + dmnsn_array_pop(opstack, &type); + + dmnsn_astnode astnode, lhs, rhs; + astnode.type = type; + astnode.children = dmnsn_new_array(sizeof(dmnsn_astnode)); + astnode.ptr = NULL; + + dmnsn_array_pop(numstack, &rhs); + dmnsn_array_pop(numstack, &lhs); + + dmnsn_array_push(astnode.children, &lhs); + dmnsn_array_push(astnode.children, &rhs); + + dmnsn_array_push(numstack, &astnode); + } + + dmnsn_array_push(astree, dmnsn_array_at(numstack, 0)); + dmnsn_delete_array(opstack); + dmnsn_delete_array(numstack); *ip = i; return 0; + + bailout: + dmnsn_delete_array(opstack); + dmnsn_delete_astree(numstack); + return 1; } static int dmnsn_parse_vector(const dmnsn_array *tokens, unsigned int *ip, dmnsn_array *astree) { + dmnsn_token token; unsigned int i = *ip; if (dmnsn_parse_expect(DMNSN_T_LESS, tokens, &i) != 0) @@ -121,26 +299,22 @@ dmnsn_parse_vector(const dmnsn_array *tokens, unsigned int *ip, astnode.children = dmnsn_new_array(sizeof(dmnsn_astnode)); astnode.ptr = NULL; - /* First element */ - if (dmnsn_parse_float(tokens, &i, astnode.children) != 0) - goto bailout; - - if (dmnsn_parse_expect(DMNSN_T_COMMA, tokens, &i) != 0) - goto bailout; - - /* Second element */ - if (dmnsn_parse_float(tokens, &i, astnode.children) != 0) - goto bailout; - - if (dmnsn_parse_expect(DMNSN_T_COMMA, tokens, &i) != 0) - goto bailout; + do { + if (dmnsn_parse_arithexp(tokens, &i, astnode.children) != 0) + goto bailout; - /* Third element */ - if (dmnsn_parse_float(tokens, &i, astnode.children) != 0) - goto bailout; + dmnsn_array_get(tokens, i, &token); + if (token.type != DMNSN_T_COMMA && token.type != DMNSN_T_GREATER) { + dmnsn_diagnostic(token.filename, token.line, token.col, + "Expected '%s' or '%s'; found '%s'", + dmnsn_token_string(DMNSN_T_COMMA), + dmnsn_token_string(DMNSN_T_GREATER), + dmnsn_token_string(token.type)); + goto bailout; + } - if (dmnsn_parse_expect(DMNSN_T_GREATER, tokens, &i) != 0) - goto bailout; + ++i; + } while (token.type != DMNSN_T_GREATER); dmnsn_array_push(astree, &astnode); *ip = i; @@ -214,7 +388,7 @@ dmnsn_parse_sphere(const dmnsn_array *tokens, unsigned int *ip, goto bailout; /* Radius */ - if (dmnsn_parse_float(tokens, &i, astnode.children) != 0) + if (dmnsn_parse_number(tokens, &i, astnode.children) != 0) goto bailout; if (dmnsn_parse_expect(DMNSN_T_RBRACE, tokens, &i) != 0) @@ -250,18 +424,13 @@ dmnsn_parse(const dmnsn_array *tokens) switch (token.type) { case DMNSN_T_BOX: - if (dmnsn_parse_box(tokens, &i, astree) != 0) { - dmnsn_diagnostic(token.filename, token.line, token.col, "Invalid box"); + if (dmnsn_parse_box(tokens, &i, astree) != 0) goto bailout; - } break; case DMNSN_T_SPHERE: - if (dmnsn_parse_sphere(tokens, &i, astree) != 0) { - dmnsn_diagnostic(token.filename, token.line, token.col, - "Invalid sphere"); + if (dmnsn_parse_sphere(tokens, &i, astree) != 0) goto bailout; - } break; default: @@ -310,9 +479,15 @@ dmnsn_delete_astree(dmnsn_array *astree) static void dmnsn_print_astnode(FILE *file, dmnsn_astnode astnode) { + long ivalue; double dvalue; switch (astnode.type) { + case DMNSN_AST_INTEGER: + ivalue = *(long *)astnode.ptr; + fprintf(file, "(%s %ld)", dmnsn_astnode_string(astnode.type), ivalue); + break; + case DMNSN_AST_FLOAT: dvalue = *(double *)astnode.ptr; fprintf(file, "(%s %g)", dmnsn_astnode_string(astnode.type), dvalue); @@ -377,9 +552,15 @@ dmnsn_astnode_string(dmnsn_astnode_type astnode_type) case type: \ return str; + dmnsn_astnode_map(DMNSN_AST_FLOAT, "float"); + dmnsn_astnode_map(DMNSN_AST_INTEGER, "integer"); + dmnsn_astnode_map(DMNSN_AST_NEGATE, "-"); + dmnsn_astnode_map(DMNSN_AST_ADD, "+"); + dmnsn_astnode_map(DMNSN_AST_SUB, "-"); + dmnsn_astnode_map(DMNSN_AST_MUL, "*"); + dmnsn_astnode_map(DMNSN_AST_DIV, "/"); dmnsn_astnode_map(DMNSN_AST_BOX, "box"); dmnsn_astnode_map(DMNSN_AST_VECTOR, "vector"); - dmnsn_astnode_map(DMNSN_AST_FLOAT, "float"); dmnsn_astnode_map(DMNSN_AST_SPHERE, "sphere"); default: diff --git a/dimension/parse.h b/dimension/parse.h index 02bda6e..d4420fa 100644 --- a/dimension/parse.h +++ b/dimension/parse.h @@ -22,6 +22,11 @@ typedef enum { DMNSN_AST_FLOAT, DMNSN_AST_INTEGER, + DMNSN_AST_NEGATE, + DMNSN_AST_ADD, + DMNSN_AST_SUB, + DMNSN_AST_MUL, + DMNSN_AST_DIV, DMNSN_AST_VECTOR, DMNSN_AST_BOX, DMNSN_AST_SPHERE, diff --git a/dimension/realize.c b/dimension/realize.c index 8bbf0cc..f9f5532 100644 --- a/dimension/realize.c +++ b/dimension/realize.c @@ -25,14 +25,41 @@ static double dmnsn_realize_float(dmnsn_astnode astnode) { - if (astnode.type == DMNSN_AST_FLOAT) { - double *x = astnode.ptr; - return *x; - } else if (astnode.type == DMNSN_AST_INTEGER) { - long *x = astnode.ptr; - return *x; - } else { - dmnsn_error(DMNSN_SEVERITY_HIGH, "Expected a float or an integer."); + dmnsn_astnode lhs, rhs; + + switch (astnode.type) { + case DMNSN_AST_FLOAT: + return *(double *)astnode.ptr; + + case DMNSN_AST_INTEGER: + return *(long *)astnode.ptr; + + case DMNSN_AST_NEGATE: + dmnsn_array_get(astnode.children, 0, &rhs); + return -dmnsn_realize_float(rhs); + + case DMNSN_AST_ADD: + dmnsn_array_get(astnode.children, 0, &lhs); + dmnsn_array_get(astnode.children, 1, &rhs); + return dmnsn_realize_float(lhs) + dmnsn_realize_float(rhs); + + case DMNSN_AST_SUB: + dmnsn_array_get(astnode.children, 0, &lhs); + dmnsn_array_get(astnode.children, 1, &rhs); + return dmnsn_realize_float(lhs) - dmnsn_realize_float(rhs); + + case DMNSN_AST_MUL: + dmnsn_array_get(astnode.children, 0, &lhs); + dmnsn_array_get(astnode.children, 1, &rhs); + return dmnsn_realize_float(lhs) * dmnsn_realize_float(rhs); + + case DMNSN_AST_DIV: + dmnsn_array_get(astnode.children, 0, &lhs); + dmnsn_array_get(astnode.children, 1, &rhs); + return dmnsn_realize_float(lhs) / dmnsn_realize_float(rhs); + + default: + dmnsn_error(DMNSN_SEVERITY_HIGH, "Invalid arithmetic expression."); return 0; /* Silence compiler warning */ } } diff --git a/tests/dimension/demo.pov b/tests/dimension/demo.pov index 386fdd0..24d934a 100644 --- a/tests/dimension/demo.pov +++ b/tests/dimension/demo.pov @@ -20,9 +20,9 @@ // Render demo scene box { - <-1.0, -1.0, -1.0>, <1.0, 1.0, 1.0> + <-2.0 + 1, -2/2.0, -1.0>, <1.0, (1.0 + 2)*2 - 5, 1.0 + 2*2 - 4> } sphere { - <0, 0, 0>, 1.25 + <1/5 + -1/5, 1/5.0 - 1.0/5, 0>, 1.25 } diff --git a/tests/dimension/demo.sh b/tests/dimension/demo.sh index 7674fd4..bd05f3d 100755 --- a/tests/dimension/demo.sh +++ b/tests/dimension/demo.sh @@ -20,8 +20,8 @@ ######################################################################### demo=$(${top_builddir}/dimension/dimension --tokenize --parse ${srcdir}/demo.pov) -demo_exp='(box { < - (float "1.0") , - (float "1.0") , - (float "1.0") > , < (float "1.0") , (float "1.0") , (float "1.0") > } sphere { < (integer "0") , (integer "0") , (integer "0") > , (float "1.25") }) -((box (vector (float -1) (float -1) (float -1)) (vector (float 1) (float 1) (float 1))) (sphere (vector (float 0) (float 0) (float 0)) (float 1.25)))' +demo_exp='(box { < - (float "2.0") + (integer "1") , - (integer "2") / (float "2.0") , - (float "1.0") > , < (float "1.0") , \( (float "1.0") + (integer "2") \) * (integer "2") - (integer "5") , (float "1.0") + (integer "2") * (integer "2") - (integer "4") > } sphere { < (integer "1") / (integer "5") + - (integer "1") / (integer "5") , (integer "1") / (float "5.0") - (float "1.0") / (integer "5") , (integer "0") > , (float "1.25") }) +((box (vector (+ (- (float 2)) (integer 1)) (/ (- (integer 2)) (float 2)) (- (float 1))) (vector (float 1) (- (* (+ (float 1) (integer 2)) (integer 2)) (integer 5)) (- (+ (float 1) (* (integer 2) (integer 2))) (integer 4)))) (sphere (vector (+ (/ (integer 1) (integer 5)) (/ (- (integer 1)) (integer 5))) (- (/ (integer 1) (float 5)) (/ (float 1) (integer 5))) (integer 0)) (float 1.25)))' if [ "$demo" != "$demo_exp" ]; then echo "demo.pov parsed as \"$demo\"" >&2 -- cgit v1.2.3