diff options
| -rw-r--r-- | dimension/parse.c | 58 |
1 files changed, 53 insertions, 5 deletions
diff --git a/dimension/parse.c b/dimension/parse.c index 25d983c..f4b32fb 100644 --- a/dimension/parse.c +++ b/dimension/parse.c @@ -24,6 +24,7 @@ #include <stdio.h> #include <locale.h> +/* Expect a particular token next, and complain if we see something else */ static int dmnsn_parse_expect(dmnsn_token_type type, const dmnsn_array *tokens, unsigned int *ip) @@ -49,6 +50,7 @@ dmnsn_parse_expect(dmnsn_token_type type, const dmnsn_array *tokens, return 0; } +/* Parse a number - a float or an integer */ static int dmnsn_parse_number(const dmnsn_array *tokens, unsigned int *ip, dmnsn_array *astree) @@ -69,6 +71,7 @@ dmnsn_parse_number(const dmnsn_array *tokens, unsigned int *ip, astnode.children = NULL; if (token.type == DMNSN_T_INTEGER) { + /* An exact integer */ astnode.type = DMNSN_AST_INTEGER; long *value = malloc(sizeof(double)); @@ -79,6 +82,7 @@ dmnsn_parse_number(const dmnsn_array *tokens, unsigned int *ip, astnode.ptr = value; ++i; } else if (token.type == DMNSN_T_FLOAT) { + /* A floating-point value */ astnode.type = DMNSN_AST_FLOAT; double *value = malloc(sizeof(double)); @@ -106,6 +110,7 @@ dmnsn_parse_number(const dmnsn_array *tokens, unsigned int *ip, return 1; } +/* Map an operator token to an operator node type */ static dmnsn_astnode_type dmnsn_op_map(dmnsn_token_type type) { @@ -128,6 +133,7 @@ dmnsn_op_map(dmnsn_token_type type) } } +/* Return the precedence of a given operator */ static int dmnsn_op_precedence(dmnsn_astnode_type type) { @@ -147,13 +153,38 @@ dmnsn_op_precedence(dmnsn_astnode_type type) } } -static int dmnsn_parse_arithexp(const dmnsn_array *tokens, unsigned int *ip, - dmnsn_array *astree); - +/* Parse an arithmetic expression */ static int dmnsn_parse_arithexp(const dmnsn_array *tokens, unsigned int *ip, dmnsn_array *astree) { + /* + * We use a stack of numbers (numstack), and a stack of operators (opstack). + * Each time we see a number (or a parenthetical sub-expression, which is + * evaluated recursively), it goes on the numstack. When we see an operator, + * it goes on the opstack, but if it has the same or lower precedence than + * the operator below it on the stack, the two top elements of numstack are + * folded with the correct operator until either opstack is empty or the + * current operator has a higher precedence. Example: + * + * 1 - 2 * 3 - 4 * 5 --> ... - 4 * 5 --> ... - 4 * 5 --> ... - 4 * 5 + * _____ --> ___________ --> _______________ + * 3 | * (* 2 3) | - (- 1 (* 2 3)) | + * 2 | - 1 | + * 1 | + * + * --> ... + * --> _________________ + * 5 | * + * 4 | - + * (- 1 (* 2 3)) | + * + * Then the stack is collapsed from the top down until we have a single value: + * + * --> _________________ --> (- (- 1 (* 2 3)) (* 4 5)) + * (* 4 5) | - + * (- 1 (* 2 3)) | + */ dmnsn_token token; unsigned int i = *ip; @@ -169,13 +200,16 @@ dmnsn_parse_arithexp(const dmnsn_array *tokens, unsigned int *ip, dmnsn_array_get(tokens, i, &token); if (token.type == DMNSN_T_INTEGER || token.type == DMNSN_T_FLOAT) { + /* Item is a number */ dmnsn_parse_number(tokens, &i, numstack); } else if (token.type == DMNSN_T_LPAREN) { - ++i; + ++i; /* Skip past '(' */ + /* Parse the contents of the parentheses */ if (dmnsn_parse_arithexp(tokens, &i, numstack) != 0) goto bailout; + /* Match a closing ')' */ if (dmnsn_parse_expect(DMNSN_T_RPAREN, tokens, &i) != 0) goto bailout; } else if (token.type == DMNSN_T_PLUS @@ -184,7 +218,9 @@ dmnsn_parse_arithexp(const dmnsn_array *tokens, unsigned int *ip, || token.type == DMNSN_T_SLASH) { + /* Item is an operator */ if (dmnsn_array_size(opstack) == dmnsn_array_size(numstack)) { + /* The last item was an operator too */ if (token.type == DMNSN_T_MINUS) { /* Unary '-' -- negation */ dmnsn_astnode astnode; @@ -210,6 +246,7 @@ dmnsn_parse_arithexp(const dmnsn_array *tokens, unsigned int *ip, return 1; } } else if (dmnsn_array_size(opstack) == 0) { + /* opstack is empty; push the operator */ dmnsn_astnode_type type = dmnsn_op_map(token.type); dmnsn_array_push(opstack, &type); ++i; @@ -218,6 +255,7 @@ dmnsn_parse_arithexp(const dmnsn_array *tokens, unsigned int *ip, dmnsn_array_get(opstack, dmnsn_array_size(opstack) - 1, &last_type); while (dmnsn_op_precedence(type) <= dmnsn_op_precedence(last_type)) { + /* Repeatedly collapse numstack */ dmnsn_astnode astnode, lhs, rhs; astnode.type = last_type; astnode.children = dmnsn_new_array(sizeof(dmnsn_astnode)); @@ -243,10 +281,12 @@ dmnsn_parse_arithexp(const dmnsn_array *tokens, unsigned int *ip, ++i; } } else { + /* Unrecognized token; arithmetic expression must be over */ break; } } + /* Prevent us from matching nothing */ if (dmnsn_array_size(numstack) == 0) { dmnsn_diagnostic(token.filename, token.line, token.col, "Expected arithmetic expression, found '%s'", @@ -255,6 +295,7 @@ dmnsn_parse_arithexp(const dmnsn_array *tokens, unsigned int *ip, } while (dmnsn_array_size(numstack) > 1) { + /* Collapse numstack */ dmnsn_astnode_type type; dmnsn_array_pop(opstack, &type); @@ -284,6 +325,7 @@ dmnsn_parse_arithexp(const dmnsn_array *tokens, unsigned int *ip, return 1; } +/* Parse a vector */ static int dmnsn_parse_vector(const dmnsn_array *tokens, unsigned int *ip, dmnsn_array *astree) @@ -291,6 +333,7 @@ dmnsn_parse_vector(const dmnsn_array *tokens, unsigned int *ip, dmnsn_token token; unsigned int i = *ip; + /* Vectors start with '<' */ if (dmnsn_parse_expect(DMNSN_T_LESS, tokens, &i) != 0) return 1; @@ -300,6 +343,7 @@ dmnsn_parse_vector(const dmnsn_array *tokens, unsigned int *ip, astnode.ptr = NULL; do { + /* Parse comma-separated aritexp's, closed by '>' */ if (dmnsn_parse_arithexp(tokens, &i, astnode.children) != 0) goto bailout; @@ -325,12 +369,14 @@ dmnsn_parse_vector(const dmnsn_array *tokens, unsigned int *ip, return 1; } +/* Parse a box definition */ static int dmnsn_parse_box(const dmnsn_array *tokens, unsigned int *ip, dmnsn_array *astree) { unsigned int i = *ip; + /* Opens with "box {" */ if (dmnsn_parse_expect(DMNSN_T_BOX, tokens, &i) != 0) return 1; if (dmnsn_parse_expect(DMNSN_T_LBRACE, tokens, &i) != 0) @@ -364,12 +410,14 @@ dmnsn_parse_box(const dmnsn_array *tokens, unsigned int *ip, return 1; } +/* Parse a sphere definition */ static int dmnsn_parse_sphere(const dmnsn_array *tokens, unsigned int *ip, dmnsn_array *astree) { unsigned int i = *ip; + /* Opens with "sphere {" */ if (dmnsn_parse_expect(DMNSN_T_SPHERE, tokens, &i) != 0) return 1; if (dmnsn_parse_expect(DMNSN_T_LBRACE, tokens, &i) != 0) @@ -414,7 +462,7 @@ dmnsn_parse(const dmnsn_array *tokens) char *lc_ctype = strdup(setlocale(LC_CTYPE, NULL)); char *lc_numeric = strdup(setlocale(LC_NUMERIC, NULL)); - /* Set the locale to `C' to make strtoul(), etc. consistent */ + /* Set the locale to `C' to make strtol(), etc. consistent */ setlocale(LC_CTYPE, "C"); setlocale(LC_NUMERIC, "C"); |