lexer.c (17404B)
1 #include <fcntl.h> 2 3 #include "dlib.h" 4 #include "lexer.h" 5 6 Sv keywords[] = { 7 [T_RETURN - T_KEYWORDS_] = sv_literal("return"), 8 [T_EXTERN - T_KEYWORDS_] = sv_literal("extern"), 9 [T_I8 - T_KEYWORDS_] = sv_literal("i8"), 10 [T_I16 - T_KEYWORDS_] = sv_literal("i16"), 11 [T_I32 - T_KEYWORDS_] = sv_literal("i32"), 12 [T_I64 - T_KEYWORDS_] = sv_literal("i64"), 13 [T_PTR - T_KEYWORDS_] = sv_literal("ptr"), 14 [T_VOID - T_KEYWORDS_] = sv_literal("void"), 15 [T_LOAD - T_KEYWORDS_] = sv_literal("load"), 16 [T_STORE - T_KEYWORDS_] = sv_literal("store"), 17 [T_CALL - T_KEYWORDS_] = sv_literal("call"), 18 [T_SYSCALL - T_KEYWORDS_] = sv_literal("syscall"), 19 [T_JUMP - T_KEYWORDS_] = sv_literal("jump"), 20 [T_BRANCH - T_KEYWORDS_] = sv_literal("branch"), 21 [T_PHI - T_KEYWORDS_] = sv_literal("phi"), 22 }; 23 24 static_assert(T_COUNT_ - T_KEYWORDS_ == 15, "keywords[] wrong length"); 25 int keywords_count = (sizeof(keywords) / sizeof(keywords[0])); 26 27 void 28 sb_append_loc(Sb *sb, Loc loc) 29 { 30 sb_printf(sb, "%.*s:%li:%li: ", (int) loc.filename.count, loc.filename.items, loc.line, loc.column); 31 } 32 33 void 34 sb_append_token_kind(Sb *sb, Token_kind kind) 35 { 36 if (kind >= 32 && kind <= 127) sb_append_char(sb, kind); 37 else if (kind == T_ERROR_) sb_append_cstr(sb, "T_ERROR_"); 38 else if (kind == T_EOF) sb_append_cstr(sb, "T_EOF"); 39 else if (kind == T_INVALID) sb_append_cstr(sb, "T_INVALID"); 40 else if (kind == T_WHITESPACE) sb_append_cstr(sb, "T_WHITESPACE"); 41 else if (kind == T_WHITESPACE_NL) sb_append_cstr(sb, "T_WHITESPACE_NL"); 42 else if (kind == T_CONST_SYMBOL) sb_append_cstr(sb, "T_CONST_SYMBOL"); 43 else if (kind == T_VARIABLE_SYMBOL) sb_append_cstr(sb, "T_VARIABLE_SYMBOL"); 44 else if (kind == T_FUNCTION_SYMBOL) sb_append_cstr(sb, "T_FUNCTION_SYMBOL"); 45 else if (kind == T_LABEL) sb_append_cstr(sb, "T_LABEL"); 46 else if (kind == T_TEMP) sb_append_cstr(sb, "T_TEMP"); 47 else if (kind == T_ARROW) sb_append_cstr(sb, "->"); 48 else if (kind == T_RETURN) sb_append_cstr(sb, "return"); 49 else if (kind == T_EXTERN) sb_append_cstr(sb, "extern"); 50 else if (kind == T_I8) sb_append_cstr(sb, "i8"); 51 else if (kind == T_I16) sb_append_cstr(sb, "i16"); 52 else if (kind == T_I32) sb_append_cstr(sb, "i32"); 53 else if (kind == T_I64) sb_append_cstr(sb, "i64"); 54 else if (kind == T_PTR) sb_append_cstr(sb, "ptr"); 55 else if (kind == T_VOID) sb_append_cstr(sb, "void"); 56 else if (kind == T_LOAD) sb_append_cstr(sb, "load"); 57 else if (kind == T_STORE) sb_append_cstr(sb, "store"); 58 else if (kind == T_CALL) sb_append_cstr(sb, "call"); 59 else if (kind == T_SYSCALL) sb_append_cstr(sb, "syscall"); 60 else if (kind == T_JUMP) sb_append_cstr(sb, "jump"); 61 else if (kind == T_BRANCH) sb_append_cstr(sb, "branch"); 62 else if (kind == T_PHI) sb_append_cstr(sb, "phi"); 63 else sb_append_cstr(sb, "(unknown token)"); 64 } 65 66 void 67 print_loc(Loc loc) 68 { 69 fprintf(stderr, "%.*s:%li:%li: ", (int) loc.filename.count, loc.filename.items, loc.line, loc.column); 70 } 71 72 void 73 print_loc_pad(Loc loc, int min_width) 74 { 75 int len = fprintf(stderr, "%.*s:%li:%li: ", (int) loc.filename.count, loc.filename.items, loc.line, loc.column); 76 if (len < min_width) { 77 fprintf(stderr, "%*s", min_width - len, ""); 78 } 79 } 80 81 void 82 debug_print_token(Token t) 83 { 84 print_loc(t.loc); 85 if (t.kind == T_ERROR_) { 86 fprintf(stderr, "ERROR"); 87 } else if (t.kind >= 32 && t.kind < 127) { 88 fprintf(stderr, "'%c'", t.kind); 89 } else if (t.kind == T_EOF) { 90 fprintf(stderr, "EOF"); 91 } else if (t.kind == T_WHITESPACE || t.kind == T_WHITESPACE_NL) { 92 if (t.kind == T_WHITESPACE) { 93 fprintf(stderr, "WHITESPACE("); 94 } else { 95 fprintf(stderr, "WHITESPACE_NL("); 96 } 97 char last_char = '?'; 98 int last_char_count = 0; 99 for (int i = 0; i < t.sv.count; i++) { 100 char c = '?'; 101 switch (t.sv.items[i]) { 102 case ' ' : c = 's'; break; 103 case '\t': c = 't'; break; 104 case '\n': c = 'n'; break; 105 case '\r': c = 'r'; break; 106 case '\v': c = 'v'; break; 107 case '\f': c = 'f'; break; 108 } 109 if (last_char != c) { 110 if (last_char_count > 1) { 111 fprintf(stderr, "(%i)", last_char_count); 112 } 113 last_char_count = 0; 114 fputc(c, stderr); 115 } else if (!last_char_count) { 116 fputc(c, stderr); 117 } 118 last_char = c; 119 last_char_count++; 120 } 121 if (last_char_count > 1) { 122 fprintf(stderr, "(%i)", last_char_count); 123 } 124 fputc(')', stderr); 125 } else if (t.kind == T_IDENT) { 126 fprintf(stderr, "IDENT(%.*s)", (int) t.sv.count, t.sv.items); 127 } else if (t.kind == T_NUMBER) { 128 fprintf(stderr, "NUMBER(%.*s)", (int) t.sv.count, t.sv.items); 129 } else if (t.kind == T_SQ_STRING || t.kind == T_DQ_STRING) { 130 fprintf(stderr, "STRING(%.*s)", (int) t.sv.count, t.sv.items); 131 } else if (t.kind >= T_KEYWORDS_ && t.kind < T_COUNT_) { 132 Sv keyword = keywords[t.kind - T_KEYWORDS_]; 133 fprintf(stderr, "%.*s", (int) keyword.count, keyword.data); 134 } else { 135 fprintf(stderr, "unknown token 0x%02x", t.kind); 136 } 137 fprintf(stderr, "\n"); 138 } 139 140 int 141 next_utf8_continuation(Lexer *lexer) 142 { 143 if (!lexer->source.count) { 144 fprintf(stderr, "Error: expected utf-8 continuation byte\n"); 145 return CHAR_INVALID; 146 } 147 unsigned int c = *lexer->source.items++; 148 lexer->source.count--; 149 if ((c & 0b11000000) != 0b10000000) { 150 print_loc(lexer->current_loc); 151 fprintf(stderr, "Error: expected utf-8 continuation byte\n"); 152 return CHAR_INVALID; 153 } 154 return c & 0b00111111; 155 } 156 157 int 158 next_char(Lexer *lexer) 159 { 160 int result; 161 if (!lexer->source.count) return EOF; 162 unsigned int c0 = *lexer->source.items++; 163 int c1; 164 lexer->source.count--; 165 result = c0; 166 if (c0 == '\n') { 167 lexer->current_loc.column = 1; 168 lexer->current_loc.line++; 169 } else { 170 if (c0 > 127) { 171 if ((c0 & 0b11000000) != 0b11000000) { 172 print_loc(lexer->current_loc); 173 fprintf(stderr, "Error: invalid utf-8 character\n"); 174 return CHAR_INVALID; 175 } 176 c1 = next_utf8_continuation(lexer); 177 if (c1 == CHAR_INVALID) return CHAR_INVALID; 178 result = (c0 & 0b00011111) << 6 | c1; 179 180 if ((c0 & 0b11100000) == 0b11100000) { 181 c1 = next_utf8_continuation(lexer); 182 if (c1 == CHAR_INVALID) return CHAR_INVALID; 183 result = result << 6 | c1; 184 } 185 if ((c0 & 0b11110000) == 0b11110000) { 186 c1 = next_utf8_continuation(lexer); 187 if (c1 == CHAR_INVALID) return CHAR_INVALID; 188 result = result << 6 | c1; 189 } 190 if ((c0 & 0b11111000) == 0b11111000) { 191 c1 = next_utf8_continuation(lexer); 192 if (c1 == CHAR_INVALID) return CHAR_INVALID; 193 result = result << 6 | c1; 194 } 195 if ((c0 & 0b11111110) == 0b11111100) { 196 c1 = next_utf8_continuation(lexer); 197 if (c1 == CHAR_INVALID) return CHAR_INVALID; 198 result = result << 6 | c1; 199 } 200 } 201 lexer->current_loc.column++; 202 } 203 return result; 204 } 205 206 int 207 peek_char(Lexer *lexer) 208 { 209 if (!lexer->source.count || lexer->source.count == 1) return EOF; 210 return *lexer->source.items; 211 } 212 213 int 214 next_char_if(Lexer *lexer, int (*pred)(int)) 215 { 216 if (!lexer->source.count) return EOF; 217 if (pred(*lexer->source.items)) { 218 return next_char(lexer); 219 } 220 return CHAR_INVALID; 221 } 222 223 int 224 isbdigit_or_sep(int c) 225 { 226 if (c == '_') return true; 227 return isbdigit(c); 228 } 229 230 int 231 isodigit_or_sep(int c) 232 { 233 if (c == '_') return true; 234 return isodigit(c); 235 } 236 237 int 238 isddigit_or_sep(int c) 239 { 240 if (c == '_') return true; 241 return isddigit(c); 242 } 243 244 int 245 isxdigit_or_sep(int c) 246 { 247 if (c == '_') return true; 248 return isxdigit(c); 249 } 250 251 int 252 is_ident_char(int c) 253 { 254 return c == '_' || 255 (c >= '0' && c <= '9') || 256 (c >= 'A' && c <= 'Z') || 257 (c >= 'a' && c <= 'z'); 258 } 259 260 int 261 is_symbol_char(int c) 262 { 263 return c == '+' || 264 c == '-' || 265 c == '*' || 266 c == '/' || 267 c == '%' || 268 c == '(' || 269 c == ')' || 270 c == '[' || 271 c == ']' || 272 c == '<' || 273 c == '>' || 274 c == '{' || 275 c == '}' || 276 c == '=' || 277 c == '&' || 278 c == '|' || 279 c == '^' || 280 c == '~' || 281 c == '?' || 282 c == '!' || 283 c == '.' || 284 c == ',' || 285 c == ':' || 286 c == ';' || 287 c == '`' || 288 c == '#' || 289 c == '@' || 290 c == '$' || 291 0; 292 } 293 294 bool 295 is_operator_token(Token_kind kind) { 296 return kind == '+' || 297 kind == '-' || 298 kind == '*' || 299 kind == '/' || 300 kind == '%' || 301 /* kind == '(' || */ 302 /* kind == ')' || */ 303 /* kind == '[' || */ 304 /* kind == ']' || */ 305 kind == '<' || 306 kind == '>' || 307 /* kind == '{' || */ 308 /* kind == '}' || */ 309 kind == '=' || 310 kind == '&' || 311 kind == '|' || 312 kind == '^' || 313 kind == '~' || 314 kind == '?' || 315 kind == '!' || 316 /* kind == '.' || */ 317 /* kind == ',' || */ 318 kind == T_IDENT || 319 0; 320 } 321 322 int 323 skip_comment(Lexer *lexer) 324 { 325 Loc start_loc = lexer->current_loc; 326 int len = 0; 327 if (sv_starts_with_cstr(lexer->source, "/*")) { 328 len = 2; 329 next_char(lexer); 330 next_char(lexer); 331 while (lexer->source.count && !sv_starts_with_cstr(lexer->source, "*/")) { 332 if (sv_starts_with_cstr(lexer->source, "/*")) { 333 len += skip_comment(lexer); 334 } else { 335 len++; 336 next_char(lexer); 337 } 338 } 339 if (!lexer->source.count) { 340 print_loc(start_loc); 341 fprintf(stderr, "Error: unterminated comment\n"); 342 return -1; 343 } 344 next_char(lexer); 345 next_char(lexer); 346 len += 2; 347 } else if (sv_starts_with_cstr(lexer->source, "//")) { 348 char next; 349 while ((next = next_char(lexer)) != '\n' && next != EOF) len++; 350 } 351 return len; 352 } 353 354 Token 355 next_token(Lexer *lexer) 356 { 357 Loc start_loc = lexer->current_loc; 358 Token result = { .loc = start_loc, .sv = { .items = lexer->source.items, .count = 0 } }; 359 360 if (lexer->last_tok.kind != T_WHITESPACE) { 361 lexer->last_valid_loc = start_loc; 362 } 363 364 if (!lexer->source.count) { 365 result.kind = T_EOF; 366 lexer->last_tok = result; 367 return result; 368 } 369 370 int c = next_char_if(lexer, isspace); 371 size_t len = 0; 372 373 { 374 bool whitespace = false; 375 int comment_len = 0; 376 while (isspace(c) || (comment_len = skip_comment(lexer))) { 377 if (comment_len < 0) { 378 return (Token) { 379 .kind = T_ERROR_, 380 .loc = start_loc, 381 }; 382 } else if (comment_len > 0) { 383 len += comment_len; 384 } else { 385 len++; 386 } 387 whitespace = true; 388 while ((c = next_char_if(lexer, isspace)) >= 0) { 389 len++; 390 } 391 } 392 if (whitespace) { 393 if (start_loc.line < lexer->current_loc.line) { 394 result.kind = T_WHITESPACE_NL; 395 } else { 396 result.kind = T_WHITESPACE; 397 } 398 result.sv.count = len; 399 lexer->last_tok = result; 400 return result; 401 } 402 } 403 404 len = 1; 405 406 c = next_char(lexer); 407 408 if (c == '!' && is_ident_char(peek_char(lexer))) { 409 /* result.sv.data++; */ 410 /* len = 0; */ 411 while (next_char_if(lexer, is_ident_char) >= 0) len++; 412 assert(len > 0); 413 result.sv.count = len; 414 result.kind = T_CONST_SYMBOL; 415 lexer->last_tok = result; 416 return result; 417 } 418 419 if (c == '?' && is_ident_char(peek_char(lexer))) { 420 /* result.sv.data++; */ 421 /* len = 0; */ 422 while (next_char_if(lexer, is_ident_char) >= 0) len++; 423 assert(len > 0); 424 result.sv.count = len; 425 result.kind = T_VARIABLE_SYMBOL; 426 lexer->last_tok = result; 427 return result; 428 } 429 430 if (c == '$' && is_ident_char(peek_char(lexer))) { 431 result.sv.data++; 432 len = 0; 433 while (next_char_if(lexer, is_ident_char) >= 0) len++; 434 assert(len > 0); 435 result.sv.count = len; 436 result.kind = T_FUNCTION_SYMBOL; 437 lexer->last_tok = result; 438 return result; 439 } 440 441 if (c == '#' && is_ident_char(peek_char(lexer))) { 442 result.sv.data++; 443 len = 0; 444 while (next_char_if(lexer, is_ident_char) >= 0) len++; 445 result.kind = T_LABEL; 446 result.sv.count = len; 447 /* result.i64 = sv_to_number(result.sv, 10); */ 448 lexer->last_tok = result; 449 return result; 450 } 451 452 if (c == '%' && isdigit(peek_char(lexer))) { 453 result.sv.data++; 454 len = 0; 455 while (next_char_if(lexer, isdigit) >= 0) len++; 456 result.kind = T_TEMP; 457 result.sv.count = len; 458 result.i64 = sv_to_number(result.sv, 10); 459 lexer->last_tok = result; 460 return result; 461 } 462 463 if (c == '-' && peek_char(lexer) == '>') { 464 len++; 465 next_char(lexer); 466 result.sv.count = len; 467 result.kind = T_ARROW; 468 lexer->last_tok = result; 469 return result; 470 } 471 472 if (c == '-' && isdigit(peek_char(lexer))) { 473 c = next_char(lexer); 474 len++; 475 } 476 if (isdigit(c)) { 477 int peek; 478 int base = 10; 479 int (*digit_fn)(int) = isddigit_or_sep; 480 if (c == '0') { 481 peek = peek_char(lexer); 482 len++; 483 if (peek == 'b') { 484 next_char(lexer); 485 base = 2; 486 digit_fn = isbdigit_or_sep; 487 } else if (peek == 'o') { 488 next_char(lexer); 489 base = 8; 490 digit_fn = isodigit_or_sep; 491 } else if (peek == 'x') { 492 next_char(lexer); 493 base = 16; 494 digit_fn = isxdigit_or_sep; 495 } else { 496 len--; 497 base = 8; 498 digit_fn = isodigit_or_sep; 499 } 500 } 501 502 while (next_char_if(lexer, digit_fn) >= 0) len++; 503 504 result.kind = T_NUMBER; 505 result.sv.count = len; 506 result.i64 = sv_to_number(result.sv, base); 507 lexer->last_tok = result; 508 return result; 509 } 510 511 if (is_ident_char(c)) { 512 while (next_char_if(lexer, is_ident_char) >= 0) len++; 513 result.sv.count = len; 514 result.kind = get_keyword_kind(result.sv); 515 lexer->last_tok = result; 516 return result; 517 } 518 519 if (is_symbol_char(c)) { 520 result.kind = c; 521 result.sv.count = len; 522 lexer->last_tok = result; 523 return result; 524 } 525 526 if (c == '\'' || c == '"') { 527 char next; 528 while ((next = next_char(lexer)) != EOF && next != c) { 529 len++; 530 if (next == '\\') { 531 next_char(lexer); 532 len++; 533 } 534 } 535 if (next != c) { 536 print_loc(start_loc); 537 fprintf(stderr, "Error: unterminated %s quoted string\n", c == '"' ? "double" : "single"); 538 539 return (Token) { 540 .kind = T_ERROR_, 541 .loc = start_loc, 542 }; 543 } 544 result.kind = c == '"' ? T_DQ_STRING : T_SQ_STRING; 545 result.sv.count = --len; 546 result.sv.data++; 547 lexer->last_tok = result; 548 return result; 549 } 550 551 print_loc(start_loc); 552 fprintf(stderr, "Error: unknown character '%c'\n", c); 553 554 return (Token) { 555 .kind = T_ERROR_, 556 .loc = start_loc, 557 }; 558 } 559 560 Token 561 peek_token(Lexer *lexer) 562 { 563 Lexer peek = *lexer; 564 return next_token(&peek); 565 } 566 567 Token_kind 568 get_keyword_kind(Sv sv) 569 { 570 int i = 0; 571 for (;i < keywords_count; i++) { 572 if (sv_equal(sv, keywords[i])) { 573 return i + T_KEYWORDS_; 574 } 575 } 576 return T_IDENT; 577 } 578 579 Token 580 next_token_if_kind(Lexer *lexer, Token_kind kind) 581 { 582 Lexer peek = *lexer; 583 Token t = next_token(&peek); 584 if (t.kind == kind) { 585 *lexer = peek; 586 return t; 587 } 588 return (Token) { 589 .kind = T_INVALID, 590 .loc = lexer->current_loc, 591 }; 592 } 593 594 Token 595 next_token_if(Lexer *lexer, int (*pred)(Token)) 596 { 597 Lexer peek = *lexer; 598 Token t = next_token(&peek); 599 if (pred(t)) { 600 *lexer = peek; 601 return t; 602 } 603 return (Token) { 604 .kind = T_INVALID, 605 .loc = lexer->current_loc, 606 }; 607 } 608 609 void 610 skip_whitespace(Lexer *lexer) 611 { 612 Lexer peek = *lexer; 613 Token t = next_token(&peek); 614 if (t.kind == T_WHITESPACE || t.kind == T_WHITESPACE_NL) { 615 *lexer = peek; 616 } 617 } 618 619 bool 620 expect_token_kind(Lexer *lexer, Token_kind kind) 621 { 622 Token t = next_token(lexer); 623 if (t.kind != kind) { 624 Sb error = {0}; 625 626 /* sb_append_loc(&error, t.loc); */ 627 sb_append_loc(&error, lexer->last_valid_loc); 628 sb_append_cstr(&error, "Error: expected token "); 629 sb_append_token_kind(&error, kind); 630 sb_append_cstr(&error, ", but got "); 631 sb_append_token_kind(&error, t.kind); 632 633 fprintf(stderr, "%.*s\n", (int) error.count, error.items); 634 635 sb_release(&error); 636 return false; 637 /* return (Token) { */ 638 /* .kind = T_ERROR_, */ 639 /* .loc = t.loc, */ 640 /* }; */ 641 } 642 return true; 643 } 644 645 bool 646 expect_end_statement_impl(Lexer *lexer, const char *file, int line) 647 { 648 if (lexer->last_tok.kind == T_WHITESPACE_NL) { 649 fprintf(stderr, "%s:%i: expect_end_statement hack\n", file, line); 650 return true; 651 /* return lexer->last_tok; */ 652 } 653 Token t = next_token(lexer); 654 if (t.kind == ';' || t.kind == T_WHITESPACE_NL) { 655 /* return t; */ 656 skip_whitespace(lexer); 657 return true; 658 } 659 if (t.kind == T_WHITESPACE) { 660 if (peek_token(lexer).kind == ';') { 661 next_token(lexer); 662 skip_whitespace(lexer); 663 return true; 664 } 665 } 666 Sb error = {0}; 667 668 /* sb_append_loc(&error, t.loc); */ 669 sb_append_loc(&error, lexer->last_valid_loc); 670 sb_append_cstr(&error, "Error: expected ; or newline, but got "); 671 sb_append_token_kind(&error, t.kind); 672 673 fprintf(stderr, "%.*s\n", (int) error.count, error.items); 674 675 sb_release(&error); 676 return false; 677 /* return (Token) { */ 678 /* .kind = T_ERROR_, */ 679 /* .loc = t.loc, */ 680 /* }; */ 681 }