parser: parser boolean comparison expressions

After this commit, this is a valid expression:

  1 || 2 && 3 > 4 < 5 >= 6 <= 7 == 8 != 9

Signed-off-by: Carlos Maniero <carlos@maniero.me>
Signed-off-by: Johnny Richard <johnny@johnnyrichard.com>

3 files changed, 251 insertions, 57 deletions

diff --git a/src/ast.h b/src/ast.h
index f91632c..f95aee2 100644
--- a/src/ast.h
+++ b/src/ast.h
@@ -57,6 +57,14 @@ typedef enum ast_binary_operation_kind_t
   AST_BINOP_SUBTRACTION,
   AST_BINOP_MULTIPLICATION,
   AST_BINOP_DIVISION,
+  AST_BINOP_EQUAL,
+  AST_BINOP_NOT_EQUAL,
+  AST_BINOP_AND,
+  AST_BINOP_OR,
+  AST_BINOP_GT,
+  AST_BINOP_LT,
+  AST_BINOP_LT_EQUAL,
+  AST_BINOP_GT_EQUAL,
   AST_BINOP_N
 } ast_binary_operation_kind_t;
 
diff --git a/src/parser.c b/src/parser.c
index 7a22f16..2817fa0 100644
--- a/src/parser.c
+++ b/src/parser.c
@@ -128,67 +128,94 @@ token_to_binary_operation_kind(token_t *token)
       return AST_BINOP_MULTIPLICATION;
     case TOKEN_SLASH:
       return AST_BINOP_DIVISION;
+    case TOKEN_EQUAL:
+      return AST_BINOP_EQUAL;
+    case TOKEN_NOT_EQUAL:
+      return AST_BINOP_NOT_EQUAL;
+    case TOKEN_AND:
+      return AST_BINOP_AND;
+    case TOKEN_OR:
+      return AST_BINOP_OR;
+    case TOKEN_GT:
+      return AST_BINOP_GT;
+    case TOKEN_GT_EQUAL:
+      return AST_BINOP_GT_EQUAL;
+    case TOKEN_LT:
+      return AST_BINOP_LT;
+    case TOKEN_LT_EQUAL:
+      return AST_BINOP_LT_EQUAL;
     default:
       assert(false && "token mapping not found.");
   }
 }
 
+ast_node_t *
+parser_parse_expression(parser_t *parser);
+
 static ast_node_t *
-parser_parse_factor(parser_t *parser)
+parser_parse_comparison(parser_t *parser);
+
+static ast_node_t *
+parser_parse_arithmetic1(parser_t *parser);
+
+static ast_node_t *
+parser_parse_arithmetic2(parser_t *parser);
+
+static ast_node_t *
+parser_parse_factor(parser_t *parser);
+
+/**
+ *
+ * <expression>  ::= <comparison>
+ * <comparison>  ::= <arithmetic1> (('>' | '>=' | '=' | ...) arithmetic1)*
+ * <arithmetic1> ::= <arithmetic2> (('+' | '-') arithmetic2)*
+ * <arithmetic2> ::= <factor> (('*' | '/') factor)*
+ * <factor>      ::= <integer> | '(' <expression> ')'
+ *
+ */
+ast_node_t *
+parser_parse_expression(parser_t *parser)
 {
-  token_t token;
-  lexer_next_token(parser->lexer, &token);
+  return parser_parse_comparison(parser);
+}
 
