[olang/patches/.build.yml] build success

[olang/patches/.build.yml] build success

[builds.sr.ht]

olang/patches/.build.yml: SUCCESS in 34s

[frontend: add basic arithmetic expr support][0] from [Johnny Richard][1]

[0]: https://lists.sr.ht/~johnnyrichard/olang-devel/patches/50195
[1]: mailto:johnny@johnnyrichard.com

✓ #1168244 SUCCESS olang/patches/.build.yml https://builds.sr.ht/~johnnyrichard/job/1168244

[PATCH olang v1 0/3] frontend: add basic arithmetic expr support

[Johnny Richard]

This patchset implements the frontend for parsing basic arithmetic
expressions. The backend implementation is not implemented on this patch
series.

Johnny Richard (3):
  lexer: add tokenize support to '+' '/' '*' '-'
  ast: create binary operation ast node
  parser: add basic arithmetic expressions '+' '*' '/' '-'

 examples/expression.ol        |   3 +
 src/ast.c                     |  14 ++++
 src/ast.h                     |  20 +++++
 src/lexer.c                   |  24 +++++-
 src/lexer.h                   |   4 +
 src/parser.c                  | 140 ++++++++++++++++++++++++++++++----
 tests/integration/cli_test.c  |  56 +++++++++++++-
 tests/integration/proc_exec.h |   3 +-
 8 files changed, 247 insertions(+), 17 deletions(-)
 create mode 100644 examples/expression.ol


base-commit: b34e6e1e8dde2852c2d1b050b6ac882605959180
-- 
2.44.0

[PATCH olang v1 1/3] lexer: add tokenize support for '+' '/' '*' '-'

[Johnny Richard]

Signed-off-by: Johnny Richard <johnny@johnnyrichard.com>
---
 examples/expression.ol        |  3 ++
 src/lexer.c                   | 24 ++++++++++++++-
 src/lexer.h                   |  4 +++
 tests/integration/cli_test.c  | 56 +++++++++++++++++++++++++++++++++--
 tests/integration/proc_exec.h |  3 +-
 5 files changed, 86 insertions(+), 4 deletions(-)
 create mode 100644 examples/expression.ol

diff --git a/examples/expression.ol b/examples/expression.ol
new file mode 100644
index 0000000..efa4ab5
--- /dev/null
+++ b/examples/expression.ol
@@ -0,0 +1,3 @@
+fn main(): u32 {
+  return (10 + 1 * 2) - (10 - (1 + 1) / 2)
+}
diff --git a/src/lexer.c b/src/lexer.c
index dd6f11d..45a3d63 100644
--- a/src/lexer.c
+++ b/src/lexer.c
@@ -126,6 +126,26 @@ lexer_next_token(lexer_t *lexer, token_t *token)
                 lexer_skip_char(lexer);
                 return;
             }
