diff options
Diffstat (limited to 'parse.c')
| -rw-r--r-- | parse.c | 1404 |
1 files changed, 0 insertions, 1404 deletions
diff --git a/parse.c b/parse.c deleted file mode 100644 index 8f06a83..0000000 --- a/parse.c +++ /dev/null @@ -1,1404 +0,0 @@ -#define LVAR_MAX 32 - -struct LocalVar { - const char* name; - Type* ty; - int stack_offset; -}; -typedef struct LocalVar LocalVar; - -struct Scope { - struct Scope* outer; - const char** lvar_names; - int* lvar_indices; -}; -typedef struct Scope Scope; - -struct GlobalVar { - const char* name; - Type* ty; -}; -typedef struct GlobalVar GlobalVar; - -struct Func { - const char* name; - Type* ty; -}; -typedef struct Func Func; - -struct Parser { - TokenArray* tokens; - int pos; - LocalVar* lvars; - int n_lvars; - Scope* scope; - GlobalVar* gvars; - int n_gvars; - Func* funcs; - int n_funcs; - AstNode* structs; - int n_structs; - AstNode* unions; - int n_unions; - AstNode* enums; - int n_enums; - AstNode* typedefs; - int n_typedefs; - const char** str_literals; - int n_str_literals; -}; -typedef struct Parser Parser; - -Parser* parser_new(TokenArray* tokens) { - Parser* p = calloc(1, sizeof(Parser)); - p->tokens = tokens; - p->gvars = calloc(128, sizeof(GlobalVar)); - p->funcs = calloc(256, sizeof(Func)); - p->structs = calloc(64, sizeof(AstNode)); - p->unions = calloc(64, sizeof(AstNode)); - p->enums = calloc(16, sizeof(AstNode)); - p->typedefs = calloc(64, sizeof(AstNode)); - p->str_literals = calloc(1024, sizeof(char*)); - - p->funcs[p->n_funcs].name = "__ducc_va_start"; - p->funcs[p->n_funcs].ty = calloc(1, sizeof(Type)); - p->funcs[p->n_funcs].ty->kind = TypeKind_void; - ++p->n_funcs; - - return p; -} - -Token* peek_token(Parser* p) { - return &p->tokens->data[p->pos]; -} - -Token* next_token(Parser* p) { - return &p->tokens->data[p->pos++]; -} - -Token* consume_token_if(Parser* p, TokenKind expected) { - if (peek_token(p)->kind == expected) { - return next_token(p); - } else { - return NULL; - } -} - -BOOL eof(Parser* p) { - return peek_token(p)->kind != TokenKind_eof; -} - -Token* expect(Parser* p, TokenKind expected) { - Token* t = next_token(p); - if (t->kind == expected) { - return t; - } - fatal_error("%s:%d: expected '%s', but got '%s'", t->loc.filename, t->loc.line, token_kind_stringify(expected), - token_stringify(t)); -} - -int find_lvar_in_scope(Parser* p, Scope* scope, const char* name) { - for (int i = 0; i < LVAR_MAX; ++i) { - if (scope->lvar_names[i] && strcmp(scope->lvar_names[i], name) == 0) { - return scope->lvar_indices[i]; - } - } - return -1; -} - -int find_lvar_in_current_scope(Parser* p, const char* name) { - return find_lvar_in_scope(p, p->scope, name); -} - -int find_lvar(Parser* p, const char* name) { - Scope* scope = p->scope; - while (scope) { - int idx = find_lvar_in_scope(p, scope, name); - if (idx != -1) - return idx; - scope = scope->outer; - } - return -1; -} - -int calc_stack_offset(Parser* p, Type* ty, BOOL is_param) { - int align; - if (is_param) { - if (8 < type_sizeof(ty) || 8 < type_alignof(ty)) { - fatal_error("too large"); - } - align = 8; - } else { - align = type_alignof(ty); - } - - int offset; - if (p->n_lvars == 0) { - offset = 0; - } else { - offset = p->lvars[p->n_lvars - 1].stack_offset; - } - - offset += type_sizeof(ty); - return to_aligned(offset, align); -} - -int add_lvar(Parser* p, const char* name, Type* ty, BOOL is_param) { - int stack_offset = calc_stack_offset(p, ty, is_param); - p->lvars[p->n_lvars].name = name; - p->lvars[p->n_lvars].ty = ty; - p->lvars[p->n_lvars].stack_offset = stack_offset; - for (int i = 0; i < LVAR_MAX; ++i) { - if (p->scope->lvar_names[i] == NULL) { - p->scope->lvar_names[i] = name; - p->scope->lvar_indices[i] = p->n_lvars; - break; - } - } - ++p->n_lvars; - return stack_offset; -} - -AstNode* generate_temporary_lvar(Parser* p, Type* ty) { - int stack_offset = add_lvar(p, NULL, ty, FALSE); - AstNode* lvar = ast_new(AstNodeKind_lvar); - lvar->name = NULL; - lvar->node_stack_offset = stack_offset; - lvar->ty = ty; - return lvar; -} - -int find_gvar(Parser* p, const char* name) { - for (int i = 0; i < p->n_gvars; ++i) { - if (strcmp(p->gvars[i].name, name) == 0) { - return i; - } - } - return -1; -} - -int find_func(Parser* p, const char* name) { - for (int i = 0; i < p->n_funcs; ++i) { - if (strcmp(p->funcs[i].name, name) == 0) { - return i; - } - } - return -1; -} - -int find_struct(Parser* p, const char* name) { - for (int i = 0; i < p->n_structs; ++i) { - if (strcmp(p->structs[i].name, name) == 0) { - return i; - } - } - return -1; -} - -int find_union(Parser* p, const char* name) { - for (int i = 0; i < p->n_unions; ++i) { - if (strcmp(p->unions[i].name, name) == 0) { - return i; - } - } - return -1; -} - -int find_enum(Parser* p, const char* name) { - for (int i = 0; i < p->n_enums; ++i) { - if (strcmp(p->enums[i].name, name) == 0) { - return i; - } - } - return -1; -} - -int find_enum_member(Parser* p, const char* name) { - for (int i = 0; i < p->n_enums; ++i) { - for (int j = 0; j < p->enums[i].node_members->node_len; ++j) { - if (strcmp(p->enums[i].node_members->node_items[j].name, name) == 0) { - return i * 1000 + j; - } - } - } - return -1; -} - -int find_typedef(Parser* p, const char* name) { - for (int i = 0; i < p->n_typedefs; ++i) { - if (strcmp(p->typedefs[i].name, name) == 0) { - return i; - } - } - return -1; -} - -void enter_scope(Parser* p) { - Scope* outer_scope = p->scope; - p->scope = calloc(1, sizeof(Scope)); - p->scope->outer = outer_scope; - p->scope->lvar_names = calloc(LVAR_MAX, sizeof(char*)); - p->scope->lvar_indices = calloc(LVAR_MAX, sizeof(int)); -} - -void leave_scope(Parser* p) { - p->scope = p->scope->outer; -} - -void enter_func(Parser* p) { - p->lvars = calloc(LVAR_MAX, sizeof(LocalVar)); - p->n_lvars = 0; - enter_scope(p); -} - -void leave_func(Parser* p) { - leave_scope(p); -} - -AstNode* parse_assignment_expr(Parser* p); -AstNode* parse_expr(Parser* p); -AstNode* parse_stmt(Parser* p); - -const char* parse_ident(Parser* p) { - return expect(p, TokenKind_ident)->value.string; -} - -int register_str_literal(Parser* p, const char* s) { - p->str_literals[p->n_str_literals] = s; - ++p->n_str_literals; - return p->n_str_literals; -} - -AstNode* parse_primary_expr(Parser* p) { - Token* t = next_token(p); - if (t->kind == TokenKind_literal_int) { - return ast_new_int(t->value.integer); - } else if (t->kind == TokenKind_literal_str) { - AstNode* e = ast_new(AstNodeKind_str_expr); - e->node_idx = register_str_literal(p, t->value.string); - e->ty = type_new_static_string(strlen(t->value.string)); - return e; - } else if (t->kind == TokenKind_paren_l) { - AstNode* e = parse_expr(p); - expect(p, TokenKind_paren_r); - return e; - } else if (t->kind == TokenKind_ident) { - const char* name = t->value.string; - - if (peek_token(p)->kind == TokenKind_paren_l) { - AstNode* e = ast_new(AstNodeKind_func_call); - int func_idx = find_func(p, name); - if (func_idx == -1) { - fatal_error("undefined function: %s", name); - } - e->name = name; - e->ty = p->funcs[func_idx].ty; - return e; - } - - int lvar_idx = find_lvar(p, name); - if (lvar_idx == -1) { - int gvar_idx = find_gvar(p, name); - if (gvar_idx == -1) { - int enum_member_idx = find_enum_member(p, name); - if (enum_member_idx == -1) { - fatal_error("undefined variable: %s", name); - } - int enum_idx = enum_member_idx / 1000; - int n = enum_member_idx % 1000; - AstNode* e = ast_new_int(p->enums[enum_idx].node_members->node_items[n].node_int_value); - e->ty = type_new(TypeKind_enum); - e->ty->def = p->enums + enum_idx; - return e; - } - AstNode* e = ast_new(AstNodeKind_gvar); - e->name = name; - e->ty = p->gvars[gvar_idx].ty; - return e; - } - - AstNode* e = ast_new(AstNodeKind_lvar); - e->name = name; - e->node_stack_offset = p->lvars[lvar_idx].stack_offset; - e->ty = p->lvars[lvar_idx].ty; - return e; - } else { - fatal_error("%s:%d: expected an expression, but got '%s'", t->loc.filename, t->loc.line, token_stringify(t)); - } -} - -AstNode* parse_arg_list(Parser* p) { - AstNode* list = ast_new_list(6); - while (peek_token(p)->kind != TokenKind_paren_r) { - AstNode* arg = parse_assignment_expr(p); - ast_append(list, arg); - if (!consume_token_if(p, TokenKind_comma)) { - break; - } - } - if (list->node_len > 6) { - fatal_error("too many arguments"); - } - return list; -} - -// e++ -// tmp1 = &e; tmp2 = *tmp1; *tmp1 += 1; tmp2 -// e-- -// tmp1 = &e; tmp2 = *tmp1; *tmp1 -= 1; tmp2 -AstNode* create_new_postfix_inc_or_dec(Parser* p, AstNode* e, TokenKind op) { - AstNode* tmp1_lvar = generate_temporary_lvar(p, type_new_ptr(e->ty)); - AstNode* tmp2_lvar = generate_temporary_lvar(p, e->ty); - - AstNode* expr1 = ast_new_assign_expr(TokenKind_assign, tmp1_lvar, ast_new_ref_expr(e)); - AstNode* expr2 = ast_new_assign_expr(TokenKind_assign, tmp2_lvar, ast_new_deref_expr(tmp1_lvar)); - AstNode* expr3; - if (op == TokenKind_plusplus) { - expr3 = ast_new_assign_add_expr(ast_new_deref_expr(tmp1_lvar), ast_new_int(1)); - } else { - expr3 = ast_new_assign_sub_expr(ast_new_deref_expr(tmp1_lvar), ast_new_int(1)); - } - AstNode* expr4 = tmp2_lvar; - - AstNode* ret = ast_new_list(4); - ast_append(ret, expr1); - ast_append(ret, expr2); - ast_append(ret, expr3); - ast_append(ret, expr4); - ret->ty = expr4->ty; - return ret; -} - -AstNode* parse_postfix_expr(Parser* p) { - AstNode* ret = parse_primary_expr(p); - while (1) { - TokenKind tk = peek_token(p)->kind; - if (consume_token_if(p, TokenKind_paren_l)) { - AstNode* args = parse_arg_list(p); - expect(p, TokenKind_paren_r); - ret->node_args = args; - } else if (consume_token_if(p, TokenKind_bracket_l)) { - AstNode* idx = parse_expr(p); - expect(p, TokenKind_bracket_r); - idx = ast_new_binary_expr(TokenKind_star, idx, ast_new_int(type_sizeof(ret->ty->base))); - ret = ast_new_deref_expr(ast_new_binary_expr(TokenKind_plus, ret, idx)); - } else if (consume_token_if(p, TokenKind_dot)) { - const char* name = parse_ident(p); - ret = ast_new_member_access_expr(ast_new_ref_expr(ret), name); - } else if (consume_token_if(p, TokenKind_arrow)) { - const char* name = parse_ident(p); - ret = ast_new_member_access_expr(ret, name); - } else if (consume_token_if(p, TokenKind_plusplus)) { - ret = create_new_postfix_inc_or_dec(p, ret, TokenKind_plusplus); - } else if (consume_token_if(p, TokenKind_minusminus)) { - ret = create_new_postfix_inc_or_dec(p, ret, TokenKind_minusminus); - } else { - break; - } - } - return ret; -} - -BOOL is_type_token(Parser* p, Token* token) { - if (token->kind == TokenKind_keyword_int || token->kind == TokenKind_keyword_short || - token->kind == TokenKind_keyword_long || token->kind == TokenKind_keyword_char || - token->kind == TokenKind_keyword_void || token->kind == TokenKind_keyword_enum || - token->kind == TokenKind_keyword_struct || token->kind == TokenKind_keyword_union || - token->kind == TokenKind_keyword_const) { - return TRUE; - } - if (token->kind != TokenKind_ident) { - return FALSE; - } - return find_typedef(p, token->value.string) != -1; -} - -Type* parse_type(Parser* p) { - Token* t = next_token(p); - if (t->kind == TokenKind_keyword_const) { - t = next_token(p); - } - if (!is_type_token(p, t)) { - fatal_error("%s:%d: parse_type: expected type, but got '%s'", t->loc.filename, t->loc.line, token_stringify(t)); - } - Type* ty; - if (t->kind == TokenKind_ident) { - int typedef_idx = find_typedef(p, t->value.string); - if (typedef_idx == -1) { - fatal_error("parse_type: unknown typedef, %s", t->value.string); - } - ty = p->typedefs[typedef_idx].ty; - } else { - ty = type_new(TypeKind_unknown); - if (t->kind == TokenKind_keyword_char) { - ty->kind = TypeKind_char; - } else if (t->kind == TokenKind_keyword_short) { - ty->kind = TypeKind_short; - } else if (t->kind == TokenKind_keyword_int) { - ty->kind = TypeKind_int; - } else if (t->kind == TokenKind_keyword_long) { - ty->kind = TypeKind_long; - } else if (t->kind == TokenKind_keyword_void) { - ty->kind = TypeKind_void; - } else if (t->kind == TokenKind_keyword_enum) { - ty->kind = TypeKind_enum; - const char* name = parse_ident(p); - int enum_idx = find_enum(p, name); - if (enum_idx == -1) { - fatal_error("parse_type: unknown enum, %s", name); - } - ty->def = p->enums + enum_idx; - } else if (t->kind == TokenKind_keyword_struct) { - ty->kind = TypeKind_struct; - const char* name = parse_ident(p); - int struct_idx = find_struct(p, name); - if (struct_idx == -1) { - fatal_error("parse_type: unknown struct, %s", name); - } - ty->def = p->structs + struct_idx; - } else if (t->kind == TokenKind_keyword_union) { - ty->kind = TypeKind_union; - const char* name = parse_ident(p); - int union_idx = find_union(p, name); - if (union_idx == -1) { - fatal_error("parse_type: unknown union, %s", name); - } - ty->def = p->unions + union_idx; - } else { - unreachable(); - } - } - while (1) { - if (!consume_token_if(p, TokenKind_star)) { - break; - } - ty = type_new_ptr(ty); - } - return ty; -} - -AstNode* parse_prefix_expr(Parser* p) { - TokenKind op = peek_token(p)->kind; - if (consume_token_if(p, TokenKind_minus)) { - AstNode* operand = parse_prefix_expr(p); - return ast_new_binary_expr(op, ast_new_int(0), operand); - } else if (consume_token_if(p, TokenKind_not)) { - AstNode* operand = parse_prefix_expr(p); - return ast_new_unary_expr(op, operand); - } else if (consume_token_if(p, TokenKind_and)) { - AstNode* operand = parse_prefix_expr(p); - return ast_new_ref_expr(operand); - } else if (consume_token_if(p, TokenKind_star)) { - AstNode* operand = parse_prefix_expr(p); - return ast_new_deref_expr(operand); - } else if (consume_token_if(p, TokenKind_plusplus)) { - AstNode* operand = parse_prefix_expr(p); - return ast_new_assign_add_expr(operand, ast_new_int(1)); - } else if (consume_token_if(p, TokenKind_minusminus)) { - AstNode* operand = parse_prefix_expr(p); - return ast_new_assign_sub_expr(operand, ast_new_int(1)); - } else if (consume_token_if(p, TokenKind_keyword_sizeof)) { - expect(p, TokenKind_paren_l); - Token* next_tok = peek_token(p); - Type* ty = NULL; - if (next_tok->kind == TokenKind_ident) { - int lvar_idx = find_lvar(p, next_tok->value.string); - if (lvar_idx != -1) { - next_token(p); - ty = p->lvars[lvar_idx].ty; - } - int gvar_idx = find_gvar(p, next_tok->value.string); - if (gvar_idx != -1) { - next_token(p); - ty = p->gvars[gvar_idx].ty; - } - } - if (!ty) { - ty = parse_type(p); - } - expect(p, TokenKind_paren_r); - return ast_new_int(type_sizeof(ty)); - } - return parse_postfix_expr(p); -} - -AstNode* parse_multiplicative_expr(Parser* p) { - AstNode* lhs = parse_prefix_expr(p); - while (1) { - TokenKind op = peek_token(p)->kind; - if (op == TokenKind_star || op == TokenKind_slash || op == TokenKind_percent) { - next_token(p); - AstNode* rhs = parse_prefix_expr(p); - lhs = ast_new_binary_expr(op, lhs, rhs); - } else { - break; - } - } - return lhs; -} - -AstNode* parse_additive_expr(Parser* p) { - AstNode* lhs = parse_multiplicative_expr(p); - while (1) { - if (consume_token_if(p, TokenKind_plus)) { - AstNode* rhs = parse_multiplicative_expr(p); - if (lhs->ty->base) { - lhs = ast_new_binary_expr( - TokenKind_plus, lhs, - ast_new_binary_expr(TokenKind_star, rhs, ast_new_int(type_sizeof(lhs->ty->base)))); - } else if (rhs->ty->base) { - lhs = ast_new_binary_expr( - TokenKind_plus, ast_new_binary_expr(TokenKind_star, lhs, ast_new_int(type_sizeof(rhs->ty->base))), - rhs); - } else { - lhs = ast_new_binary_expr(TokenKind_plus, lhs, rhs); - } - } else if (consume_token_if(p, TokenKind_minus)) { - AstNode* rhs = parse_multiplicative_expr(p); - if (lhs->ty->base) { - if (rhs->ty->base) { - // (a - b) / sizeof(a) - lhs = ast_new_binary_expr(TokenKind_slash, ast_new_binary_expr(TokenKind_minus, lhs, rhs), - ast_new_int(type_sizeof(lhs->ty->base))); - } else { - // a - b*sizeof(a) - lhs = ast_new_binary_expr( - TokenKind_minus, lhs, - ast_new_binary_expr(TokenKind_star, rhs, ast_new_int(type_sizeof(lhs->ty->base)))); - } - } else { - lhs = ast_new_binary_expr(TokenKind_minus, lhs, rhs); - } - } else { - break; - } - } - return lhs; -} - -AstNode* parse_shift_expr(Parser* p) { - AstNode* lhs = parse_additive_expr(p); - while (1) { - TokenKind op = peek_token(p)->kind; - if (op == TokenKind_lshift || op == TokenKind_rshift) { - next_token(p); - AstNode* rhs = parse_additive_expr(p); - lhs = ast_new_binary_expr(op, lhs, rhs); - } else { - break; - } - } - return lhs; -} - -AstNode* parse_relational_expr(Parser* p) { - AstNode* lhs = parse_shift_expr(p); - while (1) { - TokenKind op = peek_token(p)->kind; - if (op == TokenKind_lt || op == TokenKind_le) { - next_token(p); - AstNode* rhs = parse_shift_expr(p); - lhs = ast_new_binary_expr(op, lhs, rhs); - } else if (consume_token_if(p, TokenKind_gt)) { - AstNode* rhs = parse_shift_expr(p); - lhs = ast_new_binary_expr(TokenKind_lt, rhs, lhs); - } else if (consume_token_if(p, TokenKind_ge)) { - AstNode* rhs = parse_shift_expr(p); - lhs = ast_new_binary_expr(TokenKind_le, rhs, lhs); - } else { - break; - } - } - return lhs; -} - -AstNode* parse_equality_expr(Parser* p) { - AstNode* lhs = parse_relational_expr(p); - while (1) { - TokenKind op = peek_token(p)->kind; - if (op == TokenKind_eq || op == TokenKind_ne) { - next_token(p); - AstNode* rhs = parse_relational_expr(p); - lhs = ast_new_binary_expr(op, lhs, rhs); - } else { - break; - } - } - return lhs; -} - -AstNode* parse_bitwise_or_expr(Parser* p) { - AstNode* lhs = parse_equality_expr(p); - while (1) { - TokenKind op = peek_token(p)->kind; - if (consume_token_if(p, TokenKind_or)) { - AstNode* rhs = parse_equality_expr(p); - lhs = ast_new_binary_expr(op, lhs, rhs); - lhs->ty = type_new(TypeKind_int); - } else { - break; - } - } - return lhs; -} - -AstNode* parse_logical_and_expr(Parser* p) { - AstNode* lhs = parse_bitwise_or_expr(p); - while (1) { - TokenKind op = peek_token(p)->kind; - if (consume_token_if(p, TokenKind_andand)) { - AstNode* rhs = parse_bitwise_or_expr(p); - AstNode* e = ast_new(AstNodeKind_logical_expr); - e->node_op = op; - e->node_lhs = lhs; - e->node_rhs = rhs; - e->ty = type_new(TypeKind_int); - lhs = e; - } else { - break; - } - } - return lhs; -} - -AstNode* parse_logical_or_expr(Parser* p) { - AstNode* lhs = parse_logical_and_expr(p); - while (1) { - TokenKind op = peek_token(p)->kind; - if (consume_token_if(p, TokenKind_oror)) { - AstNode* rhs = parse_logical_and_expr(p); - AstNode* e = ast_new(AstNodeKind_logical_expr); - e->node_op = op; - e->node_lhs = lhs; - e->node_rhs = rhs; - e->ty = type_new(TypeKind_int); - lhs = e; - } else { - break; - } - } - return lhs; -} - -AstNode* parse_conditional_expr(Parser* p) { - AstNode* e = parse_logical_or_expr(p); - if (consume_token_if(p, TokenKind_question)) { - AstNode* then_expr = parse_expr(p); - expect(p, TokenKind_colon); - AstNode* else_expr = parse_assignment_expr(p); - AstNode* ret = ast_new(AstNodeKind_cond_expr); - ret->node_cond = e; - ret->node_then = then_expr; - ret->node_else = else_expr; - ret->ty = then_expr->ty; - return ret; - } else { - return e; - } -} - -// constant-expression: -// conditional-expression -AstNode* parse_constant_expression(Parser* p) { - return parse_conditional_expr(p); -} - -AstNode* parse_assignment_expr(Parser* p) { - AstNode* lhs = parse_conditional_expr(p); - while (1) { - TokenKind op = peek_token(p)->kind; - // TODO: check if the lhs is unary expression. - if (op == TokenKind_assign || op == TokenKind_assign_mul || op == TokenKind_assign_div || - op == TokenKind_assign_mod) { - next_token(p); - AstNode* rhs = parse_assignment_expr(p); - lhs = ast_new_assign_expr(op, lhs, rhs); - } else if (consume_token_if(p, TokenKind_assign_add)) { - AstNode* rhs = parse_assignment_expr(p); - lhs = ast_new_assign_add_expr(lhs, rhs); - } else if (consume_token_if(p, TokenKind_assign_sub)) { - AstNode* rhs = parse_assignment_expr(p); - lhs = ast_new_assign_sub_expr(lhs, rhs); - } else { - break; - } - } - return lhs; -} - -AstNode* parse_comma_expr(Parser* p) { - AstNode* lhs = parse_assignment_expr(p); - while (1) { - TokenKind op = peek_token(p)->kind; - if (consume_token_if(p, TokenKind_comma)) { - AstNode* rhs = parse_assignment_expr(p); - AstNode* list = ast_new_list(2); - ast_append(list, lhs); - ast_append(list, rhs); - list->ty = rhs->ty; - lhs = list; - } else { - break; - } - } - return lhs; -} - -AstNode* parse_expr(Parser* p) { - return parse_comma_expr(p); -} - -AstNode* parse_return_stmt(Parser* p) { - expect(p, TokenKind_keyword_return); - if (consume_token_if(p, TokenKind_semicolon)) { - return ast_new(AstNodeKind_return_stmt); - } - - AstNode* expr = parse_expr(p); - expect(p, TokenKind_semicolon); - - AstNode* ret = ast_new(AstNodeKind_return_stmt); - ret->node_expr = expr; - return ret; -} - -AstNode* parse_if_stmt(Parser* p) { - expect(p, TokenKind_keyword_if); - expect(p, TokenKind_paren_l); - AstNode* cond = parse_expr(p); - expect(p, TokenKind_paren_r); - AstNode* then_body = parse_stmt(p); - AstNode* else_body = NULL; - if (consume_token_if(p, TokenKind_keyword_else)) { - else_body = parse_stmt(p); - } - - AstNode* stmt = ast_new(AstNodeKind_if_stmt); - stmt->node_cond = cond; - stmt->node_then = then_body; - stmt->node_else = else_body; - return stmt; -} - -// pointer: -// '*' TODO attribute-specifier-sequence_opt TODO type-qualifier-list_opt -// '*' TODO attribute-specifier-sequence_opt TODO type-qualifier-list_opt pointer -Type* parse_pointer_opt(Parser* p, Type* ty) { - while (peek_token(p)->kind == TokenKind_star) { - next_token(p); - ty = type_new_ptr(ty); - } - return ty; -} - -// array-declarator: -// direct-declarator '[' TODO type-qualifier-list_opt TODO assignment-expression_opt ']' -// TODO direct-declarator '[' 'static' type-qualifier-list_opt assignment-expression_opt ']' -// TODO direct-declarator '[' type-qualifier-list 'static' assignment-expression_opt ']' -// TODO direct-declarator '[' type-qualifier-list_opt '*' ']' -Type* parse_array_declarator_suffix(Parser* p, Type* ty) { - next_token(p); // skip '[' - - AstNode* size_expr = parse_expr(p); - if (size_expr->kind != AstNodeKind_int_expr) { - fatal_error("parse_var_decl: invalid array size"); - } - int size = size_expr->node_int_value; - expect(p, TokenKind_bracket_r); - - return type_new_array(ty, size); -} - -// direct-declarator: -// identifier TODO attribute-specifier-sequence_opt -// TODO '(' declarator ')' -// array-declarator TODO attribute-specifier-sequence_opt -// TODO function-declarator TODO attribute-specifier-sequence_opt -AstNode* parse_direct_declarator(Parser* p, Type* ty) { - const char* name = parse_ident(p); - while (1) { - if (peek_token(p)->kind == TokenKind_bracket_l) { - ty = parse_array_declarator_suffix(p, ty); - } else { - break; - } - } - - AstNode* ret = ast_new(AstNodeKind_declarator); - ret->name = name; - ret->ty = ty; - return ret; -} - -// declarator: -// pointer_opt direct-declarator -AstNode* parse_declarator(Parser* p, Type* ty) { - ty = parse_pointer_opt(p, ty); - return parse_direct_declarator(p, ty); -} - -// initializer: -// assignment-expression -// TODO braced-initializer -AstNode* parse_initializer(Parser* p) { - return parse_assignment_expr(p); -} - -// init-declarator: -// declarator -// declarator '=' initializer -AstNode* parse_init_declarator(Parser* p, Type* ty) { - AstNode* decl = parse_declarator(p, ty); - AstNode* init = NULL; - if (consume_token_if(p, TokenKind_assign)) { - init = parse_initializer(p); - } - decl->node_init = init; - return decl; -} - -// init-declarator-list: -// init-declarator -// init-declarator-list ',' init-declarator -AstNode* parse_init_declarator_list(Parser* p, Type* ty) { - AstNode* list = ast_new_list(1); - while (1) { - AstNode* d = parse_init_declarator(p, ty); - ast_append(list, d); - if (!consume_token_if(p, TokenKind_comma)) { - break; - } - } - return list; -} - -AstNode* parse_var_decl(Parser* p) { - Type* base_ty = parse_type(p); - if (type_is_unsized(base_ty)) { - fatal_error("parse_var_decl: invalid type for variable"); - } - - AstNode* decls = parse_init_declarator_list(p, base_ty); - expect(p, TokenKind_semicolon); - - for (int i = 0; i < decls->node_len; ++i) { - AstNode* decl = &decls->node_items[i]; - - if (find_lvar_in_current_scope(p, decl->name) != -1) { - // TODO: use name's location. - fatal_error("%s:%d: '%s' redeclared", peek_token(p)->loc.filename, peek_token(p)->loc.line, decl->name); - } - int stack_offset = add_lvar(p, decl->name, decl->ty, FALSE); - - if (decl->node_init) { - AstNode* lhs = ast_new(AstNodeKind_lvar); - lhs->name = decl->name; - lhs->node_stack_offset = stack_offset; - lhs->ty = decl->ty; - AstNode* assign = ast_new_assign_expr(TokenKind_assign, lhs, decl->node_init); - decl->kind = AstNodeKind_expr_stmt; - decl->node_expr = assign; - } else { - decl->kind = AstNodeKind_nop; - } - } - return decls; -} - -AstNode* parse_for_stmt(Parser* p) { - expect(p, TokenKind_keyword_for); - expect(p, TokenKind_paren_l); - AstNode* init = NULL; - AstNode* cond = NULL; - AstNode* update = NULL; - enter_scope(p); - if (peek_token(p)->kind != TokenKind_semicolon) { - if (is_type_token(p, peek_token(p))) { - init = parse_var_decl(p)->node_items[0].node_expr; - } else { - init = parse_expr(p); - expect(p, TokenKind_semicolon); - } - } else { - expect(p, TokenKind_semicolon); - } - if (peek_token(p)->kind != TokenKind_semicolon) { - cond = parse_expr(p); - } else { - cond = ast_new_int(1); - } - expect(p, TokenKind_semicolon); - if (peek_token(p)->kind != TokenKind_paren_r) { - update = parse_expr(p); - } - expect(p, TokenKind_paren_r); - AstNode* body = parse_stmt(p); - leave_scope(p); - - AstNode* stmt = ast_new(AstNodeKind_for_stmt); - stmt->node_cond = cond; - stmt->node_init = init; - stmt->node_update = update; - stmt->node_body = body; - return stmt; -} - -AstNode* parse_while_stmt(Parser* p) { - expect(p, TokenKind_keyword_while); - expect(p, TokenKind_paren_l); - AstNode* cond = parse_expr(p); - expect(p, TokenKind_paren_r); - AstNode* body = parse_stmt(p); - - AstNode* stmt = ast_new(AstNodeKind_for_stmt); - stmt->node_cond = cond; - stmt->node_body = body; - return stmt; -} - -AstNode* parse_do_while_stmt(Parser* p) { - expect(p, TokenKind_keyword_do); - AstNode* body = parse_stmt(p); - expect(p, TokenKind_keyword_while); - expect(p, TokenKind_paren_l); - AstNode* cond = parse_expr(p); - expect(p, TokenKind_paren_r); - expect(p, TokenKind_semicolon); - - AstNode* stmt = ast_new(AstNodeKind_do_while_stmt); - stmt->node_cond = cond; - stmt->node_body = body; - return stmt; -} - -AstNode* parse_break_stmt(Parser* p) { - expect(p, TokenKind_keyword_break); - expect(p, TokenKind_semicolon); - return ast_new(AstNodeKind_break_stmt); -} - -AstNode* parse_continue_stmt(Parser* p) { - expect(p, TokenKind_keyword_continue); - expect(p, TokenKind_semicolon); - return ast_new(AstNodeKind_continue_stmt); -} - -AstNode* parse_expr_stmt(Parser* p) { - AstNode* e = parse_expr(p); - expect(p, TokenKind_semicolon); - AstNode* stmt = ast_new(AstNodeKind_expr_stmt); - stmt->node_expr = e; - return stmt; -} - -AstNode* parse_block_stmt(Parser* p) { - AstNode* list = ast_new_list(4); - expect(p, TokenKind_brace_l); - enter_scope(p); - while (peek_token(p)->kind != TokenKind_brace_r) { - AstNode* stmt = parse_stmt(p); - ast_append(list, stmt); - } - leave_scope(p); - expect(p, TokenKind_brace_r); - return list; -} - -AstNode* parse_empty_stmt(Parser* p) { - consume_token_if(p, TokenKind_semicolon); - return ast_new(AstNodeKind_nop); -} - -AstNode* parse_stmt(Parser* p) { - Token* t = peek_token(p); - if (t->kind == TokenKind_keyword_return) { - return parse_return_stmt(p); - } else if (t->kind == TokenKind_keyword_if) { - return parse_if_stmt(p); - } else if (t->kind == TokenKind_keyword_for) { - return parse_for_stmt(p); - } else if (t->kind == TokenKind_keyword_while) { - return parse_while_stmt(p); - } else if (t->kind == TokenKind_keyword_do) { - return parse_do_while_stmt(p); - } else if (t->kind == TokenKind_keyword_break) { - return parse_break_stmt(p); - } else if (t->kind == TokenKind_keyword_continue) { - return parse_continue_stmt(p); - } else if (t->kind == TokenKind_brace_l) { - return parse_block_stmt(p); - } else if (t->kind == TokenKind_semicolon) { - return parse_empty_stmt(p); - } else if (is_type_token(p, t)) { - return parse_var_decl(p); - } else { - return parse_expr_stmt(p); - } -} - -void register_params(Parser* p, AstNode* params) { - for (int i = 0; i < params->node_len; ++i) { - AstNode* param = params->node_items + i; - add_lvar(p, param->name, param->ty, TRUE); - } -} - -void register_func(Parser* p, const char* name, Type* ty) { - p->funcs[p->n_funcs].name = name; - p->funcs[p->n_funcs].ty = ty; - ++p->n_funcs; -} - -AstNode* parse_param(Parser* p) { - Type* ty = parse_type(p); - const char* name = NULL; - TokenKind tk = peek_token(p)->kind; - if (tk != TokenKind_comma && tk != TokenKind_paren_r) { - name = parse_ident(p); - } - AstNode* param = ast_new(AstNodeKind_param); - param->ty = ty; - if (name) { - param->name = name; - } - return param; -} - -AstNode* parse_param_list(Parser* p) { - BOOL has_void = FALSE; - AstNode* list = ast_new_list(6); - while (peek_token(p)->kind != TokenKind_paren_r) { - if (consume_token_if(p, TokenKind_ellipsis)) { - break; - } - AstNode* param = parse_param(p); - has_void = has_void || param->ty->kind == TypeKind_void; - ast_append(list, param); - if (!consume_token_if(p, TokenKind_comma)) { - break; - } - } - if (list->node_len > 6) { - fatal_error("too many parameters"); - } - if (has_void) { - if (list->node_len != 1) { - fatal_error("invalid use of void param"); - } - list->node_len = 0; - } - return list; -} - -AstNode* parse_global_var_decl(Parser* p) { - Type* base_ty = parse_type(p); - if (type_is_unsized(base_ty)) { - fatal_error("parse_global_var_decl: invalid type for variable"); - } - - AstNode* decls = parse_init_declarator_list(p, base_ty); - expect(p, TokenKind_semicolon); - - for (int i = 0; i < decls->node_len; ++i) { - AstNode* decl = &decls->node_items[i]; - - if (find_gvar(p, decl->name) != -1) { - fatal_error("parse_global_var_decl: %s redeclared", decl->name); - } - p->gvars[p->n_gvars].name = decl->name; - p->gvars[p->n_gvars].ty = decl->ty; - ++p->n_gvars; - - decl->kind = AstNodeKind_gvar_decl; - decl->node_expr = decl->node_init; - } - return decls; -} - -AstNode* parse_func_decl_or_def(Parser* p) { - // TODO: remove it. - int start_pos = p->pos; - - Type* ty = parse_type(p); - const char* name = parse_ident(p); - - if (peek_token(p)->kind != TokenKind_paren_l) { - // TODO: avoid backtracking - p->pos = start_pos; - return parse_global_var_decl(p); - } - - expect(p, TokenKind_paren_l); - register_func(p, name, ty); - AstNode* params = parse_param_list(p); - expect(p, TokenKind_paren_r); - if (consume_token_if(p, TokenKind_semicolon)) { - return ast_new(AstNodeKind_func_decl); - } - enter_func(p); - register_params(p, params); - AstNode* body = parse_block_stmt(p); - leave_func(p); - AstNode* func = ast_new(AstNodeKind_func_def); - func->ty = ty; - func->name = name; - func->node_params = params; - func->node_body = body; - if (p->n_lvars == 0) { - func->node_stack_size = 0; - } else { - func->node_stack_size = p->lvars[p->n_lvars - 1].stack_offset + type_sizeof(p->lvars[p->n_lvars - 1].ty); - } - return func; -} - -AstNode* parse_struct_member(Parser* p) { - Type* ty = parse_type(p); - const char* name = parse_ident(p); - expect(p, TokenKind_semicolon); - AstNode* member = ast_new(AstNodeKind_struct_member); - member->name = name; - member->ty = ty; - return member; -} - -AstNode* parse_struct_members(Parser* p) { - AstNode* list = ast_new_list(4); - while (peek_token(p)->kind != TokenKind_brace_r) { - AstNode* member = parse_struct_member(p); - ast_append(list, member); - } - return list; -} - -AstNode* parse_struct_decl_or_def(Parser* p) { - expect(p, TokenKind_keyword_struct); - const char* name = parse_ident(p); - - if (peek_token(p)->kind != TokenKind_semicolon && peek_token(p)->kind != TokenKind_brace_l) { - p->pos = p->pos - 2; - return parse_func_decl_or_def(p); - } - - int struct_idx = find_struct(p, name); - if (struct_idx == -1) { - struct_idx = p->n_structs; - p->structs[struct_idx].kind = AstNodeKind_struct_def; - p->structs[struct_idx].name = name; - ++p->n_structs; - } - if (consume_token_if(p, TokenKind_semicolon)) { - return ast_new(AstNodeKind_struct_decl); - } - if (p->structs[struct_idx].node_members) { - fatal_error("parse_struct_decl_or_def: struct %s redefined", name); - } - expect(p, TokenKind_brace_l); - AstNode* members = parse_struct_members(p); - expect(p, TokenKind_brace_r); - expect(p, TokenKind_semicolon); - p->structs[struct_idx].node_members = members; - return p->structs + struct_idx; -} - -AstNode* parse_union_member(Parser* p) { - Type* ty = parse_type(p); - const char* name = parse_ident(p); - expect(p, TokenKind_semicolon); - AstNode* member = ast_new(AstNodeKind_union_member); - member->name = name; - member->ty = ty; - return member; -} - -AstNode* parse_union_members(Parser* p) { - AstNode* list = ast_new_list(4); - while (peek_token(p)->kind != TokenKind_brace_r) { - AstNode* member = parse_union_member(p); - ast_append(list, member); - } - return list; -} - -AstNode* parse_union_decl_or_def(Parser* p) { - expect(p, TokenKind_keyword_union); - const char* name = parse_ident(p); - - if (peek_token(p)->kind != TokenKind_semicolon && peek_token(p)->kind != TokenKind_brace_l) { - p->pos = p->pos - 2; - return parse_func_decl_or_def(p); - } - - int union_idx = find_union(p, name); - if (union_idx == -1) { - union_idx = p->n_unions; - p->unions[union_idx].kind = AstNodeKind_union_def; - p->unions[union_idx].name = name; - ++p->n_unions; - } - if (consume_token_if(p, TokenKind_semicolon)) { - return ast_new(AstNodeKind_union_decl); - } - if (p->unions[union_idx].node_members) { - fatal_error("parse_union_decl_or_def: union %s redefined", name); - } - expect(p, TokenKind_brace_l); - AstNode* members = parse_union_members(p); - expect(p, TokenKind_brace_r); - expect(p, TokenKind_semicolon); - p->unions[union_idx].node_members = members; - return p->unions + union_idx; -} - -AstNode* parse_enum_member(Parser* p) { - const char* name = parse_ident(p); - AstNode* member = ast_new(AstNodeKind_enum_member); - member->name = name; - return member; -} - -AstNode* parse_enum_members(Parser* p) { - int next_value = 0; - AstNode* list = ast_new_list(16); - while (peek_token(p)->kind != TokenKind_brace_r) { - AstNode* member = parse_enum_member(p); - member->node_int_value = next_value; - ++next_value; - ast_append(list, member); - if (!consume_token_if(p, TokenKind_comma)) { - break; - } - } - return list; -} - -AstNode* parse_enum_def(Parser* p) { - expect(p, TokenKind_keyword_enum); - const char* name = parse_ident(p); - - if (peek_token(p)->kind != TokenKind_brace_l) { - p->pos = p->pos - 2; - return parse_func_decl_or_def(p); - } - - int enum_idx = find_enum(p, name); - if (enum_idx == -1) { - enum_idx = p->n_enums; - p->enums[enum_idx].kind = AstNodeKind_enum_def; - p->enums[enum_idx].name = name; - ++p->n_enums; - } else { - fatal_error("parse_enum_def: enum %s redefined", name); - } - expect(p, TokenKind_brace_l); - AstNode* members = parse_enum_members(p); - expect(p, TokenKind_brace_r); - expect(p, TokenKind_semicolon); - p->enums[enum_idx].node_members = members; - return p->enums + enum_idx; -} - -AstNode* parse_typedef_decl(Parser* p) { - expect(p, TokenKind_keyword_typedef); - Type* ty = parse_type(p); - const char* name = parse_ident(p); - expect(p, TokenKind_semicolon); - AstNode* decl = ast_new(AstNodeKind_typedef_decl); - decl->name = name; - decl->ty = ty; - p->typedefs[p->n_typedefs].name = name; - p->typedefs[p->n_typedefs].ty = ty; - ++p->n_typedefs; - return decl; -} - -AstNode* parse_extern_var_decl(Parser* p) { - expect(p, TokenKind_keyword_extern); - Type* ty = parse_type(p); - if (type_is_unsized(ty)) { - fatal_error("parse_extern_var_decl: invalid type for variable"); - } - const char* name = parse_ident(p); - expect(p, TokenKind_semicolon); - - if (find_lvar(p, name) != -1 || find_gvar(p, name) != -1) { - fatal_error("parse_extern_var_decl: %s redeclared", name); - } - p->gvars[p->n_gvars].name = name; - p->gvars[p->n_gvars].ty = ty; - ++p->n_gvars; - - return ast_new(AstNodeKind_gvar_decl); -} - -AstNode* parse_toplevel(Parser* p) { - TokenKind tk = peek_token(p)->kind; - if (tk == TokenKind_keyword_struct) { - return parse_struct_decl_or_def(p); - } else if (tk == TokenKind_keyword_union) { - return parse_union_decl_or_def(p); - } else if (tk == TokenKind_keyword_enum) { - return parse_enum_def(p); - } else if (tk == TokenKind_keyword_typedef) { - return parse_typedef_decl(p); - } else if (tk == TokenKind_keyword_extern) { - return parse_extern_var_decl(p); - } else { - return parse_func_decl_or_def(p); - } -} - -Program* parse(TokenArray* tokens) { - Parser* p = parser_new(tokens); - AstNode* funcs = ast_new_list(32); - AstNode* vars = ast_new_list(16); - while (eof(p)) { - AstNode* n = parse_toplevel(p); - if (n->kind == AstNodeKind_func_def) { - ast_append(funcs, n); - } else if (n->kind == AstNodeKind_gvar_decl && n->ty) { - ast_append(vars, n); - } else if (n->kind == AstNodeKind_list) { - for (int i = 0; i < n->node_len; ++i) { - ast_append(vars, &n->node_items[i]); - } - } - } - Program* prog = calloc(1, sizeof(Program)); - prog->funcs = funcs; - prog->vars = vars; - prog->str_literals = p->str_literals; - return prog; -} - -int eval(AstNode* e) { - if (e->kind == AstNodeKind_int_expr) { - return e->node_int_value; - } else if (e->kind == AstNodeKind_unary_expr) { - int v = eval(e->node_operand); - if (e->node_op == TokenKind_not) { - return !v; - } else { - unimplemented(); - } - } else if (e->kind == AstNodeKind_binary_expr || e->kind == AstNodeKind_logical_expr) { - int v1 = eval(e->node_lhs); - int v2 = eval(e->node_rhs); - if (e->node_op == TokenKind_andand) { - return v1 && v2; - } else if (e->node_op == TokenKind_oror) { - return v1 || v2; - } else { - unimplemented(); - } - } else { - unimplemented(); - } -} - -BOOL pp_eval_constant_expression(TokenArray* pp_tokens) { - TokenArray* tokens = tokenize(pp_tokens); - Parser* p = parser_new(tokens); - AstNode* e = parse_constant_expression(p); - return eval(e) != 0; -} |