sync

1 files changed, 153 insertions, 0 deletions

diff --git a/bu-parser.c b/bu-parser.c
new file mode 100644
index 0000000..624bedc
--- /dev/null
+++ b/bu-parser.c
@@ -0,0 +1,153 @@
+#include "bu-parser.h"
+
+void free_node(node *n) {
+  if (n->lhs) free_node(n->lhs);
+  if (n->rhs) free_node(n->rhs);
+  free(n);
+}
+
+struct expr_parser expr_parser_init(lexer_fn src, void* lex_data) {
+  return (struct expr_parser){
+    .lex = src,
+    .lex_data = lex_data,
+    .lahead = {0},
+    .st = PARSER_READY,
+    .stack = {0},
+    .stack_idx = 0,
+  };
+}
+
+void expr_parser_finish(struct expr_parser *ep) {
+  for (size_t i = 0; i < ep->stack_idx; i++) {
+    if (ep->stack[i].id == STACKMEMBER_EXPR)
+      free_node(ep->stack[i].expr);
+  }
+}
+
+struct stackmember stack_pos(struct expr_parser *ep, size_t pos) {
+  ssize_t npos = ep->stack_idx - pos;
+  if (npos < 0) {
+    fprintf(stderr, "bad stack idx");
+    return (struct stackmember)
+      { .id = (enum stackmember_id)TOKEN_OOB, .expr = NULL };
+  }
+  return ep->stack[npos];
+}
+
+void shift(struct expr_parser *ep) {
+  ep->stack[ep->stack_idx] = (struct stackmember){
+    .id = (enum stackmember_id)ep->lahead.id,
+    .terminal = ep->lahead.c,
+  };
+  ep->stack_idx++;
+  ep->lahead = ep->lex(ep->lex_data);
+}
+
+void var_expr(struct expr_parser *ep) {
+  struct stackmember v = stack_pos(ep, 0);
+  if (v.id != TOKEN_VARIABLE) {
+    ep->st = PARSER_ERR;
+    fprintf(stderr, "%s: not a variable token", __func__);
+    return;
+  }
+
+  node *n = malloc(sizeof(node));
+  n->type = LTTR;
+  n->el = v.terminal;
+
+  struct stackmember newm = {
+    .id = STACKMEMBER_EXPR,
+    .expr = n,
+  };
+
+  ep->stack[ep->stack_idx] = newm;
+}
+
+void binary_expr(struct expr_parser *ep) {
+  struct stackmember rhs, op, lhs;
+  lhs = stack_pos(ep, 2);
+  op  = stack_pos(ep, 1);
+  rhs = stack_pos(ep, 0);
+  if ( lhs.id != STACKMEMBER_EXPR
+    || op.id != TOKEN_BINARY_OPERATOR
+    || rhs.id != STACKMEMBER_EXPR
+  ) {
+    ep->st = PARSER_ERR;
+    fprintf(stderr, "%s: incorrect token pattern", __func__);
+    return;
+  }
+
+  node *n = malloc(sizeof(node));
+  n->type = BIOP;
+  n->el = op.terminal;
+  n->lhs = lhs.expr;
+  n->rhs = rhs.expr;
+
+  struct stackmember newm = {
+    .id = STACKMEMBER_EXPR,
+    .expr = n,
+  };
+  
+  ep->stack_idx -= 2;
+  ep->stack[ep->stack_idx] = newm;
+}
+
+void unary_expr(struct expr_parser *ep) {
+  struct stackmember op, val;
+  op  = stack_pos(ep, 1);
+  val = stack_pos(ep, 0);
+  if ( op.id != TOKEN_UNARY_OPERATOR
+    || val.id != STACKMEMBER_EXPR
+  ) {
+    ep->st = PARSER_ERR;
+    fprintf(stderr, "%s: incorrect token pattern", __func__);
+    return;
+  }
+
+  node *n = malloc(sizeof(node));
+  n->type = UNOP;
+  n->el = op.terminal;
+  n->value = val.expr;
+
+  struct stackmember newm = {
+    .id = STACKMEMBER_EXPR,
+    .expr = n,
+  };
+  
+  ep->stack_idx -= 1;
+  ep->stack[ep->stack_idx] = newm;
+}
+
+int expr_parser_run(struct expr_parser *ep) {
+  while (ep->st != PARSER_ERR) {
+    shift(ep);
+    struct stackmember top = stack_pos(ep, 0);
+    if (top.id == TOKEN_EOS) {
+      ep->st = PARSER_OK;
+      continue;
+    }
+    if (top.id == TOKEN_VARIABLE) {
+      var_expr(ep);
+    }
+    if (ep->st == PARSER_OR_OP || ep->st == PARSER_AND_OP) {
+      if (ep->st == PARSER_OR_OP) {
+        if (ep->lahead.c == '*') continue;
+      }
+      binary_expr(ep);
+    }
+    else if (ep->st == PARSER_NOT_OP) {
+      unary_expr(ep);
+    }
+    if (top.id == TOKEN_BINARY_OPERATOR || top.id == TOKEN_UNARY_OPERATOR) {
+      switch (top.terminal) {
+        case '+': ep->st = PARSER_OR_OP; break;
+        case '*': ep->st = PARSER_AND_OP; break;
+        case '!': ep->st = PARSER_NOT_OP; break;
+        default: break;
+      }
+      continue;
+    }
+  }
+  return ep->st;
+}
+