From 3829a704150a06b2767d542b39179377a592da0f Mon Sep 17 00:00:00 2001 From: Flavian Kaufmann Date: Tue, 20 May 2025 10:29:33 +0200 Subject: folder structure --- Makefile | 70 ++++++++------- README.md | 2 +- ast.c | 244 -------------------------------------------------- ast.h | 52 ----------- driver.c | 31 ------- example.imp | 1 - example/example.imp | 1 + include/ast.h | 44 +++++++++ include/hash_map.h | 12 +++ include/interpreter.h | 17 ++++ lexer.l | 47 ---------- parser.y | 107 ---------------------- src/ast.c | 131 +++++++++++++++++++++++++++ src/driver.c | 31 +++++++ src/hash_map.c | 110 +++++++++++++++++++++++ src/interpreter.c | 117 ++++++++++++++++++++++++ src/lexer.l | 47 ++++++++++ src/parser.y | 107 ++++++++++++++++++++++ 18 files changed, 656 insertions(+), 515 deletions(-) delete mode 100644 ast.c delete mode 100644 ast.h delete mode 100644 driver.c delete mode 100644 example.imp create mode 100644 example/example.imp create mode 100644 include/ast.h create mode 100644 include/hash_map.h create mode 100644 include/interpreter.h delete mode 100644 lexer.l delete mode 100644 parser.y create mode 100644 src/ast.c create mode 100644 src/driver.c create mode 100644 src/hash_map.c create mode 100644 src/interpreter.c create mode 100644 src/lexer.l create mode 100644 src/parser.y 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/ast.c b/ast.c deleted file mode 100644 index 29fe64c..0000000 --- a/ast.c +++ /dev/null @@ -1,244 +0,0 @@ -#include -#include -#include -#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) { - if (strcmp(e->name, name) == 0) { - e->val = val; - return; - } - } - Env *e = malloc(sizeof(Env)); - e->name = strdup(name); - e->val = val; - e->next = *env; - *env = e; -} - -static int env_lookup(Env **env, const char *name) { - for (Env *e = *env; e; e = e->next) { - if (strcmp(e->name, name) == 0) - return e->val; - } - env_update(env, name, 0); - return env_lookup(env, name); -} - -void env_print(Env *env) { - Env *e = env; - while (e) { - printf("%s = %d\n", e->name, e->val); - e = e->next; - } -} - -static int eval_aexpr(Env **env, ASTNode *node) { - switch (node->type) { - case NT_INT: return node->u.d_int.val; - case NT_VAR: return env_lookup(env, node->u.d_var.name); - case NT_AOP: { - int aexp1 = eval_aexpr(env, node->u.d_aop.aexp1); - int aexp2 = eval_aexpr(env, node->u.d_aop.aexp2); - switch (node->u.d_aop.aop) { - case AOP_ADD: return aexp1 + aexp2; - case AOP_SUB: return aexp1 - aexp2; - case AOP_MUL: return aexp1 * aexp2; - } - } - default: - fprintf(stderr, "Bad aexpr node %d\n", node->type); - exit(EXIT_FAILURE); - } -} - -static int eval_bexpr(Env **env, ASTNode *node) { - switch (node->type) { - case NT_BOP: { - int bexp1 = eval_bexpr(env, node->u.d_bop.bexp1); - int bexp2 = eval_bexpr(env, node->u.d_bop.bexp2); - switch (node->u.d_bop.bop) { - case BOP_AND: return bexp1 && bexp2; - case BOP_OR: return bexp1 || bexp2; - } - } - case NT_NOT: - return !eval_bexpr(env, node->u.d_not.bexp); - case NT_ROP: { - int aexp1 = eval_aexpr(env, node->u.d_rop.aexp1); - int aexp2 = eval_aexpr(env, node->u.d_rop.aexp2); - switch (node->u.d_rop.rop) { - case ROP_EQ: return aexp1 == aexp2; - case ROP_NE: return aexp1 != aexp2; - case ROP_LT: return aexp1 < aexp2; - case ROP_LE: return aexp1 <= aexp2; - case ROP_GT: return aexp1 > aexp2; - case ROP_GE: return aexp1 >= aexp2; - } - } - default: - fprintf(stderr, "Bad bexpr node %d\n", node->type); - exit(EXIT_FAILURE); - } -} - -void exec_stmt(Env **env, ASTNode *node) { - while (node) { - switch (node->type) { - case NT_SKIP: - return; - case NT_ASSIGN: { - char *var = node->u.d_assign.var->u.d_var.name; - int val = eval_aexpr(env, node->u.d_assign.aexp); - env_update(env, var, val); - return; - } - case NT_SEQ: - exec_stmt(env, node->u.d_seq.stm1); - exec_stmt(env, node->u.d_seq.stm2); - return; - case NT_IF: - if (eval_bexpr(env, node->u.d_if.bexp)) - exec_stmt(env, node->u.d_if.stm1); - else - exec_stmt(env, node->u.d_if.stm2); - return; - case NT_WHILE: - while (eval_bexpr(env, node->u.d_while.bexp)) { - exec_stmt(env, node->u.d_while.stm); - } - return; - default: - fprintf(stderr, "Bad stmt node %d\n", node->type); - exit(EXIT_FAILURE); - } - } -} diff --git a/ast.h b/ast.h deleted file mode 100644 index 7dd9697..0000000 --- a/ast.h +++ /dev/null @@ -1,52 +0,0 @@ -#ifndef AST_H -#define AST_H - -typedef enum { - NT_SKIP, NT_ASSIGN, NT_SEQ, NT_IF, NT_WHILE, - NT_INT, NT_VAR, NT_AOP, NT_BOP, NT_NOT, NT_ROP -} NodeType; - -typedef enum { AOP_ADD, AOP_SUB, AOP_MUL } AOp; -typedef enum { BOP_AND, BOP_OR } BOp; -typedef enum { ROP_EQ, ROP_NE, ROP_LT, ROP_LE, ROP_GT, ROP_GE } ROp; - -typedef struct ASTNode { - NodeType type; - union { - struct { struct ASTNode *var, *aexp; } d_assign; - struct { struct ASTNode *stm1, *stm2; } d_seq; - struct { struct ASTNode *bexp, *stm1, *stm2; } d_if; - struct { struct ASTNode *bexp, *stm; } d_while; - struct { int val; } d_int ; - struct { char *name; } d_var; - struct { AOp aop; struct ASTNode *aexp1, *aexp2; } d_aop; - struct { BOp bop; struct ASTNode *bexp1, *bexp2; } d_bop; - struct { struct ASTNode *bexp; } d_not; - struct { ROp rop; struct ASTNode *aexp1, *aexp2; } d_rop; - } u; -} ASTNode; - -ASTNode *ast_skip(void); -ASTNode *ast_assign(ASTNode *var, ASTNode *aexp); -ASTNode *ast_seq(ASTNode *stm1, ASTNode *stm2); -ASTNode *ast_if(ASTNode *bexp, ASTNode *stm1, ASTNode *stm2); -ASTNode *ast_while(ASTNode *bexp, ASTNode *stm); -ASTNode *ast_int(int val); -ASTNode *ast_var(char *name); -ASTNode *ast_aop(AOp aop, ASTNode *aexp1, ASTNode *aexp2); -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/driver.c b/driver.c deleted file mode 100644 index 6b0909e..0000000 --- a/driver.c +++ /dev/null @@ -1,31 +0,0 @@ -#include -#include -#include "ast.h" - -extern FILE *yyin; -extern int yyparse(void); -extern ASTNode *ast_root; - -int main(int argc, char **argv) { - if (argc > 1) { - yyin = fopen(argv[1], "r"); - if (!yyin) { - perror(argv[1]); - return EXIT_FAILURE; - } - } else { - yyin = stdin; - } - - if (yyparse() != 0) { - fprintf(stderr, "Parsing failed.\n"); - return EXIT_FAILURE; - } - - Env *env = NULL; - exec_stmt(&env, ast_root); - env_print(env); - free_ast(ast_root); - - return EXIT_SUCCESS; -} diff --git a/example.imp b/example.imp deleted file mode 100644 index d87c891..0000000 --- a/example.imp +++ /dev/null @@ -1 +0,0 @@ -(x := 1; while x < 10 do x := (x * 2) end) diff --git a/example/example.imp b/example/example.imp new file mode 100644 index 0000000..d87c891 --- /dev/null +++ b/example/example.imp @@ -0,0 +1 @@ +(x := 1; while x < 10 do x := (x * 2) end) diff --git a/include/ast.h b/include/ast.h new file mode 100644 index 0000000..9c6b6bd --- /dev/null +++ b/include/ast.h @@ -0,0 +1,44 @@ +#ifndef AST_H +#define AST_H + +typedef enum { + NT_SKIP, NT_ASSIGN, NT_SEQ, NT_IF, NT_WHILE, + NT_INT, NT_VAR, NT_AOP, NT_BOP, NT_NOT, NT_ROP +} NodeType; + +typedef enum { AOP_ADD, AOP_SUB, AOP_MUL } AOp; +typedef enum { BOP_AND, BOP_OR } BOp; +typedef enum { ROP_EQ, ROP_NE, ROP_LT, ROP_LE, ROP_GT, ROP_GE } ROp; + +typedef struct ASTNode { + NodeType type; + union { + struct { struct ASTNode *var, *aexp; } d_assign; + struct { struct ASTNode *stm1, *stm2; } d_seq; + struct { struct ASTNode *bexp, *stm1, *stm2; } d_if; + struct { struct ASTNode *bexp, *stm; } d_while; + struct { int val; } d_int ; + struct { char *name; } d_var; + struct { AOp aop; struct ASTNode *aexp1, *aexp2; } d_aop; + struct { BOp bop; struct ASTNode *bexp1, *bexp2; } d_bop; + struct { struct ASTNode *bexp; } d_not; + struct { ROp rop; struct ASTNode *aexp1, *aexp2; } d_rop; + } u; +} ASTNode; + +ASTNode *ast_skip(void); +ASTNode *ast_assign(ASTNode *var, ASTNode *aexp); +ASTNode *ast_seq(ASTNode *stm1, ASTNode *stm2); +ASTNode *ast_if(ASTNode *bexp, ASTNode *stm1, ASTNode *stm2); +ASTNode *ast_while(ASTNode *bexp, ASTNode *stm); +ASTNode *ast_int(int val); +ASTNode *ast_var(char *name); +ASTNode *ast_aop(AOp aop, ASTNode *aexp1, ASTNode *aexp2); +ASTNode *ast_bop(BOp bop, ASTNode *bexp1, ASTNode *bexp2); +ASTNode *ast_not(ASTNode *bexp); +ASTNode *ast_rop(ROp rop, ASTNode *aexp1, ASTNode *aexp2); + +void free_ast(ASTNode *node); + +#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/lexer.l b/lexer.l deleted file mode 100644 index c9aaff0..0000000 --- a/lexer.l +++ /dev/null @@ -1,47 +0,0 @@ -%option noyywrap yylineno - -%{ -#include "parser.tab.h" -%} - -DIGIT [0-9] -IDENT [A-Za-z][A-Za-z0-9]* -WHITESPACE [ \t\r\n]+ - -%% - -"skip" { return TOKEN_SKIP; } -"if" { return TOKEN_IF; } -"then" { return TOKEN_THEN; } -"else" { return TOKEN_ELSE; } -"end" { return TOKEN_END; } -"while" { return TOKEN_WHILE; } -"do" { return TOKEN_DO; } - -"(" { return TOKEN_LEFT_PARENTHESIS; } -")" { return TOKEN_RIGHT_PARENTHESIS; } -";" { return TOKEN_SEMICOLON; } -":=" { return TOKEN_ASSIGN; } - -"+" { return TOKEN_PLUS; } -"-" { return TOKEN_MINUS; } -"*" { return TOKEN_MULTIPLY; } - -"or" { return TOKEN_OR; } -"and" { return TOKEN_AND; } -"not" { return TOKEN_NOT; } - -"=" { return TOKEN_EQUALS; } -"#" { return TOKEN_NOT_EQUALS; } -"<=" { return TOKEN_LESS_EQUAL; } -"<" { return TOKEN_LESS_THAN; } -">=" { return TOKEN_GREATER_EQUAL; } -">" { return TOKEN_GREATER_THAN; } - -{DIGIT}+ { yylval.num = atoi(yytext); return TOKEN_NUMERAL; } -{IDENT} { yylval.id = strdup(yytext); return TOKEN_IDENTIFIER; } - -{WHITESPACE} { } -. { fprintf(stderr, "Unknown char: %s\n", yytext); } - -%% diff --git a/parser.y b/parser.y deleted file mode 100644 index 9a94480..0000000 --- a/parser.y +++ /dev/null @@ -1,107 +0,0 @@ -%{ -#include -#include "ast.h" - -extern char *yytext; -extern int yylineno; -extern int yylex(); - -ASTNode *ast_root; - -void yyerror(const char *s) { - fprintf(stderr, "Parse error at token \"%s\", line %d: %s\n", yytext, yylineno, s); -} -%} - - -%union { - int num; - char *id; - int op; - struct ASTNode *node; -} - -%start program - -%token TOKEN_IDENTIFIER -%token TOKEN_NUMERAL -%token TOKEN_ASSIGN -%token TOKEN_LEFT_PARENTHESIS TOKEN_RIGHT_PARENTHESIS -%token TOKEN_SEMICOLON -%token TOKEN_SKIP -%token TOKEN_IF TOKEN_THEN TOKEN_ELSE TOKEN_END TOKEN_WHILE TOKEN_DO -%token TOKEN_PLUS TOKEN_MINUS TOKEN_MULTIPLY -%token TOKEN_NOT TOKEN_OR TOKEN_AND -%token TOKEN_EQUALS TOKEN_NOT_EQUALS TOKEN_LESS_THAN TOKEN_LESS_EQUAL TOKEN_GREATER_THAN TOKEN_GREATER_EQUAL - -%type program statement variable arithmetic_expression boolean_expression -%type arithmetic_operation boolean_operation relational_operation - - -%% - -program : statement - { ast_root = $1; } - ; - -statement : TOKEN_SKIP - { $$ = ast_skip(); } - | variable TOKEN_ASSIGN arithmetic_expression - { $$ = ast_assign($1, $3); } - | TOKEN_LEFT_PARENTHESIS statement TOKEN_SEMICOLON statement TOKEN_RIGHT_PARENTHESIS - { $$ = ast_seq($2, $4); } - | TOKEN_IF boolean_expression TOKEN_THEN statement TOKEN_ELSE statement TOKEN_END - { $$ = ast_if($2, $4, $6); } - | TOKEN_WHILE boolean_expression TOKEN_DO statement TOKEN_END - { $$ = ast_while($2, $4); } - ; - -variable : TOKEN_IDENTIFIER - { $$ = ast_var($1); } - ; - -arithmetic_expression : TOKEN_LEFT_PARENTHESIS arithmetic_expression arithmetic_operation arithmetic_expression TOKEN_RIGHT_PARENTHESIS - { $$ = ast_aop($3, $2, $4); } - | variable - { $$ = $1; } - | TOKEN_NUMERAL - { $$ = ast_int($1); } - ; - -arithmetic_operation : TOKEN_PLUS - { $$ = AOP_ADD; } - | TOKEN_MINUS - { $$ = AOP_SUB; } - | TOKEN_MULTIPLY - { $$ = AOP_MUL; } - ; - -boolean_expression : TOKEN_LEFT_PARENTHESIS boolean_expression boolean_operation boolean_expression TOKEN_RIGHT_PARENTHESIS - { $$ = ast_bop($3, $2, $4); } - | TOKEN_NOT boolean_expression - { $$ = ast_not($2); } - | arithmetic_expression relational_operation arithmetic_expression - { $$ = ast_rop($2, $1, $3); } - ; - -boolean_operation : TOKEN_OR - { $$ = BOP_OR; } - | TOKEN_AND - { $$ = BOP_AND; } - ; - -relational_operation : TOKEN_EQUALS - { $$ = ROP_EQ; } - | TOKEN_NOT_EQUALS - { $$ = ROP_NE; } - | TOKEN_LESS_THAN - { $$ = ROP_LT; } - | TOKEN_LESS_EQUAL - { $$ = ROP_LE; } - | TOKEN_GREATER_THAN - { $$ = ROP_GT; } - | TOKEN_GREATER_EQUAL - { $$ = ROP_GE; } - ; - -%% 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 +#include +#include +#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/src/driver.c b/src/driver.c new file mode 100644 index 0000000..90ee892 --- /dev/null +++ b/src/driver.c @@ -0,0 +1,31 @@ +#include +#include +#include "interpreter.h" + +extern FILE *yyin; +extern int yyparse(void); +extern ASTNode *ast_root; + +int main(int argc, char **argv) { + if (argc > 1) { + yyin = fopen(argv[1], "r"); + if (!yyin) { + perror(argv[1]); + return EXIT_FAILURE; + } + } else { + yyin = stdin; + } + + if (yyparse() != 0) { + fprintf(stderr, "Parsing failed.\n"); + return EXIT_FAILURE; + } + + Env *env = NULL; + exec_stmt(&env, ast_root); + env_print(env); + free_ast(ast_root); + + return EXIT_SUCCESS; +} 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 +#include +#include +#include +#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/src/interpreter.c b/src/interpreter.c new file mode 100644 index 0000000..4d1f8f9 --- /dev/null +++ b/src/interpreter.c @@ -0,0 +1,117 @@ +#include "interpreter.h" +#include +#include +#include + +static void env_update(Env **env, const char *name, int val) { + for (Env *e = *env; e; e = e->next) { + if (strcmp(e->name, name) == 0) { + e->val = val; + return; + } + } + Env *e = malloc(sizeof(Env)); + e->name = strdup(name); + e->val = val; + e->next = *env; + *env = e; +} + +static int env_lookup(Env **env, const char *name) { + for (Env *e = *env; e; e = e->next) { + if (strcmp(e->name, name) == 0) + return e->val; + } + env_update(env, name, 0); + return env_lookup(env, name); +} + +void env_print(Env *env) { + Env *e = env; + while (e) { + printf("%s = %d\n", e->name, e->val); + e = e->next; + } +} + +static int eval_aexpr(Env **env, ASTNode *node) { + switch (node->type) { + case NT_INT: return node->u.d_int.val; + case NT_VAR: return env_lookup(env, node->u.d_var.name); + case NT_AOP: { + int aexp1 = eval_aexpr(env, node->u.d_aop.aexp1); + int aexp2 = eval_aexpr(env, node->u.d_aop.aexp2); + switch (node->u.d_aop.aop) { + case AOP_ADD: return aexp1 + aexp2; + case AOP_SUB: return aexp1 - aexp2; + case AOP_MUL: return aexp1 * aexp2; + } + } + default: + fprintf(stderr, "Bad aexpr node %d\n", node->type); + exit(EXIT_FAILURE); + } +} + +static int eval_bexpr(Env **env, ASTNode *node) { + switch (node->type) { + case NT_BOP: { + int bexp1 = eval_bexpr(env, node->u.d_bop.bexp1); + int bexp2 = eval_bexpr(env, node->u.d_bop.bexp2); + switch (node->u.d_bop.bop) { + case BOP_AND: return bexp1 && bexp2; + case BOP_OR: return bexp1 || bexp2; + } + } + case NT_NOT: + return !eval_bexpr(env, node->u.d_not.bexp); + case NT_ROP: { + int aexp1 = eval_aexpr(env, node->u.d_rop.aexp1); + int aexp2 = eval_aexpr(env, node->u.d_rop.aexp2); + switch (node->u.d_rop.rop) { + case ROP_EQ: return aexp1 == aexp2; + case ROP_NE: return aexp1 != aexp2; + case ROP_LT: return aexp1 < aexp2; + case ROP_LE: return aexp1 <= aexp2; + case ROP_GT: return aexp1 > aexp2; + case ROP_GE: return aexp1 >= aexp2; + } + } + default: + fprintf(stderr, "Bad bexpr node %d\n", node->type); + exit(EXIT_FAILURE); + } +} + +void exec_stmt(Env **env, ASTNode *node) { + while (node) { + switch (node->type) { + case NT_SKIP: + return; + case NT_ASSIGN: { + char *var = node->u.d_assign.var->u.d_var.name; + int val = eval_aexpr(env, node->u.d_assign.aexp); + env_update(env, var, val); + return; + } + case NT_SEQ: + exec_stmt(env, node->u.d_seq.stm1); + exec_stmt(env, node->u.d_seq.stm2); + return; + case NT_IF: + if (eval_bexpr(env, node->u.d_if.bexp)) + exec_stmt(env, node->u.d_if.stm1); + else + exec_stmt(env, node->u.d_if.stm2); + return; + case NT_WHILE: + while (eval_bexpr(env, node->u.d_while.bexp)) { + exec_stmt(env, node->u.d_while.stm); + } + return; + default: + fprintf(stderr, "Bad stmt node %d\n", node->type); + exit(EXIT_FAILURE); + } + } +} diff --git a/src/lexer.l b/src/lexer.l new file mode 100644 index 0000000..c9aaff0 --- /dev/null +++ b/src/lexer.l @@ -0,0 +1,47 @@ +%option noyywrap yylineno + +%{ +#include "parser.tab.h" +%} + +DIGIT [0-9] +IDENT [A-Za-z][A-Za-z0-9]* +WHITESPACE [ \t\r\n]+ + +%% + +"skip" { return TOKEN_SKIP; } +"if" { return TOKEN_IF; } +"then" { return TOKEN_THEN; } +"else" { return TOKEN_ELSE; } +"end" { return TOKEN_END; } +"while" { return TOKEN_WHILE; } +"do" { return TOKEN_DO; } + +"(" { return TOKEN_LEFT_PARENTHESIS; } +")" { return TOKEN_RIGHT_PARENTHESIS; } +";" { return TOKEN_SEMICOLON; } +":=" { return TOKEN_ASSIGN; } + +"+" { return TOKEN_PLUS; } +"-" { return TOKEN_MINUS; } +"*" { return TOKEN_MULTIPLY; } + +"or" { return TOKEN_OR; } +"and" { return TOKEN_AND; } +"not" { return TOKEN_NOT; } + +"=" { return TOKEN_EQUALS; } +"#" { return TOKEN_NOT_EQUALS; } +"<=" { return TOKEN_LESS_EQUAL; } +"<" { return TOKEN_LESS_THAN; } +">=" { return TOKEN_GREATER_EQUAL; } +">" { return TOKEN_GREATER_THAN; } + +{DIGIT}+ { yylval.num = atoi(yytext); return TOKEN_NUMERAL; } +{IDENT} { yylval.id = strdup(yytext); return TOKEN_IDENTIFIER; } + +{WHITESPACE} { } +. { fprintf(stderr, "Unknown char: %s\n", yytext); } + +%% diff --git a/src/parser.y b/src/parser.y new file mode 100644 index 0000000..9a94480 --- /dev/null +++ b/src/parser.y @@ -0,0 +1,107 @@ +%{ +#include +#include "ast.h" + +extern char *yytext; +extern int yylineno; +extern int yylex(); + +ASTNode *ast_root; + +void yyerror(const char *s) { + fprintf(stderr, "Parse error at token \"%s\", line %d: %s\n", yytext, yylineno, s); +} +%} + + +%union { + int num; + char *id; + int op; + struct ASTNode *node; +} + +%start program + +%token TOKEN_IDENTIFIER +%token TOKEN_NUMERAL +%token TOKEN_ASSIGN +%token TOKEN_LEFT_PARENTHESIS TOKEN_RIGHT_PARENTHESIS +%token TOKEN_SEMICOLON +%token TOKEN_SKIP +%token TOKEN_IF TOKEN_THEN TOKEN_ELSE TOKEN_END TOKEN_WHILE TOKEN_DO +%token TOKEN_PLUS TOKEN_MINUS TOKEN_MULTIPLY +%token TOKEN_NOT TOKEN_OR TOKEN_AND +%token TOKEN_EQUALS TOKEN_NOT_EQUALS TOKEN_LESS_THAN TOKEN_LESS_EQUAL TOKEN_GREATER_THAN TOKEN_GREATER_EQUAL + +%type program statement variable arithmetic_expression boolean_expression +%type arithmetic_operation boolean_operation relational_operation + + +%% + +program : statement + { ast_root = $1; } + ; + +statement : TOKEN_SKIP + { $$ = ast_skip(); } + | variable TOKEN_ASSIGN arithmetic_expression + { $$ = ast_assign($1, $3); } + | TOKEN_LEFT_PARENTHESIS statement TOKEN_SEMICOLON statement TOKEN_RIGHT_PARENTHESIS + { $$ = ast_seq($2, $4); } + | TOKEN_IF boolean_expression TOKEN_THEN statement TOKEN_ELSE statement TOKEN_END + { $$ = ast_if($2, $4, $6); } + | TOKEN_WHILE boolean_expression TOKEN_DO statement TOKEN_END + { $$ = ast_while($2, $4); } + ; + +variable : TOKEN_IDENTIFIER + { $$ = ast_var($1); } + ; + +arithmetic_expression : TOKEN_LEFT_PARENTHESIS arithmetic_expression arithmetic_operation arithmetic_expression TOKEN_RIGHT_PARENTHESIS + { $$ = ast_aop($3, $2, $4); } + | variable + { $$ = $1; } + | TOKEN_NUMERAL + { $$ = ast_int($1); } + ; + +arithmetic_operation : TOKEN_PLUS + { $$ = AOP_ADD; } + | TOKEN_MINUS + { $$ = AOP_SUB; } + | TOKEN_MULTIPLY + { $$ = AOP_MUL; } + ; + +boolean_expression : TOKEN_LEFT_PARENTHESIS boolean_expression boolean_operation boolean_expression TOKEN_RIGHT_PARENTHESIS + { $$ = ast_bop($3, $2, $4); } + | TOKEN_NOT boolean_expression + { $$ = ast_not($2); } + | arithmetic_expression relational_operation arithmetic_expression + { $$ = ast_rop($2, $1, $3); } + ; + +boolean_operation : TOKEN_OR + { $$ = BOP_OR; } + | TOKEN_AND + { $$ = BOP_AND; } + ; + +relational_operation : TOKEN_EQUALS + { $$ = ROP_EQ; } + | TOKEN_NOT_EQUALS + { $$ = ROP_NE; } + | TOKEN_LESS_THAN + { $$ = ROP_LT; } + | TOKEN_LESS_EQUAL + { $$ = ROP_LE; } + | TOKEN_GREATER_THAN + { $$ = ROP_GT; } + | TOKEN_GREATER_EQUAL + { $$ = ROP_GE; } + ; + +%% -- cgit v1.2.3