parser.c (14902B)
1 #include "lexer.h" 2 #include "parser.h" 3 4 int binop_precedence[] = { 5 [BINOP_INVALID] = 250, 6 [BINOP_ADD] = 20, 7 [BINOP_SUB] = 20, 8 [BINOP_MUL] = 10, 9 [BINOP_DIV] = 10, 10 [BINOP_MOD] = 10, 11 [BINOP_BAND] = 60, 12 [BINOP_BOR] = 80, 13 [BINOP_BXOR] = 70, 14 [BINOP_LSHIFT] = 30, 15 [BINOP_RSHIFT] = 30, 16 [BINOP_ASSIGN] = 121, 17 [BINOP_ADD_ASSIGN] = 121, 18 [BINOP_SUB_ASSIGN] = 121, 19 [BINOP_MUL_ASSIGN] = 121, 20 [BINOP_DIV_ASSIGN] = 121, 21 [BINOP_MOD_ASSIGN] = 121, 22 [BINOP_BAND_ASSIGN] = 121, 23 [BINOP_BOR_ASSIGN] = 121, 24 [BINOP_BXOR_ASSIGN] = 121, 25 [BINOP_LSHIFT_ASSIGN] = 121, 26 [BINOP_RSHIFT_ASSIGN] = 121, 27 [BINOP_LAND] = 90, 28 [BINOP_LOR] = 110, 29 [BINOP_LXOR] = 100, 30 [BINOP_LT] = 40, 31 [BINOP_LE] = 40, 32 [BINOP_EQ] = 50, 33 [BINOP_NEQ] = 50, 34 [BINOP_GE] = 40, 35 [BINOP_GT] = 40, 36 [BINOP_COMMA] = 130, 37 [BINOP_ALL_] = 140, 38 }; 39 40 Ast_node * 41 new_ast_node(Parser *p, Ast_kind kind, Token loc) 42 { 43 Ast_node *result = p->ast_alloc(); 44 result->kind = kind; 45 result->start_tok = loc; 46 return result; 47 } 48 49 Ast_node * 50 parse_postfix(Parser *p, Ast_node *child) 51 { 52 (void) p; 53 return child; 54 } 55 56 Ast_node * 57 parse_primitive(Parser *p) 58 { 59 Ast_node *result; 60 Token t = next_token(&p->lexer); 61 if (t.kind == T_NUMBER) { 62 result = new_ast_node(p, AST_NUMBER, t); 63 } else if (t.kind == T_IDENT) { 64 result = new_ast_node(p, AST_IDENT, t); 65 } else if (t.kind == '(') { 66 result = parse_expression(p); 67 expect_token_kind(&p->lexer, ')'); 68 } else { 69 Sb sb = {0}; 70 sb_append_loc(&sb, t.loc); 71 sb_append_cstr(&sb, "Error: invalid primitive "); 72 sb_append_token_kind(&sb, t.kind); 73 sb_append_char(&sb, '\n'); 74 sb_write(2, sb); 75 sb_release(&sb); 76 abort(); 77 } 78 return parse_postfix(p, result); 79 } 80 81 Ast_node * 82 parse_prefix(Parser *p) 83 { 84 Ast_node *result = parse_primitive(p); 85 return result; 86 } 87 88 Binop 89 collect_binop(Parser *p) 90 { 91 Lexer saved_lexer; 92 Token peek = peek_token(&p->lexer); 93 Binop result = { .tok = peek }; 94 switch((int) peek.kind) { 95 case '+': 96 next_token(&p->lexer); 97 peek = peek_token(&p->lexer); 98 if (peek.kind == '=') { 99 next_token(&p->lexer); 100 result.kind = BINOP_ADD_ASSIGN; 101 result.tok.sv.count++; 102 } else { 103 result.kind = BINOP_ADD; 104 } 105 break; 106 case '-': 107 next_token(&p->lexer); 108 peek = peek_token(&p->lexer); 109 if (peek.kind == '=') { 110 next_token(&p->lexer); 111 result.kind = BINOP_SUB_ASSIGN; 112 result.tok.sv.count++; 113 } else { 114 result.kind = BINOP_SUB; 115 } 116 break; 117 case '*': 118 next_token(&p->lexer); 119 peek = peek_token(&p->lexer); 120 if (peek.kind == '=') { 121 next_token(&p->lexer); 122 result.kind = BINOP_MUL_ASSIGN; 123 result.tok.sv.count++; 124 } else { 125 result.kind = BINOP_MUL; 126 } 127 break; 128 case '/': 129 next_token(&p->lexer); 130 peek = peek_token(&p->lexer); 131 if (peek.kind == '=') { 132 next_token(&p->lexer); 133 result.kind = BINOP_DIV_ASSIGN; 134 result.tok.sv.count++; 135 } else { 136 result.kind = BINOP_DIV; 137 } 138 break; 139 case '%': 140 next_token(&p->lexer); 141 peek = peek_token(&p->lexer); 142 if (peek.kind == '=') { 143 next_token(&p->lexer); 144 result.kind = BINOP_MOD_ASSIGN; 145 result.tok.sv.count++; 146 } else { 147 result.kind = BINOP_MOD; 148 } 149 break; 150 case '&': 151 next_token(&p->lexer); 152 peek = peek_token(&p->lexer); 153 if (peek.kind == '=') { 154 next_token(&p->lexer); 155 result.kind = BINOP_BAND_ASSIGN; 156 result.tok.sv.count++; 157 } else if (peek.kind == '&') { 158 next_token(&p->lexer); 159 result.kind = BINOP_LAND; 160 result.tok.sv.count++; 161 } else { 162 result.kind = BINOP_BAND; 163 } 164 break; 165 case '|': 166 next_token(&p->lexer); 167 peek = peek_token(&p->lexer); 168 if (peek.kind == '=') { 169 next_token(&p->lexer); 170 result.kind = BINOP_BOR_ASSIGN; 171 result.tok.sv.count++; 172 } else if (peek.kind == '|') { 173 next_token(&p->lexer); 174 result.kind = BINOP_LOR; 175 result.tok.sv.count++; 176 } else { 177 result.kind = BINOP_BOR; 178 } 179 break; 180 case '^': 181 next_token(&p->lexer); 182 peek = peek_token(&p->lexer); 183 if (peek.kind == '=') { 184 next_token(&p->lexer); 185 result.kind = BINOP_BXOR_ASSIGN; 186 result.tok.sv.count++; 187 } else if (peek.kind == '^') { 188 next_token(&p->lexer); 189 result.kind = BINOP_LXOR; 190 result.tok.sv.count++; 191 } else { 192 result.kind = BINOP_BXOR; 193 } 194 break; 195 case '<': 196 next_token(&p->lexer); 197 peek = peek_token(&p->lexer); 198 if (peek.kind == '=') { 199 next_token(&p->lexer); 200 result.kind = BINOP_LE; 201 result.tok.sv.count++; 202 } else if (peek.kind == '<') { 203 next_token(&p->lexer); 204 peek = peek_token(&p->lexer); 205 if (peek.kind == '=') { 206 next_token(&p->lexer); 207 result.kind = BINOP_LSHIFT_ASSIGN; 208 result.tok.sv.count++; 209 } else { 210 result.kind = BINOP_LSHIFT; 211 result.tok.sv.count++; 212 } 213 } else { 214 result.kind = BINOP_LT; 215 } 216 break; 217 case '>': 218 next_token(&p->lexer); 219 peek = peek_token(&p->lexer); 220 if (peek.kind == '=') { 221 next_token(&p->lexer); 222 result.kind = BINOP_GE; 223 result.tok.sv.count++; 224 } else if (peek.kind == '>') { 225 next_token(&p->lexer); 226 peek = peek_token(&p->lexer); 227 if (peek.kind == '=') { 228 next_token(&p->lexer); 229 result.kind = BINOP_RSHIFT_ASSIGN; 230 result.tok.sv.count++; 231 } else { 232 result.kind = BINOP_RSHIFT; 233 result.tok.sv.count++; 234 } 235 } else { 236 result.kind = BINOP_GT; 237 } 238 break; 239 case '=': 240 next_token(&p->lexer); 241 peek = peek_token(&p->lexer); 242 if (peek.kind == '=') { 243 next_token(&p->lexer); 244 result.kind = BINOP_EQ; 245 result.tok.sv.count++; 246 } else { 247 result.kind = BINOP_ASSIGN; 248 } 249 break; 250 case '!': 251 saved_lexer = p->lexer; 252 next_token(&p->lexer); 253 peek = peek_token(&p->lexer); 254 if (peek.kind == '=') { 255 next_token(&p->lexer); 256 result.kind = BINOP_NEQ; 257 result.tok.sv.count++; 258 } else { 259 p->lexer = saved_lexer; 260 result.kind = BINOP_INVALID; 261 } 262 break; 263 case ',': 264 next_token(&p->lexer); 265 result.kind = BINOP_COMMA; 266 break; 267 default: 268 result.kind = BINOP_INVALID; 269 break; 270 } 271 return result; 272 } 273 274 Ast_node * 275 parse_binop(Parser *p, int precedence, Ast_node *left_child) 276 { 277 Lexer saved_lexer; 278 Ast_node *left; 279 Ast_node *right = NULL; 280 Ast_node *result; 281 Binop binop; 282 int next_prec; 283 if (!left_child) { 284 left = parse_prefix(p); 285 } else { 286 left = left_child; 287 } 288 do { 289 saved_lexer = p->lexer; 290 skip_whitespace(&p->lexer); 291 Binop binop_peek = collect_binop(p); 292 next_prec = binop_precedence[binop_peek.kind]; 293 if (binop_peek.kind == BINOP_INVALID) { 294 break; 295 } 296 if (next_prec > precedence) { 297 p->lexer = saved_lexer; 298 break; 299 } 300 if (next_prec < precedence) { 301 p->lexer = saved_lexer; 302 skip_whitespace(&p->lexer); 303 if (right) { 304 right = parse_binop(p, next_prec, right); 305 } else { 306 left = parse_binop(p, next_prec, left); 307 } 308 continue; 309 } 310 skip_whitespace(&p->lexer); 311 if (right) { 312 result = new_ast_node(p, AST_BINOP, binop.tok); 313 result->binop.op = binop; 314 result->binop.left = left; 315 result->binop.right = right; 316 left = result; 317 } 318 binop = binop_peek; 319 if (next_prec & 1) { 320 right = parse_binop(p, next_prec, NULL); 321 } else { 322 right = parse_prefix(p); 323 } 324 } while (1); 325 if (right) { 326 result = new_ast_node(p, AST_BINOP, binop.tok); 327 result->binop.op = binop; 328 result->binop.left = left; 329 result->binop.right = right; 330 left = result; 331 } 332 return left; 333 } 334 335 Ast_node * 336 parse_expression(Parser *p) 337 { 338 Ast_node *result = parse_binop(p, binop_precedence[BINOP_ALL_], NULL); 339 return result; 340 } 341 342 Ast_node * 343 parse_type(Parser *p) 344 { 345 Token base = expect_token_kind(&p->lexer, T_IDENT); 346 return new_ast_node(p, AST_TYPE, base); 347 } 348 349 Ast_node * 350 parse_var_declaration(Parser *p) 351 { 352 Token var_name; 353 Ast_node *var_type = NULL; 354 Ast_node *var_value = NULL; 355 Ast_node *result; 356 357 var_name = expect_token_kind(&p->lexer, T_IDENT); 358 skip_whitespace(&p->lexer); 359 expect_token_kind(&p->lexer, ':'); 360 skip_whitespace(&p->lexer); 361 if (peek_token(&p->lexer).kind != '=') { 362 var_type = parse_type(p); 363 skip_whitespace(&p->lexer); 364 } 365 if (peek_token(&p->lexer).kind == '=') { 366 next_token(&p->lexer); 367 skip_whitespace(&p->lexer); 368 var_value = parse_expression(p); 369 } 370 result = new_ast_node(p, AST_VAR_DECL, var_name); 371 result->var.name = var_name; 372 result->var.type = var_type; 373 result->var.value = var_value; 374 375 return result; 376 } 377 378 Ast_node * 379 parse_var_declaration_statement(Parser *p) { 380 Token start_tok; 381 start_tok = expect_token_kind(&p->lexer, T_VAR); 382 383 skip_whitespace(&p->lexer); 384 Ast_node *result = parse_var_declaration(p); 385 386 skip_whitespace(&p->lexer); 387 expect_token_kind(&p->lexer, ';'); 388 389 result->start_tok = start_tok; 390 return result; 391 } 392 393 Ast_node * 394 parse_block(Parser *p) 395 { 396 Token end_tok; 397 Token start_tok = expect_token_kind(&p->lexer, '{'); 398 skip_whitespace(&p->lexer); 399 Ast_node *node, *result; 400 Ast_node_list list = {0}; 401 Token peek; 402 skip_whitespace(&p->lexer); 403 while ((peek = peek_token(&p->lexer)).kind != '}') { 404 if (peek.kind == T_VAR) { 405 node = parse_var_declaration_statement(p); 406 } else if (peek.kind == ';') { 407 next_token(&p->lexer); 408 skip_whitespace(&p->lexer); 409 continue; 410 } else if (peek.kind == '{') { 411 node = parse_block(p); 412 } else if (peek.kind == T_EOF) { 413 // Leaking nodes 414 free(list.items); 415 416 print_loc(start_tok.loc); 417 fprintf(stderr, "Error: unterminated block\n"); 418 return new_ast_node(p, AST_ERROR, peek); 419 } else if (peek.kind == T_ERROR_) { 420 // Leaking nodes 421 free(list.items); 422 return new_ast_node(p, AST_ERROR, peek); 423 } else { 424 node = parse_expression(p); 425 expect_token_kind(&p->lexer, ';'); 426 } 427 da_append(&list, node); 428 skip_whitespace(&p->lexer); 429 } 430 end_tok = expect_token_kind(&p->lexer, '}'); 431 result = new_ast_node(p, AST_BLOCK, start_tok); 432 result->block.list = list; 433 result->block.end_tok = end_tok; 434 return result; 435 } 436 437 Ast_node_list 438 parse_func_arg_declaraction_list(Parser *p) 439 { 440 Token peek; 441 Ast_node *node; 442 Ast_node_list list = {0}; 443 while ((peek = peek_token(&p->lexer)).kind != ')') { 444 node = parse_var_declaration(p); 445 da_append(&list, node); 446 skip_whitespace(&p->lexer); 447 } 448 return list; 449 } 450 451 Ast_node * 452 parse_func_declaration_statement(Parser *p) 453 { 454 Ast_node *ret_type = NULL; 455 Ast_node *result; 456 Token start_tok = expect_token_kind(&p->lexer, T_FUNC); 457 skip_whitespace(&p->lexer); 458 Token name = expect_token_kind(&p->lexer, T_IDENT); 459 460 skip_whitespace(&p->lexer); 461 expect_token_kind(&p->lexer, '('); 462 skip_whitespace(&p->lexer); 463 Ast_node_list arg_list = parse_func_arg_declaraction_list(p); 464 expect_token_kind(&p->lexer, ')'); 465 466 skip_whitespace(&p->lexer); 467 if (peek_token(&p->lexer).kind == '-') { 468 expect_token_kind(&p->lexer, '-'); 469 expect_token_kind(&p->lexer, '>'); 470 skip_whitespace(&p->lexer); 471 ret_type = parse_type(p); 472 skip_whitespace(&p->lexer); 473 } 474 475 Ast_node *body = parse_block(p); 476 477 result = new_ast_node(p, AST_FUNC_DECL, start_tok); 478 result->func.body = body; 479 result->func.ret_type = ret_type; 480 result->func.name = name; 481 result->func.arg_list = arg_list; 482 return result; 483 } 484 485 Ast_node_list 486 parse(Parser *p) 487 { 488 Ast_node *node; 489 Ast_node_list list = {0}; 490 Token peek; 491 skip_whitespace(&p->lexer); 492 while ((peek = peek_token(&p->lexer)).kind != T_EOF) { 493 if (peek.kind == T_VAR) { 494 node = parse_var_declaration_statement(p); 495 } else if (peek.kind == T_FUNC) { 496 node = parse_func_declaration_statement(p); 497 } else if (peek.kind == T_ERROR_) { 498 abort(); 499 } else { 500 Sb sb = {0}; 501 sb_append_loc(&sb, peek.loc); 502 sb_append_cstr(&sb, "Error: invalid top level declaration at token "); 503 sb_append_token_kind(&sb, peek.kind); 504 sb_append_char(&sb, '\n'); 505 sb_write(2, sb); 506 sb_release(&sb); 507 abort(); 508 } 509 da_append(&list, node); 510 skip_whitespace(&p->lexer); 511 } 512 return list; 513 } 514 515 void 516 debug_print_ast_node(Ast_node *node, int indent) 517 { 518 if (!node) { 519 fprintf(stderr, "%*s", indent * 2, ""); 520 fprintf(stderr, "(null)"); 521 return; 522 } 523 int min_width = node->start_tok.loc.filename.count + 11; 524 print_loc_pad(node->start_tok.loc, min_width); 525 fprintf(stderr, "%*s", indent * 2, ""); 526 527 switch (node->kind) { 528 case AST_TYPE: 529 fprintf(stderr, "Type(%.*s)\n", (int) node->start_tok.sv.count, node->start_tok.sv.items); 530 break; 531 case AST_VAR_DECL: 532 fprintf(stderr, "VarDecl(%.*s)\n", (int) node->var.name.sv.count, node->var.name.sv.items); 533 if (node->var.type) { 534 debug_print_ast_node(node->var.type, indent + 1); 535 } 536 if (node->var.value) { 537 debug_print_ast_node(node->var.value, indent + 1); 538 } 539 break; 540 case AST_FUNC_DECL: 541 fprintf(stderr, "FuncDecl(%.*s)\n", (int) node->func.name.sv.count, node->func.name.sv.items); 542 if (node->func.ret_type) { 543 debug_print_ast_node(node->func.ret_type, indent + 1); 544 } 545 for (int i = 0; i < node->func.arg_list.count; ++i) { 546 debug_print_ast_node(node->func.arg_list.items[i], indent + 1); 547 } 548 debug_print_ast_node(node->func.body, indent + 1); 549 break; 550 case AST_TYPE_DECL: 551 fprintf(stderr, "TypeDecl\n"); 552 break; 553 case AST_BLOCK: 554 fprintf(stderr, "Block {\n"); 555 for (int i = 0; i < node->block.list.count; ++i) { 556 debug_print_ast_node(node->block.list.items[i], indent + 1); 557 } 558 print_loc_pad(node->block.end_tok.loc, min_width); 559 fprintf(stderr, "%*s\n", indent * 2, "}"); 560 break; 561 case AST_BINOP: 562 fprintf(stderr, "Binop(%.*s)\n", (int) node->binop.op.tok.sv.count, node->binop.op.tok.sv.items); 563 debug_print_ast_node(node->binop.left, indent + 1); 564 debug_print_ast_node(node->binop.right, indent + 1); 565 break; 566 case AST_NUMBER: 567 fprintf(stderr, "Number(%.*s)\n", (int) node->start_tok.sv.count, node->start_tok.sv.items); 568 break; 569 case AST_IDENT: 570 fprintf(stderr, "Ident(%.*s)\n", (int) node->start_tok.sv.count, node->start_tok.sv.items); 571 break; 572 case AST_ERROR: 573 fprintf(stderr, "Error\n"); 574 break; 575 default: 576 fprintf(stderr, "Unreachable\n"); 577 abort(); 578 } 579 }