aboutsummaryrefslogtreecommitdiff
path: root/interpreter
diff options
context:
space:
mode:
Diffstat (limited to 'interpreter')
-rw-r--r--interpreter/.gitignore2
-rw-r--r--interpreter/Makefile18
-rw-r--r--interpreter/eval.c258
-rw-r--r--interpreter/eval.h9
-rw-r--r--interpreter/fuspelc.c64
-rw-r--r--interpreter/lex.c101
-rw-r--r--interpreter/lex.h8
-rw-r--r--interpreter/log.c9
-rw-r--r--interpreter/log.h14
-rw-r--r--interpreter/mem.c16
-rw-r--r--interpreter/mem.h9
-rw-r--r--interpreter/parse.c251
-rw-r--r--interpreter/parse.h8
-rw-r--r--interpreter/print.c102
-rw-r--r--interpreter/print.h13
-rw-r--r--interpreter/syntax.c166
-rw-r--r--interpreter/syntax.h80
17 files changed, 1128 insertions, 0 deletions
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 <stdio.h>
+#include <string.h>
+
+#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 <stdio.h>
+#include <string.h>
+
+#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 <string.h>
+
+#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 <stdio.h>
+
+#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 <stdio.h>
+
+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 <stdlib.h>
+
+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 <string.h>
+
+#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 <stdio.h>
+
+#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 <string.h>
+
+#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
generated by cgit v1.2.3 (git 2.39.1) at 2025-03-13 15:41:42 +0000