-  switch (token.kind) {
-    case TOKEN_NUMBER:
-      return parser_literal_integer_node(&token);
-    case TOKEN_TRUE:
-      return parser_literal_bool_node(&token);
-    case TOKEN_FALSE:
-      return parser_literal_bool_node(&token);
-    case TOKEN_OPAREN: {
-      ast_node_t *expression = parser_parse_expression(parser);
+static ast_node_t *
+parser_parse_comparison(parser_t *parser)
+{
+  ast_node_t *node = parser_parse_arithmetic1(parser);
 
-      if (expression == NULL) {
-        return NULL;
-      }
+  if (node == NULL) {
+    return NULL;
+  }
 
-      if (!drop_expected_token(parser, TOKEN_CPAREN)) {
-        ast_node_destroy(expression);
-        return NULL;
-      }
+  token_t token;
+  lexer_peek_next_token(parser->lexer, &token);
 
-      return expression;
-    }
-    case TOKEN_NAME: {
-      // TODO: Check node kind, today accepts only variables
-      ast_node_t *var_node = scope_get(parser->scope, token.value);
+  while (token.kind == TOKEN_GT || token.kind == TOKEN_LT || token.kind == TOKEN_GT_EQUAL ||
+         token.kind == TOKEN_LT_EQUAL || token.kind == TOKEN_EQUAL || token.kind == TOKEN_NOT_EQUAL ||
+         token.kind == TOKEN_AND || token.kind == TOKEN_OR) {
+    lexer_drop_next_token(parser->lexer);
 
-      if (var_node == NULL) {
-        parser_error_t error;
-        error.token = token;
-        sprintf(error.message, "identifier '" SVFMT "' not defined", SVARG(&token.value));
-        parser->errors[parser->errors_len++] = error;
-        return NULL;
-      }
+    ast_node_t *left = node;
+    ast_node_t *right = parser_parse_arithmetic1(parser);
 
-      return ast_node_new_variable(&var_node->data.variable_declaration.identifier,
-                                   var_node->data.variable_declaration.type);
-    }
-    default: {
-      parser_error_t error;
-      error.token = token;
-      sprintf(error.message, "unexpected '%s (" SVFMT ")' token", token_kind_to_str(token.kind), SVARG(&token.value));
-      parser->errors[parser->errors_len++] = error;
+    if (right == NULL) {
+      ast_node_destroy(node);
       return NULL;
     }
+
+    node = ast_node_new_binary_operation(token_to_binary_operation_kind(&token), left, right, TYPE_BOOL);
+
+    lexer_peek_next_token(parser->lexer, &token);
   }
+
+  return node;
 }
 
 static ast_node_t *
-parser_parse_term(parser_t *parser)
+parser_parse_arithmetic1(parser_t *parser)
 {
-  ast_node_t *node = parser_parse_factor(parser);
+  ast_node_t *node = parser_parse_arithmetic2(parser);
 
   if (node == NULL) {
     return NULL;
@@ -197,14 +224,14 @@ parser_parse_term(parser_t *parser)
   token_t token;
   lexer_peek_next_token(parser->lexer, &token);
 
-  while (token.kind == TOKEN_STAR || token.kind == TOKEN_SLASH) {
+  while (token.kind == TOKEN_PLUS || token.kind == TOKEN_MINUS) {
     lexer_drop_next_token(parser->lexer);
 
     ast_node_t *left = node;
-    ast_node_t *right = parser_parse_factor(parser);
+    ast_node_t *right = parser_parse_arithmetic2(parser);
 
     if (right == NULL) {
-      ast_node_destroy(node);
+      ast_node_destroy(left);
       return NULL;
     }
 
@@ -216,17 +243,10 @@ parser_parse_term(parser_t *parser)
   return node;
 }
 
-/**
- *
- * <expression> ::= <term> (('+' | '-') term)*
- * <term>       ::= <factor> (('*' | '/') factor)*
- * <factor>     ::= <integer> | '(' <expression> ')'
- *
- */
-ast_node_t *
-parser_parse_expression(parser_t *parser)
+static ast_node_t *
+parser_parse_arithmetic2(parser_t *parser)
 {
-  ast_node_t *node = parser_parse_term(parser);
+  ast_node_t *node = parser_parse_factor(parser);
 
   if (node == NULL) {
     return NULL;
@@ -235,14 +255,14 @@ parser_parse_expression(parser_t *parser)
   token_t token;
   lexer_peek_next_token(parser->lexer, &token);
 
-  while (token.kind == TOKEN_PLUS || token.kind == TOKEN_MINUS) {
+  while (token.kind == TOKEN_STAR || token.kind == TOKEN_SLASH) {
     lexer_drop_next_token(parser->lexer);
 
     ast_node_t *left = node;
-    ast_node_t *right = parser_parse_term(parser);
+    ast_node_t *right = parser_parse_factor(parser);
 
     if (right == NULL) {
-      ast_node_destroy(left);
+      ast_node_destroy(node);
       return NULL;
     }
 
@@ -255,6 +275,58 @@ parser_parse_expression(parser_t *parser)
 }
 
 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 parser_literal_integer_node(&token);
+    case TOKEN_TRUE:
+      return parser_literal_bool_node(&token);
+    case TOKEN_FALSE:
+      return parser_literal_bool_node(&token);
+    case TOKEN_OPAREN: {
+      ast_node_t *expression = parser_parse_expression(parser);
+
+      if (expression == NULL) {
+        return NULL;
+      }
+
+      if (!drop_expected_token(parser, TOKEN_CPAREN)) {
+        ast_node_destroy(expression);
+        return NULL;
+      }
+
+      return expression;
+    }
+    case TOKEN_NAME: {
+      // TODO: Check node kind, today accepts only variables
+      ast_node_t *var_node = scope_get(parser->scope, token.value);
+
+      if (var_node == NULL) {
+        parser_error_t error;
+        error.token = token;
+        sprintf(error.message, "identifier '" SVFMT "' not defined", SVARG(&token.value));
+        parser->errors[parser->errors_len++] = error;
+        return NULL;
+      }
+
+      return ast_node_new_variable(&var_node->data.variable_declaration.identifier,
+                                   var_node->data.variable_declaration.type);
+    }
+    default: {
+      parser_error_t error;
+      error.token = token;
+      sprintf(error.message, "unexpected '%s (" SVFMT ")' token", token_kind_to_str(token.kind), SVARG(&token.value));
+      parser->errors[parser->errors_len++] = error;
+      return NULL;
+    }
+  }
+}
+
+static ast_node_t *
 parser_parse_return_stmt(parser_t *parser, type_t result_type)
 {
   token_t token;
diff --git a/test/parser_test.c b/test/parser_test.c
index 1371453..830fed7 100644
--- a/test/parser_test.c
+++ b/test/parser_test.c
@@ -244,6 +244,118 @@ test_parse_arithmetic_expression(const MunitParameter params[], void *user_data_
   return MUNIT_OK;
 }
 
+static MunitResult
+test_parse_boolean_expression(const MunitParameter params[], void *user_data_or_fixture)
+{
+  parser_t parser;
+  lexer_t lexer;
+  scope_t *scope = scope_new();
+
+  make_lexer_from_static_src(&lexer, "1 + 3 > 3 / 2 - 7");
+  parser_init(&parser, &lexer, scope);
+
+  ast_node_t *ast_expression = parser_parse_expression(&parser);
+  assert_not_null(ast_expression);
+
+  ast_node_t *exp1 = ast_expression;
+  {
+
+    assert_int(AST_BINARY_OPERATION, ==, exp1->kind);
+    assert_int(AST_BINOP_GT, ==, exp1->data.binary_operation.kind);
+
+    ast_node_t *exp1_left = exp1->data.binary_operation.left;
+    {
+
+      assert_int(AST_BINARY_OPERATION, ==, exp1_left->kind);
+      assert_int(AST_BINOP_ADITION, ==, exp1_left->data.binary_operation.kind);
+
+      assert_int(AST_LITERAL, ==, exp1_left->data.binary_operation.left->kind);
+      assert_int(exp1_left->data.binary_operation.left->data.literal.value.integer, ==, 1);
+
+      assert_int(AST_LITERAL, ==, exp1_left->data.binary_operation.right->kind);
+      assert_int(exp1_left->data.binary_operation.right->data.literal.value.integer, ==, 3);
+    }
+
+    ast_node_t *exp1_right = exp1->data.binary_operation.right;
+    {
+
+      assert_int(AST_BINARY_OPERATION, ==, exp1_right->kind);
+      assert_int(AST_BINOP_SUBTRACTION, ==, exp1_right->data.binary_operation.kind);
+
+      ast_node_t *exp2_left = exp1_right->data.binary_operation.left;
+      {
+        assert_int(AST_BINARY_OPERATION, ==, exp2_left->kind);
+        assert_int(AST_BINOP_DIVISION, ==, exp2_left->data.binary_operation.kind);
+
+        assert_int(AST_LITERAL, ==, exp2_left->data.binary_operation.left->kind);
+        assert_int(exp2_left->data.binary_operation.left->data.literal.value.integer, ==, 3);
+
+        assert_int(AST_LITERAL, ==, exp2_left->data.binary_operation.right->kind);
+        assert_int(exp2_left->data.binary_operation.right->data.literal.value.integer, ==, 2);
+      }
+
+      assert_int(AST_LITERAL, ==, exp1_right->data.binary_operation.right->kind);
+      assert_int(exp1_right->data.binary_operation.right->data.literal.value.integer, ==, 7);
+    }
+  }
+
+  ast_node_destroy(ast_expression);
+  scope_destroy(scope);
+
+  return MUNIT_OK;
+}
+
+static MunitResult
+test_parse_all_boolean_expression(const MunitParameter params[], void *user_data_or_fixture)
+{
+  parser_t parser;
+  lexer_t lexer;
+  scope_t *scope = scope_new();
+
+  make_lexer_from_static_src(&lexer, "1 || 2 && 3 > 4 < 5 >= 6 <= 7 == 8 != 9");
+  parser_init(&parser, &lexer, scope);
+
+  ast_node_t *ast_expression = parser_parse_expression(&parser);
+  assert_not_null(ast_expression);
+
+  ast_node_t *exp1 = ast_expression;
+  assert_int(TYPE_BOOL, ==, exp1->result_type);
+  assert_int(AST_BINOP_NOT_EQUAL, ==, exp1->data.binary_operation.kind);
+
+  ast_node_t *exp2 = exp1->data.binary_operation.left;
+  assert_int(TYPE_BOOL, ==, exp2->result_type);
+  assert_int(AST_BINOP_EQUAL, ==, exp2->data.binary_operation.kind);
+
+  ast_node_t *exp3 = exp2->data.binary_operation.left;
+  assert_int(TYPE_BOOL, ==, exp3->result_type);
+  assert_int(AST_BINOP_LT_EQUAL, ==, exp3->data.binary_operation.kind);
+
+  ast_node_t *exp4 = exp3->data.binary_operation.left;
+  assert_int(TYPE_BOOL, ==, exp4->result_type);
+  assert_int(AST_BINOP_GT_EQUAL, ==, exp4->data.binary_operation.kind);
+
+  ast_node_t *exp5 = exp4->data.binary_operation.left;
+  assert_int(TYPE_BOOL, ==, exp5->result_type);
+  assert_int(AST_BINOP_LT, ==, exp5->data.binary_operation.kind);
+
+  ast_node_t *exp6 = exp5->data.binary_operation.left;
+  assert_int(TYPE_BOOL, ==, exp6->result_type);
+  assert_int(AST_BINOP_GT, ==, exp6->data.binary_operation.kind);
+
+  ast_node_t *exp7 = exp6->data.binary_operation.left;
+  assert_int(TYPE_BOOL, ==, exp7->result_type);
+  assert_int(AST_BINOP_AND, ==, exp7->data.binary_operation.kind);
+
+  ast_node_t *exp8 = exp7->data.binary_operation.left;
+  assert_int(TYPE_BOOL, ==, exp8->result_type);
+  assert_int(AST_BINOP_OR, ==, exp8->data.binary_operation.kind);
+
+  ast_node_destroy(ast_expression);
+  scope_destroy(scope);
+
+  return MUNIT_OK;
+}
+
 void
 assert_string_view_equal(char *expected, string_view_t actual)
 {
@@ -295,6 +407,8 @@ static MunitTest tests[] = {
   { "/test_parse_boolean", test_parse_boolean, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
   { "/test_parse_basic_syntax_errors", test_parse_basic_syntax_errors, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
   { "/test_parse_arithmetic_expression", test_parse_arithmetic_expression, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+  { "/test_parse_boolean_expression", test_parse_boolean_expression, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+  { "/test_parse_all_boolean_expression", test_parse_all_boolean_expression, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
   { "/test_parse_variable_definition", test_parse_variable_definition, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
   { NULL, NULL, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL }
 };