From e7f69c8fbbbcbddde84933b2becd91e787d1ac63 Mon Sep 17 00:00:00 2001 From: Johnny Richard Date: Fri, 11 Apr 2025 01:15:01 +0200 Subject: Intial commit Signed-off-by: Johnny Richard --- src/array.c | 41 +++++++++ src/array.h | 35 ++++++++ src/lexer.c | 253 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/lexer.h | 74 ++++++++++++++++ src/main.c | 27 ++++++ src/parser.c | 173 +++++++++++++++++++++++++++++++++++++ src/parser.h | 18 ++++ src/stack.c | 21 +++++ src/stack.h | 15 ++++ src/string_view.c | 14 +++ src/string_view.h | 20 +++++ src/utils.c | 53 ++++++++++++ src/utils.h | 7 ++ src/vm.c | 198 ++++++++++++++++++++++++++++++++++++++++++ src/vm.h | 64 ++++++++++++++ 15 files changed, 1013 insertions(+) create mode 100644 src/array.c create mode 100644 src/array.h create mode 100644 src/lexer.c create mode 100644 src/lexer.h create mode 100644 src/main.c create mode 100644 src/parser.c create mode 100644 src/parser.h create mode 100644 src/stack.c create mode 100644 src/stack.h create mode 100644 src/string_view.c create mode 100644 src/string_view.h create mode 100644 src/utils.c create mode 100644 src/utils.h create mode 100644 src/vm.c create mode 100644 src/vm.h (limited to 'src') diff --git a/src/array.c b/src/array.c new file mode 100644 index 0000000..95c2b7b --- /dev/null +++ b/src/array.c @@ -0,0 +1,41 @@ +#include +#include +#include + +#include "array.h" + +void * +array_new(size_t item_size) +{ + array_header_t *h = malloc((item_size * ARRAY_INITIAL_CAPACITY) + sizeof(array_header_t)); + if (h == NULL) { + return NULL; + } + h->length = 0; + h->item_size = item_size; + h->capacity = ARRAY_INITIAL_CAPACITY; + return h + sizeof(array_header_t); +} + +array_header_t * +array_get_header(void *arr) +{ + return (array_header_t *) arr - sizeof(array_header_t); +} + +void * +array_grow(void *arr) +{ + array_header_t *h = array_get_header(arr); + h->capacity *= 2; + h = realloc(h, sizeof(array_header_t) + (h->capacity * h->item_size)); + return h + sizeof(array_header_t); +} + +size_t +array_length(void *arr) +{ + assert(arr); + array_header_t *header = array_get_header(arr); + return header->length; +} diff --git a/src/array.h b/src/array.h new file mode 100644 index 0000000..75d88d0 --- /dev/null +++ b/src/array.h @@ -0,0 +1,35 @@ +#ifndef ARRAY_H +#define ARRAY_H +#include + +#define ARRAY_INITIAL_CAPACITY 4 + +#define array(T) (T *)array_new(sizeof(T)) + +#define array_append(arr, item) do { \ + array_header_t *h = array_get_header(arr); \ + if (h->capacity < h->length + 1) { \ + arr = array_grow(arr); \ + } \ + arr[h->length++] = item; \ + } while (0) + +typedef struct array_header { + size_t capacity; + size_t item_size; + size_t length; +} array_header_t; + +void * +array_new(size_t item_size); + +array_header_t * +array_get_header(void *arr); + +void * +array_grow(void *arr); + +size_t +array_length(void *arr); + +#endif /* ARRAY_H */ diff --git a/src/lexer.c b/src/lexer.c new file mode 100644 index 0000000..9e9ab90 --- /dev/null +++ b/src/lexer.c @@ -0,0 +1,253 @@ +#include +#include +#include +#include +#include +#include "utils.h" +#include "array.h" +#include "string_view.h" +#include "lexer.h" + +void +lexer_init(lexer_t *lexer, char *file_name) +{ + assert(lexer); + + char *program = read_file_contents(file_name); + if (program == NULL) { + fprintf(stderr, "Unable to read file <%s>\n", file_name); + exit(EXIT_FAILURE); + } + + lexer->file_name = file_name; + lexer->loc = (lex_loc_t) { 0 }; + lexer->source = string_view_from_cstr(program); +} + +bool +lexer_is_eof(lexer_t *lexer) +{ + return !(lexer->loc.offset < lexer->source.size); +} + +char +lexer_current_char(lexer_t *lexer) +{ + return lexer->source.chars[lexer->loc.offset]; +} + +static bool +_isspace(char c) +{ + return isspace(c) && c != '\n'; +} + +char +lexer_next_char(lexer_t *lexer) +{ + assert(lexer->loc.offset < lexer->source.size); + char previous_char = lexer_current_char(lexer); + if (previous_char == '\n') { + lexer->loc.lineno++; + lexer->loc.lineoffset = ++lexer->loc.offset; + } else { + lexer->loc.offset++; + } + return lexer_current_char(lexer); +} + +void +lexer_next_token(lexer_t *lexer, token_t *token) +{ + if (lexer_is_eof(lexer)) { + *token = (token_t) { .kind = TOKEN_EOF }; + return; + } + + char c = lexer_current_char(lexer); + if (_isspace(c) && !lexer_is_eof(lexer)) { + while (_isspace(c) && !lexer_is_eof(lexer)) { + c = lexer_next_char(lexer); + } + } + + if (lexer_is_eof(lexer)) { + *token = (token_t) { .kind = TOKEN_EOF }; + return; + } + + if (c == '\n') { + token->kind = TOKEN_EOS; + token->loc = lexer->loc; + token->value = (string_view_t) { .size = 1, .chars = lexer->source.chars + lexer->loc.offset }; + lexer_next_char(lexer); + return; + } + + if (isalpha(c)) { + lex_loc_t start_loc = lexer->loc; + while (isalnum(c) && !lexer_is_eof(lexer)) { + c = lexer_next_char(lexer); + } + string_view_t token_value = { + .size = lexer->loc.offset - start_loc.offset, + .chars = lexer->source.chars + start_loc.offset + }; + token->value = token_value; + token->loc = start_loc; + if (string_view_eq(token_value, string_view_from_cstr("push"))) { + token->kind = TOKEN_KW_PUSH; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("dup"))) { + token->kind = TOKEN_KW_DUP; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("copy"))) { + token->kind = TOKEN_KW_COPY; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("swap"))) { + token->kind = TOKEN_KW_SWAP; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("drop"))) { + token->kind = TOKEN_KW_DROP; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("slide"))) { + token->kind = TOKEN_KW_SLIDE; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("add"))) { + token->kind = TOKEN_KW_ADD; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("sub"))) { + token->kind = TOKEN_KW_SUB; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("mul"))) { + token->kind = TOKEN_KW_MUL; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("div"))) { + token->kind = TOKEN_KW_DIV; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("mod"))) { + token->kind = TOKEN_KW_MOD; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("store"))) { + token->kind = TOKEN_KW_STORE; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("load"))) { + token->kind = TOKEN_KW_LOAD; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("call"))) { + token->kind = TOKEN_KW_CALL; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("ret"))) { + token->kind = TOKEN_KW_RET; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("jmp"))) { + token->kind = TOKEN_KW_JMP; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("jz"))) { + token->kind = TOKEN_KW_JMPZ; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("jn"))) { + token->kind = TOKEN_KW_JMPN; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("printi"))) { + token->kind = TOKEN_KW_PRINTI; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("printc"))) { + token->kind = TOKEN_KW_PRINTC; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("readi"))) { + token->kind = TOKEN_KW_READI; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("readc"))) { + token->kind = TOKEN_KW_READC; + return; + } + if (string_view_eq(token_value, string_view_from_cstr("end"))) { + token->kind = TOKEN_KW_END; + return; + } + token->kind = TOKEN_IDENT; + return; + } + + if (isdigit(c)) { + lex_loc_t start_loc = lexer->loc; + while (isdigit(c) && !lexer_is_eof(lexer)) { + c = lexer_next_char(lexer); + } + string_view_t token_value = { + .size = lexer->loc.offset - start_loc.offset, + .chars = lexer->source.chars + start_loc.offset + }; + token->kind = TOKEN_NUMBER; + token->value = token_value; + token->loc = start_loc; + } + + if (c == ':') { + token->kind = TOKEN_COLON; + token->value = (string_view_t) { .size = 1, .chars = lexer->source.chars + lexer->loc.offset}; + token->loc = lexer->loc; + lexer_next_char(lexer); + return; + } +} + +static char *token_to_cstr_table[] = { + [TOKEN_KW_PUSH] = "push", + [TOKEN_KW_DUP] = "dup", + [TOKEN_KW_COPY] = "copy", + [TOKEN_KW_SWAP] = "swap", + [TOKEN_KW_DROP] = "drop", + [TOKEN_KW_SLIDE] = "slide", + [TOKEN_KW_ADD] = "add", + [TOKEN_KW_SUB] = "sub", + [TOKEN_KW_MUL] = "mul", + [TOKEN_KW_DIV] = "div", + [TOKEN_KW_MOD] = "mod", + [TOKEN_KW_STORE] = "store", + [TOKEN_KW_LOAD] = "load", + [TOKEN_KW_CALL] = "call", + [TOKEN_KW_RET] = "ret", + [TOKEN_KW_JMP] = "jmp", + [TOKEN_KW_JMPZ] = "jz", + [TOKEN_KW_JMPN] = "jn", + [TOKEN_KW_PRINTI] = "printi", + [TOKEN_KW_PRINTC] = "printc", + [TOKEN_KW_READI] = "readi", + [TOKEN_KW_READC] = "readc", + [TOKEN_KW_END] = "end", + [TOKEN_IDENT] = "identifier", + [TOKEN_EOS] = "", + [TOKEN_NUMBER] = "number", + [TOKEN_COLON] = ":", + [TOKEN_UNKOWN] = "", + [TOKEN_EOF] = "", +}; + +char * +token_to_cstr(token_kind_t kind) +{ + return token_to_cstr_table[kind]; +} diff --git a/src/lexer.h b/src/lexer.h new file mode 100644 index 0000000..bac1d6a --- /dev/null +++ b/src/lexer.h @@ -0,0 +1,74 @@ +#ifndef LEXER_H +#define LEXER_H +#include "string_view.h" + + +typedef enum token_kind { + TOKEN_KW_PUSH, + TOKEN_KW_DUP, + TOKEN_KW_COPY, + TOKEN_KW_SWAP, + TOKEN_KW_DROP, + TOKEN_KW_SLIDE, + TOKEN_KW_ADD, + TOKEN_KW_SUB, + TOKEN_KW_MUL, + TOKEN_KW_DIV, + TOKEN_KW_MOD, + TOKEN_KW_STORE, + TOKEN_KW_LOAD, + TOKEN_KW_CALL, + TOKEN_KW_RET, + TOKEN_KW_JMP, + TOKEN_KW_JMPZ, + TOKEN_KW_JMPN, + TOKEN_KW_PRINTI, + TOKEN_KW_PRINTC, + TOKEN_KW_READI, + TOKEN_KW_READC, + TOKEN_KW_END, + TOKEN_EOS, + TOKEN_NUMBER, + TOKEN_IDENT, + TOKEN_COLON, + TOKEN_UNKOWN, + TOKEN_EOF +} token_kind_t; + +typedef struct lex_loc { + size_t offset; + size_t lineoffset; + size_t lineno; +} lex_loc_t; + +typedef struct token { + token_kind_t kind; + string_view_t value; + lex_loc_t loc; +} token_t; + +typedef struct lexer { + char *file_name; + string_view_t source; + lex_loc_t loc; +} lexer_t; + +void +lexer_init(lexer_t *lexer, char *file_name); + +bool +lexer_is_eof(lexer_t *lexer); + +char +lexer_current_char(lexer_t *lexer); + +char +lexer_next_char(lexer_t *lexer); + +void +lexer_next_token(lexer_t *lexer, token_t *token); + +char * +token_to_cstr(token_kind_t kind); + +#endif /* LEXER_H */ diff --git a/src/main.c b/src/main.c new file mode 100644 index 0000000..e26ea49 --- /dev/null +++ b/src/main.c @@ -0,0 +1,27 @@ +#include +#include +#include "array.h" +#include "lexer.h" +#include "parser.h" + +int +main(int argc, char **argv) +{ + if (argc < 2) { + fprintf(stderr, "Usage: %s file.wsa\n", argv[0]); + return EXIT_FAILURE; + } + + vm_t vm; + vm_init(&vm); + + char *file_name = argv[1]; + + parser_t parser; + parser_init(&parser, file_name); + + inst_t *insts = parser_parse(&parser); + vm_run(&vm, insts); + + return EXIT_SUCCESS; +} diff --git a/src/parser.c b/src/parser.c new file mode 100644 index 0000000..d978847 --- /dev/null +++ b/src/parser.c @@ -0,0 +1,173 @@ +#include +#include +#include +#include + +#include "array.h" +#include "parser.h" +#include "lexer.h" +#include "string_view.h" + +void +parser_init(parser_t *parser, char *file_name) +{ + assert(parser && file_name); + lexer_init(&parser->lexer, file_name); +} + +void +parser_next_expected_token(parser_t *parser, token_t *token, token_kind_t kind) +{ + lexer_next_token(&parser->lexer, token); + if (token->kind != kind) { + fprintf( + stderr, + "%s:%zu:%zu: parser error: expected token <%s> but got <%s>.\n", + parser->lexer.file_name, + token->loc.lineno + 1, + token->loc.offset - token->loc.lineoffset + 1, + token_to_cstr(kind), + token_to_cstr(token->kind)); + exit(EXIT_FAILURE); + } +} + +inst_t * +parser_parse(parser_t *parser) { + inst_t *insts = array(inst_t); + + token_t token = { 0 }; + int label_count = 0; + + lexer_next_token(&parser->lexer, &token); + while (token.kind != TOKEN_EOF) { + switch (token.kind) { + case TOKEN_KW_PUSH: { + parser_next_expected_token(parser, &token, TOKEN_NUMBER); + + char value[token.value.size + 1]; + value[token.value.size] = '\0'; + memcpy(value, token.value.chars, token.value.size); + + array_append(insts, ((inst_t) { .type = INST_PUSH, .operand = atoi(value) })); + + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_ADD: { + array_append(insts, ((inst_t) { .type = INST_ADD })); + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_DUP: { + array_append(insts, ((inst_t) { .type = INST_DUP })); + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_SWAP: { + array_append(insts, ((inst_t) { .type = INST_SWAP })); + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_SUB: { + array_append(insts, ((inst_t) { .type = INST_SUB })); + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_MUL: { + array_append(insts, ((inst_t) { .type = INST_MUL })); + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_STORE: { + array_append(insts, ((inst_t) { .type = INST_STORE })); + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_LOAD: { + array_append(insts, ((inst_t) { .type = INST_LOAD })); + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_RET: { + array_append(insts, ((inst_t) { .type = INST_RET })); + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_IDENT: { + array_append(insts, ((inst_t) { .type = INST_LABEL, .operand = label_count++ })); + parser_next_expected_token(parser, &token, TOKEN_COLON); + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_JMP: { + parser_next_expected_token(parser, &token, TOKEN_NUMBER); + + char value[token.value.size + 1]; + value[token.value.size] = '\0'; + memcpy(value, token.value.chars, token.value.size); + + array_append(insts, ((inst_t) { .type = INST_JMP, .operand = atoi(value) })); + + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_JMPZ: { + parser_next_expected_token(parser, &token, TOKEN_NUMBER); + + char value[token.value.size + 1]; + value[token.value.size] = '\0'; + memcpy(value, token.value.chars, token.value.size); + + array_append(insts, ((inst_t) { .type = INST_JMPZ, .operand = atoi(value) })); + + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_CALL: { + parser_next_expected_token(parser, &token, TOKEN_NUMBER); + + char value[token.value.size + 1]; + value[token.value.size] = '\0'; + memcpy(value, token.value.chars, token.value.size); + + array_append(insts, ((inst_t) { .type = INST_CALL, .operand = atoi(value) })); + + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_READI: { + array_append(insts, ((inst_t) { .type = INST_READI })); + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_READC: { + array_append(insts, ((inst_t) { .type = INST_READC })); + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_PRINTI: { + array_append(insts, ((inst_t) { .type = INST_PRINTI })); + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_PRINTC: { + array_append(insts, ((inst_t) { .type = INST_PRINTC })); + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_KW_END: { + array_append(insts, ((inst_t) { .type = INST_END })); + parser_next_expected_token(parser, &token, TOKEN_EOS); + break; + } + case TOKEN_EOS: { + break; + } + default: break; + } + lexer_next_token(&parser->lexer, &token); + } + + return insts; +} diff --git a/src/parser.h b/src/parser.h new file mode 100644 index 0000000..ad76bc9 --- /dev/null +++ b/src/parser.h @@ -0,0 +1,18 @@ +#ifndef PARSER_H +#define PARSER_H + +#include "lexer.h" +#include "vm.h" + +typedef struct parser +{ + lexer_t lexer; +} parser_t; + +void +parser_init(parser_t *parser, char *file_name); + +inst_t * +parser_parse(parser_t *parser); + +#endif /* PARSER_H */ diff --git a/src/stack.c b/src/stack.c new file mode 100644 index 0000000..e8e9bb1 --- /dev/null +++ b/src/stack.c @@ -0,0 +1,21 @@ +#include +#include "stack.h" + +void stack_push(stack_t *stack, int value) +{ + if (stack->size >= stack->capacity) { + perror("stack overflow"); + exit(EXIT_FAILURE); + } + stack->data[stack->size++] = value; +} + +int stack_pop(stack_t *stack) +{ + if (stack->size <= 0) { + perror("stack_pop: Stack already empty"); + exit(EXIT_FAILURE); + } + return stack->data[--stack->size]; +} + diff --git a/src/stack.h b/src/stack.h new file mode 100644 index 0000000..30722ee --- /dev/null +++ b/src/stack.h @@ -0,0 +1,15 @@ +#ifndef STACK_H +#define STACK_H +#include + +typedef struct stack +{ + size_t capacity; + size_t size; + int *data; +} stack_t; + +void stack_push(stack_t *stack, int value); +int stack_pop(stack_t *stack); + +#endif /* STACK_H */ diff --git a/src/string_view.c b/src/string_view.c new file mode 100644 index 0000000..fbdad23 --- /dev/null +++ b/src/string_view.c @@ -0,0 +1,14 @@ +#include +#include "string_view.h" + +string_view_t +string_view_from_cstr(char *cstr) +{ + return (string_view_t) { .size = strlen(cstr), .chars = cstr }; +} + +bool +string_view_eq(string_view_t s1, string_view_t s2) +{ + return s1.size == s2.size && memcmp(s1.chars, s2.chars, s1.size) == 0; +} diff --git a/src/string_view.h b/src/string_view.h new file mode 100644 index 0000000..6757689 --- /dev/null +++ b/src/string_view.h @@ -0,0 +1,20 @@ +#ifndef STRING_VIEW_H +#define STRING_VIEW_H +#include +#include + +#define PRIsv "%.*s" +#define PRIsvARG(sv) (int) (sv).size, (sv).chars + +typedef struct string_view { + size_t size; + char *chars; +} string_view_t; + +string_view_t +string_view_from_cstr(char *cstr); + +bool +string_view_eq(string_view_t s1, string_view_t s2); + +#endif /* STRING_VIEW_H */ diff --git a/src/utils.c b/src/utils.c new file mode 100644 index 0000000..5adbd0f --- /dev/null +++ b/src/utils.c @@ -0,0 +1,53 @@ +#include +#include +#include "utils.h" + +char * +read_file_contents(char *file_path) +{ + FILE *file; + int file_size; + + file = fopen(file_path, "r"); + if (file == NULL) { + perror("fopen"); + return NULL; + } + + if (fseek(file, 0, SEEK_END) == -1) { + perror("fseek SEEK_END"); + fclose(file); + return NULL; + } + + if ((file_size = ftell(file)) == -1) { + perror("ftell"); + fclose(file); + return NULL; + } + + if (fseek(file, 0, SEEK_SET) == -1) { + perror("fseek 0 SEEK_SET"); + fclose(file); + return NULL; + } + + char *file_content = (char *)calloc(file_size + 1, sizeof(char)); + if (file_content == NULL) { + fprintf(stderr, "Could not allocate mem for file_content\n"); + fclose(file); + return NULL; + } + + size_t ret = fread(file_content, sizeof(char), file_size, file); + if (ret == 0 && ferror(file) != 0) { + perror("fread"); + free(file_content); + fclose(file); + return NULL; + } + + fclose(file); + + return file_content; +} diff --git a/src/utils.h b/src/utils.h new file mode 100644 index 0000000..1fc7113 --- /dev/null +++ b/src/utils.h @@ -0,0 +1,7 @@ +#ifndef UTILS_H +#define UTILS_H + +char * +read_file_contents(char *file_path); + +#endif /* UTILS_H */ diff --git a/src/vm.c b/src/vm.c new file mode 100644 index 0000000..c7f91f0 --- /dev/null +++ b/src/vm.c @@ -0,0 +1,198 @@ +#include +#include +#include +#include "array.h" +#include "stack.h" +#include "vm.h" + +void +vm_init(vm_t *vm) +{ + assert(vm); + vm->stack = (stack_t) { + .capacity = STACK_CAPACITY, + .size = 0, + .data = calloc(sizeof(int), STACK_CAPACITY) + }; + vm->call_stack = (stack_t) { + .capacity = 3000, + .size = 0, + .data = calloc(sizeof(int), 3000) + }; + vm->heap = calloc(sizeof(int), HEAP_CAPACITY); + vm->labels = array(label_t); +} + +void +vm_run(vm_t *vm, inst_t *insts) +{ + size_t program_size = array_length(insts); + + // resolve lables + for (size_t ip = 0; ip < program_size; ++ip) { + if (insts[ip].type == INST_LABEL) { + int name = insts[ip].operand; + label_t label = { .name = name, .index = ip }; + array_append(vm->labels, label); + } + } + + // resolve jumps + for (size_t ip = 0; ip < program_size; ++ip) { + switch (insts[ip].type) { + case INST_CALL: + case INST_JMP: + case INST_JMPN: + case INST_JMPZ: { + int label_name = insts[ip].operand; + size_t i = 0; + size_t labels_size = array_length(vm->labels); + for (; i < labels_size; ++i) { + if (vm->labels[i].name == label_name) { + insts[ip].operand = vm->labels[i].index; + break; + } + } + assert(i < labels_size); + } + default: break; + } + } + + // run + for (size_t ip = 0; ip < program_size; ++ip) { + switch (insts[ip].type) { + case INST_PUSH: { + stack_push(&vm->stack, insts[ip].operand); + break; + } + case INST_DUP: { + stack_push(&vm->stack, vm->stack.data[vm->stack.size - 1]); + break; + } + case INST_COPY: { + int operand = insts[ip].operand; + stack_push(&vm->stack, vm->stack.data[vm->stack.size - 1 - operand]); + break; + } + case INST_SWAP: { + int a = stack_pop(&vm->stack); + int b = stack_pop(&vm->stack); + stack_push(&vm->stack, a); + stack_push(&vm->stack, b); + break; + } + case INST_DROP: { + stack_pop(&vm->stack); + break; + } + case INST_SLIDE: { + int operand = insts[ip].operand; + int top = stack_pop(&vm->stack); + while (operand-- > 0) { + stack_pop(&vm->stack); + } + stack_push(&vm->stack, top); + break; + } + case INST_ADD: { + int lhs = stack_pop(&vm->stack); + int rhs = stack_pop(&vm->stack); + stack_push(&vm->stack, lhs + rhs); + break; + } + case INST_SUB: { + int rhs = stack_pop(&vm->stack); + int lhs = stack_pop(&vm->stack); + stack_push(&vm->stack, lhs - rhs); + break; + } + case INST_MUL: { + int rhs = stack_pop(&vm->stack); + int lhs = stack_pop(&vm->stack); + stack_push(&vm->stack, lhs * rhs); + break; + } + case INST_DIV: { + int rhs = stack_pop(&vm->stack); + int lhs = stack_pop(&vm->stack); + stack_push(&vm->stack, lhs / rhs); + break; + } + case INST_MOD: { + int rhs = stack_pop(&vm->stack); + int lhs = stack_pop(&vm->stack); + stack_push(&vm->stack, lhs % rhs); + break; + } + case INST_STORE: { + int value = stack_pop(&vm->stack); + int address = stack_pop(&vm->stack); + vm->heap[address] = value; + break; + } + case INST_LOAD: { + int address = stack_pop(&vm->stack); + stack_push(&vm->stack, vm->heap[address]); + break; + } + case INST_CALL: { + stack_push(&vm->call_stack, ip + 1); + ip = insts[ip].operand; + break; + } + case INST_RET: { + ip = stack_pop(&vm->call_stack); + break; + } + case INST_JMP: { + ip = insts[ip].operand; + break; + } + case INST_JMPZ: { + int value = stack_pop(&vm->stack); + if (value == 0) { + ip = insts[ip].operand; + } + break; + } + case INST_JMPN: { + int value = stack_pop(&vm->stack); + if (value < 0) { + ip = insts[ip].operand; + } + break; + } + case INST_PRINTI: { + int value = stack_pop(&vm->stack); + printf("%d", value); + break; + } + case INST_PRINTC: { + int value = stack_pop(&vm->stack); + printf("%c", value); + break; + } + case INST_READI: { + int address = stack_pop(&vm->stack); + scanf("%d", vm->heap + address); + break; + } + case INST_READC: { + int address = stack_pop(&vm->stack); + vm->heap[address] = getchar(); + break; + } + case INST_END: { + return; + } + case INST_LABEL: { + break; + } + default: { + assert(0 && "Unsupported instruction"); + break; + } + } + } +} diff --git a/src/vm.h b/src/vm.h new file mode 100644 index 0000000..2e9e487 --- /dev/null +++ b/src/vm.h @@ -0,0 +1,64 @@ +#ifndef VM_H +#define VM_H +#include "stack.h" + +#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(program[0])) +#define STACK_CAPACITY 1024 +#define HEAP_CAPACITY 1024 + +typedef enum inst_type { + // stack + INST_PUSH, + INST_DUP, + INST_COPY, + INST_SWAP, + INST_DROP, + INST_SLIDE, + // arithmetics + INST_ADD, + INST_SUB, + INST_MUL, + INST_DIV, + INST_MOD, + // heap access + INST_STORE, + INST_LOAD, + // Flow control + INST_CALL, + INST_RET, + INST_LABEL, + INST_JMP, + INST_JMPZ, + INST_JMPN, + // I/O + INST_PRINTI, + INST_PRINTC, + INST_READI, + INST_READC, + INST_END, +} inst_type_t; + +typedef struct instr { + inst_type_t type; + int operand; +} inst_t; + +typedef struct label { + int name; + int index; +} label_t; + +typedef struct vm { + stack_t stack; + stack_t call_stack; + int *heap; + label_t *labels; +} vm_t; + +void +vm_init(vm_t *vm); + +void +vm_run(vm_t *vm, inst_t *insts); + +#endif /* VM_H */ -- cgit v1.2.3