parser: Parse integers arithmetic expression

This patch implements the AST creation for arithmetic expressions.

NOTE:

The implementation works only for integer numbers.

Signed-off-by: Johnny Richard <johnny@johnnyrichard.com>
Reviewed-by: Carlos Maniero <carlosmaniero@gmail.com>

6 files changed, 104 insertions, 6 deletions

diff --git a/src/ast.c b/src/ast.c
index 7f3af9e..5c94d68 100644
--- a/src/ast.c
+++ b/src/ast.c
@@ -64,12 +64,16 @@ ast_node_destroy(ast_node_t *node)
     case AST_FUNCTION_DECLARATION:
       ast_node_destroy(node->data.function.body);
       break;
+    case AST_BINARY_OPERATION:
+      ast_node_destroy(node->data.binary_operation.left);
+      ast_node_destroy(node->data.binary_operation.right);
+      break;
+    case AST_LITERAL:
+      break;
     case AST_RETURN_STMT:
       break;
     case AST_UNKOWN_NODE:
       break;
-    case AST_LITERAL:
-      break;
     default:
       assert(false && "unmapped free strategy");
   }
diff --git a/src/ast.h b/src/ast.h
index 1c4bbb8..cb9b8d5 100644
--- a/src/ast.h
+++ b/src/ast.h
@@ -38,6 +38,13 @@ typedef struct ast_function_declaration_t {
   ast_node_t* body;
 } ast_function_declaration_t;
 
+typedef struct ast_binary_operation_t {
+  // FIXME: We want to use enum to distinguish operators
+  string_view_t op;
+  ast_node_t* left;
+  ast_node_t* right;
+} ast_binary_operation_t;
+
 typedef enum {
   AST_LITERAL_INTEGER
 } ast_literal_kind_t;
@@ -59,6 +66,7 @@ typedef struct ast_visitor_t {
 
 typedef enum {
   AST_FUNCTION_DECLARATION,
+  AST_BINARY_OPERATION,
   AST_LITERAL,
   AST_RETURN_STMT,
   AST_UNKOWN_NODE
@@ -66,6 +74,7 @@ typedef enum {
 
 typedef union {
   ast_function_declaration_t function;
+  ast_binary_operation_t binary_operation;
   ast_literal_t literal;
   ast_return_stmt_t return_stmt;
 } ast_node_data_t;
diff --git a/src/lexer.c b/src/lexer.c
index 2c8ffb9..b641752 100644
--- a/src/lexer.c
+++ b/src/lexer.c
@@ -44,6 +44,7 @@ lexer_define_literal_token_props(lexer_t *lexer, token_t *token, token_kind_t ki
   token->filepath = lexer->filepath;
   token->row = lexer->row;
   token->col = lexer->cur - lexer->bol;
+  token->bol = lexer->bol;
 }
 
 static void
@@ -73,6 +74,7 @@ lexer_tokenize_number(lexer_t *lexer, token_t *token)
   token->filepath = lexer->filepath;
   token->row = lexer->row;
   token->col = begin - lexer->bol;
+  token->bol = lexer->bol;
 }
 
 static void
@@ -88,6 +90,7 @@ lexer_tokenize_name(lexer_t *lexer, token_t *token)
   token->filepath = lexer->filepath;
   token->row = lexer->row;
   token->col = begin - lexer->bol;
+  token->bol = lexer->bol;
 }
 
 void
@@ -197,6 +200,14 @@ lexer_load_file_contents(lexer_t *lexer)
 }
 
 void
+lexer_step_back_to(lexer_t *lexer, token_t *token)
+{
+  lexer->cur = token->bol + token->col;
+  lexer->row = token->row;
+  lexer->bol = token->bol;
+}
+
+void
 lexer_drop_char(lexer_t *lexer)
 {
   lexer->cur++;
diff --git a/src/lexer.h b/src/lexer.h
index ae8ab60..9f45910 100644
--- a/src/lexer.h
+++ b/src/lexer.h
@@ -42,6 +42,7 @@ typedef struct token_t {
   char         *filepath;
   uint32_t      row;
   uint32_t      col;
+  uint32_t      bol;
 } token_t;
 
 
@@ -68,6 +69,8 @@ bool lexer_is_not_eof(lexer_t *lexer);
 
 void lexer_drop_char(lexer_t *lexer);
 
+void lexer_step_back_to(lexer_t *lexer, token_t *token);
+
 char * token_kind_to_str(token_kind_t kind);
 
 #endif /* LEXER_H */
diff --git a/src/parser.c b/src/parser.c
index 176a4a8..ad38125 100644
--- a/src/parser.c
+++ b/src/parser.c
@@ -109,16 +109,20 @@ parser_literal_integer_node(ast_node_t *node, token_t *token)
 }
 
 bool
