Parsecもどき

Haskellだとなんだかしらんけど、パーサコンビネータとかParsecとかがなんだか凄いらしい。
しかし、パーサコンビネータってどんなもんなん？
わからん。うー。
とりあえず、D言語で実装みたいなところまで来れたと。
いうわけで、

DによるParsecもどきです。
例外投げまくり、オブジェクト生成しまくり、なので、遅いです。
ある程度、最適化とか考えてみたんですが。いまいち。
D言語のデリゲードが関数抜けても使えたらもうちょっと、違う風に出来たと思うんですが、、、。

/*
   パーサコンビネータっぽいプログラム
 */
import std.string;

// キャッシュ的な仕組みの導入
template parser() {
	static Parser p; static Parser opCall() { return p; }
	static this() { p = new typeof(this)(); }
}
template parser(T) {
	static Parser[T] ps;
	static Parser opCall(T c) {
		if (c in ps) return ps[c];
		return ps[c] = new typeof(this)(c);
	}
	T f1;
	this(T f1) { this.f1 = f1; }
}
template parser(T,T2) {
	static Parser[T][T2] ps;
	static Parser opCall(T f1, T2 f2) {
		if (f2 in ps && f1 in ps[f2]) return ps[f2][f1];
		return ps[f2][f1] = new typeof(this)(f1, f2);
	}
	T f1; T2 f2;
	this(T f1, T2 f2) { this.f1 = f1; this.f2 = f2; }
}
template aliasParser() {
	static Parser p; static Parser opCall() { return p; }
}
//////////////////////////////////////////////////////////
class Tree {
	static Tree opCall() { return new Tree(); }
	static Tree opCall(char[] s, Tree[] ts ...) { return new Tree(s, ts); }
	char[] s;
	Tree[] ts;
	this(){}
	this(char[] s, Tree[] ts ...) {this.s = s;this.ts = ts.dup;}
	char[] toString() {
		char[] r;
		foreach (Tree t;ts)r ~= t.toString() ~ ",";
		if (r == "") return s;
		return s ~ "(" ~ r[0 .. r.length - 1] ~ ")";
	}
	Tree opUShr(Parser f) { return f.parse(this); } // >>> 演算子
	
	void print() {printf("%.*s\n", toString());}
}
//////////////////////////////////////////////////////////

class Parser {
	Tree parse(Tree t) { err(); return t;}
	Tree parse(char[] str) { return parse(Tree(str));}
	Parser opOr(Parser f)  { return OR(this, f); } 	// |  演算子
	Parser opShr(Parser f) { return AND(this, f); }	// >> 演算子
	void err()   { throw new Exception (toString()); }
	static void many(void delegate() d) {
		try {for (;;) {d();}} catch (Exception e) {}
	}
	static void or(void delegate() d1, void delegate() d2) {
		try { d1(); } catch (Exception e) { d2(); }
	}
}

class OR : Parser { mixin parser!(Parser,Parser);
	Tree parse(Tree t) {
		try{ return f1.parse(t); } catch (Exception e) { return f2.parse(t); }
	}
}

class AND : Parser { mixin parser!(Parser,Parser);
	Tree parse(Tree t) {
		Tree t2 = f2.parse(t = f1.parse(t));
		return Tree(t2.s, t.ts ~ t2.ts);
	}
}
//////////////////////////////////////////////////////////
class Just : Parser { mixin parser!();
	Tree parse(Tree t) { return Tree(t.s, Tree("")); }
}

class Char: Parser { mixin parser!(char);
	Tree parse(Tree t) {
		if (t.s[0] == f1) return Tree(t.s[1..length], Tree("" ~ f1));
		err();
	}
}

class ManyChars: Parser { mixin parser!(char[]);
	Tree parse(Tree t) {
		int i = 0;
		while (f1.find(t.s[i])!= -1) {i++;}
		if (i == 0) err();
		return Tree(t.s[i..length], Tree(t.s[0..i]));
	}
}

//////////////////////////////////////////////////////////
// alias 的なパーサ
class Number { mixin aliasParser!();
	static this() { p = ManyChars("0123456789"); }
}

class Space { mixin aliasParser!();
	static this() { p = ManyChars(" \t\r\n"); }
}

class SkipSpace { mixin aliasParser!();
	static this() { p = (Space() | Just()); }
}

//////////////////////////////////////////////////////////
class Exp: Parser { mixin parser!();
	Tree parse(Tree t) {
		t = t >>> Term();
		many({
			Tree t2 = t >>> (SkipSpace() >>(Char('+')|Char('-')) >> Term());
			t = Tree(t2.s, Tree(t2.ts[1].s, t.ts[0], t2.ts[2]));
		});
		return t;
	}
}

class Term: Parser { mixin parser!();
	Tree parse(Tree t) {
		t = t >>> Fact();
		many({
			Tree t2 = t >>> (SkipSpace() >> (Char('*')|Char('/')) >> Fact());
			t = Tree(t2.s, Tree(t2.ts[1].s, t.ts[0], t2.ts[2]));
		});
		return t;
	}
}

class Fact: Parser { mixin parser!();
	Tree parse(Tree t) {
		or({
			t = t >>> (SkipSpace() >> Number());
			t = Tree(t.s, t.ts[1]);
		},{
			t = t >>> (SkipSpace() >> Char('(') >> Exp() >> SkipSpace() >> Char(')'));
			t = Tree(t.s, t.ts[2]);
		});
		return t;
	}
}

//////////////////////////////////////////////////////////
import std.date;
void main() {
	int time = getUTCtime();
	for (int i = 0; i < 1000; i++) {
		Tree t = Exp().parse("  ( 123 + 2 ) - ( 4 - 5 ); ");
		t = Exp().parse(" 1 * 2 - 4 / 5;  ");
	}
	printf("%dms\n", getUTCtime() - time);
	Tree t = Exp().parse("  ( 123 + 2 ) - ( 4 - 5 ); ");
	t.print();
	t = Exp().parse(" 1 * 2 - 4 / 5;  ");
	t.print();
}