Add some arithmetic binary operations into lex+parse+generation

5 files changed, 184 insertions, 19 deletions

diff --git a/cup/ast.c b/cup/ast.c
index 6adf0d0..3565274 100644
--- a/cup/ast.c
+++ b/cup/ast.c
@@ -23,6 +23,50 @@ char *node_type_to_str(NodeType type)
     }
 }
 
+bool is_binary_op(NodeType type)
+{
+    switch (type)
+    {
+    case OP_PLUS:
+    case OP_MINUS:
+    case OP_MUL:
+    case OP_DIV:
+    case OP_MOD:
+    case OP_LSHIFT:
+    case OP_RSHIFT:
+    case OP_AND:
+    case OP_OR:
+    case OP_XOR:
+    case OP_EQ:
+    case OP_NEQ:
+    case OP_LT:
+    case OP_LEQ:
+    case OP_GT:
+    case OP_GEQ: 
+        return true;
+    default: return false;
+    }
+}
+
+bool is_unary_op(NodeType type)
+{
+    switch (type)
+    {
+    case OP_NEG:
+    case OP_NOT:
+    case OP_BWINV:
+        return true;
+    default: return false;
+    }
+}
+
+bool is_expression(NodeType type)
+{
+    if (is_unary_op(type) || is_binary_op(type))
+        return true;
+    return type == AST_LITERAL;
+}
+
 static void do_print_ast(Node *node, int depth)
 {
     for (int i = 0; i < depth; i++) {
@@ -59,17 +103,15 @@ static void do_print_ast(Node *node, int depth)
     } else if (node->type == AST_RETURN) {
         printf("return\n");
         do_print_ast(node->unary_expr, depth + 1);
-    } else if (node->type == OP_NEG) {
-        printf("-\n");
-        do_print_ast(node->unary_expr, depth + 1);
-    } else if (node->type == OP_NOT) {
-        printf("!\n");
-        do_print_ast(node->unary_expr, depth + 1);
-    } else if (node->type == OP_BWINV) {
-        printf("~\n");
+    } else if (is_unary_op(node->type)) {
+        printf("%s\n", node_type_to_str(node->type));
         do_print_ast(node->unary_expr, depth + 1);
+    } else if (is_binary_op(node->type)) {
+        printf("%s\n", node_type_to_str(node->type));
+        do_print_ast(node->binary.left, depth + 1);
+        do_print_ast(node->binary.right, depth + 1);
     } else {
-        printf("(unknown)\n");
+        printf("Don't know how to handle: `%s`\n", node_type_to_str(node->type));
     }
 }
 
diff --git a/cup/ast.h b/cup/ast.h
index c35ab87..6e05257 100644
--- a/cup/ast.h
+++ b/cup/ast.h
@@ -10,12 +10,23 @@
   F(OP_MINUS, "-")                                                             \
   F(OP_MUL, "*")                                                               \
   F(OP_DIV, "/")                                                               \
+  F(OP_MOD, "%")                                                               \
+  F(OP_LSHIFT, "<<")                                                           \
+  F(OP_RSHIFT, ">>")                                                           \
+  F(OP_AND, "&&")                                                              \
+  F(OP_OR, "||")                                                               \
+  F(OP_XOR, "^")                                                               \
+  F(OP_EQ, "==")                                                               \
+  F(OP_NEQ, "!=")                                                              \
+  F(OP_LT, "<")                                                                \
+  F(OP_LEQ, "<=")                                                              \
+  F(OP_GT, ">")                                                                \
+  F(OP_GEQ, ">=")                                                              \
   F(AST_LITERAL, "literal")                                                    \
   F(AST_RETURN, "return")                                                      \
   F(AST_FUNC, "func")                                                          \
   F(AST_PROGRAM, "program")                                                    \
