From 1e07cecafc62d18ba05f21101e13b131a10e8c45 Mon Sep 17 00:00:00 2001
From: Mel <mel@rnrd.eu>
Date: Wed, 21 May 2025 16:19:59 +0200
Subject: Basic expression parser with operator precedence and associativity

Signed-off-by: Mel <mel@rnrd.eu>
---
 boot/tree.c | 149 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 149 insertions(+)

(limited to 'boot/tree.c')

diff --git a/boot/tree.c b/boot/tree.c
index 339f12c..4fb4b73 100644
--- a/boot/tree.c
+++ b/boot/tree.c
@@ -4,12 +4,31 @@
 
 enum Unary_Operation
 {
+    UNARY_NONE,
+
     UNARY_MINUS,
     UNARY_NOT,
 
     UNARY_BITWISE_NOT,
 };
 
+enum Unary_Operation
+unary_operation_from_token(const struct Token* token)
+{
+    switch (token->kind) {
+    case TOKEN_MINUS:
+        return UNARY_MINUS;
+    case TOKEN_NOT:
+        return UNARY_NOT;
+        // TODO: tilde token
+        // case TOKEN_TILDE:
+        //    return UNARY_BITWISE_NOT;
+
+    default:
+        return UNARY_NONE;
+    }
+}
+
 const ascii*
 unary_operation_to_string(enum Unary_Operation operation)
 {
@@ -28,6 +47,8 @@ unary_operation_to_string(enum Unary_Operation operation)
 
 enum Binary_Operation
 {
+    BINARY_NONE,
+
     BINARY_PLUS,
     BINARY_MINUS,
     BINARY_MULTIPLY,
@@ -50,6 +71,101 @@ enum Binary_Operation
     BINARY_BITWISE_RIGHT_SHIFT,
 };
 
+enum Binary_Operation
+binary_operation_from_token(const struct Token* token)
+{
+    switch (token->kind) {
+    case TOKEN_PLUS:
+        return BINARY_PLUS;
+    case TOKEN_MINUS:
+        return BINARY_MINUS;
+    case TOKEN_STAR:
+        return BINARY_MULTIPLY;
+    case TOKEN_SLASH:
+        return BINARY_DIVIDE;
+        // TODO: percent token
+        // case TOKEN_PERCENT:
+        // return BINARY_MODULO;
+
+    case TOKEN_EQUAL:
+        return BINARY_EQUAL;
+    case TOKEN_NOT_EQUAL:
+        return BINARY_NOT_EQUAL;
+    case TOKEN_GREATER:
+        return BINARY_GREATER_THAN;
+    case TOKEN_GREATER_EQUAL:
+        return BINARY_GREATER_THAN_EQUAL;
+    case TOKEN_LESS:
+        return BINARY_LESS_THAN;
+    case TOKEN_LESS_EQUAL:
+        return BINARY_LESS_THAN_EQUAL;
+    case TOKEN_AND:
+        return BINARY_AND;
+    case TOKEN_OR:
+        return BINARY_OR;
+
+    default:
+        return BINARY_NONE;
+    }
+}
+
+// return the precedence of the given binary operation.
+// lower values are weaker, with 1 being the weakest.
+// the values are taken mostly the same as other C-family languages.
+uint
+binary_operation_precedence(enum Binary_Operation operation)
+{
+    switch (operation) {
+    // weakest
+    case BINARY_OR:
+        return 1;
+    case BINARY_AND:
+        return 2;
+    case BINARY_BITWISE_OR:
+        return 3;
+    case BINARY_BITWISE_XOR:
+        return 4;
+    case BINARY_BITWISE_AND:
+        return 5;
+    case BINARY_EQUAL:
+    case BINARY_NOT_EQUAL:
+        return 6;
+    case BINARY_GREATER_THAN:
+    case BINARY_GREATER_THAN_EQUAL:
+    case BINARY_LESS_THAN:
+    case BINARY_LESS_THAN_EQUAL:
+        return 7;
+    case BINARY_BITWISE_LEFT_SHIFT:
+    case BINARY_BITWISE_RIGHT_SHIFT:
+        return 8;
+    case BINARY_PLUS:
+    case BINARY_MINUS:
+        return 9;
+    case BINARY_MULTIPLY:
+    case BINARY_DIVIDE:
+    case BINARY_MODULO:
+        return 10;
+        // strongest
+
+    default:
+        return 0;
+    }
+}
+
+enum Binary_Operation_Associativity
+{
+    BINARY_ASSOCIATIVITY_NONE,
+    BINARY_ASSOCIATIVITY_LEFT,
+    BINARY_ASSOCIATIVITY_RIGHT,
+};
+
+enum Binary_Operation_Associativity
+binary_operation_associativity(enum Binary_Operation operation)
+{
+    // all operations are left associative by default.
+    return BINARY_ASSOCIATIVITY_LEFT;
+}
+
 const ascii*
 binary_operation_to_string(enum Binary_Operation operation)
 {
@@ -208,6 +324,23 @@ struct Expression
 
 REGION(struct Expression, expression)
 
+struct Expression*
+expression_new(
+    enum Expression_Kind kind, union Expression_Value value, struct Span span,
+    struct Cursor location)
+{
+    check(region_expression_cursor < REGION_SIZE, "out of expression memory");
+    struct Expression* expression = &region_expression[region_expression_cursor++];
+    *expression = (struct Expression){
+        .kind = kind,
+        .value = value,
+        .span = span,
+        .location = location,
+        .next = nil,
+    };
+    return expression;
+}
+
 void
 expression_print(const struct Expression* expression)
 {
@@ -303,6 +436,22 @@ struct Statement
 
 REGION(struct Statement, statement)
 
+struct Statement*
+statement_new(
+    enum Statement_Kind kind, union Statement_Value value, struct Span span, struct Cursor location)
+{
+    check(region_statement_cursor < REGION_SIZE, "out of statement memory");
+    struct Statement* statement = &region_statement[region_statement_cursor++];
+    *statement = (struct Statement){
+        .kind = kind,
+        .value = value,
+        .span = span,
+        .location = location,
+        .next = nil,
+    };
+    return statement;
+}
+
 void
 statement_print(const struct Statement* statement)
 {
-- 
cgit 1.4.1