Update parser

It will now construct an AST of the tokens

1 files changed, 190 insertions, 60 deletions

diff --git a/main.c b/main.c
index 4ffc5dc..ab255ed 100644
--- a/main.c
+++ b/main.c
@@ -71,11 +71,12 @@ typedef struct AExp {
 
 static usize f_read(FILE* restrict stream, char** restrict dst);
 static usize f_size(FILE* restrict stream);
-static void l_print_token(Token_t token, char* restrict text);
+static void l_print_token(Token_t token, const char* restrict text);
 static line_offsets_t* l_read(char const* restrict text, usize text_length,
                               TokenList_t** restrict dst);
 static AExp_t* p_arith(char const* restrict text, TokenList_t* restrict tokens);
 static AExp_t p_number(char const* restrict text, Token_t* restrict tnum);
+static void print_aexp(AExp_t* t);
 
 int
 main(int argc, char* argv[]) {
@@ -120,35 +121,37 @@ main(int argc, char* argv[]) {
 
       AExp_t* expression = p_arith(contents, tokens);
       printf("ast:\n");
-      i16 indentation = 0;
-      for (int tokenidx = 0; tokenidx < num_tokens; tokenidx++) {
-        switch (expression[tokenidx].type) {
-        case e_mul:
-          printf("%*s*\n", indentation, " ");
-          indentation++;
-          break;
-        case e_div:
-          printf("%*s/\n", indentation, " ");
-          indentation++;
-          break;
-        case e_add:
-          printf("%*s+\n", indentation, " ");
-          indentation++;
-          break;
-        case e_sub:
-          printf("%*s-\n", indentation, " ");
-          indentation++;
-          break;
-        case e_number:
-          printf("%*d\n", indentation, expression[tokenidx].data.number);
-          indentation--;
-          break;
-        case e_error:
-        default:
-          printf("%*s\n", indentation, "error: invalid token");
-          break;
-        }
-      }
+      print_aexp(expression);
+      printf("\n");
+      // i16 indentation = 0;
+      // for (int tokenidx = 0; tokenidx < num_tokens; tokenidx++) {
+      //   switch (expression[tokenidx].type) {
+      //   case e_mul:
+      //     printf("%*s*\n", indentation, " ");
+      //     indentation++;
+      //     break;
+      //   case e_div:
+      //     printf("%*s/\n", indentation, " ");
+      //     indentation++;
+      //     break;
+      //   case e_add:
+      //     printf("%*s+\n", indentation, " ");
+      //     indentation++;
+      //     break;
+      //   case e_sub:
+      //     printf("%*s-\n", indentation, " ");
+      //     indentation++;
+      //     break;
+      //   case e_number:
+      //     printf("%*d\n", indentation, expression[tokenidx].data.number);
+      //     indentation--;
+      //     break;
+      //   case e_error:
+      //   default:
+      //     printf("%*s\n", indentation, "error: invalid token");
+      //     break;
+      //   }
+      // }
     }
 
     if (tokens != NULL) {
@@ -232,13 +235,13 @@ f_size(FILE* restrict stream) {
 }
 
 static void
-l_print_token(Token_t token, char* restrict text) {
+l_print_token(Token_t token, const char* restrict text) {
 
-  fprintf(stdout, "[%4d] %2d:%d-%d  ", token.pos.offset, token.pos.line,
-          token.pos.column, token.pos.size);
+  // fprintf(stdout, "[%4d] %2d:%d-%d  ", token.pos.offset, token.pos.line,
+  //         token.pos.column, token.pos.size);
   switch (token.type) {
   case t_error:
-    fputs(" error ", stdout);
+    fputs("%% error ", stdout);
     break;
   case t_size:
     fprintf(stdout, "size");
@@ -256,24 +259,24 @@ l_print_token(Token_t token, char* restrict text) {
     fputs(" - ", stdout);
     break;
   case t_number:
-    fputs("number:", stdout);
     fwrite(&text[token.pos.offset], token.pos.size, sizeof(char), stdout);
     break;
-  case t_space:
-    fprintf(stdout, "space:%d", token.pos.size);
-    break;
-  case t_tab:
-    fprintf(stdout, "tab:%d", token.pos.size);
-    break;
-  case t_newline:
-    fprintf(stdout, "\\n offset:%d line:%d column:%d length:%d",
-            token.pos.offset, token.pos.line, token.pos.column, token.pos.size);
-    break;
+  // case t_space:
+  //   fprintf(stdout, "space:%d", token.pos.size);
+  //   break;
+  // case t_tab:
+  //   fprintf(stdout, "tab:%d", token.pos.size);
+  //   break;
+  // case t_newline:
+  //   fprintf(stdout, "\\n offset:%d line:%d column:%d length:%d",
+  //           token.pos.offset, token.pos.line, token.pos.column,
+  //           token.pos.size);
+  //   break;
   default:
     break;
   }
 
-  puts("");
+  // puts("");
 }
 
 /* Reads text and parses it into an array of tokens
@@ -414,27 +417,110 @@ l_read(char const* restrict text, usize text_length,
 static AExp_t*
 p_arith(char const* restrict text, TokenList_t* restrict tokens) {
   i64 exp_idx          = 0;
+  // "groups" or parenthesized expressions
+  // i64 groups           = 0;
 
   const i64 num_tokens = tokens->length;
-  AExp_t* expression   = malloc(sizeof(AExp_t) * num_tokens * 2);
+  // upper bounded by tokens
+  AExp_t* expression   = calloc(num_tokens, sizeof(AExp_t));
+
+  // Root is the "current working root"
+  AExp_t* root         = NULL;
+  // Exp is the return expression, or the "root" of the expression that has
+  // parsed.
+  AExp_t* exp          = NULL;
+
   for (int tokenidx = 0; tokenidx < num_tokens; tokenidx++) {
-    if (tokens->elements[tokenidx].type == t_multiply) {
-      expression[exp_idx] = (AExp_t){.type = e_mul};
+    // ignore whitespace
+    if (tokens->elements[tokenidx].type == t_space ||
+        tokens->elements[tokenidx].type == t_tab ||
+        tokens->elements[tokenidx].type == t_newline) {
+      continue;
+    }
+
+    if (tokens->elements[tokenidx].type == t_number && root == NULL) {
+      expression[exp_idx] = p_number(text, &tokens->elements[tokenidx]);
+      root                = &expression[exp_idx];
+      exp                 = &expression[exp_idx];
       exp_idx++;
-    } else if (tokens->elements[tokenidx].type == t_add) {
-      expression[exp_idx] = (AExp_t){.type = e_add};
+
+    } else if (tokens->elements[tokenidx].type == t_number && root != NULL &&
+               root->type == e_number) {
+      fprintf(stderr, "Unexpected number at %d:%d\n",
+              tokens->elements[tokenidx].pos.line,
+              tokens->elements[tokenidx].pos.column);
+      return exp;
+
+    } else if (tokens->elements[tokenidx].type == t_number && root != NULL &&
+               root->type != e_number) {
+      if (exp_idx > 0 && expression[exp_idx - 1].type == e_number) {
+        fprintf(stderr, "Unexpected number at %d:%d\n",
+                tokens->elements[tokenidx].pos.line,
+                tokens->elements[tokenidx].pos.column);
+        return exp;
+      }
+      printf("\nroot=node + ");
+      l_print_token(tokens->elements[tokenidx], text);
+      expression[exp_idx]   = p_number(text, &tokens->elements[tokenidx]);
+      root->data.e_binary.b = &expression[exp_idx];
+      // "pop" "root" stack here?
+      root                  = exp;
       exp_idx++;
-    } else if (tokens->elements[tokenidx].type == t_number) {
-      expression[exp_idx] = p_number(text, &tokens->elements[tokenidx]);
+
+    } else if (tokens->elements[tokenidx].type != t_number && root == NULL) {
+      fprintf(stderr, "Unexpected operator at %d:%d\n",
+              tokens->elements[tokenidx].pos.line,
+              tokens->elements[tokenidx].pos.column);
+      return exp;
+
+    } else if (tokens->elements[tokenidx].type != t_number && root != NULL) {
+
+      if (tokens->elements[tokenidx].type == t_multiply) {
+        expression[exp_idx] = (AExp_t){.type = e_mul};
+      } else if (tokens->elements[tokenidx].type == t_divide) {
+        expression[exp_idx] = (AExp_t){.type = e_div};
+      } else if (tokens->elements[tokenidx].type == t_add) {
+        expression[exp_idx] = (AExp_t){.type = e_add};
+      } else if (tokens->elements[tokenidx].type == t_subtract) {
+        expression[exp_idx] = (AExp_t){.type = e_sub};
+      }
+
+      // Currently best way to test if "leaf" or binary operator, also only
+      // binary are handled
+      if (root->type == e_number) {
+        expression[exp_idx].data.e_binary.a = root;
+        root                                = &expression[exp_idx];
+        exp                                 = root;
+      } else {
+        // Currently best way to test precendence (root < expression) :(
+        if ((expression[exp_idx].type == e_mul ||
+             expression[exp_idx].type == e_div) &&
+            (root->type == e_add || root->type == e_sub)) {
+          printf("\n  # root < t  #  \n");
+          expression[exp_idx].data.e_binary.a = root->data.e_binary.b;
+          // TODO: check precedence of exp vs root
+          exp                                 = root;
+          root->data.e_binary.b               = &expression[exp_idx];
+          root                                = &expression[exp_idx];
+        } else {
+          expression[exp_idx].data.e_binary.a = root;
+          root                                = &expression[exp_idx];
+          exp                                 = root;
+        }
+      }
+
       exp_idx++;
-    } else if (tokens->elements[tokenidx].type == t_newline)
-      continue;
-    else if (tokens->elements[tokenidx].type == t_space)
-      continue;
-    // else
-    //   break;
+    }
+    printf("\nexp:");
+    print_aexp(exp);
+    printf("\nroot:");
+    print_aexp(root);
+    printf("\n");
+    for (int i = tokenidx; i < num_tokens; i++) {
+      l_print_token(tokens->elements[i], (const char* restrict)text);
+    }
   }
-  return expression;
+  return exp;
 }
 
 static AExp_t
@@ -453,3 +539,47 @@ p_number(char const* restrict text, Token_t* restrict tnum) {
     .data.number = number,
   };
 }
+
+static void
+print_aexp(AExp_t* t) {
+  if (t == NULL) {
+    printf("nil");
+    return;
+  }
+  switch (t->type) {
+  case e_error:
+    fprintf(stderr, "error");
+    break;
+  case e_mul:
+    printf("( * ");
+    print_aexp(t->data.e_binary.a);
+    printf(" ");
+    print_aexp(t->data.e_binary.b);
+    printf(" )");
+    break;
+  case e_div:
+    printf("( / ");
+    print_aexp(t->data.e_binary.a);
+    printf(" ");
+    print_aexp(t->data.e_binary.b);
+    printf(" )");
+    break;
+  case e_add:
+    printf("( + ");
+    print_aexp(t->data.e_binary.a);
+    printf(" ");
+    print_aexp(t->data.e_binary.b);
+    printf(" )");
+    break;
+  case e_sub:
+    printf("( - ");
+    print_aexp(t->data.e_binary.a);
+    printf(" ");
+    print_aexp(t->data.e_binary.b);
+    printf(" )");
+    break;
+  case e_number:
+    printf("%d", t->data.number);
+    break;
+  }
+}