-  F(AST_BLOCK, "block statements")                                             \
-
+  F(AST_BLOCK, "block statements")
 
 typedef enum {
 #define DEFINE_ENUM(name, str) name,
@@ -25,6 +36,10 @@ typedef enum {
 
 char *node_type_to_str(NodeType type);
 
+bool is_binary_op(NodeType type);
+bool is_unary_op(NodeType type);
+bool is_expression(NodeType type);
+
 typedef enum {
     TYPE_NONE,
     TYPE_INT,
diff --git a/cup/generator.c b/cup/generator.c
index edb38ad..6018e47 100644
--- a/cup/generator.c
+++ b/cup/generator.c
@@ -30,6 +30,37 @@ void generate_expr_into_rax(Node *expr, FILE *out)
         generate_expr_into_rax(expr->unary_expr, out);
         fprintf(out, "    not rax\n");
         
+    } else if (expr->type == OP_PLUS) {
+        generate_expr_into_rax(expr->binary.left, out);
+        fprintf(out, "    push rax\n");
+        generate_expr_into_rax(expr->binary.right, out);
+        fprintf(out, "    pop rbx\n");
+        fprintf(out, "    add rax, rbx\n");
+
+    } else if (expr->type == OP_MINUS) {
+        generate_expr_into_rax(expr->binary.left, out);
+        fprintf(out, "    push rax\n");
+        generate_expr_into_rax(expr->binary.right, out);
+        fprintf(out, "    mov rbx, rax\n");
+        fprintf(out, "    pop rax\n");
+        fprintf(out, "    sub rax, rbx\n");
+
+    } else if (expr->type == OP_DIV) {
+        generate_expr_into_rax(expr->binary.left, out);
+        fprintf(out, "    push rax\n");
+        generate_expr_into_rax(expr->binary.right, out);
+        fprintf(out, "    mov rbx, rax\n");
+        fprintf(out, "    pop rax\n");
+        fprintf(out, "    cqo\n");
+        fprintf(out, "    idiv rbx\n");
+
+    } else if (expr->type == OP_MUL) {
+        generate_expr_into_rax(expr->binary.left, out);
+        fprintf(out, "    push rax\n");
+        generate_expr_into_rax(expr->binary.right, out);
+        fprintf(out, "    pop rbx\n");
+        fprintf(out, "    imul rbx\n");
+
     } else {
         fprintf(stderr, "Unsupported expression type in generate_expr: %d\n", expr->type);
         exit(1);
diff --git a/cup/parser.c b/cup/parser.c
index 746a139..a6ea9b2 100644
--- a/cup/parser.c
+++ b/cup/parser.c
@@ -16,6 +16,37 @@ Token do_assert_token(Token token, TokenType type, char *filename, int line)
 
 #define assert_token(token, type) do_assert_token(token, type, __FILE__, __LINE__)
 
+/******
+ * Some helpers
+ */
+
+NodeType binary_token_to_op(TokenType type)
+{
+    switch (type)
+    {
+        case TOKEN_PLUS:    return OP_PLUS;
+        case TOKEN_MINUS:   return OP_MINUS;
+        case TOKEN_STAR:    return OP_MUL;
+        case TOKEN_SLASH:   return OP_DIV;
+        case TOKEN_PERCENT: return OP_MOD;
+        case TOKEN_LSHIFT:  return OP_LSHIFT;
+        case TOKEN_RSHIFT:  return OP_RSHIFT;
+        case TOKEN_AND:     return OP_AND;
+        case TOKEN_OR:      return OP_OR;
+        case TOKEN_XOR:     return OP_XOR;
+        case TOKEN_EQ:      return OP_EQ;
+        case TOKEN_NEQ:     return OP_NEQ;
+        case TOKEN_LT:      return OP_LT;
+        case TOKEN_LEQ:     return OP_LEQ;
+        case TOKEN_GT:      return OP_GT;
+        case TOKEN_GEQ:     return OP_GEQ;
+        
+        default: assert(false && "binary_token_to_op called with invalid token type");
+    }
+}
+
+
+
 void Node_add_child(Node *parent, Node *child)
 {
     // TODO, use a vector
@@ -59,7 +90,9 @@ Node *parse_literal(Lexer *lexer)
     return node;
 }
 
-Node *parse_expression(Lexer *lexer)
+Node *parse_expression(Lexer *);
+
+Node *parse_factor(Lexer *lexer)
 {
     // TODO: Parse more complicated things
     Token token = Lexer_peek(lexer);
@@ -67,17 +100,60 @@ Node *parse_expression(Lexer *lexer)
     if (token.type == TOKEN_MINUS) {
         Lexer_next(lexer);
         expr = Node_new(OP_NEG);
-        expr->unary_expr = parse_expression(lexer);
+        expr->unary_expr = parse_factor(lexer);
     } else if (token.type == TOKEN_TILDE) {
         Lexer_next(lexer);
         expr = Node_new(OP_BWINV);
-        expr->unary_expr = parse_expression(lexer);
+        expr->unary_expr = parse_factor(lexer);
     } else if (token.type == TOKEN_EXCLAMATION) {
         Lexer_next(lexer);
         expr = Node_new(OP_NOT);
-        expr->unary_expr = parse_expression(lexer);
+        expr->unary_expr = parse_factor(lexer);
+    } else if (token.type == TOKEN_OPEN_PAREN) {
+        Lexer_next(lexer);
+        expr = parse_expression(lexer);
+        assert_token(Lexer_next(lexer), TOKEN_CLOSE_PAREN);
+    } else if (token.type == TOKEN_INTLIT) {
+        expr = parse_literal(lexer);
     } else {
-        return parse_literal(lexer);
+        die_location(token.loc, "Expected token found in parse_factor: `%s`", token_type_to_str(token.type));
+        exit(1);
+    }
+    return expr;
+}
+
+Node *parse_term(Lexer *lexer)
+{
+    Node *expr = parse_factor(lexer);
+    Token token = Lexer_peek(lexer);
+    while (token.type == TOKEN_STAR || 
+           token.type == TOKEN_SLASH || 
+           token.type == TOKEN_PERCENT) {
+        Lexer_next(lexer);
+        Node *op = Node_new(binary_token_to_op(token.type));
+        Node *right = parse_factor(lexer);
+        op->binary.left = expr;
+        op->binary.right = right;
+        expr = op;
+        token = Lexer_peek(lexer);
+    }
+    return expr;
+}
+
+
+Node *parse_expression(Lexer *lexer)
+{
+    Node *expr = parse_term(lexer);
+    Token token = Lexer_peek(lexer);
+    while (token.type == TOKEN_PLUS || 
+           token.type == TOKEN_MINUS) {
+        Lexer_next(lexer);
+        Node *op = Node_new(binary_token_to_op(token.type));
+        Node *right = parse_term(lexer);
+        op->binary.left = expr;
+        op->binary.right = right;
+        expr = op;
+        token = Lexer_peek(lexer);
     }
     return expr;
 }
@@ -93,9 +169,7 @@ Node *parse_statement(Lexer *lexer)
         node->unary_expr = parse_expression(lexer);
         assert_token(Lexer_next(lexer), TOKEN_SEMICOLON);
     } else {
-        printf("Unexpected token in parse_statement: ");
-        Token_print(stdout, &token);
-        printf("\n");
+        die_location(token.loc, ": Unexpected token in parse_statement: %s\n", token_type_to_str(token.type));
         exit(1);
     }
 
diff --git a/examples/binary-ops.cup b/examples/binary-ops.cup
new file mode 100644
index 0000000..13e5083
--- /dev/null
+++ b/examples/binary-ops.cup
@@ -0,0 +1,3 @@
+fn main() {
+    return 2 + 5 * (12 / 4) - 1;
+}
\ No newline at end of file