From f98a945eba01ec020711119b1019cf57dab578b1 Mon Sep 17 00:00:00 2001 From: cassowarii <2374677+cassowarii@users.noreply.github.com> Date: Fri, 19 Jun 2026 17:55:31 -0700 Subject: [PATCH] lexer almost complete barring a few weird corner cases --- src/common.h | 18 +-- src/global.h | 26 +++- src/main.c | 34 ++-- src/mem/arena.h | 9 +- src/mem/buffer.c | 65 ++++++++ src/mem/buffer.h | 26 ++++ src/mem/mem.h | 9 +- src/mem/sbstring.c | 39 +++++ src/mem/sbstring.h | 5 + src/mem/string.c | 14 -- src/mem/string.h | 3 - src/parse/lexer.c | 441 ++++++++++++++++++++++++++++++++++++++++++++++++++++ src/parse/lexer.h | 29 ++++ src/parse/scanner.c | 223 ++++++++++++++++++++------ src/parse/scanner.h | 69 ++------ src/parse/token.h | 88 +++++++++++ 16 files changed, 942 insertions(+), 156 deletions(-) create mode 100644 src/mem/buffer.c create mode 100644 src/mem/buffer.h create mode 100644 src/mem/sbstring.c create mode 100644 src/mem/sbstring.h delete mode 100644 src/mem/string.c delete mode 100644 src/mem/string.h create mode 100644 src/parse/lexer.c create mode 100644 src/parse/lexer.h create mode 100644 src/parse/token.h diff --git a/src/common.h b/src/common.h index 498ac27..842d51d 100644 --- a/src/common.h +++ b/src/common.h @@ -1,23 +1,7 @@ #ifndef __SARABANDE_COMMON_H__ #define __SARABANDE_COMMON_H__ -#include -#include -#include -#include - -typedef uint64_t u64; -typedef int64_t i64; -typedef uint32_t u32; -typedef int32_t i32; -typedef uint16_t u16; -typedef int16_t i16; -typedef uint8_t u8; -typedef int8_t i8; -typedef uint8_t flag; -typedef size_t usize; -typedef ptrdiff_t isize; - #include "global.h" +#include "mem/mem.h" #endif diff --git a/src/global.h b/src/global.h index 4abd545..b12ad0d 100644 --- a/src/global.h +++ b/src/global.h @@ -1,5 +1,27 @@ +#ifndef __SB_GLOBAL_H__ +#define __SB_GLOBAL_H__ + #ifdef DEBUG -#define PANIC(msg) do { fprintf(stderr, "panic: " __FILE__ ":%d: " msg "\n", __LINE__); abort(); } while (0) +#define PANIC(msg) do { fprintf(stderr, "PANIC: " msg " at " __FILE__ ":%d\n", __LINE__); abort(); } while (0) #else -#define PANIC(x) 0 +#define PANIC(msg) do { fprintf(stderr, "PANIC: " msg "\n"); abort(); } while (0) +#endif + +#include +#include +#include +#include + +typedef uint64_t u64; +typedef int64_t i64; +typedef uint32_t u32; +typedef int32_t i32; +typedef uint16_t u16; +typedef int16_t i16; +typedef uint8_t u8; +typedef int8_t i8; +typedef uint8_t flag; +typedef size_t usize; +typedef ptrdiff_t isize; + #endif diff --git a/src/main.c b/src/main.c index d85ddc4..1e328b5 100644 --- a/src/main.c +++ b/src/main.c @@ -1,7 +1,7 @@ #include "common.h" #include "parse/filereader.h" -#include "parse/scanner.h" +#include "parse/lexer.h" int main(int argc, char **argv) { if (argc == 2) { @@ -12,34 +12,46 @@ int main(int argc, char **argv) { return -1; } - hScanner sc = sbScanner_create(fr); + sbLexer lx; + sbLexer_initialize(&lx, fr); sbLexToken t; do { - t = sbScanner_next(sc); + t = sbLexer_next(&lx); if (t.type == T_EOF) { - printf("(EOF)"); + printf(""); } else if (t.type == T_SPACE) { - printf("( )"); + printf(""); } else if (t.type == T_NEWLINE) { - printf("(\\n)"); + printf("\n"); } else if (t.type == T_IDENTIFIER) { - printf("(ID %s)", t.str); + printf("%s", t.str); } else if (t.type == T_INTEGER) { - printf("(INT %d)", t.i); + printf("", t.i); + } else if (t.type == T_STRING) { + printf("", t.str); + } else if (t.type == T_SYMBOL) { + printf("", t.str); + } else if (t.type >= T_rAND && t.type <= T_rWHILE) { + printf("<%s>", t.str); + } else if (t.type == T_SEMICOLON) { + printf(";\n"); } else { switch (t.type) { + case T_COLONBRACE: + printf(":{"); break; case T_DOUBLEEQUALS: - printf(" == "); break; + printf("=="); break; default: - printf(" %c ", t.type); + printf("%c", t.type); } } } while (t.type != T_EOF); + printf("\n"); - sbScanner_destroy(sc); + sbLexer_deinitialize(&lx); sbFileReader_close(fr); } else { diff --git a/src/mem/arena.h b/src/mem/arena.h index 6eb5836..abb934b 100644 --- a/src/mem/arena.h +++ b/src/mem/arena.h @@ -1,4 +1,11 @@ -#include "common.h" +#include "global.h" + +/* Memory arena. Allocate memory in large chunks and hand out chunks of a requested size. + * All memory in arena is reclaimed at once, and can be reused. + * Position of memory blocks is fixed, so pointers to items in arena remain valid no matter what. + * However, memory must be requested in fixed-size chunks and can't be reallocated. + * For a flexible-length contiguous buffer that may need to grow in length, use sbBuffer instead. + * (however, sbBuffer doesn't have the 'pointer validity' guarantee.) */ typedef struct sbArena *hArena; diff --git a/src/mem/buffer.c b/src/mem/buffer.c new file mode 100644 index 0000000..f3580a4 --- /dev/null +++ b/src/mem/buffer.c @@ -0,0 +1,65 @@ +#include "buffer.h" + +#include + +void sbBuffer_initialize(hBuffer buf, usize initial_size) { + char *data = malloc(initial_size); + + if (data) { + *buf = (sbBuffer) { + .size = 0, + .capacity = initial_size, + .data = data, + }; + } else { + *buf = (sbBuffer) {0}; + } +} + +void *sbBuffer_expand(hBuffer buf, usize expand_size) { + if (expand_size == 0) return NULL; + + if (buf->capacity == 0 || buf->data == NULL) { + fprintf(stderr, "cannot expand invalid buffer!\n"); + return NULL; + } + + char *result; + usize new_size = buf->size + expand_size; + if (new_size > buf->capacity) { + /* not enough space to fit requested chunk. reallocate to fit */ + usize new_capacity = buf->capacity * 3 / 2; + if (new_capacity < new_size) { + new_capacity = new_size; + } + + char *new_data = realloc(buf->data, new_capacity); + if (new_data) { + buf->data = new_data; + } else { + fprintf(stderr, "failed to expand buffer!"); + return NULL; + } + } + + result = &buf->data[buf->size]; + buf->size = new_size; + memset(result, 0, expand_size); + return result; +} + +void sbBuffer_append(hBuffer buf, const char *data, usize data_length) { + if (data_length == 0) return; + + char *put = sbBuffer_expand(buf, data_length); + memcpy(put, data, data_length); +} + +void sbBuffer_reset(hBuffer buf) { + buf->size = 0; +} + +void sbBuffer_deinitialize(hBuffer buf) { + free(buf->data); + *buf = (sbBuffer) {0}; +} diff --git a/src/mem/buffer.h b/src/mem/buffer.h new file mode 100644 index 0000000..3767a75 --- /dev/null +++ b/src/mem/buffer.h @@ -0,0 +1,26 @@ +#include "global.h" + +/* Classic dynamic-sized array that expands when full. + * Calls realloc(), so locations of pointers inside the array may shift in transit. + * If you need a big block of memory that keeps consistent pointer values, use sbArena instead. + * However, memory allocated from sbArena must be statically sized! + * You can use sbBuffer to read in data you don't know the size of, then request a chunk + * of that size from sbArena and copy it to there for long-term storage. */ + +typedef struct sbBuffer { + usize size; + usize capacity; + char *data; +} sbBuffer; + +typedef sbBuffer *hBuffer; + +void sbBuffer_initialize(hBuffer buf, usize initial_size); + +void *sbBuffer_expand(hBuffer buf, usize expand_size); + +void sbBuffer_append(hBuffer buf, const char *data, usize data_length); + +void sbBuffer_reset(hBuffer buf); + +void sbBuffer_deinitialize(hBuffer buf); diff --git a/src/mem/mem.h b/src/mem/mem.h index fdd935a..85a6f10 100644 --- a/src/mem/mem.h +++ b/src/mem/mem.h @@ -1,4 +1,9 @@ -#include "common.h" +#ifndef __SB_MEM_H__ +#define __SB_MEM_H__ +#include "global.h" #include "arena.h" -#include "string.h" +#include "buffer.h" +#include "sbstring.h" + +#endif diff --git a/src/mem/sbstring.c b/src/mem/sbstring.c new file mode 100644 index 0000000..82f39dd --- /dev/null +++ b/src/mem/sbstring.c @@ -0,0 +1,39 @@ +#include "sbstring.h" + +usize sbstrncpy(char *dst, const char *src, usize limit) { + usize count = 0; + char ch = 0; + + do { + ch = dst[count] = src[count]; + count ++; + } while (ch && count < limit); + + count --; + if (dst[count] != 0) dst[count] = 0; + + return count; +} + +int sbstrncmp(const char *a, const char *b, usize limit) { + usize count = 0; + + while (a[count] && b[count] && a[count] == b[count] && count < limit) { + count ++; + } + + if (a[count] == 0 && b[count] == 0) { + return 0; + } else if (a[count] == 0) { + return 1; + } else if (b[count] == 0) { + return -1; + } else if (a[count] < b[count]) { + return 1; + } else if (b[count] < a[count]) { + return -1; + } else { + /* we must have reached the limit */ + return 0; + } +} diff --git a/src/mem/sbstring.h b/src/mem/sbstring.h new file mode 100644 index 0000000..5d6711b --- /dev/null +++ b/src/mem/sbstring.h @@ -0,0 +1,5 @@ +#include "global.h" + +usize sbstrncpy(char *dst, const char *src, usize limit); + +int sbstrncmp(const char *a, const char *b, usize limit); diff --git a/src/mem/string.c b/src/mem/string.c deleted file mode 100644 index 5eec54a..0000000 --- a/src/mem/string.c +++ /dev/null @@ -1,14 +0,0 @@ -#include "string.h" - -usize sbstrncpy(char *dst, char *src, usize limit) { - usize count = 0; - char ch = 0; - - do { - ch = dst[count] = src[count]; - count ++; - } while (ch && count < limit); - dst[--count] = 0; - - return count; -} diff --git a/src/mem/string.h b/src/mem/string.h deleted file mode 100644 index f98b0ee..0000000 --- a/src/mem/string.h +++ /dev/null @@ -1,3 +0,0 @@ -#include "common.h" - -usize sbstrncpy(char *dst, char *src, usize limit); diff --git a/src/parse/lexer.c b/src/parse/lexer.c new file mode 100644 index 0000000..4b37825 --- /dev/null +++ b/src/parse/lexer.c @@ -0,0 +1,441 @@ +#include "lexer.h" + +#include +#include "mem/mem.h" + +static void compute_next_token(hLexer lx); +static sbLexToken advance_output_queue(hLexer lx); + +void sbLexer_initialize(hLexer lx, hFileReader fr) { + sbBuffer_initialize(&lx->brackets_stack, 64); + sbScanner_initialize(&lx->scanner, fr); + memset(lx->input_queue, 0, LEXER_QUEUE_LENGTH * sizeof(sbLexToken)); + memset(lx->output_queue, 0, LEXER_QUEUE_LENGTH * sizeof(sbLexToken)); + lx->input_queue_length = 0; + lx->output_queue_length = 0; + lx->last_token_seen = (sbLexToken) {0}; + lx->n_brackets = 0; + lx->brace_terminated_state = 0; +} + +sbLexToken sbLexer_peek(hLexer lx) { + if (lx->output_queue_length == 0) { + compute_next_token(lx); + } + + return lx->output_queue[0]; +} + +sbLexToken sbLexer_next(hLexer lx) { + if (lx->output_queue_length == 0) { + compute_next_token(lx); + } + + return advance_output_queue(lx); +} + +void sbLexer_deinitialize(hLexer lx) { + sbScanner_deinitialize(&lx->scanner); + sbBuffer_deinitialize(&lx->brackets_stack); + lx->input_queue_length = 0; + lx->output_queue_length = 0; +} + +struct ReservedWord { + const char *name; + sbTokenType token_type; +}; + +struct ReservedWord reserved_words[] = { + { "and", T_rAND }, + { "as", T_rAS }, + { "case", T_rCASE }, + { "def", T_rDEF }, + { "do", T_rDO }, + { "else", T_rELSE }, + { "if", T_rIF }, + { "let", T_rLET }, + { "in", T_rIN }, + { "not", T_rNOT }, + { "or", T_rOR }, + { "repeat", T_rREPEAT }, + { "return", T_rREPEAT }, + { "unless", T_rUNLESS }, + { "until", T_rUNTIL }, + { "when", T_rWHEN }, + { "while", T_rWHILE }, +}; + +#define N_RESERVED_WORDS ((sizeof(reserved_words))/(sizeof(reserved_words[0]))) + +sbLexToken advance_token_queue(sbLexToken *q, int *length, char version) { + if (*length == 0) { + if (version == 'o') { + PANIC("can't advance empty lexer output queue!"); + } else { + PANIC("can't advance empty lexer input queue!"); + } + } + + sbLexToken result = q[0]; + + (*length)--; + for (int i = 0; i < *length; i++) { + if (i < LEXER_QUEUE_LENGTH - 1) { + q[i] = q[i + 1]; + } else { + q[i] = (sbLexToken) {0}; + } + } + + q[*length] = (sbLexToken) {0}; + + return result; +} + +void enqueue_token(sbLexToken *q, int *length, sbLexToken token, char version) { + if (*length == LEXER_QUEUE_LENGTH) { + if (version == 'o') { + PANIC("output token queue is full!"); + } else { + PANIC("input token queue is full!"); + } + } + + q[*length] = token; + (*length)++; +} + +static flag is_stackable(sbTokenType type); +static void stack_token(hLexer lx, sbLexToken token); +static flag is_closing_bracket(sbTokenType type); +static void unstack_visible_bracket(hLexer lx, sbLexToken closing_token); +static void unstack_sticky_invisible_parentheses(hLexer lx); + +void enqueue_output_token(hLexer lx, sbLexToken token) { + /* if leaving brackets, close invisible parentheses and remove us from + * brackets stack here */ + if (is_closing_bracket(token.type) && !token.invisible) { + unstack_visible_bracket(lx, token); + } + + enqueue_token(lx->output_queue, &lx->output_queue_length, token, 'o'); + + if (is_closing_bracket(token.type) && !token.invisible) { + unstack_sticky_invisible_parentheses(lx); + } + + /* track brackets, parentheses, braces etc */ + if (is_stackable(token.type)) { + stack_token(lx, token); + } +} + +void enqueue_input_token(hLexer lx, sbLexToken token) { + enqueue_token(lx->input_queue, &lx->input_queue_length, token, 'i'); +} + +sbLexToken advance_output_queue(hLexer lx) { + while (lx->output_queue_length == 0) { + compute_next_token(lx); + } + return advance_token_queue(lx->output_queue, &lx->output_queue_length, 'o'); +} + +sbLexToken advance_input_queue(hLexer lx) { + if (lx->input_queue_length == 0) { + enqueue_input_token(lx, sbScanner_next(&lx->scanner)); + } + return advance_token_queue(lx->input_queue, &lx->input_queue_length, 'i'); +} + +sbLexToken input_peek_ahead(hLexer lx, int count) { + /* 0 = next token; 1 = token after that; etc. + * so if count is 0, length must be at least 1 */ + while (lx->input_queue_length <= count) { + enqueue_input_token(lx, sbScanner_next(&lx->scanner)); + } + + return lx->input_queue[count]; +} + +flag is_literal(sbTokenType type) { + return type == T_IDENTIFIER + || type == T_STRING + || type == T_INTEGER + || type == T_FLOAT + || type == T_SYMBOL; +} + +flag insert_semicolon_after(sbTokenType type) { + return is_literal(type) + || type == T_RPAREN + || type == T_RBRACKET + || type == T_RBRACE + || type == T_DOUBLEPLUS + || type == T_DOUBLEMINUS; +} + +flag cancel_semicolon_before(sbTokenType type) { + return type == T_DOT + || type == T_PIPE; +} + +/* identifier + space + one of these gets a ( inserted */ +flag can_only_start_expression(sbTokenType type, flag brace_terminated_state) { + return is_literal(type) + || type == T_LPAREN + || type == T_LBRACKET + || type == T_COLONBRACE + || type == T_FATARROW + || type == T_rNOT + || type == T_rDO + || (type == T_LBRACE && !brace_terminated_state); // danger will robinson! +} + +/* identifier + space + one of these + NO SPACE gets a ( inserted but not if + * surrounded by spaces or neither space */ +flag maybe_can_start_expression(sbTokenType type) { + return type == T_PLUS + || type == T_MINUS; +} + +static flag is_stackable(sbTokenType type) { + return type == T_LPAREN + || type == T_LBRACKET + || type == T_LBRACE + || type == T_COLONBRACE; +} + +static flag is_closing_bracket(sbTokenType type) { + return type == T_RPAREN + || type == T_RBRACKET + || type == T_RBRACE; +} + +/* header keywords that introduce a block and go until a { */ +static flag begins_brace_terminated_state(sbTokenType type) { + return type == T_rDEF + || type == T_rIF + || type == T_rUNLESS + || type == T_rWHILE + || type == T_rUNTIL + || type == T_rDO + || type == T_rREPEAT + || type == T_rCASE + || type == T_rWHEN; +} + +/* when in brace-terminated state, one of these must precede a { character + * in order to exit brace-terminated state */ +flag can_end_expression(sbTokenType type) { + return is_literal(type) + || type == T_RPAREN + || type == T_RBRACKET + || type == T_RBRACE; +} + +/*static flag is_reserved_word(sbTokenType type) { + for (int i = 0; i < N_RESERVED_WORDS; i++) { + if (type == reserved_words[i].token_type) return 1; + } + return 0; +}*/ + +static void stack_token(hLexer lx, sbLexToken token) { + /* track which invisible and visible brackets we've seen, so we can close invisible brackets + * at appropriate times */ + char *stack_top = sbBuffer_expand(&lx->brackets_stack, 1); + if (token.invisible == 1 && token.type == '(') { + *stack_top = 'G'; + } else if (token.invisible == 2 && token.type == '(') { + /* this is a special invisible () that gets wrapped around something like "map:{ ... }" */ + *stack_top = 'H'; + } else if (token.type == '(' || token.type == '[' || token.type == '{') { + *stack_top = token.type; + } else if (token.type == T_COLONBRACE) { + *stack_top = ':'; + } else { + *stack_top = token.type; + } +} + +static void unstack_one_invisible_parenthesis(hLexer lx) { + if (lx->brackets_stack.size == 0) return; + + char *stack_top = &lx->brackets_stack.data[lx->brackets_stack.size - 1]; + if (lx->brackets_stack.size > 0 && (*stack_top == 'G' || *stack_top == 'H')) { + sbLexToken invisible_rparen = { .type = T_RPAREN, .invisible = 1 }; + enqueue_output_token(lx, invisible_rparen); + lx->brackets_stack.size --; + } +} + +static void unstack_invisible_parentheses_of_type(hLexer lx, char type) { + /* this happens when a real bracket closes, and also at the end of a line */ + if (lx->brackets_stack.size == 0) return; + + char *stack_top = &lx->brackets_stack.data[lx->brackets_stack.size - 1]; + while (lx->brackets_stack.size > 0 && *stack_top == type) { + sbLexToken invisible_rparen = { .type = T_RPAREN, .invisible = 1 }; + enqueue_output_token(lx, invisible_rparen); + lx->brackets_stack.size --; + stack_top = &lx->brackets_stack.data[lx->brackets_stack.size - 1]; + } +} + +static void unstack_all_invisible_parentheses(hLexer lx) { + unstack_invisible_parentheses_of_type(lx, 'G'); +} + +static void unstack_sticky_invisible_parentheses(hLexer lx) { + /* handling special case of 'map:{ ... }.whatever' --> 'map(:{ ... }).whatever . + * normally this wouldn't work except we add this sticky "H" bracket when there + * is no space before :{. so *after* right curly brace we check if there are any + * of these to close too */ + /* i don't know what G and H stand for. i think "ghost" and "hidden" */ + unstack_invisible_parentheses_of_type(lx, 'H'); +} + +static void unstack_visible_bracket(hLexer lx, sbLexToken closing_token) { + unstack_all_invisible_parentheses(lx); + + if (lx->brackets_stack.size != 0) { + char *stack_top = &lx->brackets_stack.data[lx->brackets_stack.size - 1]; + if (closing_token.type == T_RBRACE) { + if (*stack_top == '{' || *stack_top == ':') { + lx->brackets_stack.size --; + return; + } + } else if (closing_token.type == T_RBRACKET) { + if (*stack_top == '[') { + lx->brackets_stack.size --; + return; + } + } else if (closing_token.type == T_RPAREN) { + if (*stack_top == '(') { + lx->brackets_stack.size --; + return; + } + } + } + + if (lx->brackets_stack.size != 0) { + fprintf(stderr, "syntax error: mismatched bracket ('%c' for '%c')\n", lx->brackets_stack.data[lx->brackets_stack.size - 1], closing_token.type); + } else { + fprintf(stderr, "syntax error: mismatched bracket\n"); + } + enqueue_output_token(lx, (sbLexToken) { .type = T_ERROR }); +} + +void compute_next_token(hLexer lx) { + sbLexToken token = advance_input_queue(lx); + + /* if we receive an identifier, check if it is a reserved word or not */ + if (token.type == T_IDENTIFIER) { + for (int i = 0; i < N_RESERVED_WORDS; i++) { + if (!sbstrncmp(reserved_words[i].name, token.str, token.size + 1)) { + token.type = reserved_words[i].token_type; + break; + } + } + } + + if (lx->brace_terminated_state && can_end_expression(lx->last_token_seen.type) && token.type == T_LBRACE) { + /* TODO: I think this will fail in some obscure case, like where you have a '=> a, b { ... }' inside + * of the top of an `if'. Annoying. We probably need to track brace_terminated_state for each level + * of the bracket-stack individually, so that when we exit from a { } inside a block header we know + * that we are still actually in brace_terminated_state. I think that should work. But I need to think + * about the specifics a little more. */ + /* The condition for leaving brace-terminated state is correct (end-of-expression token followed + * by opening brace) but brace-terminated state can come back in some sneaky scenarios after + * a situation where we weren't in it before. */ + unstack_all_invisible_parentheses(lx); + lx->brace_terminated_state = 0; + } + + if (begins_brace_terminated_state(token.type)) { + lx->brace_terminated_state = 1; + } + + if (token.type != T_SPACE && token.type != T_NEWLINE) { + enqueue_output_token(lx, token); + } + + sbLexToken invisible_lparen = { .type = T_LPAREN, .invisible = 1 }; + if (token.type == T_IDENTIFIER && input_peek_ahead(lx, 0).type == T_COLONBRACE) { + /* identifier followed by colon-brace with no space between gets this special invisible bracket */ + /* invisible = 2 makes it a sticky H bracket */ + invisible_lparen.invisible = 2; + enqueue_output_token(lx, invisible_lparen); + } else if (token.type == T_IDENTIFIER) { + /* otherwise, if it's still an identifier and not a reserved word, we might need to insert a + * magic ( into the output stream. so look ahead at what's coming up. */ + if (lx->last_token_seen.type == T_DOT) { + /* an identifier after a dot always gets an invisible parentheses after it, + * unless there is a visible parentheses immediately after it. */ + if (input_peek_ahead(lx, 0).type != T_LPAREN) { + enqueue_output_token(lx, invisible_lparen); + + int space_offset = 0; + if (input_peek_ahead(lx, 0).type == T_SPACE) { + /* in this case, we don't care if we have a space after us. */ + space_offset = 1; + } + + sbTokenType next_type = input_peek_ahead(lx, space_offset).type; + sbTokenType next_next_type = input_peek_ahead(lx, space_offset + 1).type; + + if (maybe_can_start_expression(next_type)) { + /* this is something like 'a.b( +c' or 'a.b( + c'. if there is a space + * after the operator, or not before the operator, add an invisible ), + * otherwise don't because that's the 'a.b( +c' case */ + if (next_next_type == T_SPACE || space_offset == 0) { + unstack_one_invisible_parenthesis(lx); + } + } else if (!can_only_start_expression(next_type, lx->brace_terminated_state)) { + /* ok, so this means that we just inserted a ( in some situation like + * 'a.b(.c' or 'a.b(, c' or 'a.b( % 3' -- in this situation, we need to also + * add a matching invisible right parenthesis immediately. */ + unstack_one_invisible_parenthesis(lx); + } + /* if can_only_start_expression(next_type), then we don't want to add an invisible + * right parenthesis because it must be a parameter. */ + } + } else if (input_peek_ahead(lx, 0).type == T_SPACE) { + /* suspicious... tell me more */ + if (can_only_start_expression(input_peek_ahead(lx, 1).type, lx->brace_terminated_state)) { + /* ah ! yes. insert a magic ( into the stream. */ + enqueue_output_token(lx, invisible_lparen); + } else if (maybe_can_start_expression(input_peek_ahead(lx, 1).type)) { + /* check if it also has a space after it. if it does NOT, then + * we're looking at something like "a +b", so put a ( in */ + if (input_peek_ahead(lx, 2).type != T_SPACE) { + enqueue_output_token(lx, invisible_lparen); + } + } + } + } + + if (token.type != T_SPACE && token.type != T_NEWLINE) { + lx->last_token_seen = token; + } + + /* automatic semicolon insertion: insert semicolons at the end of lines if we last saw + * an identifier, literal, ++ or --, ), ], or }) -- except if at the next line starts + * with a dot or a pipe */ + /* also close invisible parentheses in this situation even if the next line starts with + * a dot or a pipe */ + if (token.type == T_NEWLINE) { + if (insert_semicolon_after(lx->last_token_seen.type)) { + unstack_all_invisible_parentheses(lx); + sbLexToken after_newline = input_peek_ahead(lx, 0); + + if (!cancel_semicolon_before(after_newline.type)) { + sbLexToken invisible_semicolon = { .type = T_SEMICOLON, .invisible = 1 }; + enqueue_output_token(lx, invisible_semicolon); + lx->last_token_seen = invisible_semicolon; + } + } + } +} diff --git a/src/parse/lexer.h b/src/parse/lexer.h new file mode 100644 index 0000000..b4e35ed --- /dev/null +++ b/src/parse/lexer.h @@ -0,0 +1,29 @@ +#include "common.h" + +#include "filereader.h" +#include "token.h" +#include "scanner.h" + +#define LEXER_QUEUE_LENGTH 32 + +typedef struct sbLexer { + sbScanner scanner; + sbLexToken input_queue[LEXER_QUEUE_LENGTH]; + sbLexToken output_queue[LEXER_QUEUE_LENGTH]; + int input_queue_length; + int output_queue_length; + sbLexToken last_token_seen; + flag brace_terminated_state; + sbBuffer brackets_stack; + int n_brackets; +} sbLexer; + +typedef struct sbLexer *hLexer; + +void sbLexer_initialize(hLexer lx, hFileReader fr); + +sbLexToken sbLexer_next(hLexer lx); + +sbLexToken sbLexer_peek(hLexer lx); + +void sbLexer_deinitialize(hLexer lx); diff --git a/src/parse/scanner.c b/src/parse/scanner.c index 6713e71..d398739 100644 --- a/src/parse/scanner.c +++ b/src/parse/scanner.c @@ -1,8 +1,5 @@ #include "scanner.h" -#include "filereader.h" -#include "mem/mem.h" - /* This is like, the pre lexing stage. I mean, this does a lot of the tokenizing, * but it includes stuff like spaces and newlines, too. Think of this as 'normalizing' * the input. The lexer in the second stage will use some additional context and state @@ -13,59 +10,75 @@ * which have different semantics. */ #define MEM_BLOCK_SIZE 65536 -#define TOKEN_BUFFER_SIZE 256 +#define TOKEN_BUFFER_SIZE 64 -typedef struct sbScanner { - hFileReader file_reader; - hArena arena; - sbLexToken next_token; -} sbScanner; +static void check_if_start(hScanner sc); +static sbLexToken compute_next_token(hScanner sc); -hScanner sbScanner_create(hFileReader fr) { - hScanner sc = malloc(sizeof(sbScanner)); +void sbScanner_initialize(hScanner sc, hFileReader fr) { sc->arena = sbArena_create(MEM_BLOCK_SIZE); sc->file_reader = fr; sc->next_token = (sbLexToken) {0}; - return sc; + sbBuffer_initialize(&sc->dynamic_buffer, 8); } sbLexToken sbScanner_peek(hScanner sc) { + check_if_start(sc); return sc->next_token; } -void sbScanner_destroy(hScanner sc) { +sbLexToken sbScanner_next(hScanner sc) { + check_if_start(sc); + sbLexToken to_return = sc->next_token; + sc->next_token = compute_next_token(sc); + return to_return; +} + +void sbScanner_deinitialize(hScanner sc) { sbArena_destroy(sc->arena); - free(sc); + sbBuffer_deinitialize(&sc->dynamic_buffer); } /* yeah, yeah, unicode! get off my achin' back! i'll do it later! (maybe) */ -flag is_digit(char c) { +static flag is_digit(char c) { return ('0' <= c && c <= '9'); } -flag is_alpha(char c) { +static flag is_alpha(char c) { return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z') || c == '_'; } -flag is_space(char c) { +static flag is_space(char c) { return c == ' ' || c == '\t' || c == '\r'; } -flag is_start_identifier(char c) { +static flag is_start_identifier(char c) { return is_alpha(c); } -flag is_mid_identifier(char c) { +static flag is_mid_identifier(char c) { return is_start_identifier(c) || is_digit(c); } -flag is_end_identifier(char c) { +static flag is_end_identifier(char c) { return is_mid_identifier(c) || c == '?'; } -flag is_base_digit(char c, int base) { +static flag is_start_symbol(char c) { + return is_start_identifier(c); +} + +static flag is_mid_symbol(char c) { + return is_mid_identifier(c); +} + +static flag is_end_symbol(char c) { + return is_end_identifier(c) || c == '='; +} + +static flag is_base_digit(char c, int base) { if (base == 10) { return is_digit(c); } else if (base == 16) { @@ -79,7 +92,7 @@ flag is_base_digit(char c, int base) { } } -int base_digit_value(char c) { +static int base_digit_value(char c) { if (is_digit(c)) { return c - '0'; } else if ('a' <= c && c <= 'z') { @@ -94,33 +107,77 @@ int base_digit_value(char c) { #define NEXT sbFileReader_next(sc->file_reader) #define PEEK sbFileReader_peek(sc->file_reader) -usize read_identifier(hScanner sc, char *token_buffer, usize max_size) { +char token_buffer[TOKEN_BUFFER_SIZE]; +usize tb_length = 0; + +static void finalize_char_buffer(hScanner sc) { + /* move the currently buffered string into the dynamic_buffer */ + sbBuffer_append(&sc->dynamic_buffer, token_buffer, tb_length); + tb_length = 0; +} + +static void read_char_into_buffer(hScanner sc, char c) { + token_buffer[tb_length++] = c; + if (tb_length == TOKEN_BUFFER_SIZE) { + finalize_char_buffer(sc); + } +} + +static void *save_buffer(hScanner sc) { + char *storage = sbArena_alloc(sc->arena, sc->dynamic_buffer.size); + sbstrncpy(storage, sc->dynamic_buffer.data, sc->dynamic_buffer.size); + return storage; +} + +static usize read_identifier(hScanner sc) { + usize token_size = 0; + char ch = 0; + + do { + read_char_into_buffer(sc, NEXT); + token_size ++; + ch = PEEK; + } while (is_mid_identifier(ch)); + + if (is_end_identifier(ch)) { + read_char_into_buffer(sc, NEXT); + token_size ++; + } + + read_char_into_buffer(sc, '\0'); + finalize_char_buffer(sc); + + return token_size; +} + +static usize read_symbol(hScanner sc) { usize token_size = 0; char ch = 0; do { - token_buffer[token_size] = NEXT; + read_char_into_buffer(sc, NEXT); token_size ++; ch = PEEK; - } while (is_mid_identifier(ch) && token_size < max_size - 1); + } while (is_mid_symbol(ch)); - if (is_end_identifier(ch) && token_size < max_size - 1) { - token_buffer[token_size] = NEXT; + if (is_end_symbol(ch)) { + read_char_into_buffer(sc, NEXT); token_size ++; } - token_buffer[token_size] = '\0'; + read_char_into_buffer(sc, '\0'); + finalize_char_buffer(sc); return token_size; } -sbLexToken compute_next_token(hScanner sc) { +static sbLexToken compute_next_token(hScanner sc) { int next = PEEK; char ch = (char)next; - char token_buffer[TOKEN_BUFFER_SIZE]; - usize token_size; + sbBuffer_reset(&sc->dynamic_buffer); + usize token_size = 0; sbLexToken new_token = {0}; if (next == EOF) { @@ -138,7 +195,12 @@ sbLexToken compute_next_token(hScanner sc) { NEXT; ch = PEEK; } while (ch != '\n'); - NEXT; /* eat the newline */ + + /* eat newline, and skip all spaces after the newline */ + do { + NEXT; + } while (is_space(PEEK)); + new_token.type = T_NEWLINE; } else if (ch == '(' || ch == ')' || ch == '[' || ch == ']' @@ -149,6 +211,36 @@ sbLexToken compute_next_token(hScanner sc) { /* unambiguously single-character tokens */ new_token.type = ch; NEXT; + } else if (ch == '!') { + NEXT; + ch = PEEK; + if (ch == '=') { + new_token.type = T_NOTEQUALS; + } else { + /* ! on its own is not an operator i guess. not sure how to handle this elegantly */ + fprintf(stderr, "don't know how to handle character: '!'\n"); + new_token.type = T_ERROR; + } + } else if (ch == '>') { + NEXT; + ch = PEEK; + if (ch == '>') { + new_token.type = T_DOUBLEGREATER; + } else if (ch == '=') { + new_token.type = T_GREATEREQUALS; + } else { + new_token.type = T_GREATER; + } + } else if (ch == '<') { + NEXT; + ch = PEEK; + if (ch == '<') { + new_token.type = T_DOUBLEGREATER; + } else if (ch == '=') { + new_token.type = T_LESSEQUALS; + } else { + new_token.type = T_LESS; + } } else if (ch == '%') { NEXT; ch = PEEK; @@ -226,18 +318,17 @@ sbLexToken compute_next_token(hScanner sc) { if (ch == ':') { /* :: */ new_token.type = T_PAAMAYIM_NEKUDOTAYIM; + NEXT; } else if (ch == '{') { /* :{ */ new_token.type = T_COLONBRACE; - } else if (is_start_identifier(ch)) { + NEXT; + } else if (is_start_symbol(ch)) { /* :abc... */ new_token.type = T_SYMBOL; - token_size = read_identifier(sc, token_buffer, TOKEN_BUFFER_SIZE); - - char *storage = sbArena_alloc(sc->arena, token_size + 1); - - sbstrncpy(storage, token_buffer, token_size + 1); + token_size = read_symbol(sc); + char *storage = save_buffer(sc); new_token.str = storage; new_token.size = token_size; @@ -269,14 +360,48 @@ sbLexToken compute_next_token(hScanner sc) { NEXT; } while (is_space(PEEK)); } - } else if (is_start_identifier(ch)) { - new_token.type = T_IDENTIFIER; + } else if (ch == '`') { + /* Raw string */ + new_token.type = T_STRING; + NEXT; - token_size = read_identifier(sc, token_buffer, TOKEN_BUFFER_SIZE); + flag in_string = 1; - char *storage = sbArena_alloc(sc->arena, token_size + 1); + while (in_string) { + ch = PEEK; + while (ch != '`') { + NEXT; + read_char_into_buffer(sc, ch); + ch = PEEK; + } - sbstrncpy(storage, token_buffer, token_size + 1); + /* ok, now we know ch is a backtick. discard it and look at what's next */ + NEXT; + ch = PEEK; + + if (ch == '`') { + /* it was a double backtick. so count this as one backtick (escaped) and + * continue reading into the string */ + NEXT; + read_char_into_buffer(sc, ch); + } else { + /* it is something else. end of string. exit loop. */ + in_string = 0; + } + } + + read_char_into_buffer(sc, '\0'); + + finalize_char_buffer(sc); + char *storage = save_buffer(sc); + + new_token.str = storage; + new_token.size = sc->dynamic_buffer.size; + } else if (is_start_identifier(ch)) { + new_token.type = T_IDENTIFIER; + + token_size = read_identifier(sc); + char *storage = save_buffer(sc); new_token.str = storage; new_token.size = token_size; @@ -310,6 +435,11 @@ sbLexToken compute_next_token(hScanner sc) { intval *= base; intval += base_digit_value(ch); ch = PEEK; + while (ch == '_') { + /* skip over underscores in numeric literals */ + NEXT; + ch = PEEK; + } } while (is_base_digit(ch, base)); /* if we are now looking at still a character that's a letter or digit, throw error */ @@ -319,6 +449,7 @@ sbLexToken compute_next_token(hScanner sc) { } else { fprintf(stderr, "unexpected character in base %d numeric literal: '%c'\n", base, ch); } + new_token.type = T_ERROR; NEXT; } else { @@ -335,13 +466,9 @@ sbLexToken compute_next_token(hScanner sc) { return new_token; } -sbLexToken sbScanner_next(hScanner sc) { +static void check_if_start(hScanner sc) { if (sc->next_token.type == T_NULL) { /* if we just started, queue up the first token */ sc->next_token = compute_next_token(sc); } - - sbLexToken to_return = sc->next_token; - sc->next_token = compute_next_token(sc); - return to_return; } diff --git a/src/parse/scanner.h b/src/parse/scanner.h index 7af527c..c016cd8 100644 --- a/src/parse/scanner.h +++ b/src/parse/scanner.h @@ -1,69 +1,22 @@ #include "common.h" #include "filereader.h" +#include "token.h" +#include "mem/mem.h" -typedef struct sbScanner *hScanner; +typedef struct sbScanner { + sbLexToken next_token; + hFileReader file_reader; + hArena arena; + sbBuffer dynamic_buffer; +} sbScanner; -typedef enum sbTokenType { - T_LPAREN = '(', - T_RPAREN = ')', - T_LBRACKET = '[', - T_RBRACKET = ']', - T_LBRACE = '{', - T_RBRACE = '}', - T_ASTERISK = '*', - T_SLASH = '/', - T_PLUS = '+', - T_MINUS = '-', - T_PERCENT = '%', - T_PIPE = '|', - T_DOT = '.', - T_COMMA = ',', - T_EQUALS = '=', - T_COLON = ':', - T_SEMICOLON = ';', - T_BACKSLASH = '\\', - T_NEWLINE = '\n', - T_SPACE = ' ', - T_NULL = 0, - T_ERROR = 1, - T_KEYWORD, - T_IDENTIFIER, - T_SYMBOL, - T_INTEGER, - T_FLOAT, - T_STRING, - T_ARROW, - T_FATARROW, - T_COLONBRACE, - T_DOUBLEEQUALS, - T_DOUBLEMINUS, - T_DOUBLEPLUS, - T_DOUBLEASTERISK, - T_DOUBLESLASH, - T_MINUSEQUALS, - T_PLUSEQUALS, - T_ASTERISKEQUALS, - T_SLASHEQUALS, - T_PERCENTEQUALS, - T_PAAMAYIM_NEKUDOTAYIM, - T_EOF = 255, -} sbTokenType; +typedef sbScanner *hScanner; -typedef struct sbLexToken { - sbTokenType type; - usize size; - union { - char *str; - float fl; - int i; - }; -} sbLexToken; - -hScanner sbScanner_create(hFileReader fr); +void sbScanner_initialize(hScanner sc, hFileReader fr); sbLexToken sbScanner_next(hScanner sc); sbLexToken sbScanner_peek(hScanner sc); -void sbScanner_destroy(hScanner sc); +void sbScanner_deinitialize(hScanner sc); diff --git a/src/parse/token.h b/src/parse/token.h new file mode 100644 index 0000000..6de2d7c --- /dev/null +++ b/src/parse/token.h @@ -0,0 +1,88 @@ +#ifndef __SB_TOKEN_H__ +#define __SB_TOKEN_H__ + +typedef enum sbTokenType { + T_LPAREN = '(', + T_RPAREN = ')', + T_LBRACKET = '[', + T_RBRACKET = ']', + T_LBRACE = '{', + T_RBRACE = '}', + T_ASTERISK = '*', + T_SLASH = '/', + T_PLUS = '+', + T_MINUS = '-', + T_PERCENT = '%', + T_PIPE = '|', + T_DOT = '.', + T_COMMA = ',', + T_EQUALS = '=', + T_LESS = '<', + T_GREATER = '>', + T_COLON = ':', + T_SEMICOLON = ';', + T_BACKSLASH = '\\', + T_NEWLINE = '\n', + T_SPACE = ' ', + T_NULL = 0, + T_ERROR = 1, + T_KEYWORD = 128, + T_IDENTIFIER, + T_SYMBOL, + T_INTEGER, + T_FLOAT, + T_STRING, + T_ARROW, + T_FATARROW, + T_COLONBRACE, + T_DOUBLEEQUALS, + T_DOUBLEMINUS, + T_DOUBLEPLUS, + T_DOUBLEASTERISK, + T_DOUBLESLASH, + T_DOUBLEGREATER, + T_DOUBLELESS, + T_MINUSEQUALS, + T_PLUSEQUALS, + T_ASTERISKEQUALS, + T_SLASHEQUALS, + T_PERCENTEQUALS, + T_LESSEQUALS, + T_GREATEREQUALS, + T_NOTEQUALS, + T_PAAMAYIM_NEKUDOTAYIM, + + /* reserved words */ + T_rAND, + T_rAS, + T_rCASE, + T_rDEF, + T_rDO, + T_rELSE, + T_rIF, + T_rIN, + T_rLET, + T_rNOT, + T_rOR, + T_rREPEAT, + T_rRETURN, + T_rUNLESS, + T_rUNTIL, + T_rWHEN, + T_rWHILE, + + T_EOF = 255, +} sbTokenType; + +typedef struct sbLexToken { + sbTokenType type; + usize size; + flag invisible; + union { + char *str; + float fl; + int i; + }; +} sbLexToken; + +#endif -- 1.8.3.1