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 ++++++-- 3 files changed, 276 insertions(+), 63 deletions(-) (limited to 'dimension') 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 */ } } -- cgit v1.2.3