From 970ecabc1ad30fa74e58f3d4ad9ccf41baffb8b0 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sat, 19 Dec 2009 19:16:33 -0500 Subject: Implement a symbol table. --- dimension/Makefile.am | 1 + dimension/grammar.y | 442 +++----------------------------------- dimension/lexer.l | 6 +- dimension/main.c | 16 +- dimension/parse.c | 582 ++++++++++++++++++++++++++++++++++++++++++++++++++ dimension/parse.h | 70 ++++-- dimension/realize.c | 27 ++- dimension/realize.h | 6 +- dimension/tokenize.h | 3 +- dimension/utility.c | 10 +- dimension/utility.h | 2 +- 11 files changed, 719 insertions(+), 446 deletions(-) create mode 100644 dimension/parse.c (limited to 'dimension') diff --git a/dimension/Makefile.am b/dimension/Makefile.am index 4b7d20b..0e3c862 100644 --- a/dimension/Makefile.am +++ b/dimension/Makefile.am @@ -27,6 +27,7 @@ BUILT_SOURCES = grammar.h dimension_SOURCES = grammar.y \ lexer.l \ main.c \ + parse.c \ parse.h \ progressbar.c \ progressbar.h \ diff --git a/dimension/grammar.y b/dimension/grammar.y index 7825bc0..7955476 100644 --- a/dimension/grammar.y +++ b/dimension/grammar.y @@ -54,20 +54,6 @@ void dmnsn_yylex_destroy(void *scanner); /* Create a new astnode, populating filename, line, and col */ -static dmnsn_astnode -dmnsn_copy_astnode(dmnsn_astnode astnode) -{ - dmnsn_astnode copy = { - .type = astnode.type, - .children = dmnsn_new_array(sizeof(dmnsn_astnode)), - .ptr = NULL, - .filename = astnode.filename, - .line = astnode.line, - .col = astnode.col - }; - return copy; -} - static dmnsn_astnode dmnsn_new_astnode(dmnsn_astnode_type type, YYLTYPE lloc) { @@ -75,10 +61,17 @@ dmnsn_new_astnode(dmnsn_astnode_type type, YYLTYPE lloc) .type = type, .children = dmnsn_new_array(sizeof(dmnsn_astnode)), .ptr = NULL, + .refcount = malloc(sizeof(unsigned int)), .filename = lloc.first_filename, .line = lloc.first_line, .col = lloc.first_column }; + + if (!astnode.refcount) { + dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate reference count."); + } + *astnode.refcount = 1; + return astnode; } @@ -138,17 +131,9 @@ dmnsn_new_astnode5(dmnsn_astnode_type type, YYLTYPE lloc, return astnode; } -/* Delete a single, unused astnode */ -static void -dmnsn_delete_astnode(dmnsn_astnode astnode) -{ - dmnsn_delete_astree(astnode.children); - free(astnode.ptr); -} - void yyerror(YYLTYPE *locp, const char *filename, void *yyscanner, - dmnsn_array *astree, const char *str) + dmnsn_astree *astree, dmnsn_symbol_table *symtable, const char *str) { dmnsn_diagnostic(locp->first_filename, locp->first_line, locp->first_column, "%s", str); @@ -166,7 +151,8 @@ yyerror(YYLTYPE *locp, const char *filename, void *yyscanner, %parse-param {const char *filename} %parse-param {void *yyscanner} -%parse-param {dmnsn_array *astree} +%parse-param {dmnsn_astree *astree} +%parse-param {dmnsn_symbol_table *symtable} %lex-param {const char *filename} %lex-param {void *yyscanner} @@ -905,7 +891,7 @@ PIGMENT_TYPE: /* empty */ { /* Floats */ FLOAT: FLOAT_EXPR { - $$ = dmnsn_eval_scalar($1); + $$ = dmnsn_eval_scalar($1, symtable); dmnsn_delete_astnode($1); } ; @@ -999,6 +985,7 @@ FLOAT_LITERAL: "integer" { "Failed to allocate room for integer."); *(long *)$$.ptr = strtol($1, NULL, 0); + free($1); } | "float" { $$ = dmnsn_new_astnode(DMNSN_AST_FLOAT, @$); @@ -1007,18 +994,19 @@ FLOAT_LITERAL: "integer" { dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for float."); - *(double *)$$.ptr = strtod($1, NULL); + *(double *)$$.ptr = strtod($1, NULL); + free($1); } ; /* Vectors */ VECTOR: VECTOR_EXPR { - $$ = dmnsn_eval_vector($1); + $$ = dmnsn_eval_vector($1, symtable); dmnsn_delete_astnode($1); } | FLOAT_EXPR { - $$ = dmnsn_eval_vector($1); + $$ = dmnsn_eval_vector($1, symtable); dmnsn_delete_astnode($1); } ; @@ -1098,7 +1086,7 @@ COLOR_KEYWORD_GROUP_INIT: /* empty */ { "Failed to allocate room for integer."); *(long *)zero.ptr = 0; - $$ = dmnsn_eval_vector(zero); + $$ = dmnsn_eval_vector(zero, symtable); dmnsn_delete_astnode(zero); } ; @@ -1137,16 +1125,25 @@ COLOR_KEYWORD_ITEM: "red" FLOAT { %% -dmnsn_array * -dmnsn_parse(FILE *file, const char *filename) +dmnsn_astree * +dmnsn_parse(FILE *file, dmnsn_symbol_table *symtable) { + const char *filename; + dmnsn_astnode *fnode = dmnsn_find_symbol(symtable, "__file__"); + if (fnode && fnode->type == DMNSN_AST_STRING) { + filename = fnode->ptr; + } else { + filename = "<>"; + dmnsn_push_symbol(symtable, "__file__", dmnsn_new_ast_string(filename)); + } + void *scanner; - dmnsn_array *astree = dmnsn_new_array(sizeof(dmnsn_astnode)); + dmnsn_astree *astree = dmnsn_new_array(sizeof(dmnsn_astnode)); dmnsn_yylex_init(&scanner); dmnsn_yyset_in(file, scanner); - if (yyparse(filename, scanner, astree) != 0) { + if (yyparse(filename, scanner, astree, symtable) != 0) { dmnsn_delete_astree(astree); return NULL; } @@ -1155,383 +1152,6 @@ dmnsn_parse(FILE *file, const char *filename) return astree; } -void -dmnsn_delete_astree(dmnsn_array *astree) -{ - unsigned int i; - dmnsn_astnode node; - - if (astree) { - for (i = 0; i < dmnsn_array_size(astree); ++i) { - dmnsn_array_get(astree, i, &node); - dmnsn_delete_astree(node.children); - free(node.ptr); - } - dmnsn_delete_array(astree); - } -} - -static dmnsn_astnode -dmnsn_eval_scalar_unary(dmnsn_astnode astnode) -{ - dmnsn_astnode ret = dmnsn_copy_astnode(astnode), rhs; - dmnsn_array_get(astnode.children, 0, &rhs); - rhs = dmnsn_eval_scalar(rhs); - - if (rhs.type == DMNSN_AST_INTEGER) { - long n = *(long *)rhs.ptr; - long *res = malloc(sizeof(long)); - if (!res) - dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for integer."); - - switch(astnode.type) { - case DMNSN_AST_NEGATE: - *res = -n; - break; - - default: - dmnsn_error(DMNSN_SEVERITY_HIGH, - "Attempt to evaluate wrong unary operator."); - } - - ret.type = DMNSN_AST_INTEGER; - ret.ptr = res; - } else if (rhs.type == DMNSN_AST_FLOAT) { - double n = *(double *)rhs.ptr; - double *res = malloc(sizeof(double)); - if (!res) - dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for float."); - - switch(astnode.type) { - case DMNSN_AST_NEGATE: - *res = -n; - break; - - default: - dmnsn_error(DMNSN_SEVERITY_HIGH, - "Attempt to evaluate wrong unary operator."); - } - - ret.type = DMNSN_AST_FLOAT; - ret.ptr = res; - } else { - dmnsn_error(DMNSN_SEVERITY_HIGH, - "Invalid right hand side to unary operator."); - } - - dmnsn_delete_astnode(rhs); - return ret; -} - -static dmnsn_astnode -dmnsn_eval_scalar_binary(dmnsn_astnode astnode) -{ - dmnsn_astnode ret = dmnsn_copy_astnode(astnode), lhs, rhs; - dmnsn_array_get(astnode.children, 0, &lhs); - dmnsn_array_get(astnode.children, 1, &rhs); - lhs = dmnsn_eval_scalar(lhs); - rhs = dmnsn_eval_scalar(rhs); - - if (lhs.type == DMNSN_AST_INTEGER && rhs.type == DMNSN_AST_INTEGER - && astnode.type != DMNSN_AST_DIV) { - long l, r; - l = *(long *)lhs.ptr; - r = *(long *)rhs.ptr; - - long *res = malloc(sizeof(long)); - if (!res) - dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for integer."); - - switch (astnode.type) { - case DMNSN_AST_ADD: - *res = l + r; - break; - case DMNSN_AST_SUB: - *res = l - r; - break; - case DMNSN_AST_MUL: - *res = l*r; - break; - - default: - dmnsn_error(DMNSN_SEVERITY_HIGH, - "Attempt to evaluate wrong binary operator."); - } - - ret.type = DMNSN_AST_INTEGER; - ret.ptr = res; - } else { - double l = 0.0, r = 0.0; - - if (lhs.type == DMNSN_AST_INTEGER) - l = *(long *)lhs.ptr; - else if (lhs.type == DMNSN_AST_FLOAT) - l = *(double *)lhs.ptr; - else - dmnsn_error(DMNSN_SEVERITY_HIGH, - "Invalid left hand side to binary operator."); - - if (rhs.type == DMNSN_AST_INTEGER) - r = *(long *)rhs.ptr; - else if (rhs.type == DMNSN_AST_FLOAT) - r = *(double *)rhs.ptr; - else - dmnsn_error(DMNSN_SEVERITY_HIGH, - "Invalid right hand side to binary operator."); - - double *res = malloc(sizeof(double)); - if (!res) - dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for float."); - - switch (astnode.type) { - case DMNSN_AST_ADD: - *res = l + r; - break; - case DMNSN_AST_SUB: - *res = l - r; - break; - case DMNSN_AST_MUL: - *res = l*r; - break; - case DMNSN_AST_DIV: - *res = l/r; - break; - - default: - dmnsn_error(DMNSN_SEVERITY_HIGH, - "Attempt to evaluate wrong binary operator."); - } - - ret.type = DMNSN_AST_FLOAT; - ret.ptr = res; - } - - dmnsn_delete_astnode(lhs); - dmnsn_delete_astnode(rhs); - return ret; -} - -dmnsn_astnode -dmnsn_eval_scalar(dmnsn_astnode astnode) -{ - dmnsn_astnode ret; - - switch (astnode.type) { - case DMNSN_AST_INTEGER: - ret = dmnsn_copy_astnode(astnode); - ret.ptr = malloc(sizeof(long)); - if (!ret.ptr) - dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for integer."); - - memcpy(ret.ptr, astnode.ptr, sizeof(long)); - return ret; - - case DMNSN_AST_FLOAT: - ret = dmnsn_copy_astnode(astnode); - ret.ptr = malloc(sizeof(double)); - if (!ret.ptr) - dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for float."); - - memcpy(ret.ptr, astnode.ptr, sizeof(double)); - return ret; - - case DMNSN_AST_NEGATE: - return dmnsn_eval_scalar_unary(astnode); - - case DMNSN_AST_ADD: - case DMNSN_AST_SUB: - case DMNSN_AST_MUL: - case DMNSN_AST_DIV: - return dmnsn_eval_scalar_binary(astnode); - - default: - dmnsn_error(DMNSN_SEVERITY_HIGH, - "Given non-arithmetic-expression to evaluate."); - return astnode; /* Silence warning */ - } -} - -static dmnsn_astnode -dmnsn_vector_promote(dmnsn_astnode astnode) -{ - dmnsn_astnode promoted = dmnsn_copy_astnode(astnode), component; - promoted.type = DMNSN_AST_VECTOR; - - if (astnode.type == DMNSN_AST_VECTOR) { - unsigned int i; - for (i = 0; i < dmnsn_array_size(astnode.children); ++i) { - dmnsn_array_get(astnode.children, i, &component); - component = dmnsn_eval_scalar(component); - dmnsn_array_push(promoted.children, &component); - } - - while (dmnsn_array_size(promoted.children) < 5) { - component = dmnsn_copy_astnode(component); - component.type = DMNSN_AST_INTEGER; - - long *val = malloc(sizeof(long)); - *val = 0; - - component.ptr = val; - dmnsn_array_push(promoted.children, &component); - } - } else { - component = dmnsn_eval_scalar(astnode); - dmnsn_array_push(promoted.children, &component); - - while (dmnsn_array_size(promoted.children) < 5) { - component = dmnsn_eval_scalar(component); - dmnsn_array_push(promoted.children, &component); - } - } - - return promoted; -} - -static dmnsn_astnode -dmnsn_eval_vector_unary(dmnsn_astnode astnode) -{ - unsigned int i; - - dmnsn_astnode rhs; - dmnsn_array_get(astnode.children, 0, &rhs); - rhs = dmnsn_eval_vector(rhs); - - dmnsn_astnode ret = dmnsn_copy_astnode(astnode), temp; - ret.type = DMNSN_AST_VECTOR; - - dmnsn_astnode op = dmnsn_copy_astnode(astnode); - for (i = 0; i < 5; ++i) { - dmnsn_array_get(rhs.children, i, dmnsn_array_at(op.children, 0)); - temp = dmnsn_eval_scalar_unary(op); - dmnsn_array_set(ret.children, i, &temp); - } - - dmnsn_delete_array(op.children); - dmnsn_delete_astnode(rhs); - return ret; -} - -static dmnsn_astnode -dmnsn_eval_vector_binary(dmnsn_astnode astnode) -{ - unsigned int i; - - dmnsn_astnode lhs, rhs; - dmnsn_array_get(astnode.children, 0, &lhs); - dmnsn_array_get(astnode.children, 1, &rhs); - lhs = dmnsn_eval_vector(lhs); - rhs = dmnsn_eval_vector(rhs); - - dmnsn_astnode ret = dmnsn_copy_astnode(astnode), temp; - ret.type = DMNSN_AST_VECTOR; - - dmnsn_astnode op = dmnsn_copy_astnode(astnode); - for (i = 0; i < 5; ++i) { - dmnsn_array_get(lhs.children, i, dmnsn_array_at(op.children, 0)); - dmnsn_array_get(rhs.children, i, dmnsn_array_at(op.children, 1)); - temp = dmnsn_eval_scalar_binary(op); - dmnsn_array_set(ret.children, i, &temp); - } - - dmnsn_delete_array(op.children); - dmnsn_delete_astnode(lhs); - dmnsn_delete_astnode(rhs); - return ret; -} - -dmnsn_astnode -dmnsn_eval_vector(dmnsn_astnode astnode) -{ - switch (astnode.type) { - case DMNSN_AST_INTEGER: - case DMNSN_AST_FLOAT: - case DMNSN_AST_VECTOR: - return dmnsn_vector_promote(astnode); - - case DMNSN_AST_NEGATE: - return dmnsn_eval_vector_unary(astnode); - - case DMNSN_AST_ADD: - case DMNSN_AST_SUB: - case DMNSN_AST_MUL: - case DMNSN_AST_DIV: - return dmnsn_eval_vector_binary(astnode); - - default: - dmnsn_error(DMNSN_SEVERITY_HIGH, - "Given non-arithmetic-expression to evaluate."); - return astnode; /* Silence warning */ - } -} - -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); - break; - - default: - fprintf(file, "%s", dmnsn_astnode_string(astnode.type)); - } -} - -static void -dmnsn_print_astree(FILE *file, dmnsn_astnode astnode) -{ - unsigned int i; - dmnsn_astnode child; - - if (astnode.children && dmnsn_array_size(astnode.children) > 0) { - fprintf(file, "("); - dmnsn_print_astnode(file, astnode); - for (i = 0; i < dmnsn_array_size(astnode.children); ++i) { - dmnsn_array_get(astnode.children, i, &child); - fprintf(file, " "); - dmnsn_print_astree(file, child); - } - fprintf(file, ")"); - } else { - dmnsn_print_astnode(file, astnode); - } -} - -void -dmnsn_print_astree_sexpr(FILE *file, const dmnsn_array *astree) -{ - dmnsn_astnode astnode; - unsigned int i; - - if (dmnsn_array_size(astree) == 0) { - fprintf(file, "()"); - } else { - fprintf(file, "("); - dmnsn_array_get(astree, 0, &astnode); - dmnsn_print_astree(file, astnode); - - for (i = 1; i < dmnsn_array_size(astree); ++i) { - fprintf(file, " "); - dmnsn_array_get(astree, i, &astnode); - dmnsn_print_astree(file, astnode); - } - - fprintf(file, ")"); - } - - fprintf(file, "\n"); -} - const char * dmnsn_token_string(dmnsn_token_type token_type) { @@ -1605,6 +1225,8 @@ dmnsn_astnode_string(dmnsn_astnode_type astnode_type) dmnsn_astnode_map(DMNSN_AST_MUL, "*"); dmnsn_astnode_map(DMNSN_AST_DIV, "/"); + dmnsn_astnode_map(DMNSN_AST_STRING, "string"); + default: fprintf(stderr, "Warning: unrecognised astnode type %d.\n", (int)astnode_type); diff --git a/dimension/lexer.l b/dimension/lexer.l index 5001d3a..54d2040 100644 --- a/dimension/lexer.l +++ b/dimension/lexer.l @@ -80,8 +80,6 @@ #define STRING_TOKEN() \ do { \ NEW_TOKEN(DMNSN_T_STRING); \ - string_length = 0; \ - string_extent = 8; \ lvalp->value = malloc(string_extent); \ lvalp->value[0] = '\0'; \ CALCULATE_COLUMN(); \ @@ -100,7 +98,7 @@ } while(0) int token; -size_t string_length, string_extent; +size_t string_length = 0, string_extent = 8; unsigned long wchar; %} @@ -283,7 +281,7 @@ dmnsn_tokenize(FILE *file, const char *filename) return tokens; } -void +static void dmnsn_delete_token(dmnsn_token token) { free(token.value); diff --git a/dimension/main.c b/dimension/main.c index 2c2aea5..561ee99 100644 --- a/dimension/main.c +++ b/dimension/main.c @@ -155,28 +155,40 @@ main(int argc, char **argv) { } } + /* Construct the symbol table */ + dmnsn_symbol_table *symtable = dmnsn_new_symbol_table(); + dmnsn_push_symbol(symtable, "__file__", dmnsn_new_ast_string(input)); + /* Debugging option - output the abstract syntax tree as an S-expression */ if (parse) { - dmnsn_array *astree = dmnsn_parse(input_file, input); + dmnsn_astree *astree = dmnsn_parse(input_file, symtable); if (!astree) { fprintf(stderr, "Error parsing input file!\n"); + dmnsn_delete_symbol_table(symtable); + fclose(input_file); return EXIT_FAILURE; } dmnsn_print_astree_sexpr(stdout, astree); dmnsn_delete_astree(astree); + dmnsn_delete_symbol_table(symtable); fclose(input_file); return EXIT_SUCCESS; } /* Realize the input */ printf("Parsing scene ...\n"); - dmnsn_scene *scene = dmnsn_realize(input_file, input); + dmnsn_scene *scene = dmnsn_realize(input_file, symtable); if (!scene) { fprintf(stderr, "Error realizing input file!\n"); + dmnsn_delete_symbol_table(symtable); + fclose(input_file); return EXIT_FAILURE; } + dmnsn_delete_symbol_table(symtable); + fclose(input_file); + /* Allocate a canvas */ scene->canvas = dmnsn_new_canvas(width, height); if (!scene->canvas) { diff --git a/dimension/parse.c b/dimension/parse.c new file mode 100644 index 0000000..0bc080f --- /dev/null +++ b/dimension/parse.c @@ -0,0 +1,582 @@ +/************************************************************************* + * Copyright (C) 2009 Tavian Barnes * + * * + * This file is part of Dimension. * + * * + * Dimension is free software; you can redistribute it and/or modify it * + * under the terms of the GNU General Public License as published by the * + * Free Software Foundation; either version 3 of the License, or (at * + * your option) any later version. * + * * + * Dimension is distributed in the hope that it will be useful, but * + * WITHOUT ANY WARRANTY; without even the implied warranty of * + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * General Public License for more details. * + * * + * You should have received a copy of the GNU General Public License * + * along with this program. If not, see . * + *************************************************************************/ + +#include "parse.h" + +static dmnsn_astnode +dmnsn_new_astnode(dmnsn_astnode_type type) +{ + dmnsn_astnode astnode = { + .type = type, + .children = NULL, + .ptr = NULL, + .refcount = malloc(sizeof(unsigned int)), + .filename = "", + .line = -1, + .col = -1, + }; + + if (!astnode.refcount) { + dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate reference count."); + } + *astnode.refcount = 0; + + return astnode; +} + +dmnsn_astnode +dmnsn_new_ast_integer(long value) +{ + dmnsn_astnode astnode = dmnsn_new_astnode(DMNSN_AST_INTEGER); + + astnode.ptr = malloc(sizeof(long)); + if (!astnode.ptr) + dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate room for integer."); + + *(long *)astnode.ptr = value; + return astnode; +} + +dmnsn_astnode +dmnsn_new_ast_float(double value) +{ + dmnsn_astnode astnode = dmnsn_new_astnode(DMNSN_AST_FLOAT); + + astnode.ptr = malloc(sizeof(double)); + if (!astnode.ptr) + dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate room for float."); + + *(double *)astnode.ptr = value; + return astnode; +} + +dmnsn_astnode +dmnsn_new_ast_string(const char *value) +{ + dmnsn_astnode astnode = dmnsn_new_astnode(DMNSN_AST_STRING); + astnode.ptr = strdup(value); + return astnode; +} + +void +dmnsn_delete_astnode(dmnsn_astnode astnode) +{ + if (*astnode.refcount <= 1) { + dmnsn_delete_astree(astnode.children); + free(astnode.ptr); + free(astnode.refcount); + } else { + --*astnode.refcount; + } +} + +void +dmnsn_delete_astree(dmnsn_astree *astree) +{ + unsigned int i; + dmnsn_astnode node; + + if (astree) { + for (i = 0; i < dmnsn_array_size(astree); ++i) { + dmnsn_array_get(astree, i, &node); + dmnsn_delete_astnode(node); + } + dmnsn_delete_array(astree); + } +} + +/* TODO: use a hash table for symbol tables rather than an array */ + +typedef struct dmnsn_symbol { + char *id; + dmnsn_astnode value; +} dmnsn_symbol; + +dmnsn_symbol_table * +dmnsn_new_symbol_table() +{ + dmnsn_symbol_table *symtable = dmnsn_new_array(sizeof(dmnsn_array *)); + dmnsn_push_scope(symtable); + return symtable; +} + +static void +dmnsn_delete_scope(dmnsn_array *scope) +{ + while (dmnsn_array_size(scope) > 0) { + dmnsn_symbol symbol; + dmnsn_array_pop(scope, &symbol); + + free(symbol.id); + dmnsn_delete_astnode(symbol.value); + } + dmnsn_delete_array(scope); +} + +void +dmnsn_delete_symbol_table(dmnsn_symbol_table *symtable) +{ + while (dmnsn_array_size(symtable) > 0) { + dmnsn_array *scope; + dmnsn_array_pop(symtable, &scope); + dmnsn_delete_scope(scope); + } + dmnsn_delete_array(symtable); +} + +void +dmnsn_push_scope(dmnsn_symbol_table *symtable) +{ + dmnsn_array *scope = dmnsn_new_array(sizeof(dmnsn_symbol)); + dmnsn_array_push(symtable, &scope); +} + +void dmnsn_pop_scope(dmnsn_symbol_table *symtable) +{ + dmnsn_array *scope; + dmnsn_array_pop(symtable, &scope); + dmnsn_delete_scope(scope); +} + +void dmnsn_push_symbol(dmnsn_symbol_table *symtable, + const char *id, dmnsn_astnode value) +{ + ++*value.refcount; + + dmnsn_array *scope; + dmnsn_array_get(symtable, dmnsn_array_size(symtable) - 1, &scope); + + dmnsn_symbol symbol = { .id = strdup(id), .value = value }; + dmnsn_array_push(scope, &symbol); +} + +dmnsn_astnode * +dmnsn_find_symbol(dmnsn_symbol_table *symtable, const char *id) +{ + unsigned int i; + for (i = 0; i < dmnsn_array_size(symtable); ++i) { + dmnsn_array *scope; + dmnsn_array_get(symtable, dmnsn_array_size(symtable) - i - 1, &scope); + + unsigned int j; + for (j = 0; j < dmnsn_array_size(symtable); ++j) { + dmnsn_symbol *symbol = dmnsn_array_at(scope, + dmnsn_array_size(scope) - j - 1); + + if (strcmp(id, symbol->id) == 0) + return &symbol->value; + } + } + + return NULL; +} + +static dmnsn_astnode +dmnsn_copy_astnode(dmnsn_astnode astnode) +{ + dmnsn_astnode copy = { + .type = astnode.type, + .children = dmnsn_new_array(sizeof(dmnsn_astnode)), + .ptr = NULL, + .refcount = malloc(sizeof(unsigned int)), + .filename = astnode.filename, + .line = astnode.line, + .col = astnode.col + }; + + if (!copy.refcount) { + dmnsn_error(DMNSN_SEVERITY_HIGH, "Couldn't allocate reference count."); + } + *copy.refcount = 1; + + return copy; +} + +static dmnsn_astnode +dmnsn_eval_scalar_unary(dmnsn_astnode astnode, dmnsn_symbol_table *symtable) +{ + dmnsn_astnode ret = dmnsn_copy_astnode(astnode), rhs; + dmnsn_array_get(astnode.children, 0, &rhs); + rhs = dmnsn_eval_scalar(rhs, symtable); + + if (rhs.type == DMNSN_AST_INTEGER) { + long n = *(long *)rhs.ptr; + long *res = malloc(sizeof(long)); + if (!res) + dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for integer."); + + switch(astnode.type) { + case DMNSN_AST_NEGATE: + *res = -n; + break; + + default: + dmnsn_error(DMNSN_SEVERITY_HIGH, + "Attempt to evaluate wrong unary operator."); + } + + ret.type = DMNSN_AST_INTEGER; + ret.ptr = res; + } else if (rhs.type == DMNSN_AST_FLOAT) { + double n = *(double *)rhs.ptr; + double *res = malloc(sizeof(double)); + if (!res) + dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for float."); + + switch(astnode.type) { + case DMNSN_AST_NEGATE: + *res = -n; + break; + + default: + dmnsn_error(DMNSN_SEVERITY_HIGH, + "Attempt to evaluate wrong unary operator."); + } + + ret.type = DMNSN_AST_FLOAT; + ret.ptr = res; + } else { + dmnsn_error(DMNSN_SEVERITY_HIGH, + "Invalid right hand side to unary operator."); + } + + dmnsn_delete_astnode(rhs); + return ret; +} + +static dmnsn_astnode +dmnsn_eval_scalar_binary(dmnsn_astnode astnode, dmnsn_symbol_table *symtable) +{ + dmnsn_astnode ret = dmnsn_copy_astnode(astnode), lhs, rhs; + dmnsn_array_get(astnode.children, 0, &lhs); + dmnsn_array_get(astnode.children, 1, &rhs); + lhs = dmnsn_eval_scalar(lhs, symtable); + rhs = dmnsn_eval_scalar(rhs, symtable); + + if (lhs.type == DMNSN_AST_INTEGER && rhs.type == DMNSN_AST_INTEGER + && astnode.type != DMNSN_AST_DIV) { + long l, r; + l = *(long *)lhs.ptr; + r = *(long *)rhs.ptr; + + long *res = malloc(sizeof(long)); + if (!res) + dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for integer."); + + switch (astnode.type) { + case DMNSN_AST_ADD: + *res = l + r; + break; + case DMNSN_AST_SUB: + *res = l - r; + break; + case DMNSN_AST_MUL: + *res = l*r; + break; + + default: + dmnsn_error(DMNSN_SEVERITY_HIGH, + "Attempt to evaluate wrong binary operator."); + } + + ret.type = DMNSN_AST_INTEGER; + ret.ptr = res; + } else { + double l = 0.0, r = 0.0; + + if (lhs.type == DMNSN_AST_INTEGER) + l = *(long *)lhs.ptr; + else if (lhs.type == DMNSN_AST_FLOAT) + l = *(double *)lhs.ptr; + else + dmnsn_error(DMNSN_SEVERITY_HIGH, + "Invalid left hand side to binary operator."); + + if (rhs.type == DMNSN_AST_INTEGER) + r = *(long *)rhs.ptr; + else if (rhs.type == DMNSN_AST_FLOAT) + r = *(double *)rhs.ptr; + else + dmnsn_error(DMNSN_SEVERITY_HIGH, + "Invalid right hand side to binary operator."); + + double *res = malloc(sizeof(double)); + if (!res) + dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for float."); + + switch (astnode.type) { + case DMNSN_AST_ADD: + *res = l + r; + break; + case DMNSN_AST_SUB: + *res = l - r; + break; + case DMNSN_AST_MUL: + *res = l*r; + break; + case DMNSN_AST_DIV: + *res = l/r; + break; + + default: + dmnsn_error(DMNSN_SEVERITY_HIGH, + "Attempt to evaluate wrong binary operator."); + } + + ret.type = DMNSN_AST_FLOAT; + ret.ptr = res; + } + + dmnsn_delete_astnode(lhs); + dmnsn_delete_astnode(rhs); + return ret; +} + +dmnsn_astnode +dmnsn_eval_scalar(dmnsn_astnode astnode, dmnsn_symbol_table *symtable) +{ + dmnsn_astnode ret; + + switch (astnode.type) { + case DMNSN_AST_INTEGER: + ret = dmnsn_copy_astnode(astnode); + ret.ptr = malloc(sizeof(long)); + if (!ret.ptr) + dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for integer."); + + memcpy(ret.ptr, astnode.ptr, sizeof(long)); + return ret; + + case DMNSN_AST_FLOAT: + ret = dmnsn_copy_astnode(astnode); + ret.ptr = malloc(sizeof(double)); + if (!ret.ptr) + dmnsn_error(DMNSN_SEVERITY_HIGH, "Failed to allocate room for float."); + + memcpy(ret.ptr, astnode.ptr, sizeof(double)); + return ret; + + case DMNSN_AST_NEGATE: + return dmnsn_eval_scalar_unary(astnode, symtable); + + case DMNSN_AST_ADD: + case DMNSN_AST_SUB: + case DMNSN_AST_MUL: + case DMNSN_AST_DIV: + return dmnsn_eval_scalar_binary(astnode, symtable); + + default: + dmnsn_error(DMNSN_SEVERITY_HIGH, + "Given non-arithmetic-expression to evaluate."); + return astnode; /* Silence warning */ + } +} + +#define DMNSN_VECTOR_NELEM 5 + +static dmnsn_astnode +dmnsn_vector_promote(dmnsn_astnode astnode, dmnsn_symbol_table *symtable) +{ + dmnsn_astnode promoted = dmnsn_copy_astnode(astnode), component; + promoted.type = DMNSN_AST_VECTOR; + + if (astnode.type == DMNSN_AST_VECTOR) { + unsigned int i; + for (i = 0; i < dmnsn_array_size(astnode.children); ++i) { + dmnsn_array_get(astnode.children, i, &component); + component = dmnsn_eval_scalar(component, symtable); + dmnsn_array_push(promoted.children, &component); + } + + while (dmnsn_array_size(promoted.children) < DMNSN_VECTOR_NELEM) { + component = dmnsn_copy_astnode(component); + component.type = DMNSN_AST_INTEGER; + + long *val = malloc(sizeof(long)); + *val = 0; + + component.ptr = val; + dmnsn_array_push(promoted.children, &component); + } + } else { + component = dmnsn_eval_scalar(astnode, symtable); + dmnsn_array_push(promoted.children, &component); + + while (dmnsn_array_size(promoted.children) < DMNSN_VECTOR_NELEM) { + component = dmnsn_eval_scalar(component, symtable); + dmnsn_array_push(promoted.children, &component); + } + } + + return promoted; +} + +static dmnsn_astnode +dmnsn_eval_vector_unary(dmnsn_astnode astnode, dmnsn_symbol_table *symtable) +{ + unsigned int i; + + dmnsn_astnode rhs; + dmnsn_array_get(astnode.children, 0, &rhs); + rhs = dmnsn_eval_vector(rhs, symtable); + + dmnsn_astnode ret = dmnsn_copy_astnode(astnode), temp; + ret.type = DMNSN_AST_VECTOR; + + dmnsn_astnode op = dmnsn_copy_astnode(astnode); + for (i = 0; i < DMNSN_VECTOR_NELEM; ++i) { + dmnsn_array_get(rhs.children, i, dmnsn_array_at(op.children, 0)); + temp = dmnsn_eval_scalar_unary(op, symtable); + dmnsn_array_set(ret.children, i, &temp); + } + + dmnsn_delete_array(op.children); + op.children = NULL; + dmnsn_delete_astnode(op); + dmnsn_delete_astnode(rhs); + return ret; +} + +static dmnsn_astnode +dmnsn_eval_vector_binary(dmnsn_astnode astnode, dmnsn_symbol_table *symtable) +{ + unsigned int i; + + dmnsn_astnode lhs, rhs; + dmnsn_array_get(astnode.children, 0, &lhs); + dmnsn_array_get(astnode.children, 1, &rhs); + lhs = dmnsn_eval_vector(lhs, symtable); + rhs = dmnsn_eval_vector(rhs, symtable); + + dmnsn_astnode ret = dmnsn_copy_astnode(astnode), temp; + ret.type = DMNSN_AST_VECTOR; + + dmnsn_astnode op = dmnsn_copy_astnode(astnode); + for (i = 0; i < DMNSN_VECTOR_NELEM; ++i) { + dmnsn_array_get(lhs.children, i, dmnsn_array_at(op.children, 0)); + dmnsn_array_get(rhs.children, i, dmnsn_array_at(op.children, 1)); + temp = dmnsn_eval_scalar_binary(op, symtable); + dmnsn_array_set(ret.children, i, &temp); + } + + dmnsn_delete_array(op.children); + op.children = NULL; + dmnsn_delete_astnode(op); + dmnsn_delete_astnode(lhs); + dmnsn_delete_astnode(rhs); + return ret; +} + +dmnsn_astnode +dmnsn_eval_vector(dmnsn_astnode astnode, dmnsn_symbol_table *symtable) +{ + switch (astnode.type) { + case DMNSN_AST_INTEGER: + case DMNSN_AST_FLOAT: + case DMNSN_AST_VECTOR: + return dmnsn_vector_promote(astnode, symtable); + + case DMNSN_AST_NEGATE: + return dmnsn_eval_vector_unary(astnode, symtable); + + case DMNSN_AST_ADD: + case DMNSN_AST_SUB: + case DMNSN_AST_MUL: + case DMNSN_AST_DIV: + return dmnsn_eval_vector_binary(astnode, symtable); + + default: + dmnsn_error(DMNSN_SEVERITY_HIGH, + "Given non-arithmetic-expression to evaluate."); + return astnode; /* Silence warning */ + } +} + +static void +dmnsn_print_astnode(FILE *file, dmnsn_astnode astnode) +{ + long ivalue; + double dvalue; + const char *svalue; + + 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); + break; + + case DMNSN_AST_STRING: + svalue = astnode.ptr; + fprintf(file, "(%s \"%s\")", dmnsn_astnode_string(astnode.type), svalue); + break; + + default: + fprintf(file, "%s", dmnsn_astnode_string(astnode.type)); + } +} + +static void +dmnsn_print_astree(FILE *file, dmnsn_astnode astnode) +{ + unsigned int i; + dmnsn_astnode child; + + if (astnode.children && dmnsn_array_size(astnode.children) > 0) { + fprintf(file, "("); + dmnsn_print_astnode(file, astnode); + for (i = 0; i < dmnsn_array_size(astnode.children); ++i) { + dmnsn_array_get(astnode.children, i, &child); + fprintf(file, " "); + dmnsn_print_astree(file, child); + } + fprintf(file, ")"); + } else { + dmnsn_print_astnode(file, astnode); + } +} + +void +dmnsn_print_astree_sexpr(FILE *file, const dmnsn_astree *astree) +{ + dmnsn_astnode astnode; + unsigned int i; + + if (dmnsn_array_size(astree) == 0) { + fprintf(file, "()"); + } else { + fprintf(file, "("); + dmnsn_array_get(astree, 0, &astnode); + dmnsn_print_astree(file, astnode); + + for (i = 1; i < dmnsn_array_size(astree); ++i) { + fprintf(file, " "); + dmnsn_array_get(astree, i, &astnode); + dmnsn_print_astree(file, astnode); + } + + fprintf(file, ")"); + } + + fprintf(file, "\n"); +} diff --git a/dimension/parse.h b/dimension/parse.h index 3ea073f..6f8755d 100644 --- a/dimension/parse.h +++ b/dimension/parse.h @@ -22,6 +22,11 @@ #include "../libdimension/dimension.h" +/* + * Abstract syntax tree + */ + +/* Abstract syntax tree node types */ typedef enum { DMNSN_AST_NONE, @@ -60,11 +65,12 @@ typedef enum { DMNSN_AST_SUB, DMNSN_AST_MUL, DMNSN_AST_DIV, -} dmnsn_astnode_type; -typedef struct dmnsn_astnode dmnsn_astnode; + DMNSN_AST_STRING, +} dmnsn_astnode_type; -struct dmnsn_astnode { +/* Abstract syntax tree node (a dmnsn_array* of these is an AST) */ +typedef struct dmnsn_astnode { dmnsn_astnode_type type; /* Child nodes */ @@ -73,28 +79,61 @@ struct dmnsn_astnode { /* Generic data pointer */ void *ptr; + /* Reference count */ + unsigned int *refcount; + /* File name, and line and column numbers from source code */ const char *filename; - unsigned int line, col; -}; + int line, col; +} dmnsn_astnode; -/* The workhorse */ -dmnsn_array *dmnsn_parse(FILE *file, const char *filename); +typedef dmnsn_array dmnsn_astree; -/* Free an abstract syntax tree */ -void dmnsn_delete_astree(dmnsn_array *astree); +dmnsn_astnode dmnsn_new_ast_integer(long value); +dmnsn_astnode dmnsn_new_ast_float(double value); +dmnsn_astnode dmnsn_new_ast_string(const char *value); -/* Evaluate an arithmetic expression */ -dmnsn_astnode dmnsn_eval_scalar(dmnsn_astnode astnode); -dmnsn_astnode dmnsn_eval_vector(dmnsn_astnode astnode); +void dmnsn_delete_astnode(dmnsn_astnode astnode); +void dmnsn_delete_astree(dmnsn_astree *astree); /* Print an S-expression of the abstract syntax tree to `file' */ -void dmnsn_print_astree_sexpr(FILE *file, const dmnsn_array *astree); +void dmnsn_print_astree_sexpr(FILE *file, const dmnsn_astree *astree); -/* Returns a readable name for a token type (ex. DMNSN_T_FLOAT -> float) */ +/* Returns a readable name for an astnode type (ex. DMNSN_AST_FLOAT -> float) */ const char *dmnsn_astnode_string(dmnsn_astnode_type astnode_type); -/* Parser internals */ +/* + * Symbol table + */ + +typedef dmnsn_array dmnsn_symbol_table; + +dmnsn_symbol_table *dmnsn_new_symbol_table(); + +void dmnsn_delete_symbol_table(dmnsn_symbol_table *symtable); + +void dmnsn_push_scope(dmnsn_symbol_table *symtable); +void dmnsn_pop_scope(dmnsn_symbol_table *symtable); + +void dmnsn_push_symbol(dmnsn_symbol_table *symtable, + const char *id, dmnsn_astnode value); +dmnsn_astnode *dmnsn_find_symbol(dmnsn_symbol_table *symtable, const char *id); + +/* Evaluate an arithmetic expression */ +dmnsn_astnode dmnsn_eval_scalar(dmnsn_astnode astnode, + dmnsn_symbol_table *symtable); +dmnsn_astnode dmnsn_eval_vector(dmnsn_astnode astnode, + dmnsn_symbol_table *symtable); + + +/* + * The workhorse -- parse a file + */ +dmnsn_astree *dmnsn_parse(FILE *file, dmnsn_symbol_table *symtable); + +/* + * Parser internals + */ typedef struct dmnsn_parse_location { const char *first_filename, *last_filename; @@ -107,5 +146,4 @@ typedef union dmnsn_parse_item { dmnsn_astnode astnode; } dmnsn_parse_item; - #endif /* PARSE_H */ diff --git a/dimension/realize.c b/dimension/realize.c index a4b8df5..eda7056 100644 --- a/dimension/realize.c +++ b/dimension/realize.c @@ -540,7 +540,7 @@ dmnsn_realize_sphere(dmnsn_astnode astnode) } static dmnsn_scene * -dmnsn_realize_astree(const dmnsn_array *astree) +dmnsn_realize_astree(const dmnsn_astree *astree) { dmnsn_scene *scene = dmnsn_new_scene(); if (!scene) { @@ -612,24 +612,39 @@ dmnsn_realize_astree(const dmnsn_array *astree) } dmnsn_scene * -dmnsn_realize(FILE *file, const char *filename) +dmnsn_realize(FILE *file, dmnsn_symbol_table *symtable) { - dmnsn_array *astree = dmnsn_parse(file, filename); + if (!symtable) { + symtable = dmnsn_new_symbol_table(); + } + + dmnsn_astree *astree = dmnsn_parse(file, symtable); if (!astree) { return NULL; } - return dmnsn_realize_astree(astree); + + dmnsn_scene *scene = dmnsn_realize_astree(astree); + + dmnsn_delete_astree(astree); + return scene; } dmnsn_scene * -dmnsn_realize_string(const char *str) +dmnsn_realize_string(const char *str, dmnsn_symbol_table *symtable) { + if (!symtable) { + symtable = dmnsn_new_symbol_table(); + } + if (!dmnsn_find_symbol(symtable, "__file__")) { + dmnsn_push_symbol(symtable, "__file__", dmnsn_new_ast_string("")); + } + FILE *file = fmemopen((void *)str, strlen(str), "r"); if (!file) { return NULL; } - dmnsn_scene *scene = dmnsn_realize(file, ""); + dmnsn_scene *scene = dmnsn_realize(file, symtable); fclose(file); return scene; diff --git a/dimension/realize.h b/dimension/realize.h index f9b4d61..e351595 100644 --- a/dimension/realize.h +++ b/dimension/realize.h @@ -21,8 +21,10 @@ #define REALIZE_H #include "../libdimension/dimension.h" +#include "parse.h" -dmnsn_scene *dmnsn_realize(FILE *file, const char *filename); -dmnsn_scene *dmnsn_realize_string(const char *str); +dmnsn_scene *dmnsn_realize(FILE *file, dmnsn_symbol_table *symtable); +dmnsn_scene *dmnsn_realize_string(const char *str, + dmnsn_symbol_table *symtable); #endif /* REALIZE_H */ diff --git a/dimension/tokenize.h b/dimension/tokenize.h index 541c604..524b004 100644 --- a/dimension/tokenize.h +++ b/dimension/tokenize.h @@ -33,14 +33,13 @@ struct dmnsn_token { /* File name, and line and column numbers from source code */ const char *filename; - unsigned int line, col; + int line, col; }; /* For debugging */ dmnsn_array *dmnsn_tokenize(FILE *file, const char *filename); /* Token destruction */ -void dmnsn_delete_token(dmnsn_token token); void dmnsn_delete_tokens(dmnsn_array *tokens); /* Print an S-expression of a list of tokens to `file' */ diff --git a/dimension/utility.c b/dimension/utility.c index 1961d3e..012e704 100644 --- a/dimension/utility.c +++ b/dimension/utility.c @@ -22,13 +22,17 @@ #include void -dmnsn_diagnostic(const char *filename, unsigned int line, unsigned int col, - const char *format, ...) +dmnsn_diagnostic(const char *filename, int line, int col, const char *format, + ...) { va_list ap; va_start(ap, format); - fprintf(stderr, "%s:%u:%u: ", filename, line, col); + if (line >= 0 && col >= 0) { + fprintf(stderr, "%s:%d:%d: ", filename, line, col); + } else { + fprintf(stderr, "%s: ", filename); + } vfprintf(stderr, format, ap); fprintf(stderr, "\n"); diff --git a/dimension/utility.h b/dimension/utility.h index 5403b19..30394ed 100644 --- a/dimension/utility.h +++ b/dimension/utility.h @@ -18,5 +18,5 @@ *************************************************************************/ /* Print a parsing diagnostic to stderr */ -void dmnsn_diagnostic(const char *filename, unsigned int line, unsigned int col, +void dmnsn_diagnostic(const char *filename, int line, int col, const char *format, ...); -- cgit v1.2.3