Initial commit

21 files changed, 1079 insertions, 0 deletions

diff --git a/README.md b/README.md
new file mode 100644
index 0000000..186b5c1
--- /dev/null
+++ b/README.md
@@ -0,0 +1,5 @@
+# fuspel
+
+Functional Simple Programming Language.
+
+Copyright © 2016 Camil Staps.
diff --git a/compiler/.gitignore b/compiler/.gitignore
new file mode 100644
index 0000000..9148247
--- /dev/null
+++ b/compiler/.gitignore
@@ -0,0 +1,2 @@
+*.o
+fuspelc
diff --git a/compiler/Makefile b/compiler/Makefile
new file mode 100644
index 0000000..f44d5e4
--- /dev/null
+++ b/compiler/Makefile
@@ -0,0 +1,18 @@
+CFLAGS=-g
+
+DEPS=lex.h syntax.h error.h print.h parse.h log.h eval.h
+OBJ=fuspelc.o lex.o syntax.o error.o print.o parse.o log.o eval.o
+EXE=fuspelc
+
+all: $(EXE)
+
+$(EXE): $(OBJ)
+	gcc -o $@ $^ $(CFLAGS)
+
+%.o: %.c $(DEPS)
+	$(CC) -c -o $@ $< $(CFLAGS)
+
+clean:
+	$(RM) -v $(OBJ) $(EXE)
+
+.PHONY: all clean
diff --git a/compiler/error.c b/compiler/error.c
new file mode 100644
index 0000000..7d70f60
--- /dev/null
+++ b/compiler/error.c
@@ -0,0 +1,16 @@
+#include "error.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+
+void error(int code, char* message) {
+	if (message) {
+		fprintf(stderr, "%s\n", message);
+	}
+
+	exit(code);
+}
+
+void error_no_mem(void) {
+	error(ERROR_NO_MEMORY, "No memory");
+}
diff --git a/compiler/error.h b/compiler/error.h
new file mode 100644
index 0000000..872afd7
--- /dev/null
+++ b/compiler/error.h
@@ -0,0 +1,9 @@
+#ifndef _H_ERROR
+#define _H_ERROR
+
+void error(int code, char* message);
+void error_no_mem(void);
+
+#define ERROR_NO_MEMORY 10
+
+#endif
diff --git a/compiler/eval.c b/compiler/eval.c
new file mode 100644
index 0000000..f4bdb70
--- /dev/null
+++ b/compiler/eval.c
@@ -0,0 +1,137 @@
+#include "eval.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "error.h"
+
+void free_rules_until(fuspel* new, fuspel* old) {
+	while (new != old) {
+		free_rewrite_rule(&new->rule);
+		new = new->rest;
+	}
+}
+
+fuspel* match_expr(fuspel* rules, expression* to_match, expression* expr) {
+	switch (to_match->kind) {
+		case EXPR_NAME:
+			rules = push_fuspel(rules);
+			rules->rule.name = malloc(strlen(to_match->var1) + 1);
+			if (!rules->rule.name)
+				error_no_mem();
+			strcpy(rules->rule.name, to_match->var1);
+			rules->rule.args = NULL;
+			cpy_expression(&rules->rule.rhs, expr);
+			return rules;
+		case EXPR_INT:
+			return eq_expression(to_match, expr) ? rules : NULL;
+		case EXPR_TUPLE:
+			;fuspel* _rules = match_expr(rules, to_match->var1, expr->var1);
+			if (!_rules)
+				return NULL;
+			fuspel* __rules = match_expr(_rules, to_match->var2, expr->var2);
+			if (!__rules)
+				free_rules_until(_rules, rules);
+			return __rules;
+		default:
+			// TODO
+			return NULL;
+	}
+}
+
+fuspel* match_rule(fuspel* rules, rewrite_rule* rule, expression* expr) {
+	switch (expr->kind) {
+		case EXPR_NAME:
+			return (!strcmp(expr->var1, rule->name) &&
+				empty_args_list(rule->args)) ? rules : NULL;
+		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)) {
+					fuspel* __rules = match_expr(_rules, &args->elem, _expr);
+					if (!__rules) {
+						free_rules_until(_rules, rules);
+						free(expr_args);
+						return NULL;
+					}
+					_rules = __rules;
+
+					args = args->rest;
+					_expr = expr_args[++i];
+
+					if (!empty_args_list(args) && !_expr) {
+						free_rules_until(_rules, rules);
+						return NULL;
+					}
+				}
+				free(expr_args);
+				return _rules;
+			}
+		default:
+			return NULL;
+	}
+}
+
+unsigned apply(expression* result, rewrite_rule* rule, expression* expr) {
+	switch (expr->kind) {
+		case EXPR_NAME:
+			cpy_expression(result, &rule->rhs);
+			return 1;
+			break;
+		case EXPR_APP:
+			// TODO
+		default:
+			return 0;
+	}
+}
+
+expression* eval(fuspel* rules, expression* expr) {
+	expression* result = calloc(1, sizeof(expression));
+	if (!result)
+		error_no_mem();
+
+	expression *e1, *e2;
+	fuspel* _rules = rules;
+	fuspel* new_rules;
+
+	switch (expr->kind) {
+		case EXPR_INT:
+			cpy_expression(result, expr);
+			break;
+
+		case EXPR_NAME:
+		case EXPR_APP:
+			while (_rules) {
+				new_rules = match_rule(rules, &_rules->rule, expr);
+				if (new_rules) {
+					rules = new_rules;
+					result = eval(rules, &_rules->rule.rhs);
+					break;
+				}
+				_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;
+	}
+
+	return result;
+}
diff --git a/compiler/eval.h b/compiler/eval.h
new file mode 100644
index 0000000..bf3eea8
--- /dev/null
+++ b/compiler/eval.h
@@ -0,0 +1,8 @@
+#ifndef _H_EVAL
+#define _H_EVAL
+
+#include "syntax.h"
+
+expression* eval(fuspel*, expression*);
+
+#endif
diff --git a/compiler/fuspelc.c b/compiler/fuspelc.c
new file mode 100644
index 0000000..38e4a99
--- /dev/null
+++ b/compiler/fuspelc.c
@@ -0,0 +1,64 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "error.h"
+#include "lex.h"
+#include "parse.h"
+#include "eval.h"
+#include "print.h"
+
+static char* program =
+	"singleton x = [x:[]];"
+	"push x y = [x:y];"
+	"is_zero 0 = 1;"
+	"is_zero _ = 0;"
+	"flip (a,b) = (b,a);"
+	"main = push 3 (singleton (flip (is_zero 5, is_zero 0)));";
+//static char* program =
+//	"trip x y z = (x,(y,z));"
+//	"main       = trip (trip 1 2 3) 10 (trip a b c);";
+//static char* program =
+//	"return   = (n,1);"
+//	"main     = return;";
+
+int main(void) {
+	token_list* tokens = lex(program);
+	
+	if (!tokens)
+		error(10, "Couldn't lex program.");
+	
+	printf("\n\nLexed program:\n");
+	print_token_list(tokens);
+	printf("\n");
+	
+	fuspel* pgm = parse(tokens);
+	free_token_list(tokens);
+	free(tokens);
+	
+	if (!pgm)
+		error(10, "Couldn't parse program.");
+
+	printf("\nParsed program:\n");
+	print_fuspel(pgm);
+	printf("\n\n\n");
+
+	expression to_eval, *evaled;
+
+	to_eval.kind = EXPR_NAME;
+	to_eval.var1 = malloc(5);
+	if (!to_eval.var1)
+		error_no_mem();
+	strcpy(to_eval.var1, "main");
+
+	evaled = eval(pgm, &to_eval);
+	if (evaled) {
+		print_expression(evaled);
+		printf("\n");
+
+		free_expression(evaled);
+		free(evaled);
+	}
+
+	return 0;
+}
diff --git a/compiler/lex.c b/compiler/lex.c
new file mode 100644
index 0000000..5f42e37
--- /dev/null
+++ b/compiler/lex.c
@@ -0,0 +1,102 @@
+#include "lex.h"
+
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "error.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(char* input) {
+	if (input[0] == 0) {
+		return NULL;
+	}
+	
+	token_list* list = malloc(sizeof(token_list));
+	if (!list)
+		error_no_mem();
+	token_list* first_list = 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 = malloc(len);
+					list->elem.var = calloc(1, sizeof(int));
+					if (!s || !list->elem.var)
+						error_no_mem();
+					strncpy(s, input, len);
+					*((int*) list->elem.var) = atoi(s);
+					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 = calloc(1, len + 1);
+					if (!list->elem.var)
+						error_no_mem();
+					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);
+					free(first_list);
+					return NULL;
+				}
+		}
+
+		input++;
+
+		if (*input && proceed_to_next_token) {
+			list->rest = malloc(sizeof(token_list));
+			if (!list->rest)
+				error_no_mem();
+			list = list->rest;
+		}
+	}
+
+	return first_list;
+}
diff --git a/compiler/lex.h b/compiler/lex.h
new file mode 100644
index 0000000..61a7170
--- /dev/null
+++ b/compiler/lex.h
@@ -0,0 +1,8 @@
+#ifndef _H_LEX
+#define _H_LEX
+
+#include "syntax.h"
+
+token_list* lex(char*);
+
+#endif
diff --git a/compiler/log.c b/compiler/log.c
new file mode 100644
index 0000000..9362019
--- /dev/null
+++ b/compiler/log.c
@@ -0,0 +1,9 @@
+#include "log.h"
+
+#include <stdio.h>
+
+void log_debug(char* msg) {
+	#if(LOG_LEVEL < LOG_DEBUG)
+	fprintf(stdout, "%s\n", msg);
+	#endif
+}
diff --git a/compiler/log.h b/compiler/log.h
new file mode 100644
index 0000000..fcfbffe
--- /dev/null
+++ b/compiler/log.h
@@ -0,0 +1,10 @@
+#ifndef _H_LOG
+#define _H_LOG
+
+#define LOG_DEBUG 1
+
+#define LOG_LEVEL 0
+
+void log_debug(char*);
+
+#endif
diff --git a/compiler/parse.c b/compiler/parse.c
new file mode 100644
index 0000000..a8c4b37
--- /dev/null
+++ b/compiler/parse.c
@@ -0,0 +1,263 @@
+#include "parse.h"
+
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+
+token_list* parse_name(char** name, token_list* list) {
+	if (list->elem.kind != TOKEN_NAME)
+		return NULL;
+
+	*name = calloc(1, strlen(list->elem.var) + 1);
+	if (!*name)
+		error_no_mem();
+
+	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 = calloc(1, sizeof(int));
+			if(!expr->var1)
+				error_no_mem();
+			*((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 = calloc(1, sizeof(expression));
+					if (!_expr)
+						error_no_mem();
+					cpy_expression(_expr, expr);
+					expr->kind = EXPR_TUPLE;
+					expr->var1 = _expr;
+					expr->var2 = calloc(1, sizeof(expression));
+					if (!expr->var2)
+						error_no_mem();
+					list = parse_simple_expression(expr->var2, list->rest);
+					if (!list || list->elem.kind != TOKEN_CLOSE_P) {
+						free_expression(_expr);
+						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 = calloc(1, sizeof(expression));
+			expr->var2 = calloc(1, sizeof(expression));
+			if (!expr->var1 || !expr->var2)
+				error_no_mem();
+
+			list = parse_simple_expression(expr->var1, list);
+
+			if (!list || list->elem.kind != TOKEN_COLON) {
+				free_expression(expr->var1);
+				free(expr->var1);
+				return NULL;
+			}
+			
+			list = parse_simple_expression(expr->var2, list->rest);
+				
+			if (!list || list->elem.kind != TOKEN_CLOSE_SQ) {
+				free_expression(expr->var1);
+				free(expr->var1);
+				free_expression(expr->var2);
+				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 = calloc(1, sizeof(arg_list));
+	if (!*args)
+		error_no_mem();
+
+	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 = calloc(1, sizeof(expression));
+				if (!_expr)
+					error_no_mem();
+
+				cpy_expression(_expr, expr);
+				expr->kind = EXPR_TUPLE;
+				expr->var1 = _expr;
+
+				expr->var2 = calloc(1, sizeof(expression));
+				if (!expr->var2)
+					error_no_mem();
+
+				_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 = calloc(1, sizeof(expression));
+		expression* expr2 = calloc(1, sizeof(expression));
+		if (!expr1 || !expr2)
+			error_no_mem();
+
+		token_list* _list = parse_expression(expr1, list->rest);
+		if (!_list || _list->elem.kind != TOKEN_COLON) {
+			free(expr1);
+		} else {
+			_list = parse_expression(expr2, _list->rest);
+			if (!_list || _list->elem.kind != TOKEN_CLOSE_SQ) {
+				free_expression(expr1);
+				free(expr2);
+			} else {
+				expr->var1 = expr1;
+				expr->var2 = expr2;
+				return _list->rest;
+			}
+		}
+	}
+
+	list = parse_simple_expression(expr, list);
+	if (!list)
+		free_expression(expr);
+
+	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 = calloc(1, sizeof(expression));
+		if (!_expr)
+			error_no_mem();
+
+		cpy_expression(_expr, expr);
+		expr->kind = EXPR_APP;
+		expr->var1 = _expr;
+
+		expr->var2 = calloc(1, sizeof(expression));
+		if (!expr->var2)
+			error_no_mem();
+
+		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");
+		free(rule->name);
+		return NULL;
+	}
+
+	if (list->elem.kind != TOKEN_EQUALS) {
+		log_debug("parse_rule: no =");
+		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 = 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
new file mode 100644
index 0000000..39f74e0
--- /dev/null
+++ b/compiler/parse.h
@@ -0,0 +1,8 @@
+#ifndef _H_PARSE
+#define _H_PARSE
+
+#include "syntax.h"
+
+fuspel* parse(token_list*);
+
+#endif
diff --git a/compiler/print.c b/compiler/print.c
new file mode 100644
index 0000000..c18d337
--- /dev/null
+++ b/compiler/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", 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
new file mode 100644
index 0000000..5909087
--- /dev/null
+++ b/compiler/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/compiler/syntax.c b/compiler/syntax.c
new file mode 100644
index 0000000..c19bf3b
--- /dev/null
+++ b/compiler/syntax.c
@@ -0,0 +1,153 @@
+#include "syntax.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+void free_token(token* tk) {
+	if (tk->var) {
+		free(tk->var);
+	}
+}
+
+void free_token_list(token_list* list) {
+	if (list->rest) {
+		free_token_list(list->rest);
+	}
+	free_token(&list->elem);
+}
+
+unsigned empty_args_list(arg_list* list) {
+	return !list;
+}
+
+void cpy_expression(expression* dst, expression* src) {
+	dst->kind = src->kind;
+	switch (dst->kind) {
+		case EXPR_INT:
+			dst->var1 = malloc(sizeof(int));
+			if (!dst->var1)
+				error_no_mem();
+			*((int*) dst->var1) = *((int*) src->var1);
+			break;
+		case EXPR_NAME:
+			dst->var1 = malloc(strlen((char*) src->var1) + 1);
+			if (!dst->var1)
+				error_no_mem();
+			strcpy(dst->var1, src->var1);
+			break;
+		case EXPR_LIST:
+			if (!src->var1)
+				break;
+		case EXPR_TUPLE:
+		case EXPR_APP:
+			dst->var1 = malloc(sizeof(expression));
+			dst->var2 = malloc(sizeof(expression));
+			if (!dst->var1 || !dst->var2)
+				error_no_mem();
+			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;
+	}
+}
+
+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 = 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 = 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:
+			free(expr->var1);
+			break;
+		case EXPR_LIST:
+		case EXPR_TUPLE:
+		case EXPR_APP:
+			free_expression(expr->var1);
+			free_expression(expr->var2);
+			break;
+	}
+}
+
+void free_arg_list(arg_list* list) {
+	if (list->rest)
+		free_arg_list(list->rest);
+	free_expression(&list->elem);
+}
+
+void free_rewrite_rule(rewrite_rule* rule) {
+	free(rule->name);
+	if (rule->args)
+		free_arg_list(rule->args);
+	free_expression(&rule->rhs);
+}
diff --git a/compiler/syntax.h b/compiler/syntax.h
new file mode 100644
index 0000000..66223a9
--- /dev/null
+++ b/compiler/syntax.h
@@ -0,0 +1,79 @@
+#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*);
+
+#endif
diff --git a/doc/.gitignore b/doc/.gitignore
new file mode 100644
index 0000000..3c0381d
--- /dev/null
+++ b/doc/.gitignore
@@ -0,0 +1,7 @@
+*.aux
+*.fdb_latexmk
+*.fls
+*.log
+*.out
+*.pdf
+*.toc
diff --git a/doc/doc.tex b/doc/doc.tex
new file mode 100644
index 0000000..576d966
--- /dev/null
+++ b/doc/doc.tex
@@ -0,0 +1,26 @@
+\documentclass[a4paper]{article}
+
+\author{Camil Staps}
+\title{Fuspel}
+
+\usepackage{geometry}
+\usepackage[usenames,dvipsnames,svgnames,table]{xcolor}
+\definecolor{linkcolor}{rgb}{0.65,0,0}
+\definecolor{citecolor}{rgb}{0,0.65,0}
+\definecolor{urlcolor}{rgb}{0,0,0.65}
+\usepackage[
+    colorlinks=true,
+    linkcolor=linkcolor,
+    urlcolor=urlcolor,
+    citecolor=citecolor]{hyperref}
+
+\usepackage{syntax}
+
+\begin{document}
+
+\maketitle
+\tableofcontents
+
+\input{grammar}
+
+\end{document}
diff --git a/doc/grammar.tex b/doc/grammar.tex
new file mode 100644
index 0000000..7a67a30
--- /dev/null
+++ b/doc/grammar.tex
@@ -0,0 +1,40 @@
+\section{Grammar}
+\label{sec:grammar}
+
+\setlength{\grammarparsep}{4pt}
+\setlength{\grammarindent}{10em}
+\begin{grammar}
+	<Fuspel> ::= <Rewrite-list>
+
+	<Rewrite-list> ::= <Rewrite> `;' <Rewrite-list> | <empty>
+
+	<Rewrite> ::= <Name> <Arg-list> `=' <Rhs>
+
+	<Arg-list> ::= <Arg> ` ' <Arg-list> | <empty>
+
+	<Arg> ::= <Simple-expr>
+
+	<Simple-expr> ::= <Int>
+		\alt <Name>
+		\alt <Simple-list>
+		\alt <Simple-tuple>
+
+	<Simple-list> ::= `[' <Simple-expr> `:' <Simple-list> `]'
+		\alt `[]'
+	
+	<Simple-tuple> ::= `(' <Simple-expr> `,' <Simple-expr> `)'
+
+	<Rhs> ::= <Expr>
+
+	<Expr> ::= <Int>
+		\alt <Name>
+		\alt <List>
+		\alt <Tuple>
+		\alt <Expr> <Expr>
+		\alt `(' <Expr> `)'
+
+	<List> ::= `[' <Expr> `:' <List> `]'
+		\alt `[]'
+	
+	<Tuple> ::= `(' <Simple-expr> `,' <Simple-expr> `)'
+\end{grammar}