-parser_parse_next_expression(parser_t *parser, ast_node_t *node)
+parser_parse_factor(parser_t *parser, ast_node_t *node)
 {
   token_t token;
   lexer_next_token(parser->lexer, &token);
 
-  if (token.kind == TOKEN_NUMBER)
-  {
+  if (token.kind == TOKEN_NUMBER) {
     return parser_literal_integer_node(node, &token);
+  } else if (token.kind == TOKEN_OPAREN) {
+    parser_parse_expression(parser, node);
+    if (!drop_expected_token(parser, TOKEN_CPAREN)) return false;
+    return true;
   }
 
+  // FIXME: Extract this erros logic to a function
   parser_error_t error;
   error.token = token;
   sprintf(
@@ -128,10 +132,76 @@ parser_parse_next_expression(parser_t *parser, ast_node_t *node)
       SVARG(&token.value)
   );
   parser->errors[parser->errors_len++] = error;
+
   return false;
 }
 
 bool
+parser_parse_term(parser_t *parser, ast_node_t *node)
+{
+  if (!parser_parse_factor(parser, node)) return false;
+
+  token_t token;
+  lexer_next_token(parser->lexer, &token);
+
+  while (token.kind == TOKEN_OP && (string_view_eq(token.value, string_view_from_str("*")) || string_view_eq(token.value, string_view_from_str("/")))) {
+    ast_node_t *binary_op = ast_node_new();
+    binary_op->kind = AST_BINARY_OPERATION;
+    binary_op->data.binary_operation.op = token.value;
+
+    binary_op->data.binary_operation.left = ast_node_new();
+    *binary_op->data.binary_operation.left = *node;
+
+    binary_op->data.binary_operation.right = ast_node_new();
+    if (!parser_parse_factor(parser, binary_op->data.binary_operation.right)) return false;
+
+    *node = *binary_op;
+
+    lexer_next_token(parser->lexer, &token);
+  }
+
+  lexer_step_back_to(parser->lexer, &token);
+
+  return true;
+}
+
+/**
+ *
+ * <expression> ::= <term> (('+' | '-') term)*
+ * <term>       ::= <factor> (('*' | '/') factor)*
+ * <factor>     ::= <integer> | '(' <expression> ')'
+ *
+ */
+bool
+parser_parse_expression(parser_t *parser, ast_node_t *node)
+{
+  if (!parser_parse_term(parser, node)) return false;
+
+  token_t token;
+  lexer_next_token(parser->lexer, &token);
+
+  while (token.kind == TOKEN_OP && (string_view_eq(token.value, string_view_from_str("+")) || string_view_eq(token.value, string_view_from_str("-")))) {
+
+    ast_node_t *binary_op = ast_node_new();
+    binary_op->kind = AST_BINARY_OPERATION;
+    binary_op->data.binary_operation.op = token.value;
+
+    binary_op->data.binary_operation.left = ast_node_new();
+    *binary_op->data.binary_operation.left = *node;
+
+    binary_op->data.binary_operation.right = ast_node_new();
+    if (!parser_parse_term(parser, binary_op->data.binary_operation.right)) return false;
+
+    *node = *binary_op;
+    lexer_next_token(parser->lexer, &token);
+  }
+
+  lexer_step_back_to(parser->lexer, &token);
+
+  return true;
+}
+
+bool
 parser_parse_return_stmt(parser_t *parser, ast_node_t *node)
 {
   token_t return_keyword_token;
@@ -155,7 +225,7 @@ parser_parse_return_stmt(parser_t *parser, ast_node_t *node)
   }
 
   ast_node_t *argument_token = ast_node_new();
-  if (!parser_parse_next_expression(parser, argument_token)) return false;
+  if (!parser_parse_expression(parser, argument_token)) return false;
 
   if (!drop_expected_token(parser, TOKEN_SEMICOLON)) return false;
   if (!drop_expected_token(parser, TOKEN_CCURLY)) return false;
diff --git a/src/parser.h b/src/parser.h
index 5f73ff3..00d1aae 100644
--- a/src/parser.h
+++ b/src/parser.h
@@ -35,6 +35,7 @@ typedef struct parser_t {
 void parser_init(parser_t *parser, lexer_t *lexer);
 
 bool parser_parse_function_declaration(parser_t *parser, ast_node_t *node);
+bool parser_parse_expression(parser_t *parser, ast_node_t *node);
 
 #endif /* PARSER_H */