diff options
| -rw-r--r-- | Makefile | 70 | ||||
| -rw-r--r-- | README.md | 2 | ||||
| -rw-r--r-- | example/example.imp (renamed from example.imp) | 0 | ||||
| -rw-r--r-- | include/ast.h (renamed from ast.h) | 8 | ||||
| -rw-r--r-- | include/hash_map.h | 12 | ||||
| -rw-r--r-- | include/interpreter.h | 17 | ||||
| -rw-r--r-- | src/ast.c | 131 | ||||
| -rw-r--r-- | src/driver.c (renamed from driver.c) | 2 | ||||
| -rw-r--r-- | src/hash_map.c | 110 | ||||
| -rw-r--r-- | src/interpreter.c (renamed from ast.c) | 131 | ||||
| -rw-r--r-- | src/lexer.l (renamed from lexer.l) | 0 | ||||
| -rw-r--r-- | src/parser.y (renamed from parser.y) | 0 |
12 files changed, 312 insertions, 171 deletions
@@ -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) @@ -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 @@ -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 @@ -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) { |