diff options
| -rw-r--r-- | ast.c | 64 | ||||
| -rw-r--r-- | ast.h | 43 | ||||
| -rw-r--r-- | ccc.h | 1 | ||||
| -rw-r--r-- | codegen.c | 67 | ||||
| -rw-r--r-- | makefile | 2 | ||||
| -rw-r--r-- | parser.c | 110 | ||||
| -rw-r--r-- | test/factorial.c | 8 | ||||
| -rw-r--r-- | test/factorial2.c (renamed from test/fibonacci2.c) | 3 | ||||
| -rw-r--r-- | test/fibonacci.c | 8 | ||||
| -rw-r--r-- | type_checker.c | 57 |
10 files changed, 205 insertions, 158 deletions
@@ -5,17 +5,16 @@ static void expr_destroy(struct expr_node* node); static void stmt_destroy(struct stmt_node* node); -static void lval_destroy(struct lval_node* node) { - switch (node->type) { - case LVAL_VAR_DECL: - break; - case LVAL_VAR_REF: - break; +static void var_decl_destroy(struct var_decl_node* node) { + if (node->initial_value != NULL) { + expr_destroy(node->initial_value); + free(node->initial_value); } } static void assign_destroy(struct assign_node* node) { - lval_destroy(&node->lval); + expr_destroy(node->lval); + free(node->lval); expr_destroy(node->rval); free(node->rval); } @@ -33,16 +32,21 @@ static void group_destroy(struct group_node* node) { free(node->scope); } -static void args_decl_destroy(struct args_decl_node* node) { - if (node != NULL) { - free(node->decl); - args_decl_destroy(node->next); +static void decl_list_destroy(struct decl_list_node* node) { + var_decl_destroy(node->decl); + free(node->decl); + + if (node->next != NULL) { + decl_list_destroy(node->next); + free(node->next); } } static void fn_decl_destroy(struct fn_decl_node* node) { - args_decl_destroy(node->args); - free(node->args); + if (node->args != NULL) { + decl_list_destroy(node->args); + free(node->args); + } group_destroy(&node->body); @@ -61,17 +65,21 @@ static void str_lit_destroy(struct str_lit_node* node) { free(node->val); } -static void args_list_destroy(struct args_eval_node* node) { - if (node != NULL) { - expr_destroy(node->expr); - free(node->expr); - args_list_destroy(node->next); +static void expr_list_destroy(struct expr_list_node* node) { + expr_destroy(node->expr); + free(node->expr); + + if (node->next != NULL) { + expr_list_destroy(node->next); + free(node->next); } } static void call_destroy(struct call_node* node) { - args_list_destroy(node->args); - free(node->args); + if (node->args != NULL) { + expr_list_destroy(node->args); + free(node->args); + } } static void unary_destroy(struct unary_node* node) { @@ -129,9 +137,22 @@ static void if_destroy(struct if_node* node) { free(node->scope); } +static void loop_init_destroy(struct loop_init_node* node) { + switch (node->type) { + case INIT_EXPR_LIST: + expr_list_destroy(node->expr_list); + free(node->expr_list); + break; + case INIT_DECL: + var_decl_destroy(node->decl); + free(node->decl); + break; + } +} + static void loop_destroy(struct loop_node* node) { if (node->init != NULL) { - expr_destroy(node->init); + loop_init_destroy(node->init); free(node->init); } if (node->cond != NULL) { @@ -158,6 +179,7 @@ static void stmt_destroy(struct stmt_node* node) { expr_destroy(&node->inner.expr); break; case STMT_VAR_DECL: + var_decl_destroy(&node->inner.var_decl); break; case STMT_RETURN: return_destroy(&node->inner.return_); @@ -33,35 +33,23 @@ struct var_ref_node { struct var_decl_node { struct type_ref_node type; struct var_def* def_ref; -}; - -struct lval_node { - enum { - LVAL_VAR_DECL, - LVAL_VAR_REF, - } type; - union { - struct var_ref_node var_ref; - struct var_decl_node var_decl; - } inner; - - const struct type_def* resolved_type; + struct expr_node* initial_value; }; struct assign_node { - struct lval_node lval; + struct expr_node* lval; struct expr_node* rval; }; -struct args_eval_node { +struct expr_list_node { struct expr_node* expr; - struct args_eval_node* next; + struct expr_list_node* next; }; struct call_node { - /* TODO: eventually this could also be a function pointer */ + /* TODO: function pointers */ struct fn_decl_node* called_fn_ref; /* borrowed */ - struct args_eval_node* args; + struct expr_list_node* args; }; struct unary_node { @@ -114,15 +102,15 @@ struct group_node { struct scope* scope; }; -struct args_decl_node { +struct decl_list_node { struct var_decl_node* decl; - struct args_decl_node* next; + struct decl_list_node* next; }; struct fn_decl_node { struct type_ref_node return_type; char* name; - struct args_decl_node* args; + struct decl_list_node* args; struct group_node body; struct scope* scope; @@ -140,8 +128,19 @@ struct if_node { struct scope* scope; }; +struct loop_init_node { + enum { + INIT_EXPR_LIST, + INIT_DECL, + } type; + union { + struct expr_list_node* expr_list; + struct var_decl_node* decl; + }; +}; + struct loop_node { - struct expr_node* init; /* null if absent */ + struct loop_init_node* init; /* null if absent */ struct expr_node* cond; /* null if absent */ struct expr_node* incr; /* null if absent */ struct stmt_node* body; @@ -2,6 +2,5 @@ #define CCC_H #define CCC_PANIC { perror("ccc"); exit(1); } -#define PTR_SIZE 8 #endif @@ -300,42 +300,20 @@ static void emit_var_ref( static void emit_stmt(FILE* outfile, const struct stmt_node* node); -static struct var_def* emit_var_decl( +static void emit_var_decl( FILE* outfile, const struct var_decl_node* node ) { struct lval_def var_dst = make_stack_lval(outfile, node->def_ref->resolved_type); + node->def_ref->loc = var_dst.loc; fprintf(outfile, "\t; '%s' lives in: ", node->def_ref->name); emit_storage_loc(outfile, &var_dst.loc, var_dst.type->sz); fprintf(outfile, "\n"); - struct var_def* var_def = node->def_ref; - var_def->loc = var_dst.loc; - return var_def; -} - -static struct lval_def emit_lval( - FILE* outfile, - const struct lval_node* node -) { - struct var_def* var_def; - switch (node->type) { - case LVAL_VAR_DECL: - var_def = emit_var_decl(outfile, &node->inner.var_decl); - return (struct lval_def) { - .loc = var_def->loc, - .type = var_def->resolved_type, - }; - case LVAL_VAR_REF: - var_def = node->inner.var_ref.def_ref; - return (struct lval_def) { - .loc = var_def->loc, - .type = var_def->resolved_type, - }; - } - CGEN_PANIC("unknown lval type: %d", node->type); + if (node->initial_value != NULL) + emit_expr(outfile, node->initial_value, &var_dst); } static void emit_assignment( @@ -343,7 +321,18 @@ static void emit_assignment( const struct assign_node* node, const struct lval_def* dst ) { - const struct lval_def lval_def = emit_lval(outfile, &node->lval); + struct lval_def lval_def; + switch (node->lval->type) { + case EXPR_VAR_REF: + struct var_ref_node* var_ref = &node->lval->inner.var_ref; + lval_def = (struct lval_def) { + .type = var_ref->def_ref->resolved_type, + .loc = var_ref->def_ref->loc, + }; + break; + default: + CGEN_PANIC("expression is not assignable"); + } emit_expr(outfile, node->rval, &lval_def); if (dst != NULL) emit_mov(outfile, dst, &lval_def.loc); } @@ -356,8 +345,8 @@ static void emit_call( unsigned long long orig_bp_offset = scope->bp_offset; unsigned long long arg_bp_offset = orig_bp_offset; - struct args_decl_node* arg_decl = node->called_fn_ref->args; - struct args_eval_node* arg_eval = node->args; + struct decl_list_node* arg_decl = node->called_fn_ref->args; + struct expr_list_node* arg_eval = node->args; while (arg_decl != NULL && arg_eval != NULL) { struct lval_def arg_dst = make_stack_lval(outfile, arg_decl->decl->def_ref->resolved_type); @@ -601,10 +590,26 @@ static void emit_if(FILE* outfile, const struct if_node* node) { exit_scope(node->scope, true); } +static void emit_expr_list(FILE* outfile, const struct expr_list_node* node) { + for (; node != NULL; node = node->next) + emit_expr(outfile, node->expr, NULL); +} + +static void emit_loop_init(FILE* outfile, const struct loop_init_node* node) { + switch (node->type) { + case INIT_EXPR_LIST: + emit_expr_list(outfile, node->expr_list); + break; + case INIT_DECL: + emit_var_decl(outfile, node->decl); + break; + } +} + static void emit_loop(FILE* outfile, const struct loop_node* node) { enter_scope(node->scope, scope->bp_offset); - if (node->init != NULL) emit_expr(outfile, node->init, NULL); + if (node->init != NULL) emit_loop_init(outfile, node->init); unsigned long long loop_num = ++loop_counter; if (node->cond != NULL) { @@ -671,7 +676,7 @@ static void emit_fn_decl(FILE* outfile, const struct fn_decl_node* node) { long long spilled_bp_ofs = -16; // return address + old bp unsigned char arg_regnum = 0; - struct args_decl_node* arg_decl = node->args; + struct decl_list_node* arg_decl = node->args; for (; arg_decl != NULL; arg_decl = arg_decl->next) { struct var_def* arg_def = arg_decl->decl->def_ref; struct lval_def arg_dst = @@ -1,2 +1,4 @@ all: gcc -std=c23 -g -O0 -Wall -Werror *.c -o ccc +clean: + rm -f ./ccc *.s *.o *.out **/*.s **/*.o **/*.out @@ -124,34 +124,29 @@ static void parse_var_ref(struct var_ref_node* p_node) { } static void parse_expr_assign(struct expr_node* p_node) { - switch (p_node->type) { - case EXPR_VAR_REF: - p_node->inner.assign.lval = (struct lval_node) { - .type = LVAL_VAR_REF, - .inner.var_ref = p_node->inner.var_ref, - }; - break; - default: - PARSER_PANIC("expression is not assignable"); - } + struct expr_node* lval = protected_alloc(sizeof(struct expr_node)); + *lval = *p_node; p_node->type = EXPR_ASSIGN; - p_node->inner.assign.rval = protected_alloc(sizeof(struct expr_node)); + struct assign_node* a_node = &p_node->inner.assign; + a_node->lval = lval; expect(TK_ASSIGN); - parse_expr(p_node->inner.assign.rval); + a_node->rval = protected_alloc(sizeof(struct expr_node)); + parse_expr(a_node->rval); } -static void parse_args_eval(struct args_eval_node** pp_arg) { +static void parse_expr_list(struct expr_list_node* p_node) { for (;;) { - *pp_arg = protected_alloc(sizeof(struct args_eval_node)); - (*pp_arg)->expr = protected_alloc(sizeof(struct expr_node)); - parse_expr((*pp_arg)->expr); - pp_arg = &((*pp_arg)->next); + p_node->expr = protected_alloc(sizeof(struct expr_node)); + parse_expr(p_node->expr); peek_or_panic(); - if (tok.type == TK_RPAREN) break; + if (tok.type != TK_COMMA) break; expect(TK_COMMA); + + p_node->next = protected_alloc(sizeof(struct expr_list_node)); + p_node = p_node->next; } } @@ -174,7 +169,11 @@ static void parse_expr_call(struct expr_node* p_node) { expect(TK_LPAREN); peek_or_panic(); - if (tok.type != TK_RPAREN) parse_args_eval(&p_node->inner.call.args); + if (tok.type != TK_RPAREN) { + p_node->inner.call.args = + protected_alloc(sizeof(struct expr_list_node)); + parse_expr_list(p_node->inner.call.args); + } expect(TK_RPAREN); } @@ -286,6 +285,13 @@ static void parse_var_decl(struct var_decl_node* p_node) { }); if (p_node->def_ref == NULL) PARSER_PANIC("redefinition of '%s'", tok.data.ident); + + peek_or_panic(); + if (tok.type == TK_ASSIGN) { + expect(TK_ASSIGN); + p_node->initial_value = protected_alloc(sizeof(struct expr_node)); + parse_expr(p_node->initial_value); + } } static void parse_stmt(struct stmt_node* p_node); @@ -366,6 +372,25 @@ static void parse_while(struct loop_node* p_node) { scope_pop(&scope); } +static void parse_loop_init(struct loop_init_node* p_node) { + peek_or_panic(); + if (tok.type != TK_IDENT + || !scope_get_type(scope, NULL, &(struct type_key) { + .name = tok.data.ident, + .how_long = 0, + .marked_signed = false, + .marked_unsigned = false, + })) { + p_node->type = INIT_EXPR_LIST; + p_node->expr_list = protected_alloc(sizeof(struct expr_list_node)); + parse_expr_list(p_node->expr_list); + } else { + p_node->type = INIT_DECL; + p_node->decl = protected_alloc(sizeof(struct var_decl_node)); + parse_var_decl(p_node->decl); + } +} + static void parse_for(struct loop_node* p_node) { expect_kw("for"); @@ -375,8 +400,8 @@ static void parse_for(struct loop_node* p_node) { expect(TK_LPAREN); peek_or_panic(); if (tok.type != TK_SEMI) { - p_node->init = protected_alloc(sizeof(struct expr_node)); - parse_expr(p_node->init); + p_node->init = protected_alloc(sizeof(struct loop_init_node)); + parse_loop_init(p_node->init); } expect(TK_SEMI); peek_or_panic(); @@ -398,30 +423,6 @@ static void parse_for(struct loop_node* p_node) { scope_pop(&scope); } -static void parse_stmt_assign(struct stmt_node* p_node) { - peek_or_panic(); - if (tok.type != TK_ASSIGN) return; - - switch (p_node->type) { - case STMT_VAR_DECL: - p_node->inner.expr.inner.assign.lval = (struct lval_node) { - .type = LVAL_VAR_DECL, - .inner.var_decl = p_node->inner.var_decl, - }; - break; - default: - return; - } - - p_node->type = STMT_EXPR; - p_node->inner.expr.type = EXPR_ASSIGN; - p_node->inner.expr.inner.assign.rval = - protected_alloc(sizeof(struct expr_node)); - - expect(TK_ASSIGN); - parse_expr(p_node->inner.expr.inner.assign.rval); -} - static void parse_stmt(struct stmt_node* p_node) { peek_or_panic(); switch (tok.type) { @@ -467,20 +468,20 @@ static void parse_stmt(struct stmt_node* p_node) { parse_expr(&p_node->inner.expr); } - parse_stmt_assign(p_node); expect(TK_SEMI); } -static void parse_args_decl(struct args_decl_node** pp_decl) { +static void parse_decl_list(struct decl_list_node* p_node) { for (;;) { - *pp_decl = protected_alloc(sizeof(struct args_decl_node)); - (*pp_decl)->decl = protected_alloc(sizeof(struct var_decl_node)); - parse_var_decl((*pp_decl)->decl); - pp_decl = &((*pp_decl)->next); + p_node->decl = protected_alloc(sizeof(struct var_decl_node)); + parse_var_decl(p_node->decl); peek_or_panic(); - if (tok.type == TK_RPAREN) break; + if (tok.type != TK_COMMA) break; expect(TK_COMMA); + + p_node->next = protected_alloc(sizeof(struct decl_list_node)); + p_node = p_node->next; } } @@ -509,7 +510,10 @@ static void parse_fn_decl(struct fn_decl_node* p_node) { p_node->scope = scope; peek_or_panic(); - if (tok.type != TK_RPAREN) parse_args_decl(&p_node->args); + if (tok.type != TK_RPAREN) { + p_node->args = protected_alloc(sizeof(struct decl_list_node)); + parse_decl_list(p_node->args); + } expect(TK_RPAREN); diff --git a/test/factorial.c b/test/factorial.c new file mode 100644 index 0000000..0525b8f --- /dev/null +++ b/test/factorial.c @@ -0,0 +1,8 @@ +int fact (int n) { + if (n) return n * fact(n-1); + else return 1; +} + +int main (int argc, char** argv) { + return fact(argc); +} diff --git a/test/fibonacci2.c b/test/factorial2.c index b8adb9a..867b709 100644 --- a/test/fibonacci2.c +++ b/test/factorial2.c @@ -1,7 +1,6 @@ int main (int argc, char** argv) { - int n = argc; int result = 1; - for (; n; n = n - 1) { + for (int n = argc; n; n = n - 1) { result = result * n; } return result; diff --git a/test/fibonacci.c b/test/fibonacci.c deleted file mode 100644 index a07c111..0000000 --- a/test/fibonacci.c +++ /dev/null @@ -1,8 +0,0 @@ -int fib (int n) { - if (n) return n * fib(n-1); - else return 1; -} - -int main (int argc, char** argv) { - return fib(argc); -} diff --git a/type_checker.c b/type_checker.c index 8a07f2a..5905c83 100644 --- a/type_checker.c +++ b/type_checker.c @@ -15,7 +15,6 @@ static struct ast* ast_ref; static struct scope* scope; static void type_check_expr(struct expr_node* node); -static void type_check_lval(struct lval_node* node); static void type_check_stmt(struct stmt_node* node); static void type_check_group(struct group_node* node); @@ -78,13 +77,25 @@ static const struct type_def* resolve_var_ref(struct var_ref_node* node) { } static void type_check_var_decl(struct var_decl_node* node) { - node->def_ref->resolved_type = resolve_type_ref(&node->type); + const struct type_def* lval_type = resolve_type_ref(&node->type); + node->def_ref->resolved_type = lval_type; + if (node->initial_value != NULL) { + type_check_expr(node->initial_value); + assert_cast_compatible(lval_type, node->initial_value->resolved_type); + } } static const struct type_def* resolve_assign(struct assign_node* node) { - type_check_lval(&node->lval); + switch (node->lval->type) { + case EXPR_VAR_REF: + break; + default: + TYPE_PANIC("expression is not assignable"); + } + + type_check_expr(node->lval); type_check_expr(node->rval); - const struct type_def* lval_type = node->lval.resolved_type; + const struct type_def* lval_type = node->lval->resolved_type; const struct type_def* rval_type = node->rval->resolved_type; assert_cast_compatible(lval_type, rval_type); @@ -92,9 +103,12 @@ static const struct type_def* resolve_assign(struct assign_node* node) { } static const struct type_def* resolve_call(struct call_node* node) { - struct args_decl_node* arg_decl = node->called_fn_ref->args; - struct args_eval_node* arg_eval = node->args; + struct decl_list_node* arg_decl = node->called_fn_ref->args; + struct expr_list_node* arg_eval = node->args; while (arg_decl != NULL && arg_eval != NULL) { + if (arg_decl->decl->initial_value != NULL) + TYPE_PANIC("C does not support default arguments"); + type_check_var_decl(arg_decl->decl); const struct type_def* decl_type = arg_decl->decl->def_ref->resolved_type; @@ -127,18 +141,6 @@ static const struct type_def* resolve_binary(struct binary_node* node) { return node->lhs->resolved_type; } -static void type_check_lval(struct lval_node* node) { - switch (node->type) { - case LVAL_VAR_DECL: - type_check_var_decl(&node->inner.var_decl); - node->resolved_type = node->inner.var_decl.def_ref->resolved_type; - break; - case LVAL_VAR_REF: - node->resolved_type = resolve_var_ref(&node->inner.var_ref); - break; - } -} - static void type_check_expr(struct expr_node* node) { switch (node->type) { case EXPR_INT_LIT: @@ -185,10 +187,25 @@ static void type_check_if(struct if_node* node) { exit_scope(node->scope); } +static void type_check_expr_list(struct expr_list_node* node) { + for (; node != NULL; node = node->next) type_check_expr(node->expr); +} + +static void type_check_loop_init(struct loop_init_node* node) { + switch (node->type) { + case INIT_EXPR_LIST: + type_check_expr_list(node->expr_list); + break; + case INIT_DECL: + type_check_var_decl(node->decl); + break; + } +} + static void type_check_loop(struct loop_node* node) { enter_scope(node->scope); - if (node->init != NULL) type_check_expr(node->init); + if (node->init != NULL) type_check_loop_init(node->init); if (node->cond != NULL) type_check_expr(node->cond); if (node->incr != NULL) type_check_expr(node->incr); type_check_stmt(node->body); @@ -238,7 +255,7 @@ static void type_check_fn_decl(struct fn_decl_node* node) { node->resolved_return_type = resolve_type_ref(&node->return_type); - for (struct args_decl_node* arg_decl = node->args; + for (struct decl_list_node* arg_decl = node->args; arg_decl != NULL; arg_decl = arg_decl->next) type_check_var_decl(arg_decl->decl); |