folder structure

6 files changed, 543 insertions, 0 deletions

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/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 <stdio.h>
+#include <stdlib.h>
+#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 <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/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 <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+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 <stdio.h>
+#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 <id>  TOKEN_IDENTIFIER
+%token <num> 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 <node> program statement variable arithmetic_expression boolean_expression
+%type <op>   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; }
+                      ;
+
+%%