initial commit

+ Now to do the actual hard parts, heh

7 files changed, 1278 insertions, 0 deletions

diff --git a/src/debug.c b/src/debug.c
new file mode 100644
index 0000000..8ad6673
--- /dev/null
+++ b/src/debug.c
@@ -0,0 +1,107 @@
+#include <stdio.h>
+#include <stddef.h>
+#include <string.h>
+#include <stdarg.h>
+
+#include <qbt/debug.h>
+
+static const char *find_lineno(const char *buf, size_t no)
+{
+	if (no == 0 || no == 1)
+		return buf;
+
+	char c;
+	while ((c = *buf)) {
+		buf++;
+
+		if (c == '\n')
+			no--;
+
+		if (no == 1)
+			break;
+	}
+
+	return buf;
+}
+
+const char *issue_level_str(enum issue_level level)
+{
+	switch (level) {
+	case SRC_INFO: return "info";
+	case SRC_WARN: return "warn";
+	case SRC_ERROR: return "error";
+	}
+
+	return "unknown";
+}
+
+static void _issue(struct src_issue issue, const char *fmt, va_list args)
+{
+	/* get start and end of current line in buffer */
+	const char *line_start = find_lineno(issue.fctx.fbuf,
+	                                     issue.loc.first_line);
+	const char *line_end = strchr(line_start, '\n');
+	if (!line_end)
+		line_end = strchr(line_start, 0);
+
+	const int line_len = line_end - line_start;
+
+	fprintf(stderr, "%s:%i:%i: %s: ", issue.fctx.fname,
+	        issue.loc.first_line,
+	        issue.loc.first_col,
+	        issue_level_str(issue.level));
+
+	vfprintf(stderr, fmt, args);
+	fputc('\n', stderr);
+
+	int lineno_len = snprintf(NULL, 0, "%i", issue.loc.first_line);
+	fputc(' ', stderr);
+	fprintf(stderr, "%i | ", issue.loc.first_line);
+
+	fprintf(stderr, "%.*s\n", line_len, line_start);
+
+	for (int i = 0; i < lineno_len + 2; ++i)
+		fputc(' ', stderr);
+
+	fprintf(stderr, "| ");
+
+	for (int i = 0; i < issue.loc.first_col - 1; ++i)
+		fputc(line_start[i] == '\t' ? '\t' : ' ', stderr);
+
+	for (int i = issue.loc.first_col; i < issue.loc.last_col; ++i) {
+		if (i == issue.loc.first_col)
+			fputc('^', stderr);
+		else
+			fputc('~', stderr);
+	}
+
+	fputc('\n', stderr);
+}
+
+void src_issue(struct src_issue issue, const char *err_msg, ...)
+{
+	va_list args;
+	va_start(args, err_msg);
+	_issue(issue, err_msg, args);
+	va_end(args);
+}
+
+void internal_error(const char *fmt, ...)
+{
+	va_list args;
+	va_start(args, fmt);
+	fprintf(stderr, "internal error: ");
+	vfprintf(stderr, fmt, args);
+	fprintf(stderr, "\n");
+	va_end(args);
+}
+
+void internal_warn(const char *fmt, ...)
+{
+	va_list args;
+	va_start(args, fmt);
+	fprintf(stderr, "internal warning: ");
+	vfprintf(stderr, fmt, args);
+	fprintf(stderr, "\n");
+	va_end(args);
+}
diff --git a/src/lexer.l b/src/lexer.l
new file mode 100644
index 0000000..75e2b09
--- /dev/null
+++ b/src/lexer.l
@@ -0,0 +1,160 @@
+/* SPDX-License-Identifier: copyleft-next-0.3.1 */
+/* Copyright 2023 Kim Kuparinen < kimi.h.kuparinen@gmail.com > */
+
+%option reentrant noyywrap nounput noinput nodefault
+%{
+#define FROM_LEXER
+#include <qbt/parser.h>
+#include <qbt/debug.h>
+
+static void update_yylloc(struct parser *parser, YYLTYPE *lloc, const char *text)
+{
+	(void)parser;
+
+	lloc->first_line = lloc->last_line;
+	lloc->first_column = lloc->last_column;
+
+	for (size_t i = 0; text[i] != 0; ++i) {
+		if (text[i] == '\n') {
+			lloc->last_line++;
+			/* flex uses 1 based indexing */
+			lloc->last_column = 1;
+		} else {
+			lloc->last_column++;
+		}
+	}
+}
+
+#define YY_USER_ACTION update_yylloc(parser, yylloc, yytext);
+%}
+
+HEX		0[xX][0-9a-fA-F]+
+DEC		-?[0-9]+
+OCT		0[0-8]+
+BIN		0b[0-1]+
+
+INT		{HEX}|{DEC}|{OCT}|{BIN}
+
+HEXF		[+-]?0[xX][0-9a-fA-F]+([pP][+-]?[0-9]+)
+DECF		[+-]?[0-9]+[.]([eE]?[+-]?[0-9]+)?[fF]?
+
+ID		[_a-zA-Z][_a-zA-Z0-9]*
+
+STRING		\"(\\.|[^"\\])*\"
+
+%x SC_COMMENT
+
+%%
+"//".* {/* skip line comments */}
+
+"/*"	{BEGIN(SC_COMMENT);}
+<SC_COMMENT>{
+	"/*"	{++parser->comment_nesting;}
+	"*"+"/"	{
+		if (parser->comment_nesting)
+			--parser->comment_nesting;
+		else
+			BEGIN(INITIAL);
+	}
+
+	"*"+ {}
+	[^/*\n]+ {}
+	[/] {}
+	\n {}
+}
+
+"("		{return LEXLPAREN;}
+")"		{return LEXRPAREN;}
+"{"		{return LEXLBRACE;}
+"}"		{return LEXRBRACE;}
+","		{return LEXCOMMA;}
+":"		{return LEXCOLON;}
+"!"		{return LEXBANG;}
+
+"+"		{return LEXPLUS;}
+"-"		{return LEXMINUS;}
+"*"		{return LEXSTAR;}
+"/"		{return LEXDIV;}
+"%"		{return LEXREM;}
+
+'[^'\\]'	{
+	/* regular character constant, 'a' */
+	yylval->integer = yytext[1];
+	return INT;
+}
+
+'\\x[0-9a-fA-F]+' {
+	/* hex character constant, '\xef' */
+	/* handling is slightly different from C, here it's more or less just
+	 * another way to specify a hex integer */
+	yylval->integer = strtoll(yytext + 3, NULL, 16);
+	return INT;
+}
+
+'\\[0-8]+' {
+	/* octal character constant, '\033' */
+	yylval->integer = strtoll(yytext + 2, NULL, 8);
+	return INT;
+}
+
+'\\b[01]+' {
+	/* binary character constant, '\b101' */
+	yylval->integer = strtoll(yytext + 3, NULL, 2);
+	return INT;
+}
+
+'\\.' {
+	/* escaped character constant */
+	yylval->integer = match_escape(yytext[2]);
+	return INT;
+}
+
+"&"		{return LEXAND;}
+
+"="		{return LEXASSIGN;}
+"<"		{return LEXLT;}
+">"		{return LEXGT;}
+"<="		{return LEXLE;}
+">="		{return LEXGE;}
+"!="		{return LEXNE;}
+"=="		{return LEXEQ;}
+";"		{return LEXSEMI;}
+
+"=>"		{return LEXFATARROW;}
+"->"		{return LEXTHINARROW;}
+">>"		{return LEXTO;}
+"<<"		{return LEXFROM;}
+
+"i9"		{return LEXI9;}
+"i27"		{return LEXI27;}
+
+{STRING} {
+	/* seems risky, I know, but letting the parser choose when to allocate a
+	 * new string seems to help with syntax error cleanup */
+	yylval->str = yytext;
+	return STRING;
+}
+
+{INT} {
+	yylval->integer = strtoll(yytext, 0, 0);
+	return INT;
+}
+
+{ID} {
+	yylval->str = yytext;
+	return ID;
+}
+
+
+[[:space:]]+	{/* skip whitespace */}
+
+. {
+	struct src_issue issue;
+	issue.level = SRC_ERROR;
+	issue.loc = src_loc(*yylloc);
+	issue.fctx.fbuf = parser->buf;
+	issue.fctx.fname = parser->fname;
+	src_issue(issue, "Unexpected token: %s", yytext);
+	parser->failed = true;
+}
+%%
diff --git a/src/main.c b/src/main.c
new file mode 100644
index 0000000..a0eeb42
--- /dev/null
+++ b/src/main.c
@@ -0,0 +1,63 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <limits.h>
+
+#include <qbt/parser.h>
+#include <qbt/debug.h>
+
+static char *read_file(const char *file, FILE *f)
+{
+	fseek(f, 0, SEEK_END);
+	/** @todo check how well standardized this actually is */
+	long s = ftell(f);
+	if (s == LONG_MAX) {
+		error("%s might be a directory", file);
+		return NULL;
+	}
+
+	fseek(f, 0, SEEK_SET);
+
+	char *buf = malloc(s + 1);
+	if (!buf)
+		return NULL;
+
+	fread(buf, s + 1, 1, f);
+	/* remember terminating null */
+	buf[s] = 0;
+	return buf;
+}
+
+static void usage(FILE *f)
+{
+	fprintf(f, "qbt <file>.qbt\n");
+}
+
+int main(int argc, char *argv[])
+{
+	if (argc != 2) {
+		usage(stdout);
+		return -1;
+	}
+
+	char *fname = argv[1];
+	FILE *f = fopen(fname, "rb");
+	if (!f) {
+		fprintf(stderr, "couldn't open %s\n", fname);
+		return -1;
+	}
+
+	char *buf = read_file(fname, f);
+	fclose(f);
+
+	struct parser *p = create_parser();
+	parse(p, fname, buf);
+
+	foreach_fn(i, p->fns) {
+		struct fn_map m = fn_at(p->fns, i);
+		dump_function(m.fn);
+	}
+
+	destroy_parser(p);
+	free(buf);
+}
diff --git a/src/nodes.c b/src/nodes.c
new file mode 100644
index 0000000..9eb0113
--- /dev/null
+++ b/src/nodes.c
@@ -0,0 +1,225 @@
+#include <string.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include <qbt/nodes.h>
+#include <qbt/debug.h>
+#include <qbt/vec.h>
+
+void insadd(struct blk *b, enum insn_type o, enum val_type t, struct val r, struct val a0, struct val a1)
+{
+	struct insn i = insn_create(o, t, r, a0, a1);
+	vec_append(&b->insns, &i);
+}
+
+int64_t idalloc(struct fn *f, const char *id)
+{
+	int64_t t = idmatch(f, id);
+	if (t >= 0) {
+		return t;
+	}
+
+	t = f->ntmp++;
+	vec_append(&f->tmps, &(struct tmp_map){.id = id, .v = t});
+	return t;
+}
+
+int64_t idmatch(struct fn *f, const char *id)
+{
+	foreach_tmp(i, f->tmps) {
+		struct tmp_map t = tmp_at(f->tmps, i);
+		if (strcmp(t.id, id) == 0)
+			return t.v;
+	}
+
+	return -1;
+}
+
+void finish_block(struct blk *b, enum insn_type cmp, struct val a0, struct val a1, const char *label)
+{
+	assert(cmp >= BEQ && cmp <= RET && "illegal comparison type for block");
+	b->btype = cmp;
+	b->cmp[0] = a0;
+	b->cmp[1] = a1;
+	b->to = label;
+}
+
+struct blk *new_block(struct fn *f)
+{
+	struct blk *b = calloc(1, sizeof(struct blk));
+	b->id = ++f->nblk;
+	b->insns = vec_create(sizeof(struct insn));
+	vec_append(&f->blks, &b);
+	return b;
+}
+
+static struct label_map label_find(struct fn *f, const char *name)
+{
+	foreach_label(i, f->labels) {
+		struct label_map m = label_at(f->labels, i);
+		if (strcmp(m.id, name) == 0)
+			return m;
+	}
+
+	return (struct label_map){.id = NULL, .b = NULL};
+}
+
+bool blk_empty(struct blk *b)
+{
+	return vec_len(&b->insns) == 0;
+}
+
+void finish_function(struct fn *f, const char *name)
+{
+	/** @todo check that returns match */
+	f->name = name;
+	/* last block should always be empty and can be removed */
+	struct blk *last_blk = blk_pop(f->blks);
+	if (!blk_empty(last_blk)) {
+		error("last block not empty, %s missing return?", name);
+		abort();
+	}
+
+	destroy_block(last_blk);
+
+	foreach_blk(i, f->blks) {
+		struct blk *b = blk_at(f->blks, i);
+		if (!b->to)
+			continue;
+
+		struct label_map m = label_find(f, b->to);
+		if (!m.id) {
+			error("no label %s", b->to);
+			abort();
+		}
+
+		b->s2 = m.b;
+	}
+
+}
+
+struct fn *new_function()
+{
+	struct fn *f = calloc(1, sizeof(struct fn));
+	f->blks = vec_create(sizeof(struct blk *));
+	f->tmps = vec_create(sizeof(struct tmp_map));
+	f->labels = vec_create(sizeof(struct label_map));
+	/* empty block */
+	new_block(f);
+	return f;
+}
+
+void destroy_function(struct fn *f)
+{
+	vec_destroy(&f->tmps);
+	vec_destroy(&f->labels);
+
+	foreach_blk(i, f->blks) {
+		struct blk *b = blk_at(f->blks, i);
+		destroy_block(b);
+	}
+	vec_destroy(&f->blks);
+
+	free(f);
+}
+
+void destroy_block(struct blk *b)
+{
+	vec_destroy(&b->insns);
+	free(b);
+}
+
+void new_label(struct fn *f, struct blk *b, const char *name)
+{
+	vec_append(&f->labels, &(struct label_map){.id = name, .b = b});
+}
+
+static const char *op_str(enum insn_type n) {
+#define CASE(I) case I: return #I;
+	switch (n) {
+		FOREACH_INSN_TYPE(CASE);
+	}
+#undef CASE
+	return "unknown";
+}
+
+void dump_val(struct val val) {
+	long long r = val.r;
+	long long v = val.v;
+	const char *s = val.s;
+
+	switch (val.class) {
+	case REG: printf("r%lli", r); break;
+	case TMP: printf("t%lli", r); break;
+	case IMM: printf("%lli", v); break;
+	case MEM: printf("(r%lli, %lli)", r, v); break;
+	case REF: printf("\"%s\"", s); break;
+	case NOCLASS: break;
+	}
+}
+
+void dump_insn(struct insn i)
+{
+	printf("\t");
+
+	if (hasclass(i.out)) {
+		dump_val(i.out);
+		printf(" ");
+	}
+
+	printf("%s", op_str(i.type));
+
+	if (hasclass(i.in[0])) {
+		printf(" ");
+		dump_val(i.in[0]);
+	}
+
+	if (hasclass(i.in[1])) {
+		printf(" ");
+		dump_val(i.in[1]);
+	}
+
+	printf("\n");
+}
+
+bool return_blk(struct blk *b)
+{
+	return b->btype == RET;
+}
+
+void dump_block(struct blk *b)
+{
+	printf("\t/*** block %lld ", (long long)b->id);
+	if (b->name) printf("(%s) ", b->name);
+	printf("***/\n");
+
+	foreach_insn(i, b->insns) {
+		struct insn n = insn_at(b->insns, i);
+		dump_insn(n);
+	}
+
+	if (return_blk(b)) {
+		printf("\n");
+		return;
+	}
+
+	if (b->btype != J) {
+		assert(b->s2);
+		struct blk *s2 = b->s2;
+		printf("\t%s ", op_str(b->btype));
+		dump_val(b->cmp[0]);
+		printf(" ");
+		dump_val(b->cmp[1]);
+		printf(" -> %lli\n", (long long)s2->id);
+	}
+	printf("\n");
+}
+
+void dump_function(struct fn *f) {
+	printf("/*** function %s ***/\n", f->name);
+	foreach_blk(i, f->blks) {
+		struct blk *b = blk_at(f->blks, i);
+		dump_block(b);
+	}
+	printf("\n");
+}
diff --git a/src/parser.y b/src/parser.y
new file mode 100644
index 0000000..4a70341
--- /dev/null
+++ b/src/parser.y
@@ -0,0 +1,666 @@
+/* SPDX-License-Identifier: copyleft-next-0.3.1 */
+/* Copyright 2023 Kim Kuparinen < kimi.h.kuparinen@gmail.com > */
+
+%{
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <string.h>
+
+#include <qbt/parser.h>
+#include <qbt/debug.h>
+#include <qbt/nodes.h>
+
+struct ret_helper {
+	const char *r;
+	enum val_type t;
+};
+
+%}
+
+%locations
+
+%define parse.trace
+%define parse.error verbose
+%define api.pure full
+%define lr.type ielr
+
+%lex-param {void *scanner} {struct parser *parser}
+%parse-param {void *scanner} {struct parser* parser}
+
+%union {
+	struct val val;
+	struct ret_helper ret;
+	enum val_type type;
+	int64_t integer;
+	char *str;
+};
+
+%token <integer> INT
+%token <str> STRING
+%token <str> ID
+
+%token LEXASSIGN "="
+%token LEXCOLON ":"
+%token LEXBANG "!"
+%token LEXSTAR "*"
+%token LEXDIV "/"
+%token LEXREM "%"
+%token LEXMINUS "-"
+%token LEXPLUS "+"
+%token LEXAND "&"
+%token LEXLT "<"
+%token LEXGT ">"
+%token LEXLE "<="
+%token LEXGE ">="
+%token LEXNE "!="
+%token LEXEQ "=="
+%token LEXCOMMA ","
+%token LEXLPAREN "("
+%token LEXRPAREN ")"
+%token LEXLBRACE "{"
+%token LEXRBRACE "}"
+%token LEXFATARROW "=>"
+%token LEXTHINARROW "->"
+%token LEXTO ">>"
+%token LEXFROM "<<"
+%token LEXSEMI ";"
+
+%token LEXI9 "i9"
+%token LEXI27 "i27"
+
+%nterm <val> mem_loc
+%nterm <str> mem_base
+%nterm <integer> mem_off
+%nterm <integer> int
+%nterm <type> type
+
+%nterm <str> id addr local label
+%nterm <val> arg opt_arg
+%nterm <ret> call_ret opt_call_ret
+
+%{
+
+/** Modifies the signature of yylex to fit our parser better. */
+#define YY_DECL int yylex(YYSTYPE *yylval, YYLTYPE *yylloc, \
+	                  void *yyscanner, struct parser *parser)
+
+/**
+ * Declare yylex.
+ *
+ * @param yylval Bison current value.
+ * @param yylloc Bison location info.
+ * @param yyscanner Flex scanner.
+ * @param parser Current parser state.
+ * @return \c 0 when succesful, \c 1 otherwise.
+ * More info on yylex() can be found in the flex manual.
+ */
+YY_DECL;
+
+/**
+ * Convert bison location info to our own source location info.
+ *
+ * @param yylloc Bison location info.
+ * @return Internal location info.
+ */
+static struct src_loc src_loc(YYLTYPE yylloc);
+
+/**
+ * Print parsing error.
+ * Automatically called by bison.
+ *
+ * @param yylloc Location of error.
+ * @param lexer Lexer.
+ * @param parser Parser state.
+ * @param msg Message to print.
+ */
+static void yyerror(YYLTYPE *yylloc, void *lexer,
+		struct parser *parser, const char *msg);
+
+/**
+ * Try to convert escape code to its actual value.
+ * I.e. '\n' -> 0x0a.
+ *
+ * @param c Escape character without backslash.
+ * @return Corresponding value.
+ */
+static long long match_escape(char c);
+
+/**
+ * Similar to strdup() but skips quotation marks that would
+ * otherwise be included.
+ * I.e. "something" -> something.
+ *
+ * @param s String to clone, with quotation marks surrounding it.
+ * @return Identical string but without quotation marks around it.
+ */
+static char *clone_string(const char *s);
+
+static inline struct val do_idalloc(struct parser *p, const char *id)
+{
+	int64_t t = idalloc(p->f, id);
+	return tmp_val(t);
+}
+
+static inline struct val do_idtoval(struct parser *p, const char *id)
+{
+	int64_t t = idmatch(p->f, id);
+	if (t < 0) {
+		error("no such temporary: %s\n", id);
+		abort();
+	}
+
+	return tmp_val(t);
+}
+
+static inline void do_new_block(struct parser *p,
+	enum insn_type type,
+	struct val a0,
+	struct val a1,
+	const char *label)
+{
+	finish_block(p->b, type, a0, a1, label);
+	p->b = p->b->s1 = new_block(p->f);
+}
+
+static inline void do_insadd(struct parser *p,
+	enum insn_type cmp,
+	enum val_type t,
+	struct val r,
+	struct val a0,
+	struct val a1)
+{
+	insadd(p->b, cmp, t, r, a0, a1);
+}
+
+static inline void do_new_function(struct parser *p, const char *name)
+{
+	finish_function(p->f, name);
+	vec_append(&p->fns, &(struct fn_map){.id = name, .fn = p->f});
+	p->f = new_function();
+	p->b = blk_at(p->f->blks, 0);
+}
+
+static inline char *do_strdup(struct parser *p, const char *s)
+{
+	char *new = strdup(s);
+	vec_append(&p->strs, &new);
+	return new;
+}
+
+static inline char *do_strclone(struct parser *p, const char *s)
+{
+	char *new = clone_string(s);
+	vec_append(&p->strs, &new);
+	return new;
+}
+
+static inline void do_new_label(struct parser *p, const char *s)
+{
+	new_label(p->f, p->b, s);
+}
+
+#define INSADD(o, t, r, a0, a1)\
+	do_insadd(parser, o, t, r, a0, a1)
+
+#define IDALLOC(i)\
+	do_idalloc(parser, i)
+
+#define IDTOVAL(i)\
+	do_idtoval(parser, i)
+
+#define NEW_BLOCK(c, a0, a1, l)\
+	do_new_block(parser, c, a0, a1, l)
+
+#define NEW_FUNCTION(n)\
+	do_new_function(parser, n)
+
+#define DUP_STR(s)\
+	do_strdup(parser, s)
+
+#define CLONE_STR(s)\
+	do_strclone(parser, s)
+
+#define NEW_LABEL(s)\
+	do_new_label(parser, s)
+
+%}
+
+%start input;
+%%
+
+id
+	: ID { $$ = DUP_STR($1); }
+	| STRING { $$ = CLONE_STR($1); }
+
+int
+	: INT
+
+type
+	: "i9" { $$ = I9; }
+	| "i27" { $$ = I27; }
+
+const
+	: "i9" int
+	| "i27" int
+
+consts
+	: const "," consts
+	| const ","
+	| const
+
+opt_consts
+	: consts
+	| {}
+
+data
+	: id "=" "{" opt_consts "}"
+
+param
+	: type id {
+		struct val t = IDALLOC($[id]);
+		INSADD(PARAM, $[type], t, imm_val(parser->idx++, I27), noclass());
+	}
+
+params
+	: param "," params
+	| param ","
+	| param
+
+opt_params
+	: params
+	| {}
+
+ret
+	: type
+
+opt_ret
+	: ret
+	| {}
+
+/* only three return args permitted (keep things simple for now) */
+rets
+	: opt_ret "," opt_ret "," opt_ret
+
+label
+	: id ":" {
+		if (empty_block(parser->b)) {
+			parser->b->name = $[id];
+		} else {
+			NEW_BLOCK(J, noclass(), noclass(), NULL);
+			parser->b->name = $[id];
+		}
+		NEW_LABEL($[id]);
+	}
+
+arg
+	: id {
+		$$ = IDTOVAL($[id]);
+	}
+	| type int {
+		$$ = imm_val($[type], $[int]);
+	}
+
+arith
+	: type id "=" arg "+" arg {
+		struct val t = IDALLOC($[id]);
+		INSADD(ADD, $[type], t, $4, $6);
+	}
+	| type id "=" arg "-" arg {
+		struct val t = IDALLOC($[id]);
+		INSADD(SUB, $[type], t, $4, $6);
+	}
+	| type id "=" arg "*" arg {
+		struct val t = IDALLOC($[id]);
+		INSADD(MUL, $[type], t, $4, $6);
+	}
+	| type id "=" arg "/" arg {
+		struct val t = IDALLOC($[id]);
+		INSADD(DIV, $[type], t, $4, $6);
+	}
+	| type id "=" arg "%" arg {
+		struct val t = IDALLOC($[id]);
+		INSADD(REM, $[type], t, $4, $6);
+	}
+
+addr
+	: "&" id { $$ = $2; }
+
+imm
+	: type id "=" int {
+		struct val t = IDALLOC($[id]);
+		INSADD(COPY, $[type], t, imm_val($[int], I27), noclass());
+	}
+	| type id "=" addr {
+		struct val t = IDALLOC($[id]);
+		INSADD(COPY, $[type], t, imm_ref($[addr]), noclass());
+	}
+
+move
+	: type id "=" id {
+		struct val t = IDALLOC($2);
+		struct val f = IDTOVAL($4);
+		INSADD(MOVE, $[type], t, f, noclass());
+	}
+
+mem_base
+	: id
+
+mem_off
+	: int
+
+mem_loc
+	: "(" mem_base mem_off ")" {$$ = mem_val(IDTOVAL($[mem_base]).r, $[mem_off]);}
+
+mem
+	: type id "<<" mem_loc {
+		struct val t = IDALLOC($[id]);
+		INSADD(LOAD, $[type], t, $[mem_loc], noclass());
+	}
+	| id ">>" type mem_loc {
+		struct val t = IDALLOC($[id]);
+		INSADD(STORE, $[type], noclass(), t, $[mem_loc]);
+	}
+
+stack
+	: type id "=" "alloc" int {
+		struct val t = IDALLOC($[id]);
+		INSADD(ALLOC, $[type], t, imm_val($[int], I27), noclass());
+	}
+
+cond
+	: type id "=" arg "==" arg {
+		struct val t = IDALLOC($[id]);
+		INSADD(EQ, $[type], t, $4, $6);
+	}
+	| type id "=" arg "!=" arg {
+		struct val t = IDALLOC($[id]);
+		INSADD(NE, $[type], t, $4, $6);
+	}
+	| type id "=" arg "<=" arg {
+		struct val t = IDALLOC($[id]);
+		INSADD(LE, $[type], t, $4, $6);
+	}
+	| type id "=" arg ">=" arg {
+		struct val t = IDALLOC($[id]);
+		INSADD(GE, $[type], t, $4, $6);
+	}
+	| type id "=" arg "<"  arg {
+		struct val t = IDALLOC($[id]);
+		INSADD(LT, $[type], t, $4, $6);
+	}
+	| type id "=" arg ">"  arg {
+		struct val t = IDALLOC($[id]);
+		INSADD(GT, $[type], t, $4, $6);
+	}
+
+logic
+	: type id "=" "!" arg {
+		struct val t = IDALLOC($[id]);
+		INSADD(NOT, $[type], t, $5, noclass());
+	}
+	| type id "=" "-" arg {
+		struct val t = IDALLOC($[id]);
+		INSADD(NEG, $[type], t, $5, noclass());
+	}
+	| type id "=" arg "<<" arg {
+		struct val t = IDALLOC($[id]);
+		INSADD(LSHIFT, $[type], t, $4, $6);
+	}
+	| type id "=" arg ">>" arg {
+		struct val t = IDALLOC($[id]);
+		INSADD(RSHIFT, $[type], t, $4, $6);
+	}
+
+local
+	: id
+
+branch
+	: arg "==" arg "->" local {
+		NEW_BLOCK(BEQ, $1, $3, $[local]);
+	}
+	| arg "!=" arg "->" local {
+		NEW_BLOCK(BNE, $1, $3, $[local]);
+	}
+	| arg "<=" arg "->" local {
+		NEW_BLOCK(BLE, $1, $3, $[local]);
+	}
+	| arg ">=" arg "->" local {
+		NEW_BLOCK(BGE, $1, $3, $[local]);
+	}
+	| arg "<"  arg "->" local {
+		NEW_BLOCK(BLT, $1, $3, $[local]);
+	}
+	| arg ">"  arg "->" local {
+		NEW_BLOCK(BGT, $1, $3, $[local]);
+	}
+	| "->" local {
+		NEW_BLOCK(J, noclass(), noclass(), $[local]);
+	}
+
+call_ret
+	: type id {
+		$$ = (struct ret_helper){.r = $[id], .t = $[type]};
+	}
+
+opt_call_ret
+	: call_ret
+	| { $$ = (struct ret_helper){.r = NULL, .t = NOTYPE}; }
+
+call_arg
+	: arg {
+		INSADD(ARG, NOTYPE, noclass(), $[arg], imm_val(parser->idx++, I27));
+	}
+
+call_args
+	: call_arg "," call_args
+	| call_arg ","
+	| call_arg
+
+opt_call_args
+	: call_args
+	| {}
+
+/* empty rule for starting counts */
+reset_index
+	: {parser->idx = 0;}
+
+call
+	: "(" opt_call_ret "," opt_call_ret "," opt_call_ret ")"
+	"=" addr reset_index "(" opt_call_args ")" {
+		/* call args should have inserted their own nodes */
+		INSADD(CALL, NOTYPE, noclass(), imm_ref($[addr]), noclass());
+
+		if ($2.r) {
+			struct val t = IDALLOC($2.r);
+			INSADD(RETVAL, $2.t, t, noclass(), imm_val(0, I27));
+		}
+
+		if ($4.r) {
+			struct val t = IDALLOC($4.r);
+			INSADD(RETVAL, $4.t, t, noclass(), imm_val(1, I27));
+		}
+
+		if ($6.r) {
+			struct val t = IDALLOC($6.r);
+			INSADD(RETVAL, $6.t, t, noclass(), imm_val(2, I27));
+		}
+	}
+
+opt_arg
+	: arg
+	| { $$ = noclass(); }
+
+return
+	: "=>" "(" opt_arg "," opt_arg "," opt_arg ")" {
+		if (!hasnoclass($3))
+			INSADD(RET, NOTYPE, noclass(), $3, imm_val(0, I27));
+
+		if (!hasnoclass($5))
+			INSADD(RET, NOTYPE, noclass(), $5, imm_val(1, I27));
+
+		if (!hasnoclass($7))
+			INSADD(RET, NOTYPE, noclass(), $7, imm_val(2, I27));
+
+		NEW_BLOCK(RET, noclass(), noclass(), NULL);
+	}
+
+insn
+	: arith
+	| imm
+	| move
+	| mem
+	| stack
+	| cond
+	| logic
+	| branch
+	| call
+	| return
+
+body
+	: insn ";" body
+	| label body
+	| label
+	| insn ";"
+
+function
+	: id reset_index "(" opt_params "=>" rets ")" "{" body "}" {
+		NEW_FUNCTION($[id]);
+	}
+
+top
+	: data
+	| function
+
+unit
+	: top unit
+	| top
+
+input
+	: unit
+	| /* empty */
+
+%%
+
+#include "gen_lexer.inc"
+
+static struct src_loc src_loc(YYLTYPE yylloc)
+{
+	struct src_loc loc;
+	loc.first_line = yylloc.first_line;
+	loc.last_line = yylloc.last_line;
+	loc.first_col = yylloc.first_column;
+	loc.last_col = yylloc.last_column;
+	return loc;
+}
+
+static void yyerror(YYLTYPE *yylloc, void *lexer,
+		struct parser *parser, const char *msg)
+{
+	(void)lexer;
+
+	struct src_issue issue;
+	issue.level = SRC_ERROR;
+	issue.loc = src_loc(*yylloc);
+	issue.fctx.fbuf = parser->buf;
+	issue.fctx.fname = parser->fname;
+	src_issue(issue, msg);
+}
+
+static long long match_escape(char c)
+{
+	switch (c) {
+	case '\'': return '\'';
+	case '\\': return '\\';
+	case 'a': return '\a';
+	case 'b': return '\b';
+	case 'f': return '\f';
+	case 'n': return '\n';
+	case 'r': return '\r';
+	case 't': return '\t';
+	case 'v': return '\v';
+	}
+
+	return c;
+}
+
+static char *clone_string(const char *str)
+{
+	const size_t len = strlen(str) + 1;
+	char *buf = malloc(len);
+	if (!buf) {
+		/* should probably try to handle the error in some way... */
+		internal_error("failed allocating buffer for string clone");
+		return NULL;
+	}
+
+	/* skip quotation marks */
+	size_t j = 0;
+	for (size_t i = 1; i < len - 2; ++i) {
+		char c = str[i];
+
+		if (c == '\\')
+			c = match_escape(str[++i]);
+
+		buf[j++] = c;
+	}
+
+	buf[j] = 0;
+	return buf;
+
+}
+
+struct parser *create_parser()
+{
+	return calloc(1, sizeof(struct parser));
+}
+
+void destroy_parser(struct parser *p)
+{
+	foreach_fn(i, p->fns) {
+		struct fn_map m = fn_at(p->fns, i);
+		/* I assume the 'extra' empty function is never appended to the
+		 * function vector */
+		assert(m.fn != p->f);
+		destroy_function(m.fn);
+	}
+	vec_destroy(&p->fns);
+	destroy_function(p->f);
+
+	foreach_str(i, p->strs) {
+		char *s = str_at(p->strs, i);
+		free(s);
+	}
+	vec_destroy(&p->strs);
+
+/* data isn't really handled yet properly
+	foreach_data(i, p->datas) {
+		struct data_map m = data_at(p->datas, i);
+		destroy_data(m.data);
+		free((void *)m.id);
+	}
+	*/
+
+	yylex_destroy(p->lexer);
+	free(p);
+}
+
+void parse(struct parser *p, const char *fname, const char *buf)
+{
+	p->fname = fname;
+	p->buf = buf;
+
+	p->fns = vec_create(sizeof(struct fn_map));
+	p->strs = vec_create(sizeof(char *));
+
+	p->f = new_function();
+	p->b = blk_at(p->f->blks, 0);
+	p->comment_nesting = 0;
+
+	p->failed = false;
+
+	yylex_init(&p->lexer);
+	yy_scan_string(buf, p->lexer);
+	yyparse(p->lexer, p);
+}
diff --git a/src/source.mk b/src/source.mk
new file mode 100644
index 0000000..9fad368
--- /dev/null
+++ b/src/source.mk
@@ -0,0 +1,8 @@
+SRC_LOCAL != echo src/*.c
+SOURCES += $(SRC_LOCAL) gen/gen_parser.c
+
+gen/gen_parser.c: src/parser.y gen/gen_lexer.inc
+	bison -Wcounterexamples -o gen/gen_parser.c src/parser.y
+
+gen/gen_lexer.inc: src/lexer.l
+	flex -o gen/gen_lexer.inc src/lexer.l
diff --git a/src/vec.c b/src/vec.c
new file mode 100644
index 0000000..4ba92fb
--- /dev/null
+++ b/src/vec.c
@@ -0,0 +1,49 @@
+#include <stdlib.h>
+#include <assert.h>
+#include <string.h>
+
+#include <qbt/vec.h>
+
+struct vec vec_create(size_t ns)
+{
+	return (struct vec) {
+		.n = 0,
+		.s = 1,
+		.ns = ns,
+		.buf = malloc(ns),
+	};
+}
+
+size_t vec_len(struct vec *v)
+{
+	return v->n;
+}
+
+void *vec_at(struct vec *v, size_t i)
+{
+	assert(i < v->n && "out of vector bounds");
+	return v->buf + i * v->ns;
+}
+
+void *vec_pop(struct vec *v)
+{
+	assert(v->n && "attempting to pop empty vector");
+	v->n--;
+	return v->buf + v->n * v->ns;
+}
+
+void vec_append(struct vec *v, void *n)
+{
+	v->n++;
+	if (v->n >= v->s) {
+		v->s *= 2;
+		v->buf = realloc(v->buf, v->s * v->ns);
+	}
+
+	void *p = vec_at(v, v->n - 1);
+	memcpy(p, n, v->ns);
+}
+
+void vec_destroy(struct vec *v) {
+	free(v->buf);
+}