From 821939c6a6eb5761708146783ebd562422c2a7f7 Mon Sep 17 00:00:00 2001 From: Camil Staps Date: Thu, 25 Aug 2016 20:29:50 +0200 Subject: pedantic --- compiler/.gitignore | 2 - compiler/Makefile | 18 ---- compiler/eval.c | 251 ----------------------------------------------- compiler/eval.h | 9 -- compiler/fuspelc.c | 62 ------------ compiler/lex.c | 99 ------------------- compiler/lex.h | 8 -- compiler/log.c | 9 -- compiler/log.h | 14 --- compiler/mem.c | 16 --- compiler/mem.h | 9 -- compiler/parse.c | 246 ---------------------------------------------- compiler/parse.h | 8 -- compiler/print.c | 102 ------------------- compiler/print.h | 13 --- compiler/syntax.c | 163 ------------------------------- compiler/syntax.h | 80 --------------- interpreter/.gitignore | 2 + interpreter/Makefile | 18 ++++ interpreter/eval.c | 258 +++++++++++++++++++++++++++++++++++++++++++++++++ interpreter/eval.h | 9 ++ interpreter/fuspelc.c | 64 ++++++++++++ interpreter/lex.c | 101 +++++++++++++++++++ interpreter/lex.h | 8 ++ interpreter/log.c | 9 ++ interpreter/log.h | 14 +++ interpreter/mem.c | 16 +++ interpreter/mem.h | 9 ++ interpreter/parse.c | 251 +++++++++++++++++++++++++++++++++++++++++++++++ interpreter/parse.h | 8 ++ interpreter/print.c | 102 +++++++++++++++++++ interpreter/print.h | 13 +++ interpreter/syntax.c | 166 +++++++++++++++++++++++++++++++ interpreter/syntax.h | 80 +++++++++++++++ 34 files changed, 1128 insertions(+), 1109 deletions(-) delete mode 100644 compiler/.gitignore delete mode 100644 compiler/Makefile delete mode 100644 compiler/eval.c delete mode 100644 compiler/eval.h delete mode 100644 compiler/fuspelc.c delete mode 100644 compiler/lex.c delete mode 100644 compiler/lex.h delete mode 100644 compiler/log.c delete mode 100644 compiler/log.h delete mode 100644 compiler/mem.c delete mode 100644 compiler/mem.h delete mode 100644 compiler/parse.c delete mode 100644 compiler/parse.h delete mode 100644 compiler/print.c delete mode 100644 compiler/print.h delete mode 100644 compiler/syntax.c delete mode 100644 compiler/syntax.h create mode 100644 interpreter/.gitignore create mode 100644 interpreter/Makefile create mode 100644 interpreter/eval.c create mode 100644 interpreter/eval.h create mode 100644 interpreter/fuspelc.c create mode 100644 interpreter/lex.c create mode 100644 interpreter/lex.h create mode 100644 interpreter/log.c create mode 100644 interpreter/log.h create mode 100644 interpreter/mem.c create mode 100644 interpreter/mem.h create mode 100644 interpreter/parse.c create mode 100644 interpreter/parse.h create mode 100644 interpreter/print.c create mode 100644 interpreter/print.h create mode 100644 interpreter/syntax.c create mode 100644 interpreter/syntax.h diff --git a/compiler/.gitignore b/compiler/.gitignore deleted file mode 100644 index 9148247..0000000 --- a/compiler/.gitignore +++ /dev/null @@ -1,2 +0,0 @@ -*.o -fuspelc diff --git a/compiler/Makefile b/compiler/Makefile deleted file mode 100644 index a8cd4a1..0000000 --- a/compiler/Makefile +++ /dev/null @@ -1,18 +0,0 @@ -CFLAGS=-Wall -s - -DEPS=lex.h syntax.h print.h parse.h log.h eval.h mem.h -OBJ=fuspelc.o lex.o syntax.o print.o parse.o log.o eval.o mem.o -EXE=fuspelc - -.PHONY: all clean - -all: $(EXE) - -$(EXE): $(OBJ) - $(CC) -o $@ $^ $(CFLAGS) - -%.o: %.c $(DEPS) - $(CC) -c -o $@ $< $(CFLAGS) - -clean: - $(RM) -v $(OBJ) $(EXE) diff --git a/compiler/eval.c b/compiler/eval.c deleted file mode 100644 index c9059be..0000000 --- a/compiler/eval.c +++ /dev/null @@ -1,251 +0,0 @@ -#include "eval.h" - -#include - -#include "mem.h" - -void free_rules_until(fuspel* new, fuspel* old) { - while (new != old) { - free_rewrite_rule(&new->rule); - fuspel* _new = new->rest; - my_free(new); - new = _new; - } -} - -typedef struct replacements { - char* what; - expression* with; - struct replacements* rest; -} replacements; - -void replace(char* name, expression* new, expression* expr) { - if (!expr) - return; - - switch (expr->kind) { - case EXPR_NAME: - if (!strcmp(expr->var1, name)) { - cpy_expression(expr, new); - break; - } - case EXPR_INT: - break; - case EXPR_TUPLE: - case EXPR_LIST: - case EXPR_APP: - replace(name, new, expr->var1); - replace(name, new, expr->var2); - break; - } -} - -void replace_all(replacements* repls, expression* expr) { - while (repls) { - replace(repls->what, repls->with, expr); - repls = repls->rest; - } -} - -replacements* push_replacement(char* what, expression* with, replacements* rest) { - replacements* new = my_calloc(1, sizeof(replacements)); - new->what = what; - new->with = my_calloc(1, sizeof(expression)); - cpy_expression(new->with, with); - new->rest = rest; - return new; -} - -void free_replacements(replacements* repls) { - if (repls) { - free_replacements(repls->rest); - repls->rest = NULL; - free_expression(repls->with); - my_free(repls->with); - my_free(repls); - } -} - -unsigned match_expr(fuspel* rules, expression* to_match, expression* expr, - replacements** repls) { - if (to_match->kind != EXPR_NAME) { - expr = eval_rnf(rules, expr); - if (!expr) - return 0; - } - - unsigned matches; - - switch (to_match->kind) { - case EXPR_NAME: - *repls = push_replacement(to_match->var1, expr, *repls); - free_expression(expr); - my_free(expr); - return 1; - case EXPR_INT: - matches = eq_expression(to_match, expr); - free_expression(expr); - my_free(expr); - return matches; - case EXPR_LIST: - if (!to_match->var1) { // empty list - matches = eq_expression(to_match, expr); - free_expression(expr); - my_free(expr); - return matches; - } - case EXPR_TUPLE: - if (to_match->kind != expr->kind) { - free_expression(expr); - my_free(expr); - return 0; - } - matches = - match_expr(rules, to_match->var1, expr->var1, repls) && - match_expr(rules, to_match->var2, expr->var2, repls); - free_expression(expr); - my_free(expr); - return matches; - default: - free_expression(expr); - my_free(expr); - return 0; - } -} - -unsigned match_rule(fuspel* rules, rewrite_rule* rule, expression* expr, - replacements** repls) { - switch (expr->kind) { - case EXPR_NAME: - return (!strcmp(expr->var1, rule->name) && - empty_args_list(rule->args)) ? 1 : 0; - case EXPR_APP: - ;expression** expr_args = flatten_app_args(expr); - unsigned char i = 0; - if (!strcmp(expr_args[0]->var1, rule->name)) { - expression* _expr = expr_args[++i]; - arg_list* args = rule->args; - fuspel* _rules = rules; - while (!empty_args_list(args)) { - if (!match_expr(_rules, &args->elem, _expr, repls)) { - free_rules_until(_rules, rules); - my_free(expr_args); - return 0; - } - - args = args->rest; - _expr = expr_args[++i]; - - if (!empty_args_list(args) && !_expr) { - free_rules_until(_rules, rules); - my_free(expr_args); - return 0; - } - } - my_free(expr_args); - return 1; - } - my_free(expr_args); - default: - return 0; - } -} - -expression* eval_rnf(fuspel* rules, expression* expr) { - expression* result = my_calloc(1, sizeof(expression)); - - fuspel* _rules = rules; - - replacements** repls = my_calloc(1, sizeof(replacements*)); - - switch (expr->kind) { - case EXPR_INT: - case EXPR_TUPLE: - case EXPR_LIST: - cpy_expression(result, expr); - break; - - case EXPR_NAME: - case EXPR_APP: - while (_rules) { - if (match_rule(rules, &_rules->rule, expr, repls)) { - cpy_expression(result, &_rules->rule.rhs); - replace_all(*repls, result); - free_replacements(*repls); - my_free(repls); - expression* old_result = result; - result = eval_rnf(rules, old_result); - free_expression(old_result); - my_free(old_result); - return result; - } - free_replacements(*repls); - my_free(repls); - repls = my_calloc(1, sizeof(replacements*)); - _rules = _rules->rest; - } - cpy_expression(result, expr); - break; - } - - free_replacements(*repls); - my_free(repls); - - return result; -} - -expression* eval(fuspel* rules, expression* expr) { - expression* result = my_calloc(1, sizeof(expression)); - - expression *e1, *e2; - fuspel* _rules = rules; - - replacements** repls = my_calloc(1, sizeof(replacements*)); - - switch (expr->kind) { - case EXPR_INT: - cpy_expression(result, expr); - break; - - case EXPR_NAME: - case EXPR_APP: - while (_rules) { - if (match_rule(rules, &_rules->rule, expr, repls)) { - cpy_expression(result, &_rules->rule.rhs); - replace_all(*repls, result); - expression* old_result = result; - result = eval(rules, old_result); - free_expression(old_result); - my_free(old_result); - free_replacements(*repls); - my_free(repls); - return result; - } - free_replacements(*repls); - my_free(repls); - repls = my_calloc(1, sizeof(replacements*)); - _rules = _rules->rest; - } - cpy_expression(result, expr); - break; - - case EXPR_LIST: - if (!expr->var1) { - cpy_expression(result, expr); - break; - } - case EXPR_TUPLE: - e1 = eval(rules, expr->var1); - e2 = eval(rules, expr->var2); - - result->kind = expr->kind; - result->var1 = e1; - result->var2 = e2; - break; - } - - free_replacements(*repls); - my_free(repls); - - return result; -} diff --git a/compiler/eval.h b/compiler/eval.h deleted file mode 100644 index 3acd1d0..0000000 --- a/compiler/eval.h +++ /dev/null @@ -1,9 +0,0 @@ -#ifndef _H_EVAL -#define _H_EVAL - -#include "syntax.h" - -expression* eval_rnf(fuspel*, expression*); -expression* eval(fuspel*, expression*); - -#endif diff --git a/compiler/fuspelc.c b/compiler/fuspelc.c deleted file mode 100644 index 48ca8cb..0000000 --- a/compiler/fuspelc.c +++ /dev/null @@ -1,62 +0,0 @@ -#include -#include - -#include "eval.h" -#include "lex.h" -#include "mem.h" -#include "parse.h" -#include "print.h" - -int main(void) { - token_list* tokens = NULL; - - while (!feof(stdin)) { - char program[79]; - if (!fgets(program, 79, stdin)) { - if (feof(stdin)) - break; - fprintf(stderr, "Couldn't read input."); - exit(EXIT_FAILURE); - } - - tokens = lex(tokens, program); - if (!tokens) { - fprintf(stderr, "Couldn't lex program."); - exit(EXIT_FAILURE); - } - } - - fuspel* pgm = parse(tokens); - free_token_list(tokens); - free(tokens); - - if (!pgm) { - fprintf(stderr, "Couldn't parse program."); - exit(EXIT_FAILURE); - } - - printf("\nParsed program:\n"); - print_fuspel(pgm); - printf("\n\n\n"); - - expression to_eval, *evaled; - - to_eval.kind = EXPR_NAME; - to_eval.var1 = my_calloc(1, 5); - strcpy(to_eval.var1, "main"); - - evaled = eval(pgm, &to_eval); - free_expression(&to_eval); - if (evaled) { - print_expression(evaled); - printf("\n"); - - free_expression(evaled); - free(evaled); - } - - free_fuspel(pgm); - free(pgm); - - return 0; -} diff --git a/compiler/lex.c b/compiler/lex.c deleted file mode 100644 index 2459881..0000000 --- a/compiler/lex.c +++ /dev/null @@ -1,99 +0,0 @@ -#include "lex.h" - -#include - -#include "mem.h" - -inline unsigned is_space_char(char input) { - return input == '\t' || input == ' ' || input == '\n' || input == '\r'; -} - -inline unsigned is_int_char(char input) { - return '0' <= input && input <= '9'; -} - -// The number of bytes that should be read to read an integer -unsigned char lex_int_length(char* input) { - unsigned char n = 0; - while (is_int_char(*input++)) n++; - return n; -} - -inline unsigned is_name_char(char input) { - return (('A' <= input && input <= 'Z') || - ('a' <= input && input <= 'z') || - input == '_'); -} - -// The number of bytes that should be read to read a name -unsigned char lex_name_length(char* input) { - unsigned char n = 0; - while (is_name_char(*input++)) n++; - return n; -} - -token_list* lex(token_list* list, char* input) { - if (input[0] == 0) { - return NULL; - } - - token_list* first_list; - if (list) { - first_list = list; - while (list->rest) list = list->rest; - list->rest = my_calloc(1, sizeof(token_list)); - list = list->rest; - } else { - first_list = list = my_calloc(1, sizeof(token_list)); - } - - while (*input) { - list->elem.var = NULL; - - unsigned proceed_to_next_token = 1; - - switch (*input) { - case ';': list->elem.kind = TOKEN_SEMICOLON; break; - case ':': list->elem.kind = TOKEN_COLON; break; - case '(': list->elem.kind = TOKEN_OPEN_P; break; - case ')': list->elem.kind = TOKEN_CLOSE_P; break; - case '[': list->elem.kind = TOKEN_OPEN_SQ; break; - case ']': list->elem.kind = TOKEN_CLOSE_SQ; break; - case '=': list->elem.kind = TOKEN_EQUALS; break; - case ',': list->elem.kind = TOKEN_COMMA; break; - - default: - if (is_int_char(*input)) { - list->elem.kind = TOKEN_INT; - unsigned char len = lex_int_length(input); - char* s = my_calloc(1, len + 1); - list->elem.var = my_calloc(1, sizeof(int)); - strncpy(s, input, len); - *((int*) list->elem.var) = atoi(s); - my_free(s); - input += len - 1; - } else if (is_name_char(*input)) { - list->elem.kind = TOKEN_NAME; - unsigned char len = lex_name_length(input); - list->elem.var = my_calloc(1, len + 1); - strncpy(list->elem.var, input, len); - input += len - 1; - } else if (is_space_char(*input)) { - proceed_to_next_token = 0; - } else { - free_token_list(first_list); - my_free(first_list); - return NULL; - } - } - - input++; - - if (*input && proceed_to_next_token) { - list->rest = my_calloc(1, sizeof(token_list)); - list = list->rest; - } - } - - return first_list; -} diff --git a/compiler/lex.h b/compiler/lex.h deleted file mode 100644 index 268d0e4..0000000 --- a/compiler/lex.h +++ /dev/null @@ -1,8 +0,0 @@ -#ifndef _H_LEX -#define _H_LEX - -#include "syntax.h" - -token_list* lex(token_list*, char*); - -#endif diff --git a/compiler/log.c b/compiler/log.c deleted file mode 100644 index c369b4b..0000000 --- a/compiler/log.c +++ /dev/null @@ -1,9 +0,0 @@ -#include "log.h" - -#include - -#if(LOG_LEVEL < LOG_DEBUG) -void log_debug(char* msg) { - fprintf(stdout, "%s\n", msg); -} -#endif diff --git a/compiler/log.h b/compiler/log.h deleted file mode 100644 index 7d4e406..0000000 --- a/compiler/log.h +++ /dev/null @@ -1,14 +0,0 @@ -#ifndef _H_LOG -#define _H_LOG - -#define LOG_DEBUG 1 - -#define LOG_LEVEL 10 - -#if(LOG_LEVEL >= LOG_DEBUG) -#define log_debug(x) -#else -void log_debug(char*); -#endif - -#endif diff --git a/compiler/mem.c b/compiler/mem.c deleted file mode 100644 index 7affd71..0000000 --- a/compiler/mem.c +++ /dev/null @@ -1,16 +0,0 @@ -#include "mem.h" - -#include - -void* my_calloc(size_t num, size_t size) { - void* ptr = calloc(num, size); - if (!ptr) { - perror(NULL); - exit(EXIT_FAILURE); - } - return ptr; -} - -void my_free(void* ptr) { - free(ptr); -} diff --git a/compiler/mem.h b/compiler/mem.h deleted file mode 100644 index 0399cef..0000000 --- a/compiler/mem.h +++ /dev/null @@ -1,9 +0,0 @@ -#ifndef _H_MEM -#define _H_MEM - -#include - -void* my_calloc(size_t num, size_t size); -void my_free(void* ptr); - -#endif diff --git a/compiler/parse.c b/compiler/parse.c deleted file mode 100644 index b5ae273..0000000 --- a/compiler/parse.c +++ /dev/null @@ -1,246 +0,0 @@ -#include "parse.h" - -#include - -#include "log.h" -#include "mem.h" - -token_list* parse_name(char** name, token_list* list) { - if (list->elem.kind != TOKEN_NAME) - return NULL; - - *name = my_calloc(1, strlen(list->elem.var) + 1); - - strcpy(*name, list->elem.var); - - return list->rest; -} - -token_list* parse_simple_expression(expression* expr, token_list* list) { - switch (list->elem.kind) { - case TOKEN_INT: - expr->kind = EXPR_INT; - expr->var1 = my_calloc(1, sizeof(int)); - *((int*) expr->var1) = *((int*) list->elem.var); - return list->rest; - - case TOKEN_NAME: - expr->kind = EXPR_NAME; - list = parse_name((char**) &expr->var1, list); - return list; - - case TOKEN_OPEN_P: - list = parse_simple_expression(expr, list->rest); - if (!list) - return NULL; - - expression* _expr; - switch (list->elem.kind) { - case TOKEN_CLOSE_P: - return list->rest; - break; - case TOKEN_COMMA: - _expr = my_calloc(1, sizeof(expression)); - cpy_expression(_expr, expr); - free_expression(expr); - expr->kind = EXPR_TUPLE; - expr->var1 = _expr; - expr->var2 = my_calloc(1, sizeof(expression)); - list = parse_simple_expression(expr->var2, list->rest); - if (!list || list->elem.kind != TOKEN_CLOSE_P) { - free_expression(_expr); - my_free(_expr); - return NULL; - } else { - return list->rest; - } - break; - default: - return NULL; - } - break; - - case TOKEN_OPEN_SQ: - expr->kind = EXPR_LIST; - list = list->rest; - if (!list) - return NULL; - - if (list->elem.kind == TOKEN_CLOSE_SQ) - return list->rest; - - expr->var1 = my_calloc(1, sizeof(expression)); - expr->var2 = my_calloc(1, sizeof(expression)); - - list = parse_simple_expression(expr->var1, list); - - if (!list || list->elem.kind != TOKEN_COLON) { - free_expression(expr->var1); - return NULL; - } - - list = parse_simple_expression(expr->var2, list->rest); - - if (!list || list->elem.kind != TOKEN_CLOSE_SQ) { - free_expression(expr->var1); - my_free(expr->var1); - free_expression(expr->var2); - my_free(expr->var2); - return NULL; - } - - return list->rest; - - break; - - default: - return NULL; - } -} - -token_list* parse_arg_list(arg_list** args, token_list* list) { - if (list->elem.kind == TOKEN_EQUALS) - return list; - - *args = my_calloc(1, sizeof(arg_list)); - - list = parse_simple_expression(&(*args)->elem, list); - if (!list) - return NULL; - - list = parse_arg_list(&(*args)->rest, list); - - return list; -} - -token_list* parse_expression(expression*, token_list*); - -token_list* parse_expression_no_app(expression* expr, token_list* list) { - if (list->elem.kind == TOKEN_OPEN_P) { - token_list* _list = parse_expression(expr, list->rest); - if (_list) { - if (_list->elem.kind == TOKEN_CLOSE_P) { - return _list->rest; - } else if (_list->elem.kind == TOKEN_COMMA) { - expression* _expr = my_calloc(1, sizeof(expression)); - - cpy_expression(_expr, expr); - free_expression(expr); - expr->kind = EXPR_TUPLE; - expr->var1 = _expr; - - expr->var2 = my_calloc(1, sizeof(expression)); - - _list = parse_expression(expr->var2, _list->rest); - if (_list && _list->elem.kind == TOKEN_CLOSE_P) { - return _list->rest; - } - } - free_expression(expr); - } - } else if (list->elem.kind == TOKEN_OPEN_SQ) { - expr->kind = EXPR_LIST; - - if (list->rest->elem.kind == TOKEN_CLOSE_SQ) { - return list->rest->rest; - } - - expression* expr1 = my_calloc(1, sizeof(expression)); - expression* expr2 = my_calloc(1, sizeof(expression)); - - token_list* _list = parse_expression(expr1, list->rest); - if (!_list || _list->elem.kind != TOKEN_COLON) { - free_expression(expr1); - my_free(expr1); - my_free(expr2); - } else { - _list = parse_expression(expr2, _list->rest); - if (!_list || _list->elem.kind != TOKEN_CLOSE_SQ) { - free_expression(expr1); - free_expression(expr2); - my_free(expr1); - my_free(expr2); - } else { - expr->var1 = expr1; - expr->var2 = expr2; - return _list->rest; - } - } - } - - list = parse_simple_expression(expr, list); - - return list; -} - -token_list* parse_expression(expression* expr, token_list* list) { - list = parse_expression_no_app(expr, list); - if (!list) - return NULL; - - while (list->elem.kind != TOKEN_SEMICOLON && - list->elem.kind != TOKEN_CLOSE_P && - list->elem.kind != TOKEN_CLOSE_SQ && - list->elem.kind != TOKEN_COLON && - list->elem.kind != TOKEN_COMMA) { - - expression* _expr = my_calloc(1, sizeof(expression)); - - cpy_expression(_expr, expr); - free_expression(expr); - expr->kind = EXPR_APP; - expr->var1 = _expr; - - expr->var2 = my_calloc(1, sizeof(expression)); - - list = parse_expression_no_app(expr->var2, list); - if (!list) { - free_expression(expr); - return NULL; - } - } - - return list; -} - -token_list* parse_rule(rewrite_rule* rule, token_list* list) { - list = parse_name(&rule->name, list); - if (!list) - return NULL; - - list = parse_arg_list(&rule->args, list); - if (!list) { - log_debug("parse_rule: error in arg_list"); - my_free(rule->name); - return NULL; - } - - if (list->elem.kind != TOKEN_EQUALS) { - log_debug("parse_rule: no ="); - my_free(rule->name); - free_arg_list(rule->args); - return NULL; - } - - list = parse_expression(&rule->rhs, list->rest); - - return list; -} - -fuspel* parse(token_list* list) { - while (list && list->elem.kind == TOKEN_SEMICOLON) - list = list->rest; - - if (!list) - return NULL; - - fuspel* rules = my_calloc(1, sizeof(fuspel)); - - list = parse_rule(&rules->rule, list); - if (!list) - return NULL; - - rules->rest = parse(list); - - return rules; -} diff --git a/compiler/parse.h b/compiler/parse.h deleted file mode 100644 index 39f74e0..0000000 --- a/compiler/parse.h +++ /dev/null @@ -1,8 +0,0 @@ -#ifndef _H_PARSE -#define _H_PARSE - -#include "syntax.h" - -fuspel* parse(token_list*); - -#endif diff --git a/compiler/print.c b/compiler/print.c deleted file mode 100644 index a71e71f..0000000 --- a/compiler/print.c +++ /dev/null @@ -1,102 +0,0 @@ -#include "print.h" - -#include - -#include "log.h" - -void print_token(token* tk) { - char c; - switch (tk->kind) { - case TOKEN_SEMICOLON: c = ';'; break; - case TOKEN_COLON: c = ':'; break; - case TOKEN_OPEN_P: c = '('; break; - case TOKEN_CLOSE_P: c = ')'; break; - case TOKEN_OPEN_SQ: c = '['; break; - case TOKEN_CLOSE_SQ: c = ']'; break; - case TOKEN_EQUALS: c = '='; break; - case TOKEN_COMMA: c = ','; break; - case TOKEN_NAME: - printf("%s", (char*) tk->var); - return; - case TOKEN_INT: - printf("%d", *((int*) tk->var)); - return; - } - printf("%c", c); -} - -void print_token_list(token_list* list) { - print_token(&list->elem); - if (list->rest) { - printf(list->elem.kind == TOKEN_SEMICOLON ? "\n" : " "); - print_token_list(list->rest); - } -} - -void print_expression(expression* expr) { - switch (expr->kind) { - case EXPR_INT: - printf("%d", *((int*) expr->var1)); - break; - case EXPR_NAME: - printf("%s", (char*) expr->var1); - break; - case EXPR_LIST: - if (!expr->var1) { - printf("[]"); - } else { - printf("["); - print_expression(expr->var1); - printf(":"); - print_expression(expr->var2); - printf("]"); - } - break; - case EXPR_TUPLE: - printf("("); - print_expression(expr->var1); - printf(","); - print_expression(expr->var2); - printf(")"); - break; - case EXPR_APP: - if (((expression*) expr->var1)->kind == EXPR_APP) - printf("("); - print_expression(expr->var1); - if (((expression*) expr->var1)->kind == EXPR_APP) - printf(")"); - printf(" "); - if (((expression*) expr->var2)->kind == EXPR_APP) - printf("("); - print_expression(expr->var2); - if (((expression*) expr->var2)->kind == EXPR_APP) - printf(")"); - break; - } -} - -void print_arg_list(arg_list* args) { - if (!args) - return; - - print_expression(&args->elem); - printf(" "); - if (args->rest) - print_arg_list(args->rest); -} - -void print_rewrite_rule(rewrite_rule* rule) { - printf("%s ", rule->name); - print_arg_list(rule->args); - printf("= "); - print_expression(&rule->rhs); - printf(";"); -} - -void print_fuspel(fuspel* rules) { - print_rewrite_rule(&rules->rule); - if (rules->rest) { - printf("\n"); - print_fuspel(rules->rest); - } -} diff --git a/compiler/print.h b/compiler/print.h deleted file mode 100644 index 5909087..0000000 --- a/compiler/print.h +++ /dev/null @@ -1,13 +0,0 @@ -#ifndef _H_PRINT -#define _H_PRINT - -#include "syntax.h" - -void print_token(token*); -void print_token_list(token_list*); - -void print_expression(expression*); -void print_rewrite_rule(rewrite_rule*); -void print_fuspel(fuspel*); - -#endif diff --git a/compiler/syntax.c b/compiler/syntax.c deleted file mode 100644 index 0f80461..0000000 --- a/compiler/syntax.c +++ /dev/null @@ -1,163 +0,0 @@ -#include "syntax.h" - -#include - -#include "mem.h" - -void free_token(token* tk) { - if (tk->var) - my_free(tk->var); -} - -void free_token_list(token_list* list) { - free_token(&list->elem); - if (list->rest) - free_token_list(list->rest); - my_free(list->rest); -} - -unsigned empty_args_list(arg_list* list) { - return !list; -} - -void cpy_expression(expression* dst, expression* src) { - free_expression(dst); - dst->kind = src->kind; - switch (dst->kind) { - case EXPR_INT: - dst->var1 = my_calloc(1, sizeof(int)); - *((int*) dst->var1) = *((int*) src->var1); - break; - case EXPR_NAME: - dst->var1 = my_calloc(1, strlen((char*) src->var1) + 1); - strcpy(dst->var1, src->var1); - break; - case EXPR_LIST: - if (!src->var1) - break; - case EXPR_TUPLE: - case EXPR_APP: - dst->var1 = my_calloc(1, sizeof(expression)); - dst->var2 = my_calloc(1, sizeof(expression)); - cpy_expression(dst->var1, src->var1); - cpy_expression(dst->var2, src->var2); - break; - } -} - -unsigned eq_expression(expression* a, expression* b) { - if (a->kind != b->kind) - return 0; - - switch (a->kind) { - case EXPR_INT: return *((int*) a->var1) == *((int*) b->var1); - case EXPR_NAME: return !strcmp(a->var1, b->var1); - case EXPR_TUPLE: - case EXPR_LIST: - case EXPR_APP: - if ((!a->var1 && b->var1) || (a->var1 && !b->var1) || - (!a->var2 && b->var2) || (a->var2 && b->var2)) - return 0; - if (a->var1 && !eq_expression(a->var1, b->var1)) - return 0; - if (a->var2 && !eq_expression(a->var2, b->var2)) - return 0; - return 1; - } - - return 0; -} - -expression** flatten_app_args(expression* from) { - unsigned char len = 0; - expression* _from = from; - while (_from->kind == EXPR_APP) { - len++; - _from = _from->var1; - } - len++; - - expression** result = my_calloc(1, sizeof(expression*) * (len + 1)); - unsigned int i = 1; - while (from->kind == EXPR_APP) { - result[len - i] = from->var2; - from = from->var1; - i++; - } - result[0] = from; - result[len] = NULL; - return result; -} - -void concat_fuspel(fuspel* start, fuspel* end) { - do { - if (!start->rest) { - start->rest = end; - return; - } - start = start->rest; - } while (start); -} - -fuspel* push_fuspel(fuspel* rules) { - fuspel* new_rules = my_calloc(1, sizeof(fuspel)); - new_rules->rest = rules; - return new_rules; -} - -fuspel* pop_fuspel(fuspel* rules) { - free_rewrite_rule(&rules->rule); - return rules->rest; -} - -fuspel* popn_fuspel(fuspel* rules, unsigned char n) { - while (n > 0) { - rules = pop_fuspel(rules); - n--; - } - return rules; -} - -void free_expression(expression* expr) { - if (!expr) - return; - - switch (expr->kind) { - case EXPR_INT: - case EXPR_NAME: - my_free(expr->var1); - break; - case EXPR_LIST: - case EXPR_TUPLE: - case EXPR_APP: - free_expression(expr->var1); - free_expression(expr->var2); - my_free(expr->var1); - my_free(expr->var2); - break; - } - - expr->var1 = expr->var2 = NULL; -} - -void free_arg_list(arg_list* list) { - free_expression(&list->elem); - if (list->rest) - free_arg_list(list->rest); - my_free(list->rest); -} - -void free_rewrite_rule(rewrite_rule* rule) { - my_free(rule->name); - if (rule->args) - free_arg_list(rule->args); - my_free(rule->args); - free_expression(&rule->rhs); -} - -void free_fuspel(fuspel* rules) { - free_rewrite_rule(&rules->rule); - if (rules->rest) - free_fuspel(rules->rest); - my_free(rules->rest); -} diff --git a/compiler/syntax.h b/compiler/syntax.h deleted file mode 100644 index f71786c..0000000 --- a/compiler/syntax.h +++ /dev/null @@ -1,80 +0,0 @@ -#ifndef _H_SYNTAX -#define _H_SYNTAX - -// TOKENS - -typedef enum { - TOKEN_SEMICOLON, // ; - TOKEN_EQUALS, // = - TOKEN_OPEN_SQ, // [ - TOKEN_CLOSE_SQ, // ] - TOKEN_OPEN_P, // ( - TOKEN_CLOSE_P, // ) - TOKEN_COMMA, // , - TOKEN_COLON, // : - TOKEN_NAME, - TOKEN_INT -} token_kind; - -typedef struct { - token_kind kind; - void* var; -} token; - -typedef struct token_list { - token elem; - struct token_list* rest; -} token_list; - -void free_token(token*); -void free_token_list(token_list*); - -// ELEMENTS - -typedef enum { - EXPR_INT, - EXPR_NAME, - EXPR_LIST, - EXPR_TUPLE, - EXPR_APP -} expr_kind; - -typedef struct { - expr_kind kind; - void* var1; - void* var2; -} expression; - -typedef struct arg_list { - expression elem; - struct arg_list* rest; -} arg_list; - -typedef struct { - char* name; - arg_list* args; - expression rhs; -} rewrite_rule; - -typedef struct fuspel { - rewrite_rule rule; - struct fuspel* rest; -} fuspel; - -unsigned empty_args_list(arg_list*); - -void cpy_expression(expression* dst, expression* src); -unsigned eq_expression(expression*, expression*); -expression** flatten_app_args(expression*); - -void concat_fuspel(fuspel* start, fuspel* end); -fuspel* push_fuspel(fuspel*); -fuspel* pop_fuspel(fuspel*); -fuspel* popn_fuspel(fuspel*, unsigned char); - -void free_expression(expression*); -void free_arg_list(arg_list*); -void free_rewrite_rule(rewrite_rule*); -void free_fuspel(fuspel*); - -#endif diff --git a/interpreter/.gitignore b/interpreter/.gitignore new file mode 100644 index 0000000..9148247 --- /dev/null +++ b/interpreter/.gitignore @@ -0,0 +1,2 @@ +*.o +fuspelc diff --git a/interpreter/Makefile b/interpreter/Makefile new file mode 100644 index 0000000..c8bfeb7 --- /dev/null +++ b/interpreter/Makefile @@ -0,0 +1,18 @@ +CFLAGS=-Wall -Wextra -Werror -Wpedantic -s + +DEPS=lex.h syntax.h print.h parse.h log.h eval.h mem.h +OBJ=fuspelc.o lex.o syntax.o print.o parse.o log.o eval.o mem.o +EXE=fuspelc + +.PHONY: all clean + +all: $(EXE) + +$(EXE): $(OBJ) + $(CC) -o $@ $^ $(CFLAGS) + +%.o: %.c $(DEPS) + $(CC) -c -o $@ $< $(CFLAGS) + +clean: + $(RM) -v $(OBJ) $(EXE) diff --git a/interpreter/eval.c b/interpreter/eval.c new file mode 100644 index 0000000..fb07e92 --- /dev/null +++ b/interpreter/eval.c @@ -0,0 +1,258 @@ +#include "eval.h" + +#include +#include + +#include "mem.h" +#include "print.h" + +void free_rules_until(fuspel* new, fuspel* old) { + while (new != old) { + fuspel* _new = new->rest; + free_rewrite_rule(&new->rule); + my_free(new); + new = _new; + } +} + +typedef struct replacements { + char* what; + expression* with; + struct replacements* rest; +} replacements; + +void replace(char* name, expression* new, expression* expr) { + if (!expr) + return; + + switch (expr->kind) { + case EXPR_NAME: + if (!strcmp(expr->var1, name)) { + cpy_expression(expr, new); + break; + } + case EXPR_INT: + break; + case EXPR_TUPLE: + case EXPR_LIST: + case EXPR_APP: + replace(name, new, expr->var1); + replace(name, new, expr->var2); + break; + } +} + +void replace_all(replacements* repls, expression* expr) { + while (repls) { + replace(repls->what, repls->with, expr); + repls = repls->rest; + } +} + +replacements* push_replacement(char* what, expression* with, replacements* rest) { + replacements* new = my_calloc(1, sizeof(replacements)); + new->what = what; + new->with = my_calloc(1, sizeof(expression)); + cpy_expression(new->with, with); + new->rest = rest; + return new; +} + +void free_replacements(replacements* repls) { + if (repls) { + free_replacements(repls->rest); + repls->rest = NULL; + free_expression(repls->with); + my_free(repls->with); + my_free(repls); + } +} + +unsigned match_expr(fuspel* rules, expression* to_match, expression* expr, + replacements** repls) { + unsigned matches; + + if (to_match->kind != EXPR_NAME) { + expr = eval_rnf(rules, expr); + if (!expr) + return 0; + } + + switch (to_match->kind) { + case EXPR_NAME: + *repls = push_replacement(to_match->var1, expr, *repls); + free_expression(expr); + my_free(expr); + return 1; + case EXPR_INT: + matches = eq_expression(to_match, expr); + free_expression(expr); + my_free(expr); + return matches; + case EXPR_LIST: + if (!to_match->var1) { + matches = eq_expression(to_match, expr); + free_expression(expr); + my_free(expr); + return matches; + } + case EXPR_TUPLE: + if (to_match->kind != expr->kind) { + free_expression(expr); + my_free(expr); + return 0; + } + matches = + match_expr(rules, to_match->var1, expr->var1, repls) && + match_expr(rules, to_match->var2, expr->var2, repls); + free_expression(expr); + my_free(expr); + return matches; + default: + free_expression(expr); + my_free(expr); + return 0; + } +} + +unsigned match_rule(fuspel* rules, rewrite_rule* rule, expression* expr, + replacements** repls) { + expression** expr_args; + unsigned char i; + + switch (expr->kind) { + case EXPR_NAME: + return (!strcmp(expr->var1, rule->name) && + empty_args_list(rule->args)) ? 1 : 0; + case EXPR_APP: + expr_args = flatten_app_args(expr); + i = 0; + if (!strcmp(expr_args[0]->var1, rule->name)) { + expression* _expr = expr_args[++i]; + arg_list* args = rule->args; + fuspel* _rules = rules; + while (!empty_args_list(args)) { + if (!match_expr(_rules, &args->elem, _expr, repls)) { + free_rules_until(_rules, rules); + my_free(expr_args); + return 0; + } + + args = args->rest; + _expr = expr_args[++i]; + + if (!empty_args_list(args) && !_expr) { + free_rules_until(_rules, rules); + my_free(expr_args); + return 0; + } + } + my_free(expr_args); + return 1; + } + my_free(expr_args); + default: + return 0; + } +} + +expression* eval_rnf(fuspel* rules, expression* expr) { + expression* result = my_calloc(1, sizeof(expression)); + + fuspel* _rules = rules; + + replacements** repls = my_calloc(1, sizeof(replacements*)); + + switch (expr->kind) { + case EXPR_INT: + case EXPR_TUPLE: + case EXPR_LIST: + cpy_expression(result, expr); + break; + + case EXPR_NAME: + case EXPR_APP: + while (_rules) { + if (match_rule(rules, &_rules->rule, expr, repls)) { + expression* old_result = result; + cpy_expression(result, &_rules->rule.rhs); + replace_all(*repls, result); + free_replacements(*repls); + my_free(repls); + result = eval_rnf(rules, old_result); + free_expression(old_result); + my_free(old_result); + return result; + } + free_replacements(*repls); + my_free(repls); + repls = my_calloc(1, sizeof(replacements*)); + _rules = _rules->rest; + } + cpy_expression(result, expr); + break; + } + + free_replacements(*repls); + my_free(repls); + + return result; +} + +expression* eval(fuspel* rules, expression* expr) { + expression *e1, *e2; + fuspel* _rules = rules; + expression* result = my_calloc(1, sizeof(expression)); + replacements** repls = my_calloc(1, sizeof(replacements*)); + + printf("Evaluating: "); + print_expression(expr); + printf("\n"); + + switch (expr->kind) { + case EXPR_INT: + cpy_expression(result, expr); + break; + + case EXPR_NAME: + case EXPR_APP: + while (_rules) { + if (match_rule(rules, &_rules->rule, expr, repls)) { + expression* old_result = result; + cpy_expression(result, &_rules->rule.rhs); + replace_all(*repls, result); + result = eval(rules, old_result); + free_expression(old_result); + my_free(old_result); + free_replacements(*repls); + my_free(repls); + return result; + } + free_replacements(*repls); + my_free(repls); + repls = my_calloc(1, sizeof(replacements*)); + _rules = _rules->rest; + } + cpy_expression(result, expr); + break; + + case EXPR_LIST: + if (!expr->var1) { + cpy_expression(result, expr); + break; + } + case EXPR_TUPLE: + e1 = eval(rules, expr->var1); + e2 = eval(rules, expr->var2); + + result->kind = expr->kind; + result->var1 = e1; + result->var2 = e2; + break; + } + + free_replacements(*repls); + my_free(repls); + + return result; +} diff --git a/interpreter/eval.h b/interpreter/eval.h new file mode 100644 index 0000000..3acd1d0 --- /dev/null +++ b/interpreter/eval.h @@ -0,0 +1,9 @@ +#ifndef _H_EVAL +#define _H_EVAL + +#include "syntax.h" + +expression* eval_rnf(fuspel*, expression*); +expression* eval(fuspel*, expression*); + +#endif diff --git a/interpreter/fuspelc.c b/interpreter/fuspelc.c new file mode 100644 index 0000000..5edb48c --- /dev/null +++ b/interpreter/fuspelc.c @@ -0,0 +1,64 @@ +#include +#include + +#include "eval.h" +#include "lex.h" +#include "mem.h" +#include "parse.h" +#include "print.h" + +int main(void) { + token_list* tokens; + fuspel* pgm; + expression to_eval, *evaled; + + tokens = NULL; + + while (!feof(stdin)) { + char program[79]; + if (!fgets(program, 79, stdin)) { + if (feof(stdin)) + break; + fprintf(stderr, "Couldn't read input."); + exit(EXIT_FAILURE); + } + + tokens = lex(tokens, program); + if (!tokens) { + fprintf(stderr, "Couldn't lex program."); + exit(EXIT_FAILURE); + } + } + + pgm = parse(tokens); + free_token_list(tokens); + free(tokens); + + if (!pgm) { + fprintf(stderr, "Couldn't parse program."); + exit(EXIT_FAILURE); + } + + printf("\nParsed program:\n"); + print_fuspel(pgm); + printf("\n\n\n"); + + to_eval.kind = EXPR_NAME; + to_eval.var1 = my_calloc(1, 5); + strcpy(to_eval.var1, "main"); + + evaled = eval(pgm, &to_eval); + free_expression(&to_eval); + if (evaled) { + print_expression(evaled); + printf("\n"); + + free_expression(evaled); + free(evaled); + } + + free_fuspel(pgm); + free(pgm); + + return 0; +} diff --git a/interpreter/lex.c b/interpreter/lex.c new file mode 100644 index 0000000..b238b5e --- /dev/null +++ b/interpreter/lex.c @@ -0,0 +1,101 @@ +#include "lex.h" + +#include + +#include "mem.h" + +inline unsigned is_space_char(char input) { + return input == '\t' || input == ' ' || input == '\n' || input == '\r'; +} + +inline unsigned is_int_char(char input) { + return '0' <= input && input <= '9'; +} + +/* The number of bytes that should be read to read an integer */ +unsigned char lex_int_length(char* input) { + unsigned char n = 0; + while (is_int_char(*input++)) n++; + return n; +} + +inline unsigned is_name_char(char input) { + return (('A' <= input && input <= 'Z') || + ('a' <= input && input <= 'z') || + input == '_'); +} + +/* The number of bytes that should be read to read a name */ +unsigned char lex_name_length(char* input) { + unsigned char n = 0; + while (is_name_char(*input++)) n++; + return n; +} + +token_list* lex(token_list* list, char* input) { + token_list* first_list; + + if (input[0] == 0) { + return NULL; + } + + if (list) { + first_list = list; + while (list->rest) list = list->rest; + list->rest = my_calloc(1, sizeof(token_list)); + list = list->rest; + } else { + first_list = list = my_calloc(1, sizeof(token_list)); + } + + while (*input) { + unsigned proceed_to_next_token = 1; + + list->elem.var = NULL; + + switch (*input) { + case ';': list->elem.kind = TOKEN_SEMICOLON; break; + case ':': list->elem.kind = TOKEN_COLON; break; + case '(': list->elem.kind = TOKEN_OPEN_P; break; + case ')': list->elem.kind = TOKEN_CLOSE_P; break; + case '[': list->elem.kind = TOKEN_OPEN_SQ; break; + case ']': list->elem.kind = TOKEN_CLOSE_SQ; break; + case '=': list->elem.kind = TOKEN_EQUALS; break; + case ',': list->elem.kind = TOKEN_COMMA; break; + + default: + if (is_int_char(*input)) { + char* s; + unsigned char len = lex_int_length(input); + s = my_calloc(1, len + 1); + list->elem.kind = TOKEN_INT; + list->elem.var = my_calloc(1, sizeof(int)); + strncpy(s, input, len); + *((int*) list->elem.var) = atoi(s); + my_free(s); + input += len - 1; + } else if (is_name_char(*input)) { + unsigned char len = lex_name_length(input); + list->elem.kind = TOKEN_NAME; + list->elem.var = my_calloc(1, len + 1); + strncpy(list->elem.var, input, len); + input += len - 1; + } else if (is_space_char(*input)) { + proceed_to_next_token = 0; + } else { + free_token_list(first_list); + my_free(first_list); + return NULL; + } + } + + input++; + + if (*input && proceed_to_next_token) { + list->rest = my_calloc(1, sizeof(token_list)); + list = list->rest; + } + } + + return first_list; +} diff --git a/interpreter/lex.h b/interpreter/lex.h new file mode 100644 index 0000000..268d0e4 --- /dev/null +++ b/interpreter/lex.h @@ -0,0 +1,8 @@ +#ifndef _H_LEX +#define _H_LEX + +#include "syntax.h" + +token_list* lex(token_list*, char*); + +#endif diff --git a/interpreter/log.c b/interpreter/log.c new file mode 100644 index 0000000..c369b4b --- /dev/null +++ b/interpreter/log.c @@ -0,0 +1,9 @@ +#include "log.h" + +#include + +#if(LOG_LEVEL < LOG_DEBUG) +void log_debug(char* msg) { + fprintf(stdout, "%s\n", msg); +} +#endif diff --git a/interpreter/log.h b/interpreter/log.h new file mode 100644 index 0000000..7d4e406 --- /dev/null +++ b/interpreter/log.h @@ -0,0 +1,14 @@ +#ifndef _H_LOG +#define _H_LOG + +#define LOG_DEBUG 1 + +#define LOG_LEVEL 10 + +#if(LOG_LEVEL >= LOG_DEBUG) +#define log_debug(x) +#else +void log_debug(char*); +#endif + +#endif diff --git a/interpreter/mem.c b/interpreter/mem.c new file mode 100644 index 0000000..7affd71 --- /dev/null +++ b/interpreter/mem.c @@ -0,0 +1,16 @@ +#include "mem.h" + +#include + +void* my_calloc(size_t num, size_t size) { + void* ptr = calloc(num, size); + if (!ptr) { + perror(NULL); + exit(EXIT_FAILURE); + } + return ptr; +} + +void my_free(void* ptr) { + free(ptr); +} diff --git a/interpreter/mem.h b/interpreter/mem.h new file mode 100644 index 0000000..0399cef --- /dev/null +++ b/interpreter/mem.h @@ -0,0 +1,9 @@ +#ifndef _H_MEM +#define _H_MEM + +#include + +void* my_calloc(size_t num, size_t size); +void my_free(void* ptr); + +#endif diff --git a/interpreter/parse.c b/interpreter/parse.c new file mode 100644 index 0000000..a9fc345 --- /dev/null +++ b/interpreter/parse.c @@ -0,0 +1,251 @@ +#include "parse.h" + +#include + +#include "log.h" +#include "mem.h" + +token_list* parse_name(char** name, token_list* list) { + if (list->elem.kind != TOKEN_NAME) + return NULL; + + *name = my_calloc(1, strlen(list->elem.var) + 1); + + strcpy(*name, list->elem.var); + + return list->rest; +} + +token_list* parse_simple_expression(expression* expr, token_list* list) { + expression* _expr; + switch (list->elem.kind) { + case TOKEN_INT: + expr->kind = EXPR_INT; + expr->var1 = my_calloc(1, sizeof(int)); + *((int*) expr->var1) = *((int*) list->elem.var); + return list->rest; + + case TOKEN_NAME: + expr->kind = EXPR_NAME; + list = parse_name((char**) &expr->var1, list); + return list; + + case TOKEN_OPEN_P: + list = parse_simple_expression(expr, list->rest); + if (!list) + return NULL; + + switch (list->elem.kind) { + case TOKEN_CLOSE_P: + return list->rest; + break; + case TOKEN_COMMA: + _expr = my_calloc(1, sizeof(expression)); + cpy_expression(_expr, expr); + free_expression(expr); + expr->kind = EXPR_TUPLE; + expr->var1 = _expr; + expr->var2 = my_calloc(1, sizeof(expression)); + list = parse_simple_expression(expr->var2, list->rest); + if (!list || list->elem.kind != TOKEN_CLOSE_P) { + free_expression(_expr); + my_free(_expr); + return NULL; + } else { + return list->rest; + } + break; + default: + return NULL; + } + break; + + case TOKEN_OPEN_SQ: + expr->kind = EXPR_LIST; + list = list->rest; + if (!list) + return NULL; + + if (list->elem.kind == TOKEN_CLOSE_SQ) + return list->rest; + + expr->var1 = my_calloc(1, sizeof(expression)); + expr->var2 = my_calloc(1, sizeof(expression)); + + list = parse_simple_expression(expr->var1, list); + + if (!list || list->elem.kind != TOKEN_COLON) { + free_expression(expr->var1); + return NULL; + } + + list = parse_simple_expression(expr->var2, list->rest); + + if (!list || list->elem.kind != TOKEN_CLOSE_SQ) { + free_expression(expr->var1); + my_free(expr->var1); + free_expression(expr->var2); + my_free(expr->var2); + return NULL; + } + + return list->rest; + + break; + + default: + return NULL; + } +} + +token_list* parse_arg_list(arg_list** args, token_list* list) { + if (list->elem.kind == TOKEN_EQUALS) + return list; + + *args = my_calloc(1, sizeof(arg_list)); + + list = parse_simple_expression(&(*args)->elem, list); + if (!list) + return NULL; + + list = parse_arg_list(&(*args)->rest, list); + + return list; +} + +token_list* parse_expression(expression*, token_list*); + +token_list* parse_expression_no_app(expression* expr, token_list* list) { + if (list->elem.kind == TOKEN_OPEN_P) { + token_list* _list = parse_expression(expr, list->rest); + if (_list) { + if (_list->elem.kind == TOKEN_CLOSE_P) { + return _list->rest; + } else if (_list->elem.kind == TOKEN_COMMA) { + expression* _expr = my_calloc(1, sizeof(expression)); + + cpy_expression(_expr, expr); + free_expression(expr); + expr->kind = EXPR_TUPLE; + expr->var1 = _expr; + + expr->var2 = my_calloc(1, sizeof(expression)); + + _list = parse_expression(expr->var2, _list->rest); + if (_list && _list->elem.kind == TOKEN_CLOSE_P) { + return _list->rest; + } + } + free_expression(expr); + } + } else if (list->elem.kind == TOKEN_OPEN_SQ) { + expression *expr1, *expr2; + token_list* _list; + + expr->kind = EXPR_LIST; + + if (list->rest->elem.kind == TOKEN_CLOSE_SQ) { + return list->rest->rest; + } + + expr1 = my_calloc(1, sizeof(expression)); + expr2 = my_calloc(1, sizeof(expression)); + + _list = parse_expression(expr1, list->rest); + if (!_list || _list->elem.kind != TOKEN_COLON) { + free_expression(expr1); + my_free(expr1); + my_free(expr2); + } else { + _list = parse_expression(expr2, _list->rest); + if (!_list || _list->elem.kind != TOKEN_CLOSE_SQ) { + free_expression(expr1); + free_expression(expr2); + my_free(expr1); + my_free(expr2); + } else { + expr->var1 = expr1; + expr->var2 = expr2; + return _list->rest; + } + } + } + + list = parse_simple_expression(expr, list); + + return list; +} + +token_list* parse_expression(expression* expr, token_list* list) { + list = parse_expression_no_app(expr, list); + if (!list) + return NULL; + + while (list->elem.kind != TOKEN_SEMICOLON && + list->elem.kind != TOKEN_CLOSE_P && + list->elem.kind != TOKEN_CLOSE_SQ && + list->elem.kind != TOKEN_COLON && + list->elem.kind != TOKEN_COMMA) { + + expression* _expr = my_calloc(1, sizeof(expression)); + + cpy_expression(_expr, expr); + free_expression(expr); + expr->kind = EXPR_APP; + expr->var1 = _expr; + + expr->var2 = my_calloc(1, sizeof(expression)); + + list = parse_expression_no_app(expr->var2, list); + if (!list) { + free_expression(expr); + return NULL; + } + } + + return list; +} + +token_list* parse_rule(rewrite_rule* rule, token_list* list) { + list = parse_name(&rule->name, list); + if (!list) + return NULL; + + list = parse_arg_list(&rule->args, list); + if (!list) { + log_debug("parse_rule: error in arg_list"); + my_free(rule->name); + return NULL; + } + + if (list->elem.kind != TOKEN_EQUALS) { + log_debug("parse_rule: no ="); + my_free(rule->name); + free_arg_list(rule->args); + return NULL; + } + + list = parse_expression(&rule->rhs, list->rest); + + return list; +} + +fuspel* parse(token_list* list) { + fuspel* rules; + + while (list && list->elem.kind == TOKEN_SEMICOLON) + list = list->rest; + + if (!list) + return NULL; + + rules = my_calloc(1, sizeof(fuspel)); + + list = parse_rule(&rules->rule, list); + if (!list) + return NULL; + + rules->rest = parse(list); + + return rules; +} diff --git a/interpreter/parse.h b/interpreter/parse.h new file mode 100644 index 0000000..39f74e0 --- /dev/null +++ b/interpreter/parse.h @@ -0,0 +1,8 @@ +#ifndef _H_PARSE +#define _H_PARSE + +#include "syntax.h" + +fuspel* parse(token_list*); + +#endif diff --git a/interpreter/print.c b/interpreter/print.c new file mode 100644 index 0000000..a71e71f --- /dev/null +++ b/interpreter/print.c @@ -0,0 +1,102 @@ +#include "print.h" + +#include + +#include "log.h" + +void print_token(token* tk) { + char c; + switch (tk->kind) { + case TOKEN_SEMICOLON: c = ';'; break; + case TOKEN_COLON: c = ':'; break; + case TOKEN_OPEN_P: c = '('; break; + case TOKEN_CLOSE_P: c = ')'; break; + case TOKEN_OPEN_SQ: c = '['; break; + case TOKEN_CLOSE_SQ: c = ']'; break; + case TOKEN_EQUALS: c = '='; break; + case TOKEN_COMMA: c = ','; break; + case TOKEN_NAME: + printf("%s", (char*) tk->var); + return; + case TOKEN_INT: + printf("%d", *((int*) tk->var)); + return; + } + printf("%c", c); +} + +void print_token_list(token_list* list) { + print_token(&list->elem); + if (list->rest) { + printf(list->elem.kind == TOKEN_SEMICOLON ? "\n" : " "); + print_token_list(list->rest); + } +} + +void print_expression(expression* expr) { + switch (expr->kind) { + case EXPR_INT: + printf("%d", *((int*) expr->var1)); + break; + case EXPR_NAME: + printf("%s", (char*) expr->var1); + break; + case EXPR_LIST: + if (!expr->var1) { + printf("[]"); + } else { + printf("["); + print_expression(expr->var1); + printf(":"); + print_expression(expr->var2); + printf("]"); + } + break; + case EXPR_TUPLE: + printf("("); + print_expression(expr->var1); + printf(","); + print_expression(expr->var2); + printf(")"); + break; + case EXPR_APP: + if (((expression*) expr->var1)->kind == EXPR_APP) + printf("("); + print_expression(expr->var1); + if (((expression*) expr->var1)->kind == EXPR_APP) + printf(")"); + printf(" "); + if (((expression*) expr->var2)->kind == EXPR_APP) + printf("("); + print_expression(expr->var2); + if (((expression*) expr->var2)->kind == EXPR_APP) + printf(")"); + break; + } +} + +void print_arg_list(arg_list* args) { + if (!args) + return; + + print_expression(&args->elem); + printf(" "); + if (args->rest) + print_arg_list(args->rest); +} + +void print_rewrite_rule(rewrite_rule* rule) { + printf("%s ", rule->name); + print_arg_list(rule->args); + printf("= "); + print_expression(&rule->rhs); + printf(";"); +} + +void print_fuspel(fuspel* rules) { + print_rewrite_rule(&rules->rule); + if (rules->rest) { + printf("\n"); + print_fuspel(rules->rest); + } +} diff --git a/interpreter/print.h b/interpreter/print.h new file mode 100644 index 0000000..5909087 --- /dev/null +++ b/interpreter/print.h @@ -0,0 +1,13 @@ +#ifndef _H_PRINT +#define _H_PRINT + +#include "syntax.h" + +void print_token(token*); +void print_token_list(token_list*); + +void print_expression(expression*); +void print_rewrite_rule(rewrite_rule*); +void print_fuspel(fuspel*); + +#endif diff --git a/interpreter/syntax.c b/interpreter/syntax.c new file mode 100644 index 0000000..4eb845a --- /dev/null +++ b/interpreter/syntax.c @@ -0,0 +1,166 @@ +#include "syntax.h" + +#include + +#include "mem.h" + +void free_token(token* tk) { + if (tk->var) + my_free(tk->var); +} + +void free_token_list(token_list* list) { + free_token(&list->elem); + if (list->rest) + free_token_list(list->rest); + my_free(list->rest); +} + +unsigned empty_args_list(arg_list* list) { + return !list; +} + +void cpy_expression(expression* dst, expression* src) { + free_expression(dst); + dst->kind = src->kind; + switch (dst->kind) { + case EXPR_INT: + dst->var1 = my_calloc(1, sizeof(int)); + *((int*) dst->var1) = *((int*) src->var1); + break; + case EXPR_NAME: + dst->var1 = my_calloc(1, strlen((char*) src->var1) + 1); + strcpy(dst->var1, src->var1); + break; + case EXPR_LIST: + if (!src->var1) + break; + case EXPR_TUPLE: + case EXPR_APP: + dst->var1 = my_calloc(1, sizeof(expression)); + dst->var2 = my_calloc(1, sizeof(expression)); + cpy_expression(dst->var1, src->var1); + cpy_expression(dst->var2, src->var2); + break; + } +} + +unsigned eq_expression(expression* a, expression* b) { + if (a->kind != b->kind) + return 0; + + switch (a->kind) { + case EXPR_INT: return *((int*) a->var1) == *((int*) b->var1); + case EXPR_NAME: return !strcmp(a->var1, b->var1); + case EXPR_TUPLE: + case EXPR_LIST: + case EXPR_APP: + if ((!a->var1 && b->var1) || (a->var1 && !b->var1) || + (!a->var2 && b->var2) || (a->var2 && b->var2)) + return 0; + if (a->var1 && !eq_expression(a->var1, b->var1)) + return 0; + if (a->var2 && !eq_expression(a->var2, b->var2)) + return 0; + return 1; + } + + return 0; +} + +expression** flatten_app_args(expression* from) { + expression** result; + unsigned int i; + + unsigned char len = 0; + expression* _from = from; + while (_from->kind == EXPR_APP) { + len++; + _from = _from->var1; + } + len++; + + result = my_calloc(1, sizeof(expression*) * (len + 1)); + i = 1; + while (from->kind == EXPR_APP) { + result[len - i] = from->var2; + from = from->var1; + i++; + } + result[0] = from; + result[len] = NULL; + return result; +} + +void concat_fuspel(fuspel* start, fuspel* end) { + do { + if (!start->rest) { + start->rest = end; + return; + } + start = start->rest; + } while (start); +} + +fuspel* push_fuspel(fuspel* rules) { + fuspel* new_rules = my_calloc(1, sizeof(fuspel)); + new_rules->rest = rules; + return new_rules; +} + +fuspel* pop_fuspel(fuspel* rules) { + free_rewrite_rule(&rules->rule); + return rules->rest; +} + +fuspel* popn_fuspel(fuspel* rules, unsigned char n) { + while (n > 0) { + rules = pop_fuspel(rules); + n--; + } + return rules; +} + +void free_expression(expression* expr) { + if (!expr) + return; + + switch (expr->kind) { + case EXPR_INT: + case EXPR_NAME: + my_free(expr->var1); + break; + case EXPR_LIST: + case EXPR_TUPLE: + case EXPR_APP: + free_expression(expr->var1); + free_expression(expr->var2); + my_free(expr->var1); + my_free(expr->var2); + break; + } + + expr->var1 = expr->var2 = NULL; +} + +void free_arg_list(arg_list* list) { + free_expression(&list->elem); + if (list->rest) + free_arg_list(list->rest); + my_free(list->rest); +} + +void free_rewrite_rule(rewrite_rule* rule) { + my_free(rule->name); + if (rule->args) + free_arg_list(rule->args); + my_free(rule->args); + free_expression(&rule->rhs); +} + +void free_fuspel(fuspel* rules) { + free_rewrite_rule(&rules->rule); + if (rules->rest) + free_fuspel(rules->rest); + my_free(rules->rest); +} diff --git a/interpreter/syntax.h b/interpreter/syntax.h new file mode 100644 index 0000000..05f09c7 --- /dev/null +++ b/interpreter/syntax.h @@ -0,0 +1,80 @@ +#ifndef _H_SYNTAX +#define _H_SYNTAX + +/* TOKENS */ + +typedef enum { + TOKEN_SEMICOLON, /* ; */ + TOKEN_EQUALS, /* = */ + TOKEN_OPEN_SQ, /* [ */ + TOKEN_CLOSE_SQ, /* ] */ + TOKEN_OPEN_P, /* ( */ + TOKEN_CLOSE_P, /* ) */ + TOKEN_COMMA, /* , */ + TOKEN_COLON, /* : */ + TOKEN_NAME, + TOKEN_INT +} token_kind; + +typedef struct { + token_kind kind; + void* var; +} token; + +typedef struct token_list { + token elem; + struct token_list* rest; +} token_list; + +void free_token(token*); +void free_token_list(token_list*); + +/* ELEMENTS */ + +typedef enum { + EXPR_INT, + EXPR_NAME, + EXPR_LIST, + EXPR_TUPLE, + EXPR_APP +} expr_kind; + +typedef struct { + expr_kind kind; + void* var1; + void* var2; +} expression; + +typedef struct arg_list { + expression elem; + struct arg_list* rest; +} arg_list; + +typedef struct { + char* name; + arg_list* args; + expression rhs; +} rewrite_rule; + +typedef struct fuspel { + rewrite_rule rule; + struct fuspel* rest; +} fuspel; + +unsigned empty_args_list(arg_list*); + +void cpy_expression(expression* dst, expression* src); +unsigned eq_expression(expression*, expression*); +expression** flatten_app_args(expression*); + +void concat_fuspel(fuspel* start, fuspel* end); +fuspel* push_fuspel(fuspel*); +fuspel* pop_fuspel(fuspel*); +fuspel* popn_fuspel(fuspel*, unsigned char); + +void free_expression(expression*); +void free_arg_list(arg_list*); +void free_rewrite_rule(rewrite_rule*); +void free_fuspel(fuspel*); + +#endif -- cgit v1.2.3