+            case '+': {
+                lexer_init_char_value_token(lexer, token, TOKEN_PLUS);
+                lexer_skip_char(lexer);
+                return;
+            }
+            case '-': {
+                lexer_init_char_value_token(lexer, token, TOKEN_DASH);
+                lexer_skip_char(lexer);
+                return;
+            }
+            case '*': {
+                lexer_init_char_value_token(lexer, token, TOKEN_STAR);
+                lexer_skip_char(lexer);
+                return;
+            }
+            case '/': {
+                lexer_init_char_value_token(lexer, token, TOKEN_SLASH);
+                lexer_skip_char(lexer);
+                return;
+            }
             case '\n': {
                 lexer_init_char_value_token(lexer, token, TOKEN_LF);
                 lexer_skip_char(lexer);
@@ -151,7 +171,9 @@ static char *token_kind_str_table[] = {
     [TOKEN_RETURN] = "return",   [TOKEN_LF] = "line_feed",
     [TOKEN_OPAREN] = "(",        [TOKEN_CPAREN] = ")",
     [TOKEN_COLON] = ":",         [TOKEN_OCURLY] = "{",
-    [TOKEN_CCURLY] = "}",        [TOKEN_EOF] = "EOF",
+    [TOKEN_CCURLY] = "}",        [TOKEN_PLUS] = "+",
+    [TOKEN_DASH] = "-",          [TOKEN_STAR] = "*",
+    [TOKEN_SLASH] = "/",         [TOKEN_EOF] = "EOF",
 };
 
 char *
diff --git a/src/lexer.h b/src/lexer.h
index cb91d7e..5ab9ccc 100644
--- a/src/lexer.h
+++ b/src/lexer.h
@@ -40,6 +40,10 @@ typedef enum token_kind
     TOKEN_RETURN,
 
     // Single char
+    TOKEN_PLUS,
+    TOKEN_DASH,
+    TOKEN_SLASH,
+    TOKEN_STAR,
     TOKEN_LF,
     TOKEN_OPAREN,
     TOKEN_CPAREN,
diff --git a/tests/integration/cli_test.c b/tests/integration/cli_test.c
index 8cc22f9..8481ba3 100644
--- a/tests/integration/cli_test.c
+++ b/tests/integration/cli_test.c
@@ -20,7 +20,7 @@
 #include <stdio.h>
 
 static MunitResult
-test_cli_dump_tokens(const MunitParameter params[], void *user_data_or_fixture)
+test_cli_dump_tokens_exmaple_main_exit(const MunitParameter params[], void *user_data_or_fixture)
 {
     cli_result_t compilation_result = cli_runner_compiler_dump_tokens("../../examples/main_exit.ol");
     munit_assert_int(compilation_result.exec.exit_code, ==, 0);
@@ -42,6 +42,47 @@ test_cli_dump_tokens(const MunitParameter params[], void *user_data_or_fixture)
     return MUNIT_OK;
 }
 
+static MunitResult
+test_cli_dump_tokens_exmaple_expression(const MunitParameter params[], void *user_data_or_fixture)
+{
+    cli_result_t compilation_result = cli_runner_compiler_dump_tokens("../../examples/expression.ol");
+    munit_assert_int(compilation_result.exec.exit_code, ==, 0);
+    munit_assert_string_equal(compilation_result.exec.stdout_buf,
+                              "../../examples/expression.ol:1:1: <fn>\n"
+                              "../../examples/expression.ol:1:4: <identifier>\n"
+                              "../../examples/expression.ol:1:8: <(>\n"
+                              "../../examples/expression.ol:1:9: <)>\n"
+                              "../../examples/expression.ol:1:10: <:>\n"
+                              "../../examples/expression.ol:1:12: <identifier>\n"
+                              "../../examples/expression.ol:1:16: <{>\n"
+                              "../../examples/expression.ol:1:17: <line_feed>\n"
+                              "../../examples/expression.ol:2:3: <return>\n"
+                              "../../examples/expression.ol:2:10: <(>\n"
+                              "../../examples/expression.ol:2:11: <number>\n"
+                              "../../examples/expression.ol:2:14: <+>\n"
+                              "../../examples/expression.ol:2:16: <number>\n"
+                              "../../examples/expression.ol:2:18: <*>\n"
+                              "../../examples/expression.ol:2:20: <number>\n"
+                              "../../examples/expression.ol:2:21: <)>\n"
+                              "../../examples/expression.ol:2:23: <->\n"
+                              "../../examples/expression.ol:2:25: <(>\n"
+                              "../../examples/expression.ol:2:26: <number>\n"
+                              "../../examples/expression.ol:2:29: <->\n"
+                              "../../examples/expression.ol:2:31: <(>\n"
+                              "../../examples/expression.ol:2:32: <number>\n"
+                              "../../examples/expression.ol:2:34: <+>\n"
+                              "../../examples/expression.ol:2:36: <number>\n"
+                              "../../examples/expression.ol:2:37: <)>\n"
+                              "../../examples/expression.ol:2:39: </>\n"
+                              "../../examples/expression.ol:2:41: <number>\n"
+                              "../../examples/expression.ol:2:42: <)>\n"
+                              "../../examples/expression.ol:2:43: <line_feed>\n"
+                              "../../examples/expression.ol:3:1: <}>\n"
+                              "../../examples/expression.ol:3:2: <line_feed>\n"
+                              "../../examples/expression.ol:4:1: <EOF>\n");
+    return MUNIT_OK;
+}
+
 static MunitResult
 test_cli_compile_minimal_program(const MunitParameter params[], void *user_data_or_fixture)
 {
@@ -62,7 +103,18 @@ test_cli_compile_minimal_program(const MunitParameter params[], void *user_data_
 }
 
 static MunitTest tests[] = {
-    { "/test_cli_dump_tokens", test_cli_dump_tokens, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+    { "/test_cli_dump_tokens_exmaple_main_exit",
+      test_cli_dump_tokens_exmaple_main_exit,
+      NULL,
+      NULL,
+      MUNIT_TEST_OPTION_NONE,
+      NULL },
+    { "/test_cli_dump_tokens_exmaple_expression",
+      test_cli_dump_tokens_exmaple_expression,
+      NULL,
+      NULL,
+      MUNIT_TEST_OPTION_NONE,
+      NULL },
     { "/test_cli_compile_minimal_program", test_cli_compile_minimal_program, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
     { NULL, NULL, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL }
 };
diff --git a/tests/integration/proc_exec.h b/tests/integration/proc_exec.h
index 135aa6a..45c2977 100644
--- a/tests/integration/proc_exec.h
+++ b/tests/integration/proc_exec.h
@@ -21,7 +21,8 @@
 typedef struct proc_exec_result
 {
     int exit_code;
-    char stdout_buf[1024];
+    // FIXME: output buffer shouldn't be fixed size
+    char stdout_buf[2048];
 } proc_exec_result_t;
 
 typedef struct proc_exec_command
-- 
2.44.0

[PATCH olang v1 2/3] ast: create binary operation ast node

[Johnny Richard]

Signed-off-by: Johnny Richard <johnny@johnnyrichard.com>
---
 src/ast.c | 14 ++++++++++++++
 src/ast.h | 20 ++++++++++++++++++++
 2 files changed, 34 insertions(+)

diff --git a/src/ast.c b/src/ast.c
index ab56c96..c9f33a4 100644
--- a/src/ast.c
+++ b/src/ast.c
@@ -52,6 +52,20 @@ ast_new_node_fn_def(arena_t *arena, string_view_t identifier, type_t return_type
     return node_fn_def;
 }
 
+ast_node_t *
+ast_new_node_bin_op(arena_t *arena, ast_binary_op_kind_t kind, ast_node_t *lhs, ast_node_t *rhs)
+{
+    ast_node_t *node_bin_op = (ast_node_t *)arena_alloc(arena, sizeof(ast_node_t));
+    assert(node_bin_op);
+
+    node_bin_op->kind = AST_NODE_BINARY_OP;
+    node_bin_op->data.as_bin_op.kind = kind;
+    node_bin_op->data.as_bin_op.lhs = lhs;
+    node_bin_op->data.as_bin_op.rhs = rhs;
+
+    return node_bin_op;
+}
+
 ast_node_t *
 ast_new_node_literal_u32(arena_t *arena, uint32_t value)
 {
diff --git a/src/ast.h b/src/ast.h
index 2b42781..206a827 100644
--- a/src/ast.h
+++ b/src/ast.h
@@ -30,6 +30,7 @@ typedef enum
     AST_NODE_PROGRAM,
     AST_NODE_BLOCK,
     AST_NODE_FN_DEF,
+    AST_NODE_BINARY_OP,
     AST_NODE_RETURN_STMT,
     AST_NODE_LITERAL,
     AST_NODE_UNKNOWN
@@ -73,6 +74,21 @@ typedef struct ast_literal
     ast_literal_value_t value;
 } ast_literal_t;
 
+typedef enum ast_binary_op_kind
+{
+    AST_BINOP_ADDITION,
+    AST_BINOP_SUBTRACTION,
+    AST_BINOP_MULTIPLICATION,
+    AST_BINOP_DIVISION,
+} ast_binary_op_kind_t;
+
+typedef struct ast_binary_op
+{
+    ast_binary_op_kind_t kind;
+    ast_node_t *lhs;
+    ast_node_t *rhs;
+} ast_binary_op_t;
+
 typedef struct ast_return_stmt
 {
     ast_node_t *data;
@@ -82,6 +98,7 @@ typedef union
 {
     ast_program_t as_program;
     ast_fn_definition_t as_fn_def;
+    ast_binary_op_t as_bin_op;
     ast_literal_t as_literal;
     ast_block_t as_block;
     ast_return_stmt_t as_return_stmt;
@@ -99,6 +116,9 @@ ast_new_program(arena_t *arena, ast_node_t *fn_def);
 ast_node_t *
 ast_new_node_fn_def(arena_t *arena, string_view_t identifier, type_t return_type, ast_node_t *block);
 
+ast_node_t *
+ast_new_node_bin_op(arena_t *arena, ast_binary_op_kind_t kind, ast_node_t *lhs, ast_node_t *rhs);
+
 ast_node_t *
 ast_new_node_literal_u32(arena_t *arena, uint32_t value);
 
-- 
2.44.0

[PATCH olang v1 3/3] parser: add basic arithmetic expressions '+' '*' '/' '-'

[Johnny Richard]

This implementation uses a call chain to guarantee calling precedence.
Whenever we try to add more expression types and it becomes complexer,
we will design a solution based on priority.

Now is pretty difficult to visualize the ast tree since we don't have a
ast pretty printer.  I have validated it by running **gdb**.

Testing the ast with unit tests is quite annoying without a good "DSL".
We can design such DSL in the near future. =^)

Signed-off-by: Johnny Richard <johnny@johnnyrichard.com>
---
 src/parser.c | 140 ++++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 127 insertions(+), 13 deletions(-)

diff --git a/src/parser.c b/src/parser.c
index 5b7d39a..ab7051d 100644
--- a/src/parser.c
+++ b/src/parser.c
@@ -39,6 +39,15 @@ parser_parse_block(parser_t *parser);
 ast_node_t *
 parser_parse_fn_definition(parser_t *parser);
 
+static ast_node_t *
+parser_parse_expr(parser_t *parser);
+
+static ast_node_t *
+parser_parse_term(parser_t *parser);
+
+static ast_node_t *
+parser_parse_factor(parser_t *parser);
+
 static void
 skip_line_feeds(lexer_t *lexer);
 
@@ -57,10 +66,117 @@ ast_node_t *
 parser_parse_program(parser_t *parser)
 {
     ast_node_t *fn = parser_parse_fn_definition(parser);
+    if (fn == NULL) {
+        return NULL;
+    }
 
     return ast_new_program(parser->arena, fn);
 }
 
+static ast_binary_op_kind_t
+token_kind_to_binary_op_kind(token_kind_t kind)
+{
+    switch (kind) {
+        case TOKEN_PLUS:
+            return AST_BINOP_ADDITION;
+        case TOKEN_DASH:
+            return AST_BINOP_SUBTRACTION;
+        case TOKEN_SLASH:
+            return AST_BINOP_DIVISION;
+        case TOKEN_STAR:
+            return AST_BINOP_MULTIPLICATION;
+        default: {
+            fprintf(stderr, "error: token kind (%s) not compatible with binary op kind\n", token_kind_to_cstr(kind));
+            assert(false);
+        }
+    }
+}
+
+static ast_node_t *
+parser_parse_expr(parser_t *parser)
+{
+    ast_node_t *node = parser_parse_term(parser);
+    if (node == NULL) {
+        return NULL;
+    }
+
+    token_t token;
+    lexer_peek_next(parser->lexer, &token);
+
+    while (token.kind == TOKEN_PLUS || token.kind == TOKEN_DASH) {
+        lexer_next_token(parser->lexer, &token);
+
+        ast_node_t *lhs = node;
+        ast_node_t *rhs = parser_parse_term(parser);
+        if (rhs == NULL) {
+            return NULL;
+        }
+
+        node = ast_new_node_bin_op(parser->arena, token_kind_to_binary_op_kind(token.kind), lhs, rhs);
+
+        lexer_peek_next(parser->lexer, &token);
+    }
+
+    return node;
+}
+
+static ast_node_t *
+parser_parse_term(parser_t *parser)
+{
+    ast_node_t *node = parser_parse_factor(parser);
+    if (node == NULL) {
+        return NULL;
+    }
+
+    token_t token;
+    lexer_peek_next(parser->lexer, &token);
+
+    while (token.kind == TOKEN_STAR || token.kind == TOKEN_SLASH) {
+        lexer_next_token(parser->lexer, &token);
+
+        ast_node_t *lhs = node;
+        ast_node_t *rhs = parser_parse_factor(parser);
+        if (rhs == NULL) {
+            return NULL;
+        }
+
+        node = ast_new_node_bin_op(parser->arena, token_kind_to_binary_op_kind(token.kind), lhs, rhs);
+
+        lexer_peek_next(parser->lexer, &token);
+    }
+
+    return node;
+}
+
+static ast_node_t *
+parser_parse_factor(parser_t *parser)
+{
+    token_t token;
+    lexer_next_token(parser->lexer, &token);
+
+    switch (token.kind) {
+        case TOKEN_NUMBER:
+            return ast_new_node_literal_u32(parser->arena, string_view_to_u32(token.value));
+
+        case TOKEN_OPAREN: {
+            ast_node_t *expr = parser_parse_expr(parser);
+            if (expr == NULL) {
+                return NULL;
+            }
+
+            if (!skip_expected_token(parser, TOKEN_CPAREN)) {
+                return NULL;
+            }
+
+            return expr;
+        }
+        default: {
+            fprintf(stderr, "error: parse_factor: unsupported or invalid token (%s)\n", token_kind_to_cstr(token.kind));
+            assert(false);
+        }
+    }
+}
+
 ast_node_t *
 parser_parse_fn_definition(parser_t *parser)
 {
@@ -131,41 +247,39 @@ parser_parse_type(parser_t *parser, type_t *type)
 static ast_node_t *
 parser_parse_block(parser_t *parser)
 {
-    token_t number_token;
     if (!skip_expected_token(parser, TOKEN_OCURLY)) {
-        return false;
+        return NULL;
     }
 
     skip_line_feeds(parser->lexer);
 
     ast_node_t *node_block = ast_new_node_block(parser->arena);
+    if (node_block == NULL) {
+        return NULL;
+    }
 
     if (!skip_expected_token(parser, TOKEN_RETURN)) {
-        return false;
+        return NULL;
     }
 
     ast_node_t *node_return_stmt = ast_new_node_return_stmt(parser->arena);
     assert(node_return_stmt);
 
-    if (!expected_token(parser, &number_token, TOKEN_NUMBER)) {
-        return false;
+    ast_node_t *expr = parser_parse_expr(parser);
+    if (expr == NULL) {
+        return NULL;
     }
 
-    ast_node_t *literal_node = ast_new_node_literal_u32(parser->arena, string_view_to_u32(number_token.value));
-    assert(literal_node);
-
-    node_return_stmt->data.as_return_stmt.data = literal_node;
+    node_return_stmt->data.as_return_stmt.data = expr;
 
     list_append(node_block->data.as_block.nodes, node_return_stmt);
-
     if (!skip_expected_token(parser, TOKEN_LF)) {
-        return false;
+        return NULL;
     }
 
     skip_line_feeds(parser->lexer);
-
     if (!skip_expected_token(parser, TOKEN_CCURLY)) {
-        return false;
+        return NULL;
     }
 
     return node_block;
-- 
2.44.0

Re: [PATCH olang v1 0/3] frontend: add basic arithmetic expr support

[Johnny Richard]

This patchset has been SUPERSEDED by v2