os

lexer.om (23007B)

---

 // https://swtch.com/~rsc/regexp/regexp1.html
 
 struct nfa {
 	id: int;
 	tag: int;
 	start: int;
 	end: int;
 	out: *nfa;
 	alt: *nfa;
 	tail: **nfa;
 	ntail: int;
 	mark: int;
 }
 
 func nfa_concat(c: *compiler, a: *nfa, b:* nfa): *nfa {
 	var i: int;
 
 	if !a {
 		return nil;
 	}
 
 	if !b {
 		return nil;
 	}
 
 	i = 0;
 	loop {
 		if i == a.ntail {
 			break;
 		}
 
 		a.tail[i].out = b;
 
 		i = i + 1;
 	}
 
 	free(c.a, a.tail as *byte);
 
 	a.tail = b.tail;
 	a.ntail = b.ntail;
 
 	return a;
 }
 
 func nfa_alt(c: *compiler, a: *nfa, b: *nfa): *nfa {
 	var n: *nfa;
 	var tail: **nfa;
 	var i: int;
 	var j: int;
 
 	if !a {
 		return b;
 	}
 
 	if !b {
 		return a;
 	}
 
 	n = alloc(c.a, sizeof(*n)) as *nfa;
 	n.id = c.nfa_id;
 	c.nfa_id = c.nfa_id + 1;
 	n.start = -1;
 	n.end = -1;
 	n.out = a;
 	n.alt = b;
 	n.ntail = a.ntail + b.ntail;
 	n.tail = alloc(c.a, sizeof(*tail) * n.ntail) as **nfa;
 
 	i = 0;
 	j = 0;
 	loop {
 		if i == a.ntail {
 			break;
 		}
 
 		n.tail[j] = a.tail[i];
 
 		j = j + 1;
 		i = i + 1;
 	}
 
 	i = 0;
 	loop {
 		if i == b.ntail {
 			break;
 		}
 
 		n.tail[j] = b.tail[i];
 
 		j = j + 1;
 		i = i + 1;
 	}
 
 	free(c.a, a.tail as *byte);
 	free(c.a, b.tail as *byte);
 
 	return n;
 }
 
 func nfa_plus(c: *compiler, a: *nfa): *nfa {
 	var b: *nfa;
 	if !a {
 		return nil;
 	}
 	b = alloc(c.a, sizeof(*b)) as *nfa;
 	b.id = c.nfa_id;
 	c.nfa_id = c.nfa_id + 1;
 	b.start = -1;
 	b.end = -1;
 	b.out = nil;
 	b.alt = a;
 	b.tail = alloc(c.a, sizeof(*b.tail)) as **nfa;
 	b.ntail = 1;
 	b.tail[0] = b;
 	return nfa_concat(c, a, b);
 }
 
 func nfa_qmark(c: *compiler, a: *nfa): *nfa {
 	var b: *nfa;
 	var i: int;
 	if !a {
 		return nfa_empty(c);
 	}
 	b = alloc(c.a, sizeof(*b)) as *nfa;
 	b.id = c.nfa_id;
 	c.nfa_id = c.nfa_id + 1;
 	b.start = -1;
 	b.end = -1;
 	b.out = nil;
 	b.alt = a;
 	b.ntail = a.ntail + 1;
 	b.tail = alloc(c.a, sizeof(*b.tail) * b.ntail) as **nfa;
 	loop {
 		if i == a.ntail {
 			break;
 		}
 		b.tail[i] = a.tail[i];
 		i = i + 1;
 	}
 	b.tail[i] = b;
 	free(c.a, a.tail as *byte);
 	return b;
 }
 
 func nfa_star(c: *compiler, a: *nfa): *nfa {
 	a = nfa_plus(c, a);
 	return nfa_qmark(c, a);
 }
 
 func nfa_lit(c: *compiler, start: int, end: int): *nfa {
 	var n: *nfa;
 	n = alloc(c.a, sizeof(*n)) as *nfa;
 	n.id = c.nfa_id;
 	c.nfa_id = c.nfa_id + 1;
 	n.out = nil;
 	n.start = start;
 	n.end = end;
 	n.tail = alloc(c.a, sizeof(*n.tail)) as **nfa;
 	n.ntail = 1;
 	n.tail[0] = n;
 	return n;
 }
 
 func nfa_empty(c: *compiler): *nfa {
 	var n: *nfa;
 	n = alloc(c.a, sizeof(*n)) as *nfa;
 	n.id = c.nfa_id;
 	c.nfa_id = c.nfa_id + 1;
 	n.start = -1;
 	n.end = -1;
 	n.out = nil;
 	n.alt = nil;
 	n.tail = alloc(c.a, sizeof(*n.tail)) as **nfa;
 	n.ntail = 1;
 	n.tail[0] = n;
 	return n;
 }
 
 func nfa_any(c: *compiler): *nfa {
 	var n: *nfa;
 	n = alloc(c.a, sizeof(*n)) as *nfa;
 	n.id = c.nfa_id;
 	c.nfa_id = c.nfa_id + 1;
 	n.out = nil;
 	n.start = 0;
 	n.end = 255;
 	n.tail = alloc(c.a, sizeof(*n.tail)) as **nfa;
 	n.ntail = 1;
 	n.tail[0] = n;
 	return n;
 }
 
 func lexer_compile(c: *compiler, n: *node, err: *file) {
 	var a: *nfa;
 	var b: *nfa;
 	var d: *dfa;
 
 	n = n.a;
 	loop {
 		if !n {
 			break;
 		}
 
 		b = lexer_compile_rule(c, n.a);
 		a = nfa_alt(c, a, b);
 
 		n = n.b;
 	}
 
 	d = lexer_explode(c, a);
 
 	lexer_codegen(c, d);
 }
 
 func lexer_compile_rule(c: *compiler, n: *node): *nfa {
 	var pat: *node;
 	var act: *node;
 	var a: *nfa;
 	var b: *nfa;
 	var s: *byte;
 
 	pat = n.a;
 	act = n.b;
 
 	a = lexer_compile_pattern(c, pat);
 	b = nfa_empty(c);
 	b.tag = lexer_compile_action(c, act);
 
 	return nfa_concat(c, a, b);
 }
 
 func lexer_compile_action(c: *compiler, n: *node): int {
 	var a: *node;
 	var b: *node;
 	var d: *node;
 	var t: *node;
 	var id: int;
 	var s: *byte;
 	var func_type: *type;
 	var v: *irop;
 	var o: *irop;
 
 	ensure_arr(c.a, (&c.lex_action) as **void, &c.lex_action_cap, c.lex_action_len + 1, sizeof(*c.lex_action));
 	id = c.lex_action_len;
 
 	s = alloc(c.a, 64);
 	memcpy(s, "lexer_action_", 13);
 	int2str(&s[13], id);
 
 	c.lex_action[id] = s;
 	c.lex_action_len = c.lex_action_len + 1;
 
 	b = mknode(c.p, N_IDENT, nil, nil);
 	b.s = "ctx";
 	a = mknode(c.p, N_IDENT, nil, nil);
 	a.s = "lex";
 	a = mknode(c.p, N_PTRTYPE, a, nil);
 	a = mknode(c.p, N_ARGDECL, b, a);
 	a = mknode(c.p, N_ARGLIST, a, nil);
 	b = mknode(c.p, N_IDENT, nil, nil);
 	b.s = "int";
 	a = mknode(c.p, N_FUNCTYPE, a, b);
 	func_type = prototype(c, a);
 	b = mknode(c.p, N_IDENT, nil, nil);
 	b.s = s;
 	a = mknode(c.p, N_FUNCDECL, b, a);
 
 	b = mknode(c.p, N_NUM, nil, nil);
 	b.n = 0;
 	b = mknode(c.p, N_RETURN, b, nil);
 	t = mknode(c.p, N_STMTLIST, b, t);
 
 	d = mknode(c.p, N_IDENT, nil, nil);
 	d.s = "ctx";
 	d = mknode(c.p, N_EXPRLIST, d, nil);
 	b = mknode(c.p, N_IDENT, nil, nil);
 	b.s = "lex_skip";
 	b = mknode(c.p, N_CALL, b, d);
 	t = mknode(c.p, N_STMTLIST, b, t);
 
 	t = mknode(c.p, N_STMTLIST, n, t);
 
 	a = mknode(c.p, N_FUNC, a, t);
 
 	defun(c, a);
 
 	return id + 1;
 }
 
 func lexer_compile_pattern(c: *compiler, n: *node): *nfa {
 	var alt: *node;
 	var a: *nfa;
 	var b: *nfa;
 	var kind: int;
 
 	kind = n.kind;
 	if kind == N_STR {
 		return lexer_compile_str(c, n);
 	} else if kind == N_LEXDOT {
 		return nfa_any(c);
 	} else if kind == N_CHARSET {
 		return lexer_compile_charset(c, n);
 	} else if kind == N_LEXSTAR {
 		a = lexer_compile_pattern(c, n.a);
 		return nfa_star(c, a);
 	} else if kind == N_LEXPLUS {
 		a = lexer_compile_pattern(c, n.a);
 		return nfa_plus(c, a);
 	} else if kind == N_LEXQMARK {
 		a = lexer_compile_pattern(c, n.a);
 		return nfa_qmark(c, a);
 	} else if kind == N_LEXCONCAT {
 		a = lexer_compile_pattern(c, n.a);
 		b = lexer_compile_pattern(c, n.b);
 		return nfa_concat(c, a, b);
 	} else if kind == N_LEXALT {
 		a = lexer_compile_pattern(c, n.a);
 		b = lexer_compile_pattern(c, n.b);
 		return nfa_alt(c, a, b);
 	} else {
 		die("unknown lex node");
 		return nil;
 	}
 }
 
 func lexer_compile_str(c: *compiler, n: *node): *nfa {
 	var i: int;
 	var len: int;
 	var ok: int;
 	var ch: int;
 	var a: *nfa;
 	var b: *nfa;
 
 	i = 0;
 	a = nfa_empty(c);
 	loop {
 		ch = n.s[i] as int;
 		if ch == 0 {
 			break;
 		}
 		b = nfa_lit(c, ch, ch);
 		a = nfa_concat(c, a, b);
 		i = i + 1;
 	}
 	return a;
 }
 
 func parse_charset(a: *alloc, s: *byte, len: int): *byte {
 	var i: int;
 	var j: int;
 	var ch: int;
 	var x: int;
 	var ok: int;
 	var scratch: *byte;
 	var start: int;
 	var end: int;
 
 	scratch = alloc(a, 256);
 
 	i = 0;
 	x = 1;
 
 	if s[i] == '^' as byte {
 		x = 0;
 		j = 0;
 		loop {
 			if j == 256 {
 				break;
 			}
 			scratch[j] = 1 as byte;
 			j = j + 1;
 		}
 		i = i + 1;
 	}
 
 	loop {
 		if i == len {
 			break;
 		}
 
 		ch = s[i] as int;
 		if ch == '\\' {
 			ch = unescape(s, &i, len, &ok);
 			if !ok {
 				die("parse_charset: invalid escape");
 			}
 		} else if ch == '^' {
 			x = 0;
 			i = i + 1;
 			continue;
 		} else {
 			i = i + 1;
 		}
 
 		start = ch;
 		end = ch;
 
 		if i != len && (s[i] as int) == '-' {
 			i = i + 1;
 			ch = unescape(s, &i, len, &ok);
 			if !ok {
 				die("parse_charset: invalid escape");
 			}
 			end = ch;
 		}
 
 		j = start;
 		loop {
 			if j > end {
 				break;
 			}
 
 			scratch[j] = x as byte;
 
 			j = j + 1;
 		}
 	}
 
 	return scratch;
 }
 
 func lexer_compile_charset(c: *compiler, n: *node): *nfa {
 	var scratch: *byte;
 	var j: int;
 	var start: int;
 	var end: int;
 	var a: *nfa;
 	var b: *nfa;
 
 	scratch = n.s;
 
 	j = 0;
 	loop {
 		if j == 256 {
 			break;
 		}
 
 		if !scratch[j] {
 			j = j + 1;
 			continue;
 		}
 
 		start = j;
 
 		loop {
 			if j == 256 || !scratch[j] {
 				break;
 			}
 			j = j + 1;
 		}
 
 		end = j - 1;
 
 		b = nfa_lit(c, start, end);
 		a = nfa_alt(c, a, b);
 	}
 
 	return a;
 }
 
 func nfa_show(n: *nfa) {
 	fputs(nil, "digraph {\n");
 	nfa_show2(n);
 	fputs(nil, "}\n");
 }
 
 func nfa_show2(n: *nfa) {
 	if !n {
 		return;
 	}
 
 	if n.mark {
 		return;
 	}
 
 	n.mark = 1;
 
 	fputd(nil, n.id);
 	if n.tag != 0 {
 		fputs(nil, "[shape=doublecircle]");
 	}
 	fputs(nil, ";\n");
 
 	if n.out {
 		fputd(nil, n.id);
 		fputs(nil, "->");
 		fputd(nil, n.out.id);
 		if n.out.start != -1 {
 			fputs(nil, "[label=\"'");
 			if n.out.start == '"' || n.out.start == '\\' {
 				fputs(nil, "\\");
 			}
 			if n.out.start != 0 {
 				fputc(nil, n.out.start);
 			} else {
 				fputs(nil, "\\0");
 			}
 			fputs(nil, "'\"]");
 		}
 		fputs(nil, ";\n");
 		nfa_show2(n.out);
 	}
 
 	if n.alt {
 		fputd(nil, n.id);
 		fputs(nil, "->");
 		fputd(nil, n.alt.id);
 		if n.alt.start != -1 {
 			fputs(nil, "[label=\"'");
 			if n.alt.start == '"' || n.alt.start == '\\' {
 				fputs(nil, "\\");
 			}
 			if n.alt.start != 0 {
 				fputc(nil, n.alt.start);
 			} else {
 				fputs(nil, "\\0");
 			}
 			fputs(nil, "'\"]");
 		}
 		fputs(nil, ";\n");
 		nfa_show2(n.alt);
 	}
 }
 
 struct dfa {
 	node: rbnode;
 	id: int;
 	link: **dfa;
 	key: **nfa;
 	keylen: int;
 	mark: int;
 	tag: int;
 }
 
 struct dfakey {
 	a: *alloc;
 	live: **nfa;
 	len: int;
 	cap: int;
 	tag: int;
 }
 
 func dfakey_add(k: *dfakey, n: *nfa) {
 	var tmp: **nfa;
 
 	if !n || n.mark {
 		return;
 	}
 	n.mark = 1;
 
 	if !k.tag || (n.tag && n.tag < k.tag) {
 		k.tag = n.tag;
 	}
 
 	if k.len == k.cap {
 		if k.cap == 0 {
 			k.cap = 16;
 		} else {
 			k.cap = k.cap * 2;
 		}
 		tmp = alloc(k.a, sizeof(*k.live) * k.cap) as **nfa;
 		memcpy(tmp as *byte, k.live as *byte, sizeof(*k.live) * k.len);
 		free(k.a, k.live as *byte);
 		k.live = tmp;
 	}
 
 	k.live[k.len] = n;
 	k.len = k.len + 1;
 
 	if n.out && n.out.start == -1 {
 		dfakey_add(k, n.out);
 	}
 	if n.alt && n.alt.start == -1 {
 		dfakey_add(k, n.alt);
 	}
 }
 
 func dfakey_clear(k: *dfakey) {
 	var i: int;
 
 	i = 0;
 	loop {
 		if i == k.len {
 			break;
 		}
 
 		k.live[i].mark = 0;
 
 		i = i + 1;
 	}
 
 	k.tag = 0;
 	k.len = 0;
 }
 
 func dfakey_sort(k: *dfakey) {
 	var i: int;
 	var j: int;
 	var tmp: *nfa;
 
 	i = 1;
 	loop {
 		if i >= k.len {
 			break;
 		}
 		j = i;
 		tmp = k.live[j];
 		loop {
 			if j == 0 || k.live[j - 1].id <= tmp.id {
 				break;
 			}
 			k.live[j] = k.live[j - 1];
 			j = j - 1;
 		}
 		k.live[j] = tmp;
 		i = i + 1;
 	}
 }
 
 func lexer_explode(c: *compiler, n: *nfa): *dfa {
 	var _k: dfakey;
 	var k: *dfakey;
 	var ret: *dfa;
 
 	k = &_k;
 	k.a = c.a;
 
 	if n.start != -1 {
 		die("expected epsilon");
 	}
 
 	dfakey_add(k, n);
 
 	ret = nfa2dfa(c, k);
 
 	free(k.a, k.live as *byte);
 
 	ret = dfa_minimize(c, ret);
 
 	return ret;
 }
 
 func nfa2dfa(c: *compiler, k: *dfakey): *dfa {
 	var d: *dfa;
 	var p: *rbnode;
 	var link: **rbnode;
 	var dir: int;
 	var i: int;
 	var j: int;
 
 	if k.len == 0 {
 		return nil;
 	}
 
 	dfakey_sort(k);
 
 	p = nil;
 	link = &c.dfa_cache;
 	loop {
 		d = (*link) as *dfa;
 		if !d {
 			break;
 		}
 
 		dir = dfa_cmp(k, d);
 
 		if dir < 0 {
 			link = &d.node.left;
 			p = &d.node;
 		} else if dir > 0 {
 			link = &d.node.right;
 			p = &d.node;
 		} else {
 			return d;
 		}
 	}
 
 	d = alloc(c.a, sizeof(*d)) as *dfa;
 	d.link = alloc(c.a, sizeof(*d.link) * 256) as **dfa;
 	d.key = alloc(c.a, sizeof(*d.key) * k.len) as **nfa;
 	d.keylen = k.len;
 	d.id = c.dfa_id;
 	c.dfa_id = c.dfa_id + 1;
 
 	i = 0;
 	loop {
 		if i == k.len {
 			break;
 		}
 		d.key[i] = k.live[i];
 		i = i + 1;
 	}
 	d.tag = k.tag;
 
 	rb_link((&c.dfa_cache) as **rbnode, link, p, &d.node);
 
 	i = 0;
 	loop {
 		if i == 256 {
 			break;
 		}
 
 		dfakey_clear(k);
 		j = 0;
 		loop {
 			if j == d.keylen {
 				break;
 			}
 
 			if d.key[j].out && d.key[j].out.start <= i && d.key[j].out.end >= i {
 				dfakey_add(k, d.key[j].out);
 			}
 			if d.key[j].alt && d.key[j].alt.start <= i && d.key[j].alt.end >= i {
 				dfakey_add(k, d.key[j].alt);
 			}
 
 			j = j + 1;
 		}
 
 		d.link[i] = nfa2dfa(c, k);
 		i = i + 1;
 	}
 
 	return d;
 }
 
 func dfa_cmp(k: *dfakey, d: *dfa): int {
 	var i: int;
 
 	i = 0;
 	loop {
 		if i == k.len && i == d.keylen {
 			break;
 		}
 
 		if i == k.len {
 			return -1;
 		}
 
 		if i == d.keylen {
 			return 1;
 		}
 
 		if k.live[i].id > d.key[i].id {
 			return 1;
 		}
 
 		if k.live[i].id < d.key[i].id {
 			return -1;
 		}
 
 		i = i + 1;
 	}
 
 	return 0;
 }
 
 func dfa_show(d: *dfa) {
 	fputs(nil, "digraph {\n");
 	dfa_show2(d);
 	fputs(nil, "}\n");
 }
 
 func dfa_show2(d: *dfa) {
 	var i: int;
 	var start: int;
 	var end: int;
 	var o: *dfa;
 	if !d || d.mark {
 		return;
 	}
 	d.mark = 1;
 
 	fputd(nil, d.id);
 	if d.tag != 0 {
 		fputs(nil, "[label=\"");
 		fputd(nil, d.tag);
 		fputs(nil, "\" shape=doublecircle]");
 	} else {
 		fputs(nil, "[label=\"\"]");
 	}
 	fputs(nil, ";\n");
 
 	i = 0;
 	loop {
 		if i == 256 {
 			break;
 		}
 
 		if !d.link[i] {
 			i = i + 1;
 			continue;
 		}
 
 		start = i;
 		o = d.link[i];
 
 		loop {
 			if i == 256 || d.link[i] != o {
 				break;
 			}
 			i = i + 1;
 		}
 
 		end = i - 1;
 
 		fputd(nil, d.id);
 		fputs(nil, "->");
 		fputd(nil, o.id);
 		fputs(nil, "[label=\"");
 		if start >= ' ' && start <= '~' && start != '"' && start != '\\' {
 			fputc(nil, start);
 		} else {
 			fputs(nil, "\\\\x");
 			fputh(nil, start >> 4);
 			fputh(nil, start & 15);
 		}
 		if start != end {
 			fputs(nil, "-");
 			if end >= ' ' && end <= '~' && end != '"' && end != '\\' {
 				fputc(nil, end);
 			} else {
 				fputs(nil, "\\\\x");
 				fputh(nil, end >> 4);
 				fputh(nil, end & 15);
 			}
 		}
 		fputs(nil, "\"];\n");
 
 		dfa_show2(o);
 	}
 }
 
 struct dfamin {
 	a: *alloc;
 	sets: **dfaset;
 	nsets: int;
 	capsets: int;
 	queue: *dfaset;
 }
 
 struct dfaset {
 	next: *dfaset;
 	inqueue: int;
 	ind: **dfa;
 	ind_len: int;
 	ind_cap: int;
 	node: *dfa;
 }
 
 func dfa_minimize(c: *compiler, d: *dfa): *dfa {
 	var _ctx: dfamin;
 	var ctx: *dfamin;
 	ctx = &_ctx;
 	ctx.a = c.a;
 	dfamin_setup(ctx, d);
 	dfamin_refine(ctx);
 	return dfamin_extract(ctx, d);
 }
 
 func dfamin_setup(ctx: *dfamin, d: *dfa) {
 	var i: int;
 	var s: *dfaset;
 
 	if !d || d.mark {
 		return;
 	}
 	d.mark = d.tag + 1;
 
 	// Split states classes based on the accepting tag.
 	ensure_arr(ctx.a, (&ctx.sets) as **void, &ctx.capsets, d.tag + 1, sizeof(*ctx.sets));
 	s = ctx.sets[d.tag];
 	if !s {
 		s = alloc(ctx.a, sizeof(*s)) as *dfaset;
 		s.next = ctx.queue;
 		ctx.queue = s;
 		s.inqueue = 1;
 		ctx.sets[d.tag] = s;
 		if d.tag >= ctx.nsets {
 			ctx.nsets = d.tag + 1;
 		}
 	}
 
 	ensure_arr(ctx.a, (&s.ind) as **void, &s.ind_cap, s.ind_len + 1, sizeof(*s.ind));
 	s.ind[s.ind_len] = d;
 	s.ind_len = s.ind_len + 1;
 
 	i = 0;
 	loop {
 		if i == 256 {
 			break;
 		}
 		dfamin_setup(ctx, d.link[i]);
 		i = i + 1;
 	}
 }
 
 func dfamin_refine(ctx: *dfamin) {
 	var s: *dfaset;
 	var i: int;
 	var p: *dfaset;
 	var ch: int;
 	loop {
 		// Remove a set s from the queue
 		s = ctx.queue;
 		if !s {
 			break;
 		}
 		ctx.queue = s.next;
 		s.inqueue = 0;
 
 		i = 0;
 		loop {
 			// For each set p in the partition
 			if i == ctx.nsets {
 				break;
 			}
 			p = ctx.sets[i];
 
 			// For each letter of the alphabet
 			ch = 0;
 			loop {
 				if ch == 256 {
 					break;
 				}
 				dfamin_split(ctx, p, s, ch);
 				ch = ch + 1;
 			}
 
 			i = i + 1;
 		}
 	}
 }
 
 func dfamin_split(ctx: *dfamin, p: *dfaset, s: *dfaset, ch: int) {
 	var i: int;
 	var k: int;
 	var m: int;
 	var d: *dfa;
 	var e: *dfa;
 	var new_ind: **dfa;
 	var t: *dfaset;
 
 	// Count k the states in p that lead to s on ch
 	i = 0;
 	k = 0;
 	loop {
 		if i == p.ind_len {
 			break;
 		}
 		d = p.ind[i];
 
 		e = d.link[ch];
 		if e && ctx.sets[e.mark - 1] == s {
 			k = k + 1;
 		}
 
 		i = i + 1;
 	}
 
 	if k == 0 || k == p.ind_len {
 		return;
 	}
 
 	new_ind = alloc(ctx.a, sizeof(*new_ind) * (p.ind_len - k)) as **dfa;
 
 	// Split nodes into two sets
 	i = 0;
 	k = 0;
 	m = 0;
 	loop {
 		if i == p.ind_len {
 			break;
 		}
 		d = p.ind[i];
 
 		e = d.link[ch];
 		if e && ctx.sets[e.mark - 1] == s {
 			p.ind[k] = d;
 			k = k + 1;
 		} else {
 			new_ind[m] = d;
 			d.mark = ctx.nsets + 1;
 			m = m + 1;
 		}
 
 		i = i + 1;
 	}
 	p.ind_len = k;
 
 	// Create a new set from the nodes that don't lead to p
 	ensure_arr(ctx.a, (&ctx.sets) as **void, &ctx.capsets, ctx.nsets + 1, sizeof(*ctx.sets));
 	t = alloc(ctx.a, sizeof(*t)) as *dfaset;
 	t.next = ctx.queue;
 	t.ind = new_ind;
 	t.ind_len = m;
 	t.ind_cap = m;
 	ctx.queue = t;
 	t.inqueue = 1;
 	ctx.sets[ctx.nsets] = t;
 	ctx.nsets = ctx.nsets + 1;
 
 	// Queue up p
 	if !p.inqueue {
 		p.next = ctx.queue;
 		ctx.queue = p;
 		p.inqueue = 1;
 	}
 }
 
 func dfamin_extract(ctx: *dfamin, d: *dfa): *dfa {
 	var s: *dfaset;
 	var g: *dfa;
 	var ch: int;
 
 	if !d {
 		return nil;
 	}
 
 	s = ctx.sets[d.mark - 1];
 	if s.node {
 		return s.node;
 	}
 
 	g = alloc(ctx.a, sizeof(*g)) as *dfa;
 	g.id = d.mark - 1;
 	g.tag = d.tag;
 	g.link = alloc(ctx.a, sizeof(*g.link) * 256) as **dfa;
 
 	s.node = g;
 
 	ch = 0;
 	loop {
 		if ch == 256 {
 			break;
 		}
 		if d.link[ch] != nil {
 			g.link[ch] = dfamin_extract(ctx, d.link[ch]);
 		}
 		ch = ch + 1;
 	}
 
 	return g;
 }
 
 struct dfa_codegen {
 	a: *alloc;
 	states: **dfa;
 	states_len: int;
 	states_cap: int;
 	tag: **byte;
 	tag_len: int;
 	link: *int;
 	link_len: int;
 }
 
 func lexer_codegen(c: *compiler, d: *dfa) {
 	var _cg: dfa_codegen;
 	var cg: *dfa_codegen;
 	var i: int;
 	var ch: int;
 	cg = &_cg;
 	cg.a = c.a;
 
 	lexer_codegen_setup(cg, d);
 
 	cg.tag_len = cg.states_len * sizeof(*cg.tag);
 	cg.tag = alloc(cg.a, cg.tag_len) as **byte;
 
 	cg.link_len = cg.states_len * 256 * sizeof(*cg.link);
 	cg.link = alloc(cg.a, cg.link_len + 1) as *int;
 
 	i = 0;
 	loop {
 		if i == cg.states_len {
 			break;
 		}
 
 		d = cg.states[i];
 		d.mark = i;
 
 		i = i + 1;
 	}
 
 	i = 0;
 	loop {
 		if i == cg.states_len {
 			break;
 		}
 
 		d = cg.states[i];
 		if d.tag {
 			cg.tag[i] = c.lex_action[d.tag - 1];
 		}
 
 		ch = 0;
 		loop {
 			if ch == 256 {
 				break;
 			}
 
 			if d.link[ch] {
 				cg.link[i * 256 + ch] = d.link[ch].mark;
 			} else {
 				cg.link[i * 256 + ch] = -1;
 			}
 
 			ch = ch + 1;
 		}
 
 		i = i + 1;
 	}
 
 	lexer_output(c, cg);
 }
 
 func lexer_codegen_setup(cg: *dfa_codegen, d: *dfa) {
 	var i: int;
 
 	if !d || d.mark {
 		return;
 	}
 	d.mark = 1;
 
 	ensure_arr(cg.a, (&cg.states) as **void, &cg.states_cap, cg.states_len + 1, sizeof(*cg.states));
 	cg.states[cg.states_len] = d;
 	cg.states_len = cg.states_len + 1;
 
 	i = 0;
 	loop {
 		if i == 256 {
 			break;
 		}
 		lexer_codegen_setup(cg, d.link[i]);
 		i = i + 1;
 	}
 }
 
 func lexer_output(c: *compiler, cg: *dfa_codegen) {
 	var ic: *irfunc;
 	var o: *irop;
 	var ret_type: *type;
 	var func_type: *type;
 
 	ret_type = mktype0(c, TY_INT);
 	ret_type = mktype1(c, TY_PTR, ret_type);
 	func_type = mktype2(c, TY_FUNC, ret_type, nil);
 
 	ic = mkirfunc(c, "get_link_table");
 	o = mkirstr(ic, cg.link as *byte, cg.link_len);
 	irreturn(ic, o);
 	define_ir_func(c, ic, func_type);
 
 	ret_type = mktype0(c, TY_INT);
 	func_type = mktype2(c, TY_FUNC, ret_type, nil);
 
 	ic = mkirfunc(c, "get_num_states");
 	o = mkirconst(ic, cg.states_len);
 	irreturn(ic, o);
 	define_ir_func(c, ic, func_type);
 
 	lexer_compile_get_tag_table(c, cg);
 }
 
 func lexer_compile_get_tag_table(c: *compiler, cg: *dfa_codegen) {
 	var arg1_type: *type;
 	var args_type: *type;
 	var ret_type: *type;
 	var func_type: *type;
 	var ic: *irfunc;
 	var o: *irop;
 	var a: *irop;
 	var b: *irop;
 	var this: *irblock;
 	var next: *irblock;
 	var i: int;
 	var v: *irvar;
 
 	arg1_type = mktype0(c, TY_VOID);
 	arg1_type = mktype1(c, TY_PTR, arg1_type);
 	args_type = mktype1(c, TY_ARG, arg1_type);
 	ret_type = mktype0(c, TY_INT);
 	func_type = mktype2(c, TY_FUNC, ret_type, args_type);
 	arg1_type = mktype1(c, TY_PTR, func_type);
 	args_type = mktype1(c, TY_ARG, arg1_type);
 	ret_type = mktype0(c, TY_VOID);
 	func_type = mktype2(c, TY_FUNC, ret_type, args_type);
 
 	ic = mkirfunc(c, "get_tag_table");
 
 	v = iraddarg(ic, "t", arg1_type);
 
 	i = 0;
 	loop {
 		if i == cg.states_len {
 			break;
 		}
 
 		if cg.tag[i] {
 			a = mkirop(ic, IOP_VAR, nil, nil);
 			a.n = v.n;
 			b = mkirconst(ic, sizeof(i) * i);
 			a = mkirop(ic, IOP_ADD, a, b);
 			a = mkirop(ic, IOP_LOAD, a, nil);
 			b = mkirfuncref(ic, cg.tag[i]);
 			o = mkirop(ic, IOP_STORE, a, b);
 			o.t = arg1_type.val;
 			iraddop(ic, o);
 		}
 
 		i = i + 1;
 	}
 
 	o = mkirconst(ic, 0);
 	irreturn(ic, o);
 
 	define_ir_func(c, ic, func_type);
 }
 
 func get_num_states(): int;
 func get_tag_table(t: *(func(ctx: *void):int));
 func get_link_table(): *int;
 
 struct lex {
 	a: *alloc;
 	c: *compiler;
 
 	tag: *(func(ctx: *lex):int);
 	link: *int;
 
 	fd: int;
 	eof: int;
 	goteof: int;
 
 	buf: *byte;
 	start: int;
 	end: int;
 	fill: int;
 	cap: int;
 
 	skip: int;
 
 	start_lineno: int;
 	start_colno: int;
 	end_lineno: int;
 	end_colno: int;
 
 	_val: lex_sem;
 	val: *lex_sem;
 
 	sem: *lex_sem;
 	sem_len: int;
 
 	stack: *lex_sem;
 	stack_len: int;
 	stack_cap: int;
 }
 
 struct lex_sem {
 	n: *node;
 }
 
 func setup_lex(c: *compiler): *lex {
 	var l: *lex;
 	var i: int;
 	l = alloc(c.a, sizeof(*l)) as *lex;
 	l.a = c.a;
 	l.c = c;
 	i = get_num_states();
 	l.tag = alloc(l.a, sizeof(*l.tag) * i) as *(func(ctx:*lex):int);
 	get_tag_table(l.tag as *(func(ctx: *void):int));
 	l.link = get_link_table();
 	l.fd = 0;
 	l.eof = 1;
 	l.goteof = 1;
 	l.buf = nil;
 	l.start = 0;
 	l.end = 0;
 	l.fill = 0;
 	l.cap = 0;
 	l.start_lineno = 1;
 	l.start_colno = 1;
 	l.end_lineno = 1;
 	l.end_colno = 1;
 	l.val = &l._val;
 	l.sem = nil;
 	l.sem_len = 0;
 	l.stack = nil;
 	l.stack_len = 0;
 	l.stack_cap = 0;
 	ensure_arr(l.a, (&l.stack) as **void, &l.stack_cap, l.stack_len + 2, sizeof(*l.stack));
 	return l;
 }
 
 func open_lex(l: *lex, fd: int) {
 	l.fd = fd;
 	l.eof = 0;
 	l.goteof = 0;
 
 	l.start = 0;
 	l.end = 0;
 	l.fill = 0;
 
 	l.start_lineno = 1;
 	l.start_colno = 1;
 
 	l.end_lineno = 1;
 	l.end_colno = 1;
 }
 
 func lex_skip(l: *lex) {
 	l.skip = 1;
 }
 
 func gettok(l: *lex): int {
 	var state: int;
 	var ch: int;
 	var tag: (func(ctx:*lex):int);
 	var ptr: int;
 	var lineno: int;
 	var colno: int;
 	var ret: int;
 	var tmp: *byte;
 
 	loop {
 		loop {
 			ptr = l.end;
 			lineno = l.end_lineno;
 			colno = l.end_colno;
 
 			l.start = ptr;
 			l.start_lineno = lineno;
 			l.start_colno = colno;
 
 			l.c.lineno = lineno;
 			l.c.colno = colno;
 
 			l.end_lineno = lineno;
 			l.end_colno = colno;
 
 			state = 0;
 			tag = nil;
 			loop {
 				if ptr == l.fill {
 					if l.goteof {
 						if l.start == l.fill {
 							l.eof = 1;
 							return -1;
 						}
 						break;
 					}
 
 					if l.fill - l.start >= (l.cap >> 1) {
 						l.cap = l.cap * 2 + 16 * 1024;
 						tmp = alloc(l.a, l.cap);
 						memcpy(tmp, &l.buf[l.start], l.fill - l.start);
 						free(l.a, l.buf);
 						l.buf = tmp;
 						ptr = ptr - l.start;
 						l.end = l.end - l.start;
 						l.fill = l.fill - l.start;
 						l.start = 0;
 					} else if l.fill >= (l.cap >> 1) {
 						memcpy(l.buf, &l.buf[l.start], l.fill - l.start);
 						ptr = ptr - l.start;
 						l.end = l.end - l.start;
 						l.fill = l.fill - l.start;
 						l.start = 0;
 					}
 
 					ret = read(l.fd, &l.buf[l.fill], l.cap - l.fill);
 					if ret < 0 {
 						die("read failed");
 					}
 
 					if ret == 0 {
 						l.goteof = 1;
 						if l.start == l.fill {
 							l.eof = 1;
 							return -1;
 						}
 						break;
 					}
 
 					l.fill = l.fill + ret;
 				}
 
 				ch = l.buf[ptr] as int;
 				ptr = ptr + 1;
 
 				if ch == '\n' {
 					lineno = lineno + 1;
 					colno = 1;
 				} else {
 					colno = colno + 1;
 				}
 
 				state = l.link[state * 256 + ch];
 				if state == -1 {
 					break;
 				}
 
 				if l.tag[state] {
 					tag = l.tag[state];
 					l.end = ptr;
 					l.end_lineno = lineno;
 					l.end_colno = colno;
 				}
 			}
 
 			if !tag {
 				die("huh");
 				return -1;
 			}
 
 			l.skip = 0;
 			ret = tag(l);
 			if !l.skip {
 				return ret;
 			}
 		}
 	}
 }
 
 func dolex(c: *compiler, name: *byte, out: *file) {
 	var l: *lex;
 	var fd: int;
 	var tok: int;
 	l = setup_lex(c);
 	fd = open(name, 0, 0);
 	if fd < 0 {
 		die("open failed");
 	}
 	open_lex(l, fd);
 	loop {
 		tok = gettok(l);
 		if tok < 0 {
 			die("problem");
 		}
 		if tok == 0 {
 			return;
 		}
 		fputs(out, "\t'");
 		fputb(out, &l.buf[l.start], l.end - l.start);
 		fputs(out, "'\n");
 	}
 }