os

lalr.om (27975B)

---

 // Aho, A.V., Sethi, R. and Ullman, J.D. (2007) Compilers: Principles, techniques, and Tools. Reading, Mass: Addison-Wesley.
 
 struct lalr_ctx {
 	x: int;
 }
 
 struct lalr_item {
 	node: rbnode;
 	queue_next: *lalr_item;
 	prod: int;
 	alt: int;
 	point: int;
 	look: *rbnode;
 }
 
 struct lalr_itemset {
 	node: rbnode;
 	id: int;
 	items: *rbnode;
 	closure: *rbnode;
 	goto_next: *lalr_itemset;
 	goto_out: *rbnode;
 	mark: int;
 }
 
 struct lalr_point {
 	node: rbnode;
 	term: int;
 	id: int;
 	name: *byte;
 	out: *lalr_itemset;
 }
 
 struct lalr_alt {
 	prod: int;
 	id: int;
 	point: *lalr_point;
 	point_len: int;
 	point_cap: int;
 }
 
 struct lalr_prod {
 	node: rbnode;
 	id: int;
 	name: *byte;
 
 	use: *lalr_itemset;
 	epsilon: int;
 	first: *rbnode;
 
 	in_queue: int;
 	queue_next: *lalr_prod;
 
 	alt: **lalr_alt;
 	alt_len: int;
 	alt_cap: int;
 
 	action: *byte;
 	pos: int;
 }
 
 struct lalr_compiler {
 	a: *alloc;
 	c: *compiler;
 	err: *file;
 
 	prod_name: *rbnode;
 	prod: **lalr_prod;
 	prod_len: int;
 	prod_cap: int;
 
 	sets: *rbnode;
 	root: *lalr_itemset;
 	goto_queue: *lalr_itemset;
 
 	term_len: int;
 	sets_len: int;
 
 	act_table_len: int;
 	act_table: *int;
 	goto_table_len: int;
 	goto_table: *int;
 }
 
 func lalr_compiler(c: *compiler, pn: *node, err: *file) {
 	var _lc: lalr_compiler;
 	var lc: *lalr_compiler;
 	lc = &_lc;
 	lc.a = c.a;
 	lc.c = c;
 	lc.err = err;
 	lalr_rules(lc, pn);
 	lalr_items(lc);
 	lalr_first(lc);
 	lalr_lookahead(lc);
 	lalr_codegen(lc);
 	lalr_output(lc);
 }
 
 func lalr_mkprod(lc: *lalr_compiler): *lalr_prod {
 	var p: *lalr_prod;
 	ensure_arr(lc.a, (&lc.prod) as **void, &lc.prod_cap, lc.prod_len + 1, sizeof(*lc.prod));
 	p = alloc(lc.a, sizeof(*p)) as *lalr_prod;
 	p.id = lc.prod_len;
 	p.use = lalr_mkitemset(lc);
 	lc.prod[lc.prod_len] = p;
 	lc.prod_len = lc.prod_len + 1;
 	return p;
 }
 
 func lalr_lookup(lc: *lalr_compiler, name: *byte, new: *lalr_prod): *lalr_prod {
 	var p: *rbnode;
 	var link: **rbnode;
 	var d: *lalr_prod;
 	var dir: int;
 
 	p = nil;
 	link = &lc.prod_name;
 	loop {
 		d = (*link) as *lalr_prod;
 		if !d {
 			break;
 		}
 
 		dir = strcmp(d.name, name);
 		if dir == 0 {
 			break;
 		} else if dir < 0 {
 			link = &d.node.left;
 			p = &d.node;
 		} else {
 			link = &d.node.right;
 			p = &d.node;
 		}
 	}
 
 	if !new {
 		return d;
 	}
 
 	if d {
 		die("duplicate rule");
 	}
 
 	new.name = name;
 	rb_link(&lc.prod_name, link, p, &new.node);
 	return new;
 }
 
 func lalr_rules(lc: *lalr_compiler, pn: *node) {
 	var rule: *node;
 	var root: *lalr_prod;
 	var p: *lalr_prod;
 	var a: *lalr_alt;
 	var i: int;
 
 	root = lalr_mkprod(lc);
 
 	rule = pn.a;
 	loop {
 		if !rule {
 			break;
 		}
 		p = lalr_mkprod(lc);
 		lalr_lookup(lc, rule.a.a.s, p);
 		rule = rule.b;
 	}
 
 	i = 1;
 	rule = pn.a;
 	loop {
 		if !rule {
 			break;
 		}
 		p = lc.prod[i];
 		lalr_pattern(lc, p, rule.a.b);
 		rule = rule.b;
 		i = i + 1;
 	}
 
 	a = lalr_mkalt(lc, root);
 	lalr_alt_nonterminal(lc, a, lc.prod[1]);
 }
 
 func lalr_pattern(lc: *lalr_compiler, p: *lalr_prod, pn: *node) {
 	var a: *lalr_alt;
 	loop {
 		if !pn {
 			break;
 		}
 		a = lalr_mkalt(lc, p);
 		lalr_alt(lc, a, pn.a);
 		pn = pn.b;
 	}
 }
 
 func lalr_alt(lc: *lalr_compiler, a: *lalr_alt, pn: *node) {
 	loop {
 		if !pn {
 			break;
 		}
 		lalr_primary(lc, a, pn.a);
 		pn = pn.b;
 	}
 }
 
 func lalr_primary(lc: *lalr_compiler, a: *lalr_alt, pn: *node) {
 	var v: *decl;
 	var s: *lalr_prod;
 
 	if pn.kind == N_IDENT {
 		s = lalr_lookup(lc, pn.s, nil);
 		if s {
 			lalr_alt_nonterminal(lc, a, s);
 			return;
 		}
 
 		v = find(lc.c, pn.s, nil, 0);
 		if !v || !v.enum_defined {
 			fputs(lc.err, "name: ");
 			fputs(lc.err, pn.s);
 			fputs(lc.err, "\n");
 			die("undefined terminal");
 		}
 
 		lalr_alt_terminal(lc, a, pn.s, v.enum_value);
 		return;
 	}
 
 	lalr_action(lc, a, pn);
 }
 
 func lalr_action(lc: *lalr_compiler, a: *lalr_alt, pn: *node) {
 	var s: *byte;
 	var b: *node;
 	var d: *node;
 	var n: *node;
 	var c: *node;
 	var j: int;
 	var ch: byte;
 	var x: int;
 	var prod: *lalr_prod;
 	var alt: *lalr_alt;
 	s = alloc(lc.a, 64);
 	n = mknode0(lc.c.p, N_IDENT);
 	memcpy(s, "lalr_action_", 12);
 	prod = lalr_mkprod(lc);
 	prod.pos = a.point_len;
 	prod.action = s;
 	int2str(&s[12], prod.id);
 	n.s = s;
 	c = mknode0(lc.c.p, N_IDENT);
 	c.s = "ctx";
 	b = mknode0(lc.c.p, N_IDENT);
 	b.s = "lex";
 	b = mknode1(lc.c.p, N_PTRTYPE, b);
 	b = mknode(lc.c.p, N_ARGDECL, c, b);
 	b = mknode1(lc.c.p, N_ARGLIST, b);
 	b = mknode(lc.c.p, N_FUNCTYPE, b, nil);
 	d = mknode(lc.c.p, N_FUNCDECL, n, b);
 	n = mknode(lc.c.p, N_FUNC, d, pn);
 	defun(lc.c, n);
 	alt = lalr_mkalt(lc, prod);
 	lalr_alt_nonterminal(lc, a, prod);
 }
 
 func lalr_mkalt(lc: *lalr_compiler, p: *lalr_prod): *lalr_alt {
 	var a: *lalr_alt;
 	a = alloc(lc.a, sizeof(*a)) as *lalr_alt;
 	a.id = p.alt_len;
 	a.prod = p.id;
 	ensure_arr(lc.a, (&p.alt) as **void, &p.alt_cap, p.alt_len + 1, sizeof(*p.alt));
 	p.alt[p.alt_len] = a;
 	p.alt_len = p.alt_len + 1;
 	return a;
 }
 
 func lalr_alt_terminal(lc: *lalr_compiler, a: *lalr_alt, name: *byte, id: int) {
 	var i: int;
 	ensure_arr(lc.a, (&a.point) as **void, &a.point_cap, a.point_len + 1, sizeof(*a.point));
 	i = a.point_len;
 	a.point_len = a.point_len + 1;
 	a.point[i].term = 1;
 	a.point[i].id = id;
 	a.point[i].name = name;
 	if id < 0 {
 		die("invalid terminal");
 	}
 	if lc.term_len <= id {
 		lc.term_len = id + 1;
 	}
 }
 
 func lalr_alt_nonterminal(lc: *lalr_compiler, a: *lalr_alt, s: *lalr_prod) {
 	var use: lalr_item;
 	var i: int;
 	ensure_arr(lc.a, (&a.point) as **void, &a.point_cap, a.point_len + 1, sizeof(*a.point));
 	i = a.point_len;
 	a.point_len = a.point_len + 1;
 	a.point[i].term = 0;
 	a.point[i].id = s.id;
 	a.point[i].name = s.name;
 	use.prod = a.prod;
 	use.alt = 0;
 	use.point = 0;
 	lalr_assoc(lc, s.use, &use);
 }
 
 func lalr_show(lc: *lalr_compiler) {
 	var i: int;
 	var j: int;
 	var k: int;
 	var p: *lalr_prod;
 	var a: *lalr_alt;
 	var t: *lalr_point;
 	var out: *file;
 
 	i = 0;
 	loop {
 		if i == lc.prod_len {
 			break;
 		}
 
 		p = lc.prod[i];
 
 		j = 0;
 		loop {
 			if j == p.alt_len {
 				break;
 			}
 
 			a = p.alt[j];
 
 			if p.name {
 				fputs(out, p.name);
 			} else {
 				fputd(out, i);
 			}
 
 			fputs(out, " -> ");
 
 			k = 0;
 			loop {
 				if k == a.point_len {
 					break;
 				}
 
 				t = &a.point[k];
 				if t.name {
 					fputs(out, t.name);
 				} else {
 					fputd(out, t.id);
 				}
 				fputs(out, " ");
 
 				k = k + 1;
 			}
 
 			fputs(out, "\n");
 
 			j = j + 1;
 		}
 
 		i = i + 1;
 	}
 }
 
 func lalr_mkitemset(lc: *lalr_compiler): *lalr_itemset {
 	var i: *lalr_itemset;
 	i = alloc(lc.a, sizeof(*i)) as *lalr_itemset;
 	return i;
 }
 
 func lalr_itemcmp(a: *lalr_item, b: *lalr_item): int {
 	if a.prod < b.prod {
 		return -1;
 	} else if a.prod > b.prod {
 		return 1;
 	} else if a.alt < b.alt {
 		return -1;
 	} else if a.alt > b.alt {
 		return 1;
 	} else if a.point < b.point {
 		return -1;
 	} else if a.point > b.point {
 		return 1;
 	}
 	return 0;
 }
 
 func lalr_itemsetcmp(a: *lalr_itemset, b: *lalr_itemset): int {
 	var x: *lalr_item;
 	var y: *lalr_item;
 	var dir: int;
 	x = rb_first(a.items) as *lalr_item;
 	y = rb_first(b.items) as *lalr_item;
 	loop {
 		if !x && !y {
 			return 0;
 		} else if !x {
 			return -1;
 		} else if !y {
 			return 1;
 		}
 		dir = lalr_itemcmp(x, y);
 		if dir != 0 {
 			return dir;
 		}
 		x = rb_next(&x.node) as *lalr_item;
 		y = rb_next(&y.node) as *lalr_item;
 	}
 }
 
 func lalr_assoc(lc: *lalr_compiler, i: *lalr_itemset, t: *lalr_item): *lalr_item {
 	var p: *rbnode;
 	var link: **rbnode;
 	var d: *lalr_item;
 	var dir: int;
 	p = nil;
 	link = &i.items;
 	loop {
 		d = (*link) as *lalr_item;
 		if !d {
 			break;
 		}
 		dir = lalr_itemcmp(t, d);
 		if dir < 0 {
 			link = &d.node.left;
 			p = &d.node;
 		} else if dir > 0 {
 			link = &d.node.right;
 			p = &d.node;
 		} else {
 			return nil;
 		}
 	}
 	d = alloc(lc.a, sizeof(*d)) as *lalr_item;
 	d.prod = t.prod;
 	d.alt = t.alt;
 	d.point = t.point;
 	rb_link(&i.items, link, p, &d.node);
 	return d;
 }
 
 func lalr_items(lc: *lalr_compiler) {
 	var i: *lalr_itemset;
 	var init_state: lalr_item;
 
 	i = lalr_mkitemset(lc);
 	lalr_assoc(lc, i, &init_state);
 	lc.root = lalr_memoset(lc, i);
 
 	loop {
 		i = lc.goto_queue;
 		if !i {
 			break;
 		}
 		lc.goto_queue = i.goto_next;
 		lalr_goto(lc, i);
 	}
 }
 
 func lalr_goto(lc: *lalr_compiler, i: *lalr_itemset) {
 	var t: *lalr_item;
 	var a: *lalr_item;
 	var seen: *lalr_itemset;
 	var queue: *lalr_item;
 	var prod: *lalr_prod;
 	var alt: *lalr_alt;
 	var sym: *lalr_point;
 	var r: lalr_item;
 	var j: int;
 
 	seen = lalr_mkitemset(lc);
 
 	// Queue up the items from the current state
 	t = rb_first(i.items) as *lalr_item;
 	loop {
 		if !t {
 			break;
 		}
 		a = lalr_assoc(lc, seen, t);
 		if a {
 			a.queue_next = queue;
 			queue = a;
 		}
 		t = rb_next(&t.node) as *lalr_item;
 	}
 
 	loop {
 		t = queue;
 		if !t {
 			break;
 		}
 		queue = t.queue_next;
 
 		alt = lc.prod[t.prod].alt[t.alt];
 		if t.point == alt.point_len {
 			continue;
 		}
 
 		// That symbol is the edge in the graph
 		sym = &alt.point[t.point];
 
 		r.prod = t.prod;
 		r.alt = t.alt;
 		r.point = t.point + 1;
 
 		lalr_assoc(lc, seen, &r);
 
 		lalr_linkout(lc, &i.goto_out, sym, &r);
 		if sym.term {
 			continue;
 		}
 
 		prod = lc.prod[sym.id];
 
 		j = 0;
 		loop {
 			if j == prod.alt_len {
 				break;
 			}
 
 			r.prod = sym.id;
 			r.alt = j;
 			r.point = 0;
 
 			a = lalr_assoc(lc, seen, &r);
 			if a {
 				a.queue_next = queue;
 				queue = a;
 			}
 
 			j = j + 1;
 		}
 	}
 
 	sym = rb_first(i.goto_out) as *lalr_point;
 	loop {
 		if !sym {
 			break;
 		}
 		sym.out = lalr_memoset(lc, sym.out);
 		sym = rb_next(&sym.node) as *lalr_point;
 	}
 }
 
 func lalr_pointcmp(a: *lalr_point, b: *lalr_point): int {
 	if a.term < b.term {
 		return -1;
 	} else if a.term > b.term {
 		return 1;
 	} else if a.id < b.id {
 		return -1;
 	} else if a.id > b.id {
 		return 1;
 	}
 	return 0;
 }
 
 func lalr_linkout(lc: *lalr_compiler, out: **rbnode, sym: *lalr_point, t: *lalr_item) {
 	var p: *rbnode;
 	var link: **rbnode;
 	var d: *lalr_point;
 	var dir: int;
 	p = nil;
 	link = out;
 	loop {
 		d = (*link) as *lalr_point;
 		if !d {
 			break;
 		}
 		dir = lalr_pointcmp(sym, d);
 		if dir < 0 {
 			link = &d.node.left;
 			p = &d.node;
 		} else if dir > 0 {
 			link = &d.node.right;
 			p = &d.node;
 		} else {
 			lalr_assoc(lc, d.out, t);
 			return;
 		}
 	}
 	d = alloc(lc.a, sizeof(*d)) as *lalr_point;
 	d.term = sym.term;
 	d.id = sym.id;
 	d.name = sym.name;
 	d.out = lalr_mkitemset(lc);
 	rb_link(out, link, p, &d.node);
 	lalr_assoc(lc, d.out, t);
 }
 
 func lalr_memoset(lc: *lalr_compiler, i: *lalr_itemset): *lalr_itemset {
 	var p: *rbnode;
 	var link: **rbnode;
 	var d: *lalr_itemset;
 	var dir: int;
 	p = nil;
 	link = &lc.sets;
 	loop {
 		d = (*link) as *lalr_itemset;
 		if !d {
 			break;
 		}
 		dir = lalr_itemsetcmp(i, 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;
 		}
 	}
 	rb_link(&lc.sets, link, p, &i.node);
 	i.goto_next = lc.goto_queue;
 	i.id = lc.sets_len;
 	lc.sets_len = lc.sets_len + 1;
 	lc.goto_queue = i;
 	return i;
 }
 
 func lalr_showlr(lc: *lalr_compiler) {
 	lalr_showlr2(lc, lc.root);
 }
 
 func lalr_showlr2(lc: *lalr_compiler, i: *lalr_itemset): int {
 	var t: *lalr_item;
 	var sym: *lalr_point;
 	var prod: *lalr_prod;
 	var alt: *lalr_alt;
 	var l: *lalr_point;
 	var j: int;
 	var out: *file;
 	var k: int;
 
 	if i.mark {
 		return i.mark;
 	}
 	i.mark = 1;
 
 	fputd(out, i.id);
 	fputs(out, "{");
 
 	t = rb_first(i.items) as *lalr_item;
 	loop {
 		if !t {
 			break;
 		}
 
 		prod = lc.prod[t.prod];
 		alt = prod.alt[t.alt];
 
 		fputs(out, "[");
 		if prod.name {
 			fputs(out, prod.name);
 		} else {
 			fputd(out, prod.id);
 		}
 
 		fputs(out, "->");
 		k = 0;
 		loop {
 			if k == t.point {
 				fputs(out, "!");
 			}
 			if k == alt.point_len {
 				break;
 			}
 			sym = &alt.point[k];
 			if sym.name {
 				fputs(out, sym.name);
 			} else {
 				fputd(out, sym.id);
 			}
 			k = k + 1;
 			if k != alt.point_len && k != t.point {
 				fputc(out, ' ');
 			}
 		}
 		fputs(out, "]");
 
 		if t.point == alt.point_len {
 			fputs(out, "{");
 			l = rb_first(t.look) as *lalr_point;
 			loop {
 				if !l {
 					break;
 				}
 				fputs(out, l.name);
 				l = rb_next(&l.node) as *lalr_point;
 				if l {
 					fputs(out, " ");
 				}
 			}
 			fputs(out, "}");
 		}
 
 		t = rb_next(&t.node) as *lalr_item;
 
 		if t {
 			fputs(out, ",");
 		}
 	}
 
 	fputs(out, "};\n");
 
 	sym = rb_first(i.goto_out) as *lalr_point;
 	loop {
 		if !sym {
 			break;
 		}
 		j = lalr_showlr2(lc, sym.out);
 		fputd(out, i.id);
 		fputs(out, "->");
 		fputd(out, j);
 		fputs(out, "[");
 		if sym.name {
 			fputs(out, sym.name);
 		} else {
 			fputd(out, sym.id);
 		}
 		fputs(out, "]");
 		fputs(out, ";\n");
 		sym = rb_next(&sym.node) as *lalr_point;
 	}
 
 	return i.id;
 }
 
 struct lalr_look {
 	next: *lalr_look;
 	item: lalr_item;
 	itemset: *lalr_itemset;
 	look: **rbnode;
 	_look: *rbnode;
 }
 
 func lalr_lookahead(lc: *lalr_compiler) {
 	var queue: *lalr_look;
 	var w: *lalr_look;
 	var q: *lalr_look;
 	var r: lalr_point;
 	var sym: *lalr_point;
 	var rest_sym: *lalr_point;
 	var alt: *lalr_alt;
 	var prod: *lalr_prod;
 	var rest_prod: *lalr_prod;
 	var i: *lalr_itemset;
 	var j: int;
 	var k: int;
 	var epsilon: int;
 
 	r.term = 1;
 	r.id = lc.term_len;
 	r.name = "$";
 	lc.term_len = lc.term_len + 1;
 
 	w = alloc(lc.a, sizeof(*w)) as *lalr_look;
 	w.item.prod = 0;
 	w.item.alt = 0;
 	w.item.point = 0;
 	w.itemset = lc.root;
 	w.look = &w._look;
 	w._look = &r.node;
 	queue = w;
 
 	loop {
 		w = queue;
 		if !w {
 			break;
 		}
 
 		if !lalr_unionlook(lc, w) {
 			queue = w.next;
 			continue;
 		}
 
 		alt = lc.prod[w.item.prod].alt[w.item.alt];
 		if w.item.point == alt.point_len {
 			queue = w.next;
 			continue;
 		}
 
 		i = w.itemset;
 
 		sym = &alt.point[w.item.point];
 		lalr_findout(lc, w, sym);
 		if sym.term {
 			continue;
 		}
 		prod = lc.prod[sym.id];
 
 		epsilon = 1;
 		j = 0;
 		loop {
 			if j == prod.alt_len {
 				break;
 			}
 			alt = prod.alt[j];
 
 			k = w.item.point;
 			loop {
 				if k == lc.prod[w.item.prod].alt[w.item.alt].point_len {
 					break;
 				}
 				rest_sym = &lc.prod[w.item.prod].alt[w.item.alt].point[k];
 
 				if rest_sym.term {
 					q = alloc(lc.a, sizeof(*q)) as *lalr_look;
 					q.item.prod = sym.id;
 					q.item.alt = j;
 					q.item.point = 0;
 					q.itemset = i;
 					q.look = &q._look;
 					q._look = &rest_sym.node;
 					q.next = queue;
 					queue = q;
 					epsilon = 0;
 					break;
 				} else {
 					rest_prod = lc.prod[rest_sym.id];
 					q = alloc(lc.a, sizeof(*q)) as *lalr_look;
 					q.item.prod = sym.id;
 					q.item.alt = j;
 					q.item.point = 0;
 					q.itemset = i;
 					q.look = &rest_prod.first;
 					q.next = queue;
 					queue = q;
 					if !rest_prod.epsilon {
 						epsilon = 0;
 						break;
 					}
 				}
 
 				k = k + 1;
 			}
 
 			j = j + 1;
 		}
 
 		if !epsilon {
 			continue;
 		}
 
 		j = 0;
 		loop {
 			if j == prod.alt_len {
 				break;
 			}
 			alt = prod.alt[j];
 
 			q = alloc(lc.a, sizeof(*q)) as *lalr_look;
 			q.item.prod = sym.id;
 			q.item.alt = j;
 			q.item.point = 0;
 			q.itemset = i;
 			q.look = w.look;
 			q.next = queue;
 			queue = q;
 
 			j = j + 1;
 		}
 	}
 }
 
 func lalr_unionlook(lc: *lalr_compiler, w: *lalr_look): int {
 	var s: *rbnode;
 	var t: *lalr_item;
 	var ret: int;
 
 	t = lalr_finditem(lc, w.itemset, &w.item);
 
 	s = rb_first(*w.look);
 	loop {
 		if !s {
 			break;
 		}
 
 		if lalr_addlook(lc, &t.look, s as *lalr_point) {
 			ret = 1;
 		}
 
 		s = rb_next(s);
 	}
 
 	w.look = &t.look;
 	return ret;
 }
 
 func lalr_addlook(lc: *lalr_compiler, out: **rbnode, sym: *lalr_point): int {
 	var p: *rbnode;
 	var link: **rbnode;
 	var d: *lalr_point;
 	var dir: int;
 	p = nil;
 	link = out;
 	loop {
 		d = (*link) as *lalr_point;
 		if !d {
 			break;
 		}
 		dir = lalr_pointcmp(sym, d);
 		if dir < 0 {
 			link = &d.node.left;
 			p = &d.node;
 		} else if dir > 0 {
 			link = &d.node.right;
 			p = &d.node;
 		} else {
 			return 0;
 		}
 	}
 	d = alloc(lc.a, sizeof(*d)) as *lalr_point;
 	d.term = sym.term;
 	d.id = sym.id;
 	d.name = sym.name;
 	rb_link(out, link, p, &d.node);
 	return 1;
 }
 
 func lalr_findout(lc: *lalr_compiler, w: *lalr_look, sym: *lalr_point) {
 	var d: *lalr_point;
 	var r: lalr_item;
 	var dir: int;
 	d = w.itemset.goto_out as *lalr_point;
 	loop {
 		dir = lalr_pointcmp(sym, d);
 		if dir < 0 {
 			d = d.node.left as *lalr_point;
 		} else if dir > 0 {
 			d = d.node.right as *lalr_point;
 		} else {
 			break;
 		}
 	}
 	w.itemset = d.out;
 	w.item.point = w.item.point + 1;
 }
 
 func lalr_finditem(lc: *lalr_compiler, itemset: *lalr_itemset, item: *lalr_item): *lalr_item {
 	var p: *rbnode;
 	var link: **rbnode;
 	var d: *lalr_item;
 	var dir: int;
 
 	d = (*itemset).items as *lalr_item;
 	loop {
 		if !d {
 			break;
 		}
 		dir = lalr_itemcmp(item, d);
 		if dir < 0 {
 			d = d.node.left as *lalr_item;
 		} else if dir > 0 {
 			d = d.node.right as *lalr_item;
 		} else {
 			return d;
 		}
 	}
 
 	p = nil;
 	link = &(*itemset).closure;
 	loop {
 		d = (*link) as *lalr_item;
 		if !d {
 			break;
 		}
 		dir = lalr_itemcmp(item, 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(lc.a, sizeof(*d)) as *lalr_item;
 	d.prod = item.prod;
 	d.alt = item.alt;
 	d.point = item.point;
 	rb_link(&(*itemset).closure, link, p, &d.node);
 
 	return d;
 }
 
 func lalr_first(lc: *lalr_compiler) {
 	var use: *lalr_item;
 	var p: *lalr_prod;
 	var queue: *lalr_prod;
 	var prod: *lalr_prod;
 	var alt: *lalr_alt;
 	var sym: *lalr_point;
 	var ref: *lalr_prod;
 	var i: int;
 	var j: int;
 	var k: int;
 
 	i = 0;
 	loop {
 		if i == lc.prod_len {
 			break;
 		}
 
 		j = 0;
 		loop {
 			if j == lc.prod[i].alt_len {
 				break;
 			}
 
 			if lc.prod[i].alt[j].point_len == 0 {
 				lc.prod[i].epsilon = 1;
 				j = j + 1;
 				continue;
 			}
 
 			if lc.prod[i].alt[j].point[0].term {
 				lalr_addlook(lc, &lc.prod[i].first, &lc.prod[i].alt[j].point[0]);
 			}
 
 			j = j + 1;
 		}
 
 		lc.prod[i].in_queue = 1;
 		lc.prod[i].queue_next = queue;
 		queue = lc.prod[i];
 
 		i = i + 1;
 	}
 
 	loop {
 		p = queue;
 		if !p {
 			break;
 		}
 		p.in_queue = 0;
 		queue = p.queue_next;
 
 		use = rb_first(p.use.items) as *lalr_item;
 		loop {
 			if !use {
 				break;
 			}
 			i = use.prod;
 			prod = lc.prod[i];
 
 			j = 0;
 			loop {
 				if j == prod.alt_len {
 					break;
 				}
 				alt = prod.alt[j];
 
 				k = 0;
 				loop {
 					if k == alt.point_len {
 						if !prod.epsilon {
 							prod.epsilon = 1;
 							if !prod.in_queue {
 								prod.in_queue = 1;
 								prod.queue_next = queue;
 								queue = prod;
 							}
 						}
 						break;
 					}
 					sym = &alt.point[k];
 
 					if sym.term {
 						if lalr_add_first(lc, &prod.first, sym) {
 							if !prod.in_queue {
 								prod.in_queue = 1;
 								prod.queue_next = queue;
 								queue = prod;
 							}
 						}
 						break;
 					} else {
 						ref = lc.prod[sym.id];
 
 						if lalr_union_first(lc, &prod.first, ref.first) {
 							if !prod.in_queue {
 								prod.in_queue = 1;
 								prod.queue_next = queue;
 								queue = prod;
 							}
 						}
 
 						if !ref.epsilon {
 							break;
 						}
 					}
 
 					k = k + 1;
 				}
 
 				j = j + 1;
 			}
 
 			use = rb_next(&use.node) as *lalr_item;
 		}
 	}
 }
 
 func lalr_add_first(lc: *lalr_compiler, out: **rbnode, sym: *lalr_point): int {
 	var p: *rbnode;
 	var link: **rbnode;
 	var d: *lalr_point;
 	var dir: int;
 	p = nil;
 	link = out;
 	loop {
 		d = (*link) as *lalr_point;
 		if !d {
 			break;
 		}
 		dir = lalr_pointcmp(sym, d);
 		if dir < 0 {
 			link = &d.node.left;
 			p = &d.node;
 		} else if dir > 0 {
 			link = &d.node.right;
 			p = &d.node;
 		} else {
 			return 0;
 		}
 	}
 	d = alloc(lc.a, sizeof(*d)) as *lalr_point;
 	d.term = sym.term;
 	d.id = sym.id;
 	d.name = sym.name;
 	rb_link(out, link, p, &d.node);
 	return 1;
 }
 
 func lalr_union_first(lc: *lalr_compiler, out: **rbnode, src: *rbnode): int {
 	var s: *rbnode;
 	var t: *lalr_item;
 	var ret: int;
 
 	s = rb_first(src);
 	loop {
 		if !s {
 			break;
 		}
 
 		if lalr_add_first(lc, out, s as *lalr_point) {
 			ret = 1;
 		}
 
 		s = rb_next(s);
 	}
 
 	return ret;
 }
 
 func lalr_show_first(lc: *lalr_compiler) {
 	var i: int;
 	var p: *lalr_prod;
 	var d: *lalr_point;
 	var out: *file;
 
 	i = 0;
 	loop {
 		if i == lc.prod_len {
 			break;
 		}
 		p = lc.prod[i];
 
 		if p.name {
 			fputs(out, p.name);
 		} else {
 			fputd(out, i);
 		}
 
 		fputs(out, "->{");
 
 		if p.epsilon {
 			fputs(out, "e");
 
 			if p.first {
 				fputs(out, " ");
 			}
 		}
 
 		d = rb_first(p.first) as *lalr_point;
 		loop {
 			if !d {
 				break;
 			}
 
 			if d.name {
 				fputs(out, d.name);
 			} else {
 				fputd(out, d.id);
 			}
 
 			d = rb_next(&d.node) as *lalr_point;
 
 			if d {
 				fputs(out, " ");
 			}
 		}
 
 		fputs(out, "}\n");
 
 		i = i + 1;
 	}
 }
 
 func lalr_codegen(lc: *lalr_compiler) {
 	var i: *lalr_itemset;
 	var t: *lalr_item;
 	var next_tree: *rbnode;
 	var len: int;
 	var sym: *lalr_point;
 	var action: int;
 
 	lc.act_table_len = sizeof(*lc.act_table) * lc.sets_len * lc.term_len;
 	lc.act_table = alloc(lc.a, lc.act_table_len) as *int;
 	lc.goto_table_len = sizeof(*lc.goto_table) * lc.sets_len * lc.prod_len;
 	lc.goto_table = alloc(lc.a, lc.goto_table_len) as *int;
 
 	i = rb_first(lc.sets) as *lalr_itemset;
 	loop {
 		if !i {
 			break;
 		}
 
 		sym = rb_first(i.goto_out) as *lalr_point;
 		loop {
 			if !sym {
 				break;
 			}
 
 			if sym.term {
 				lc.act_table[i.id * lc.term_len + sym.id] = (sym.out.id << 8) + 's';
 			} else {
 				lc.goto_table[i.id * lc.prod_len + sym.id] = sym.out.id;
 			}
 
 			sym = rb_next(&sym.node) as *lalr_point;
 		}
 
 		t = rb_first(i.items) as *lalr_item;
 		next_tree = i.closure;
 		loop {
 			if !t {
 				if next_tree {
 					t = rb_first(next_tree) as *lalr_item;
 					next_tree = nil;
 					continue;
 				}
 				break;
 			}
 
 			len = lc.prod[t.prod].alt[t.alt].point_len;
 			if t.point != len {
 				t = rb_next(&t.node) as *lalr_item;
 				continue;
 			}
 
 			sym = rb_first(t.look) as *lalr_point;
 			loop {
 				if !sym {
 					break;
 				}
 
 				if lc.act_table[i.id * lc.term_len + sym.id] {
 					fputc(nil, lc.act_table[i.id * lc.term_len + sym.id]);
 					die("/reduce conflict");
 				}
 
 				if t.prod == 0 && t.alt == 0 && t.point == 1 {
 					lc.act_table[i.id * lc.term_len + sym.id] = 'a';
 				} else {
 					lc.act_table[i.id * lc.term_len + sym.id] = (len << 32) + (t.prod << 8) + 'r';
 				}
 
 				sym = rb_next(&sym.node) as *lalr_point;
 			}
 
 			t = rb_next(&t.node) as *lalr_item;
 		}
 
 		i = rb_next(&i.node) as *lalr_itemset;
 	}
 
 	if lc.prod[1].epsilon {
 		lc.act_table[0] = 'a';
 	}
 }
 
 func lalr_output(lc: *lalr_compiler) {
 	var ic: *irfunc;
 	var o: *irop;
 	var ret_type: *type;
 	var func_type: *type;
 
 	ret_type = mktype0(lc.c, TY_INT);
 	ret_type = mktype1(lc.c, TY_PTR, ret_type);
 
 	func_type = mktype2(lc.c, TY_FUNC, ret_type, nil);
 
 	ic = mkirfunc(lc.c, "get_act_table");
 	o = mkirstr(ic, lc.act_table as *byte, lc.act_table_len);
 	irreturn(ic, o);
 	define_ir_func(lc.c, ic, func_type);
 
 	ic = mkirfunc(lc.c, "get_goto_table");
 	o = mkirstr(ic, lc.goto_table as *byte, lc.goto_table_len);
 	irreturn(ic, o);
 	define_ir_func(lc.c, ic, func_type);
 
 	ret_type = mktype0(lc.c, TY_INT);
 
 	func_type = mktype2(lc.c, TY_FUNC, ret_type, nil);
 
 	ic = mkirfunc(lc.c, "get_prod_len");
 	o = mkirconst(ic, lc.prod_len);
 	irreturn(ic, o);
 	define_ir_func(lc.c, ic, func_type);
 
 	ic = mkirfunc(lc.c, "get_term_len");
 	o = mkirconst(ic, lc.term_len);
 	irreturn(ic, o);
 	define_ir_func(lc.c, ic, func_type);
 
 	lalr_compile_get_call_table(lc);
 }
 
 func lalr_compile_get_call_table(lc: *lalr_compiler) {
 	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 prod: *lalr_prod;
 	var ident: *node;
 	var i: int;
 	var v: *irvar;
 	var pos_table: *int;
 	var pos_table_len: int;
 
 	arg1_type = mktype0(lc.c, TY_VOID);
 	arg1_type = mktype1(lc.c, TY_PTR, arg1_type);
 	args_type = mktype1(lc.c, TY_ARG, arg1_type);
 	ret_type = mktype0(lc.c, TY_VOID);
 	func_type = mktype2(lc.c, TY_FUNC, ret_type, args_type);
 	arg1_type = mktype1(lc.c, TY_PTR, func_type);
 	args_type = mktype1(lc.c, TY_ARG, arg1_type);
 	ret_type = mktype0(lc.c, TY_VOID);
 	func_type = mktype2(lc.c, TY_FUNC, ret_type, args_type);
 
 	ic = mkirfunc(lc.c, "get_call_table");
 
 	v = iraddarg(ic, "t", arg1_type);
 
 	pos_table_len = lc.prod_len * sizeof(*pos_table);
 	pos_table = alloc(lc.a, pos_table_len) as *int;
 
 	i = 0;
 	loop {
 		if i == lc.prod_len {
 			break;
 		}
 		prod = lc.prod[i];
 		pos_table[i] = prod.pos;
 		if prod.action {
 			a = mkirop(ic, IOP_VAR, nil, nil);
 			a.n = v.n;
 			b = mkirconst(ic, 8 * i);
 			a = mkirop(ic, IOP_ADD, a, b);
 			a = mkirop(ic, IOP_LOAD, a, nil);
 			b = mkirfuncref(ic, prod.action);
 			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(lc.c, ic, func_type);
 
 	ret_type = mktype0(lc.c, TY_INT);
 	ret_type = mktype1(lc.c, TY_PTR, ret_type);
 
 	func_type = mktype2(lc.c, TY_FUNC, ret_type, nil);
 
 	ic = mkirfunc(lc.c, "get_pos_table");
 	o = mkirstr(ic, pos_table as *byte, pos_table_len);
 	irreturn(ic, o);
 	define_ir_func(lc.c, ic, func_type);
 }
 
 func get_act_table(): *int;
 func get_goto_table(): *int;
 func get_call_table(t: *func(ctx: *void));
 func get_pos_table(): *int;
 func get_prod_len(): int;
 func get_term_len(): int;
 
 func dolalr(c: *compiler, name: *byte, out: *file): *lex_sem {
 	var act_table: *int;
 	var goto_table: *int;
 	var tok: int;
 	var state: int;
 	var term_len: int;
 	var prod_len: int;
 	var l: *lex;
 	var fd: int;
 	var act: int;
 	var act_out: int;
 	var act_len: int;
 	var stack: *int;
 	var stack_len: int;
 	var stack_cap: int;
 	var pos_table: *int;
 	var call_table: *func(ctx: *lex);
 
 	l = setup_lex(c);
 	fd = open(name, 0, 0);
 	if fd < 0 {
 		die("open failed");
 	}
 	open_lex(l, fd);
 
 	call_table = alloc(l.a, sizeof(*call_table) * get_prod_len()) as *func(ctx: *lex);
 
 	act_table = get_act_table();
 	goto_table = get_goto_table();
 	get_call_table(call_table as *func(ctx: *void));
 	pos_table = get_pos_table();
 	term_len = get_term_len();
 	prod_len = get_prod_len();
 
 	c.filename = name;
 	c.lineno = 1;
 	c.colno = 1;
 
 	state = 0;
 	l.val = &l._val;
 	tok = gettok(l);
 	loop {
 		if tok < 0 && l.eof {
 			tok = term_len - 1;
 		} else if tok < 0 || tok >= term_len {
 			die("invalid token");
 		}
 
 		act = act_table[state * term_len + tok] & 255;
 		act_out = (act_table[state * term_len + tok] >> 8) & 0xffffff;
 		act_len = act_table[state * term_len + tok] >> 32;
 
 		if act == 's' {
 			ensure_arr(l.a, (&l.stack) as **void, &l.stack_cap, l.stack_len + 1, sizeof(*l.stack));
 			memcpy((&l.stack[l.stack_len]) as *byte, l.val as *byte, sizeof(*l.val));
 			l.stack_len = l.stack_len + 1;
 
 			ensure_arr(l.a, (&stack) as **void, &stack_cap, stack_len + 1, sizeof(*stack));
 			stack[stack_len] = state;
 			stack_len = stack_len + 1;
 
 			state = act_out;
 			memset(l.val as *byte, 0, sizeof(*l.val));
 			tok = gettok(l);
 		} else if act == 'r' {
 			ensure_arr(l.a, (&l.stack) as **void, &l.stack_cap, l.stack_len + 1, sizeof(*l.stack));
 			if act_len != 0 {
 				if act_len > stack_len {
 					die("stack underflow");
 				}
 				stack_len = stack_len - act_len;
 				state = stack[stack_len];
 				memcpy((&l.stack[l.stack_len - act_len]) as *byte, (&l.stack[l.stack_len - 1]) as *byte, sizeof(*l.stack));
 			} else {
 				l.sem_len = pos_table[act_out];
 				l.sem = &l.stack[l.stack_len - l.sem_len];
 				if call_table[act_out] {
 					l.val = &l.stack[l.stack_len];
 					if l.sem_len != 0 && l.sem[0].n {
 						l.c.lineno = l.sem[0].n.lineno;
 						l.c.colno = l.sem[0].n.colno;
 					} else {
 						l.c.lineno = l.start_lineno;
 						l.c.colno = l.start_colno;
 					}
 					call_table[act_out](l);
 					l.val = &l._val;
 				} else {
 					memset((&l.stack[l.stack_len]) as *byte, 0, sizeof(*l.val));
 				}
 			}
 			l.stack_len = l.stack_len - act_len + 1;
 
 			ensure_arr(l.a, (&stack) as **void, &stack_cap, stack_len + 1, sizeof(*stack));
 			stack[stack_len] = state;
 			stack_len = stack_len + 1;
 
 			state = goto_table[state * prod_len + act_out];
 		} else if act == 'a' {
 			if tok != term_len - 1 {
 				die("accept not at eof");
 			}
 			return &l.stack[0];
 		} else {
 			fputs(nil, "on ");
 			fputs(nil, name);
 			fputs(nil, ":");
 			fputd(nil, l.start_lineno);
 			fputs(nil, ":");
 			fputd(nil, l.start_colno);
 			die(" syntax error");
 		}
 	}
 }