folder structure

12 files changed, 312 insertions, 171 deletions

diff --git a/Makefile b/Makefile
index b20c925..112b109 100644
--- a/Makefile
+++ b/Makefile
@@ -1,54 +1,60 @@
-CC        := gcc
-CFLAGS    := -Wall -g -I.
-BISON     := bison
-FLEX      := flex
+CC ?= clang
+CFLAGS ?= -Wall -Wextra -g
+BISON ?= bison
+FLEX ?= flex
 
+SRC_DIR := src
+INC_DIR := include
 BUILD_DIR := build
 
-PARSER_Y  := parser.y
-LEXER_L   := lexer.l
-DRIVER_C  := driver.c
-AST_C     := ast.c
-AST_H     := ast.h
+PARSER_Y := $(SRC_DIR)/parser.y
+LEXER_L := $(SRC_DIR)/lexer.l
 
-PARSER_C  := $(BUILD_DIR)/parser.tab.c
-PARSER_H  := $(BUILD_DIR)/parser.tab.h
-LEXER_C   := $(BUILD_DIR)/lex.yy.c
-OBJS      := $(BUILD_DIR)/parser.tab.o $(BUILD_DIR)/lex.yy.o $(BUILD_DIR)/driver.o $(BUILD_DIR)/ast.o
+C_SRC := $(filter-out $(PARSER_Y:.y=.c) $(LEXER_L:.l=.c), $(wildcard $(SRC_DIR)/*.c))
 
-TARGET    := $(BUILD_DIR)/imp
+PARSER_C := $(BUILD_DIR)/parser.tab.c
+PARSER_H := $(BUILD_DIR)/parser.tab.h
+LEXER_C := $(BUILD_DIR)/lex.yy.c
 
-.PHONY: all clean run
+C_OBJS := $(patsubst $(SRC_DIR)/%.c,$(BUILD_DIR)/%.o,$(C_SRC))
+PARSER_O := $(BUILD_DIR)/parser.tab.o
+LEXER_O := $(BUILD_DIR)/lex.yy.o
+OBJS := $(C_OBJS) $(PARSER_O) $(LEXER_O)
+
+TARGET := $(BUILD_DIR)/imp
+
+CFLAGS += -I$(INC_DIR) -MMD -MP
+DEPS := $(OBJS:.o=.d)
+
+.PHONY: all clean example
 
 all: $(TARGET)
 
 $(TARGET): $(OBJS)
-	$(CC) $(CFLAGS) -o $@ $^
+	$(CC) $(CFLAGS) $^ -o $@
 
 $(BUILD_DIR):
-	mkdir -p $(BUILD_DIR)
+	@mkdir -p $@
+
+$(BUILD_DIR)/%.o: $(SRC_DIR)/%.c | $(BUILD_DIR)
+	$(CC) $(CFLAGS) -c $< -o $@
 
 $(PARSER_C) $(PARSER_H): $(PARSER_Y) | $(BUILD_DIR)
-	$(BISON) -d --defines=$(PARSER_H) -o $(PARSER_C) $(PARSER_Y)
+	$(BISON) -d --defines=$(PARSER_H) -o $(PARSER_C) $<
+
+$(PARSER_O): $(PARSER_C)
+	$(CC) $(CFLAGS) -c $< -o $@
 
 $(LEXER_C): $(LEXER_L) $(PARSER_H) | $(BUILD_DIR)
 	$(FLEX) -o $@ $<
 
-$(BUILD_DIR)/imp_parser.tab.o: $(PARSER_C) $(PARSER_H)
-	$(CC) $(CFLAGS) -c $(PARSER_C) -o $@
-
-$(BUILD_DIR)/lex.yy.o: $(LEXER_C) $(PARSER_H)
-	$(CC) $(CFLAGS) -c $(LEXER_C) -o $@
-
-$(BUILD_DIR)/driver.o: $(DRIVER_C) $(PARSER_H) $(AST_H) | $(BUILD_DIR)
-	$(CC) $(CFLAGS) -c $(DRIVER_C) -o $@
-
-$(BUILD_DIR)/ast.o: $(AST_C) $(AST_H) | $(BUILD_DIR)
-	$(CC) $(CFLAGS) -c $(AST_C) -o $@
+$(LEXER_O): $(LEXER_C)
+	$(CC) $(CFLAGS) -c $< -o $@
 
-run: $(TARGET)
-	./$(TARGET) example.imp
+example: $(TARGET)
+	./$(TARGET) example/example.imp
 
 clean:
-	rm -rf $(BUILD_DIR)
+	@rm -rf $(BUILD_DIR)
 
+-include $(DEPS)
diff --git a/README.md b/README.md
index bbc7b31..b327668 100644
--- a/README.md
+++ b/README.md
@@ -5,7 +5,7 @@ A small interpreter of the IMP programming language.
 ## Build
 
 - `make all` to build interpreter.
-- `make run` to interpret "example.imp".
+- `make example` to interpret "example/example.imp".
 - `make clean` to remove build folder.
 
 ## Dependencies
diff --git a/example.imp b/example/example.imp
index d87c891..d87c891 100644
--- a/example.imp
+++ b/example/example.imp
diff --git a/ast.h b/include/ast.h
index 7dd9697..9c6b6bd 100644
--- a/ast.h
+++ b/include/ast.h
@@ -38,15 +38,7 @@ ASTNode *ast_bop(BOp bop, ASTNode *bexp1, ASTNode *bexp2);
 ASTNode *ast_not(ASTNode *bexp);
 ASTNode *ast_rop(ROp rop, ASTNode *aexp1, ASTNode *aexp2);
 
-typedef struct Env {
-  char *name;
-  int val;
-  struct Env *next;
-} Env;
-
-void exec_stmt(Env **env, ASTNode *node);
 void free_ast(ASTNode *node);
-void env_print(Env *env);
 
 #endif
 
diff --git a/include/hash_map.h b/include/hash_map.h
new file mode 100644
index 0000000..ad873f8
--- /dev/null
+++ b/include/hash_map.h
@@ -0,0 +1,12 @@
+#ifndef HASH_MAP_H
+#define HASH_MAP_H
+
+typedef void *hashmap_t;
+
+hashmap_t hashmap_create(void);
+void hashmap_insert(hashmap_t map, const char *key, int value);
+int *hashmap_get(hashmap_t map, const char *key);
+void hashmap_delete(hashmap_t map, const char *key);
+void hashmap_free(hashmap_t map);
+
+#endif
\ No newline at end of file
diff --git a/include/interpreter.h b/include/interpreter.h
new file mode 100644
index 0000000..182f2e5
--- /dev/null
+++ b/include/interpreter.h
@@ -0,0 +1,17 @@
+#ifndef INTERPRETER_H
+#define INTERPRETER_H
+
+#include "ast.h"
+
+
+typedef struct Env {
+  char *name;
+  int val;
+  struct Env *next;
+} Env;
+
+void exec_stmt(Env **env, ASTNode *node);
+void env_print(Env *env);
+
+
+#endif
\ No newline at end of file
diff --git a/src/ast.c b/src/ast.c
new file mode 100644
index 0000000..acc7c9e
--- /dev/null
+++ b/src/ast.c
@@ -0,0 +1,131 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "ast.h"
+
+static ASTNode *new_node(NodeType type) {
+  ASTNode *node = malloc(sizeof(ASTNode));
+  node->type = type;
+  return node;
+}
+
+ASTNode *ast_skip(void) {
+  return new_node(NT_SKIP);
+}
+
+ASTNode *ast_assign(ASTNode *var, ASTNode *aexp) {
+  ASTNode *node = new_node(NT_ASSIGN);
+  node->u.d_assign.var = var;
+  node->u.d_assign.aexp = aexp;
+  return node;
+}
+
+ASTNode *ast_seq(ASTNode *stm1, ASTNode *stm2) {
+  ASTNode *node = new_node(NT_SEQ);
+  node->u.d_seq.stm1 = stm1;
+  node->u.d_seq.stm2 = stm2;
+  return node;
+}
+
+ASTNode *ast_if(ASTNode *bexp, ASTNode *stm1, ASTNode *stm2) {
+  ASTNode *node = new_node(NT_IF);
+  node->u.d_if.bexp = bexp;
+  node->u.d_if.stm1 = stm1;
+  node->u.d_if.stm2 = stm2;
+  return node;
+}
+
+ASTNode *ast_while(ASTNode *bexp, ASTNode *stm) {
+  ASTNode *node = new_node(NT_WHILE);
+  node->u.d_while.bexp = bexp;
+  node->u.d_while.stm = stm;
+  return node;
+}
+
+ASTNode *ast_int(int val) {
+  ASTNode *node = new_node(NT_INT);
+  node->u.d_int.val = val;
+  return node;
+}
+
+ASTNode *ast_var(char *name) {
+  ASTNode *node = new_node(NT_VAR);
+  node->u.d_var.name = strdup(name);
+  return node;
+}
+
+ASTNode *ast_aop(AOp aop, ASTNode *aexp1, ASTNode *aexp2) {
+  ASTNode *node = new_node(NT_AOP);
+  node->u.d_aop.aexp1 = aexp1;
+  node->u.d_aop.aexp2 = aexp2;
+  node->u.d_aop.aop = aop;
+  return node;
+}
+
+ASTNode *ast_bop(BOp bop, ASTNode *bexp1, ASTNode *bexp2) {
+  ASTNode *node = new_node(NT_BOP);
+  node->u.d_bop.bexp1 = bexp1;
+  node->u.d_bop.bexp2 = bexp2;
+  node->u.d_bop.bop = bop;
+  return node;
+}
+
+ASTNode *ast_not(ASTNode *bexp) {
+  ASTNode *node = new_node(NT_NOT);
+  node->u.d_not.bexp = bexp;
+  return node;
+}
+
+ASTNode *ast_rop(ROp rop, ASTNode *aexp1, ASTNode *aexp2) {
+  ASTNode *node = new_node(NT_ROP);
+  node->u.d_rop.aexp1 = aexp1;
+  node->u.d_rop.aexp2 = aexp2;
+  node->u.d_rop.rop = rop;
+  return node;
+}
+
+void free_ast(ASTNode *node) {
+  if (!node) return;
+  switch (node->type) {
+    case NT_SKIP:
+      break;
+    case NT_ASSIGN:
+      free_ast(node->u.d_assign.var);
+      free_ast(node->u.d_assign.aexp);
+      break;
+    case NT_SEQ:
+      free_ast(node->u.d_seq.stm1);
+      free_ast(node->u.d_seq.stm2);
+      break;
+    case NT_IF:
+      free_ast(node->u.d_if.bexp);
+      free_ast(node->u.d_if.stm1);
+      free_ast(node->u.d_if.stm2);
+      break;
+    case NT_WHILE:
+      free_ast(node->u.d_while.bexp);
+      free_ast(node->u.d_while.stm);
+      break;
+    case NT_INT:
+      break;
+    case NT_VAR:
+      free(node->u.d_var.name);
+      break;
+    case NT_AOP:
+      free_ast(node->u.d_aop.aexp1);
+      free_ast(node->u.d_aop.aexp2);
+      break;
+    case NT_BOP:
+      free_ast(node->u.d_bop.bexp1);
+      free_ast(node->u.d_bop.bexp2);
+      break;
+    case NT_ROP:
+      free_ast(node->u.d_rop.aexp1);
+      free_ast(node->u.d_rop.aexp2);
+      break;
+    case NT_NOT:
+      free_ast(node->u.d_not.bexp);
+      break;
+  }
+  free(node);
+}
\ No newline at end of file
diff --git a/driver.c b/src/driver.c
index 6b0909e..90ee892 100644
--- a/driver.c
+++ b/src/driver.c
@@ -1,6 +1,6 @@
 #include <stdio.h>
 #include <stdlib.h>
-#include "ast.h"
+#include "interpreter.h"
 
 extern FILE *yyin;
 extern int yyparse(void);
diff --git a/src/hash_map.c b/src/hash_map.c
new file mode 100644
index 0000000..b9c3b37
--- /dev/null
+++ b/src/hash_map.c
@@ -0,0 +1,110 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include "hash_map.h"
+
+#define INITIAL_SIZE (16)
+#define LOAD_FACTOR_THRESHOLD (0.75)
+
+typedef struct Pair {
+  char *key;
+  int value;
+  struct Pair *next;
+} Pair;
+
+typedef struct HashMap {
+  Pair **table;
+  size_t size;
+  size_t count;
+} HashMap;
+
+static unsigned int hash(const char *key, size_t size) {
+  unsigned int hash_value = 0;
+  while (*key)hash_value = (hash_value * 31) + *key++;
+  return hash_value % size;
+}
+
+hashmap_t hashmap_create(void) {
+  HashMap *map = (HashMap *)malloc(sizeof(HashMap));
+  assert(map);
+  map->size = INITIAL_SIZE;
+  map->count = 0;
+  map->table = (Pair **)calloc(map->size, sizeof(Pair *));
+  assert(map->table);
+  return map;
+}
+
+static void resize(hashmap_t map) {
+  size_t new_size = ((HashMap*)map)->size * 2;
+  Pair **new_table = (Pair **)calloc(new_size, sizeof(Pair *));
+  assert(new_table);
+  for (size_t i = 0; i < ((HashMap*)map)->size; ++i) {
+    Pair *pair = ((HashMap*)map)->table[i];
+    while (pair) {
+      unsigned int index = hash(pair->key, new_size);
+      Pair *next = pair->next;
+      pair->next = new_table[index];
+      new_table[index] = pair;
+      pair = next;
+    }
+  }
+  free(((HashMap*)map)->table);
+  ((HashMap*)map)->table = new_table;
+  ((HashMap*)map)->size = new_size;
+}
+
+void hashmap_insert(hashmap_t map, const char *key, int value) {
+  if ((float)((HashMap*)map)->count / ((HashMap*)map)->size > LOAD_FACTOR_THRESHOLD) resize(((HashMap*)map));
+  unsigned int index = hash(key, ((HashMap*)map)->size);
+  Pair *new_pair = (Pair *)malloc(sizeof(Pair));
+  assert(new_pair);
+  new_pair->key = strdup(key);
+  assert(new_pair->key);
+  new_pair->value = value;
+  new_pair->next = ((HashMap*)map)->table[index];
+  ((HashMap*)map)->table[index] = new_pair;
+  ((HashMap*)map)->count++;
+}
+
+int *hashmap_get(hashmap_t map, const char *key) {
+  unsigned int index = hash(key, ((HashMap*)map)->size);
+  Pair *pair = ((HashMap*)map)->table[index];
+  while (pair) {
+    if (strcmp(pair->key, key) == 0) return &pair->value;
+    pair = pair->next;
+  }
+  return NULL;
+}
+
+void hashmap_delete(hashmap_t map, const char *key) {
+  unsigned int index = hash(key, ((HashMap*)map)->size);
+  Pair *pair = ((HashMap*)map)->table[index];
+  Pair *prev = NULL;
+  while (pair) {
+    if (strcmp(pair->key, key) == 0) {
+      if (prev) prev->next = pair->next;
+      else ((HashMap*)map)->table[index] = pair->next;
+      free(pair->key);
+      free(pair);
+      ((HashMap*)map)->count--;
+      return;
+    }
+    prev = pair;
+    pair = pair->next;
+  }
+}
+
+void hashmap_free(hashmap_t map) {
+  for (size_t i = 0; i < ((HashMap*)map)->size; ++i) {
+    Pair *pair = ((HashMap*)map)->table[i];
+    while (pair){
+      Pair *temp = pair;
+      pair = pair->next;
+      free(temp->key);
+      free(temp);
+    }
+  }
+  free(((HashMap*)map)->table);
+  free(((HashMap*)map));
+}
\ No newline at end of file
diff --git a/ast.c b/src/interpreter.c
index 29fe64c..4d1f8f9 100644
--- a/ast.c
+++ b/src/interpreter.c
@@ -1,134 +1,7 @@
-#include <stdio.h>
+#include "interpreter.h"
 #include <stdlib.h>
+#include <stdio.h>
 #include <string.h>
-#include "ast.h"
-
-static ASTNode *new_node(NodeType type) {
-  ASTNode *node = malloc(sizeof(ASTNode));
-  node->type = type;
-  return node;
-}
-
-ASTNode *ast_skip(void) {
-  return new_node(NT_SKIP);
-}
-
-ASTNode *ast_assign(ASTNode *var, ASTNode *aexp) {
-  ASTNode *node = new_node(NT_ASSIGN);
-  node->u.d_assign.var = var;
-  node->u.d_assign.aexp = aexp;
-  return node;
-}
-
-ASTNode *ast_seq(ASTNode *stm1, ASTNode *stm2) {
-  ASTNode *node = new_node(NT_SEQ);
-  node->u.d_seq.stm1 = stm1;
-  node->u.d_seq.stm2 = stm2;
-  return node;
-}
-
-ASTNode *ast_if(ASTNode *bexp, ASTNode *stm1, ASTNode *stm2) {
-  ASTNode *node = new_node(NT_IF);
-  node->u.d_if.bexp = bexp;
-  node->u.d_if.stm1 = stm1;
-  node->u.d_if.stm2 = stm2;
-  return node;
-}
-
-ASTNode *ast_while(ASTNode *bexp, ASTNode *stm) {
-  ASTNode *node = new_node(NT_WHILE);
-  node->u.d_while.bexp = bexp;
-  node->u.d_while.stm = stm;
-  return node;
-}
-
-ASTNode *ast_int(int val) {
-  ASTNode *node = new_node(NT_INT);
-  node->u.d_int.val = val;
-  return node;
-}
-
-ASTNode *ast_var(char *name) {
-  ASTNode *node = new_node(NT_VAR);
-  node->u.d_var.name = strdup(name);
-  return node;
-}
-
-ASTNode *ast_aop(AOp aop, ASTNode *aexp1, ASTNode *aexp2) {
-  ASTNode *node = new_node(NT_AOP);
-  node->u.d_aop.aexp1 = aexp1;
-  node->u.d_aop.aexp2 = aexp2;
-  node->u.d_aop.aop = aop;
-  return node;
-}
-
-ASTNode *ast_bop(BOp bop, ASTNode *bexp1, ASTNode *bexp2) {
-  ASTNode *node = new_node(NT_BOP);
-  node->u.d_bop.bexp1 = bexp1;
-  node->u.d_bop.bexp2 = bexp2;
-  node->u.d_bop.bop = bop;
-  return node;
-}
-
-ASTNode *ast_not(ASTNode *bexp) {
-  ASTNode *node = new_node(NT_NOT);
-  node->u.d_not.bexp = bexp;
-  return node;
-}
-
-ASTNode *ast_rop(ROp rop, ASTNode *aexp1, ASTNode *aexp2) {
-  ASTNode *node = new_node(NT_ROP);
-  node->u.d_rop.aexp1 = aexp1;
-  node->u.d_rop.aexp2 = aexp2;
-  node->u.d_rop.rop = rop;
-  return node;
-}
-
-void free_ast(ASTNode *node) {
-  if (!node) return;
-  switch (node->type) {
-    case NT_SKIP:
-      break;
-    case NT_ASSIGN:
-      free_ast(node->u.d_assign.var);
-      free_ast(node->u.d_assign.aexp);
-      break;
-    case NT_SEQ:
-      free_ast(node->u.d_seq.stm1);
-      free_ast(node->u.d_seq.stm2);
-      break;
-    case NT_IF:
-      free_ast(node->u.d_if.bexp);
-      free_ast(node->u.d_if.stm1);
-      free_ast(node->u.d_if.stm2);
-      break;
-    case NT_WHILE:
-      free_ast(node->u.d_while.bexp);
-      free_ast(node->u.d_while.stm);
-      break;
-    case NT_INT:
-      break;
-    case NT_VAR:
-      free(node->u.d_var.name);
-      break;
-    case NT_AOP:
-      free_ast(node->u.d_aop.aexp1);
-      free_ast(node->u.d_aop.aexp2);
-      break;
-    case NT_BOP:
-      free_ast(node->u.d_bop.bexp1);
-      free_ast(node->u.d_bop.bexp2);
-      break;
-    case NT_ROP:
-      free_ast(node->u.d_rop.aexp1);
-      free_ast(node->u.d_rop.aexp2);
-      break;
-    case NT_NOT:
-      free_ast(node->u.d_not.bexp);
-      break;
-  }
-  free(node);
-}
 
 static void env_update(Env **env, const char *name, int val) {
   for (Env *e = *env; e; e = e->next) {
diff --git a/lexer.l b/src/lexer.l
index c9aaff0..c9aaff0 100644
--- a/lexer.l
+++ b/src/lexer.l
diff --git a/parser.y b/src/parser.y
index 9a94480..9a94480 100644
--- a/parser.y
+++ b/src/parser.y