Add parser for tokens->ast conversion

5 files changed, 379 insertions, 31 deletions

diff --git a/src/lexer.c b/src/lexer.c
index 6a417e4..ac93a5c 100755
--- a/src/lexer.c
+++ b/src/lexer.c
@@ -16,7 +16,7 @@ static const char* token_str[] = {
 
 void
 print_token(Token tok) {
-    printf("[%4ld:%-4ld] ", tok.line, tok.column);
+    printf("[%4ld:%-4ld] ", tok.line, tok.col);
     printf("%s", token_str[tok.type]);
     switch (tok.type) {
         case TOKEN_FIXNUM: {
@@ -128,11 +128,10 @@ find_primitive_type(const StringView value) {
     return TOKEN_SYMBOL;
 }
 
-Tokens
-tokenize(const StringView *sv) {
-    Tokens tokens = {0};
-    tokens.tokens = NULL;
-    array_init(tokens.tokens, 1);
+Token *
+tokenize(const StringView *sv, Errors *errors) {
+    Token *tokens = NULL;
+    array_init(tokens, 1);
     Scanner scanner = (Scanner){
         .current = *sv,
         .line_number = 1,
@@ -163,7 +162,7 @@ tokenize(const StringView *sv) {
                     n++;
                 }
                 if (!found) {
-                    error_push(&tokens.errors, (Error){
+                    error_push(errors, (Error){
                         .type = ERR_TYPE_LEXER,
                         .value = ERR_UNMATCHED_STRING,
                         .line = line,
@@ -178,9 +177,9 @@ tokenize(const StringView *sv) {
                     },
                     .type = TOKEN_STRING,
                     .line = line,
-                    .column = col,
+                    .col = col,
                 };
-                array_push(tokens.tokens, token);
+                array_push(tokens, token);
             } break;
             case '(': {
                 if (scan_peek(&scanner) == ')') {
@@ -188,25 +187,25 @@ tokenize(const StringView *sv) {
                     Token token =  (Token){
                         .type = TOKEN_NIL,
                         .line = line,
-                        .column = col,
+                        .col = col,
                     };
-                    array_push(tokens.tokens, token);
+                    array_push(tokens, token);
                 } else {
                     Token token =  (Token){
                         .type = TOKEN_LPAREN,
                         .line = line,
-                        .column = col,
+                        .col = col,
                     };
-                    array_push(tokens.tokens, token);
+                    array_push(tokens, token);
                 }
             } break;
             case ')': {
                 Token token =  (Token){
                     .type = TOKEN_RPAREN,
                     .line = line,
-                    .column = col,
+                    .col = col,
                 };
-                array_push(tokens.tokens, token);
+                array_push(tokens, token);
             } break;
             default: {
                 size_t n = 1;
@@ -224,10 +223,10 @@ tokenize(const StringView *sv) {
                     },
                     .type = TOKEN_SYMBOL,
                     .line = line,
-                    .column = col,
+                    .col = col,
                 };
                 token.type = find_primitive_type(token.value);
-                array_push(tokens.tokens, token);
+                array_push(tokens, token);
             } break;
         }
     }
@@ -236,9 +235,9 @@ tokenize(const StringView *sv) {
     Token token =  (Token){
         .type = TOKEN_EOF,
         .line = scanner.line_number,
-        .column = 1,
+        .col = 1,
     };
-    array_push(tokens.tokens, token);
+    array_push(tokens, token);
 
     return tokens;
 }
diff --git a/src/lexer.h b/src/lexer.h
index e56f5f2..43898bd 100755
--- a/src/lexer.h
+++ b/src/lexer.h
@@ -26,14 +26,9 @@ typedef struct Token {
     TokenType type;
     StringView value;
     size_t line;
-    size_t column;
+    size_t col;
 } Token;
 
-typedef struct Tokens {
-    Token *tokens;
-    Errors errors;
-} Tokens;
-
 typedef struct Scanner {
     StringView current;
     size_t line_number;
@@ -62,6 +57,6 @@ bool is_delimiter(char c);
 TokenType find_primitive_type(const StringView value);
 
 // Generate a list of tokens from the given string.
-Tokens tokenize(const StringView *sv);
+Token * tokenize(const StringView *sv, Errors *errors);
 
 #endif // BDL_LEXER_H
diff --git a/src/main.c b/src/main.c
index 90860e8..c734916 100755
--- a/src/main.c
+++ b/src/main.c
@@ -7,6 +7,7 @@
 #include "string_view.c"
 #include "errors.c"
 #include "lexer.c"
+#include "parser.c"
 
 void
 init(void) {
@@ -20,20 +21,32 @@ halt(void) {
 
 void
 process_source(const StringView *source, const char *file_name) {
+    Errors errors = {0};
+
     // Read tokens.
-    Tokens tokens = tokenize(source);
-    if (tokens.errors.n != 0) {
-        report_errors(&tokens.errors, file_name);
+    Token *tokens = tokenize(source, &errors);
+    if (errors.n != 0) {
+        report_errors(&errors, file_name);
+        array_free(tokens);
+        exit(EXIT_FAILURE);
+    }
+
+    // Parser.
+    Root *roots = parse(tokens, &errors);
+    if (errors.n != 0) {
+        report_errors(&errors, file_name);
+        free_roots(roots);
+        array_free(tokens);
         exit(EXIT_FAILURE);
     }
+    array_free(tokens);
 
-    // TODO: Parser.
     // TODO: Semantic analysis.
     // TODO: Optimization.
     // TODO: Compilation.
 
     // Free resources.
-    array_free(tokens.tokens);
+    free_roots(roots);
 }
 
 void
diff --git a/src/parser.c b/src/parser.c
new file mode 100644
index 0000000..2d70c9d
--- /dev/null
+++ b/src/parser.c
@@ -0,0 +1,257 @@
+#include "parser.h"
+#include "darray.h"
+
+Token
+peek_token(const Parser *parser) {
+    return parser->tokens[parser->current];
+}
+
+Token
+next_token(Parser *parser) {
+    return parser->tokens[parser->current++];
+}
+
+Token
+previous_token(Parser *parser) {
+    return parser->tokens[parser->current - 1];
+}
+
+Token
+rewind_token(Parser *parser) {
+    return parser->tokens[--parser->current];
+}
+
+bool
+has_next_token(const Parser *parser) {
+    return parser->current < array_size(parser->tokens)
+        && peek_token(parser).type != TOKEN_EOF;
+}
+
+Object *
+parse_fixnum(Token tok) {
+    ssize_t num = 0;
+    ssize_t sign = 1;
+    for (size_t i = 0; i < tok.value.n; i++) {
+        char c = tok.value.start[i];
+        if (c == '-') {
+            sign = -1;
+            continue;
+        }
+        num = num * 10 + (c - '0');
+    }
+    Object *ret = object_alloc(tok, OBJ_TYPE_FIXNUM);
+    ret->fixnum = num * sign;
+    return ret;
+}
+
+Object *
+parse_bool(Token tok) {
+    ObjectType type = tok.type == TOKEN_TRUE ? OBJ_TYPE_TRUE : OBJ_TYPE_FALSE;
+    Object *ret = object_alloc(tok, type);
+    return ret;
+}
+
+Object *
+parse_string(Token tok) {
+    Object *ret = object_alloc(tok, OBJ_TYPE_STRING);
+    array_init(ret->text, tok.value.n);
+    array_insert(ret->text, tok.value.start, tok.value.n);
+    return ret;
+}
+
+Object *
+parse_symbol(Token tok) {
+    Object *ret = object_alloc(tok, OBJ_TYPE_SYMBOL);
+    array_init(ret->text, tok.value.n);
+    array_insert(ret->text, tok.value.start, tok.value.n);
+    return ret;
+}
+
+Object *
+parse_list(Parser *parser, Errors *errors) {
+    if (errors->n != 0) {
+        return NULL;
+    }
+    Token start = previous_token(parser);
+    Object *root = object_alloc(start, OBJ_TYPE_PAIR);
+    root->car = NULL;
+    root->cdr = NULL;
+    Object *current = root;
+    while (has_next_token(parser)) {
+        current->car = parse_tree(parser, errors);
+        if (errors->n != 0 || current->car == NULL) {
+            object_free(root);
+            return NULL;
+        }
+
+        Token tok = peek_token(parser);
+        if (tok.type == TOKEN_RPAREN) {
+            next_token(parser);
+            return root;
+        }
+
+        Object *next = object_alloc(start, OBJ_TYPE_PAIR);
+        next->car = NULL;
+        next->cdr = NULL;
+        current->cdr = next;
+        current = current->cdr;
+    }
+    object_free(root);
+    error_push(errors, (Error){
+        .type = ERR_TYPE_PARSER,
+        .value = ERR_UNBALANCED_PAREN,
+        .line = start.line,
+        .col = start.col,
+    });
+    return NULL;
+}
+
+Object *
+parse_tree(Parser *parser, Errors *errors) {
+    Token tok = next_token(parser);
+    if (errors->n != 0) {
+        return NULL;
+    }
+    switch (tok.type) {
+        case TOKEN_FIXNUM: {
+             return parse_fixnum(tok);
+        } break;
+        case TOKEN_TRUE:
+        case TOKEN_FALSE: {
+            return parse_bool(tok);
+        } break;
+        case TOKEN_RPAREN: {
+            error_push(errors, (Error){
+                .type = ERR_TYPE_PARSER,
+                .value = ERR_UNBALANCED_PAREN,
+                .line = tok.line,
+                .col = tok.col,
+            });
+            return NULL;
+        } break;
+        case TOKEN_LPAREN: {
+            return parse_list(parser, errors);
+        } break;
+        case TOKEN_STRING: {
+            return parse_string(tok);
+        } break;
+        case TOKEN_SYMBOL: {
+            return parse_symbol(tok);
+        } break;
+        case TOKEN_NIL: {
+            return object_alloc(tok, OBJ_TYPE_NIL);
+        } break;
+        default: {
+            break;
+        } break;
+    }
+    error_push(errors, (Error){
+        .type = ERR_TYPE_PARSER,
+        .value = ERR_EOF_REACHED,
+        .line = tok.line,
+        .col = tok.col,
+    });
+    return NULL;
+}
+
+Root *
+parse(Token *tokens, Errors *errors) {
+    Root *roots = NULL;
+    array_init(roots, 0);
+    Parser parser = {
+        .tokens = tokens,
+        .current = 0,
+    };
+    while (has_next_token(&parser)) {
+        Object *root = parse_tree(&parser, errors);
+        OBJ_PRINT(root);
+        if (errors->n != 0) {
+            break;
+        }
+        array_push(roots, root);
+    }
+    return roots;
+}
+
+Object *
+object_alloc(Token tok, ObjectType type) {
+    Object *node = malloc(sizeof(Object));
+    node->line = tok.line;
+    node->col = tok.col;
+    node->type = type;
+    return node;
+}
+
+void
+object_free(Object *node) {
+    if (node == NULL) {
+        return;
+    }
+    if (IS_STRING(node) || IS_SYMBOL(node)) {
+        array_free(node->text);
+    }
+    if (IS_PAIR(node)) {
+        object_free(node->car);
+        object_free(node->cdr);
+    }
+    free(node);
+}
+
+void
+free_roots(Root *roots) {
+    if (roots != NULL) {
+        for (size_t i = 0; i < array_size(roots); i++) {
+            object_free(roots[i]);
+        }
+        array_free(roots);
+    }
+}
+
+void
+display_pair(Object *obj) {
+    object_display(obj->car);
+    if (obj->cdr == NULL) {
+        return;
+    }
+    if (IS_PAIR(obj->cdr)) {
+        printf(" ");
+        display_pair(obj->cdr);
+    } else {
+        printf(" . ");
+        object_display(obj->cdr);
+    }
+}
+
+void
+object_display(Object *obj) {
+    if (obj == NULL) {
+        printf("#{error}");
+        return;
+    }
+    switch (obj->type) {
+        case OBJ_TYPE_FIXNUM: {
+            printf("%zd", obj->fixnum);
+        } break;
+        case OBJ_TYPE_TRUE: {
+            printf("true");
+        } break;
+        case OBJ_TYPE_FALSE: {
+            printf("false");
+        } break;
+        case OBJ_TYPE_NIL: {
+            printf("()");
+        } break;
+        case OBJ_TYPE_STRING: {
+            printf("\"%.*s\"", (int)array_size(obj->text), obj->text);
+        } break;
+        case OBJ_TYPE_SYMBOL: {
+            printf(":%.*s", (int)array_size(obj->text), obj->text);
+        } break;
+        case OBJ_TYPE_PAIR: {
+            printf("(");
+            display_pair(obj);
+            printf(")");
+        } break;
+    }
+    return;
+}
diff --git a/src/parser.h b/src/parser.h
new file mode 100755
index 0000000..ee5febe
--- /dev/null
+++ b/src/parser.h
@@ -0,0 +1,84 @@
+#ifndef BDL_PARSER_H
+#define BDL_PARSER_H
+
+#include "lexer.h"
+
+typedef enum ObjectType {
+    OBJ_TYPE_NIL,
+    OBJ_TYPE_TRUE,
+    OBJ_TYPE_FALSE,
+    OBJ_TYPE_FIXNUM,
+    OBJ_TYPE_SYMBOL,
+    OBJ_TYPE_STRING,
+    OBJ_TYPE_PAIR,
+} ObjectType;
+
+typedef struct Object {
+    ObjectType type;
+    union {
+        // OBJ_TYPE_FIXNUM
+        ssize_t fixnum;
+
+        // OBJ_TYPE_STRING
+        // OBJ_TYPE_SYMBOL
+        char *text;
+
+        // OBJ_TYPE_PAIR
+        struct {
+            struct Object *car;
+            struct Object *cdr;
+        };
+    };
+
+    size_t line;
+    size_t col;
+} Object;
+
+typedef struct Parser {
+    Token *tokens;
+    size_t current;
+} Parser;
+
+typedef Object* Root;
+
+// Mimics the functionality in the Scanner functions, but for tokens.
+Token next_token(Parser *parser);
+Token previous_token(Parser *parser);
+Token rewind_token(Parser *parser);
+Token peek_token(const Parser *parser);
+bool has_next_token(const Parser *parser);
+
+// Parsing operations.
+Object * parse_tree(Parser *parser, Errors *errors);
+Object * parse_symbol(Token tok);
+Object * parse_string(Token tok);
+Object * parse_bool(Token tok);
+Object * parse_fixnum(Token tok);
+Object * parse_list(Parser *parser, Errors *errors);
+Root * parse(Token *tokens, Errors *errors);
+
+// Object operations.
+void object_display(Object *obj);
+
+// Manage resources.
+Object * object_alloc(Token tok, ObjectType type);
+void object_free(Object *node);
+void free_roots(Root *roots);
+
+//
+// Helper macros.
+//
+
+// Type checking.
+#define IS_NIL(VAL)    ((VAL)->type == OBJ_TYPE_NIL)
+#define IS_TRUE(VAL)   ((VAL)->type != OBJ_TYPE_FALSE)
+#define IS_FALSE(VAL)  ((VAL)->type == OBJ_TYPE_FALSE)
+#define IS_FIXNUM(VAL) ((VAL)->type == OBJ_TYPE_FIXNUM)
+#define IS_STRING(VAL) ((VAL)->type == OBJ_TYPE_STRING)
+#define IS_SYMBOL(VAL) ((VAL)->type == OBJ_TYPE_SYMBOL)
+#define IS_PAIR(VAL)   ((VAL)->type == OBJ_TYPE_PAIR)
+
+// Debug.
+#define OBJ_PRINT(OBJ) object_display(OBJ); printf("\n");
+
+#endif // BDL_PARSER_H