SimpleJSLex

JavaScriptなでしこもどき
http://nadesico.bz2.jp/

を見てて、字句解析器生成ツール作ってくれないかなぁと書いてあったので、シンプルな字句解析器ジェネレータを作ってみました。

JavaScriptは正規表現オブジェクト利用すれば結構楽に出来ました。

function generateLexer(tokens, name, r) {
	function escape2(str) {
		return str.replace(/\n/mg, "\\n")
			.replace(/\r/mg, "\\r")
			.replace(/\t/mg, "\\t")
			.replace(/\"/mg, "\\\"")
	}
	function escape(str) {
		return escape2(str.replace(/\\/mg, "\\\\"))
	}
	for(var s in name) if (typeof(name[s]) == "object") name[s]=name[s].source; // RegExp->String
	var flg;
	do {
		flg = false;
		for(var s in name) {
			var str = name[s];
			if (/{[a-zA-Z0-9]+}/.test(str)) {
				flg = true;
				for(var s2 in name) {
					str = str.replace(new RegExp("{" + s2 + "}", "g"), name[s2]);
				}
				name[s] = str;
			}
		}
	} while (flg);
	var out = new Array();
	for(var i in name) {
		out[out.length] = i + ": \"" + escape(name[i]) + "\"";
	}
	var a2 = new Array();
	var f2 = new Array();
	for (var str in r) {
		var a = r[str];
		for (var s2 in name) {
			str = str.replace(new RegExp("{" + s2 + "}", "g"), name[s2]);
		}
		a2[a2.length] = "/^"+escape2(str) +"/";
		f2[f2.length] = "function()"+ a;
	}
	tokens = tokens.split(/\s/);
	var o = "var buffer,line,";
	if (tokens.length > 0) {
		for(var i = 0; i < tokens.length;i++) {
			tokens[i] = tokens[i] + "="+(i+1);
		}
		o += tokens.join(",");
	}
	o +=
		",\nyylexa=[" + a2.join(",") + "],"+
		"\nyylexf=[" + f2.join(",") + "];\n"+
		"function yylex(){"+
			"a:for(;;){"+
				"for(var i=0;i<yylexa.length;i++){"+
					"var r=yylexa[i],"+
					"m=buffer.match(r);"+
					"if(m!=null&&m.length>0&&m[0].length>0){"+
						"token=m[0];"+
						"buffer=buffer.substring(m[0].length, buffer.length);"+
						"r=yylexf[i]();"+
						"if(r!=null)return r;"+
						"continue a;"+
					"}"+
				"}"+
				"return(buffer.length==0)?0:-1;"+
			"}"+
		"}\n";
	return o;
}

使い方

以下の例のように使います。

var lexer = generateLexer(
	'IDENTIFIER STRING LPAR RPAR SHARP QUOTE DOT',{
	letter: /[\x00-\xff]/,
	kanji: /([\x80-\xff]{letter})/,
	mark: /[\!\$\%\&\*\+\-\.\/\:\<\=\>\?\@\^\_~]/,
	alpha: /[A-Za-z]/,
	digit: /[0-9]/,
	ws: /[ \t\n]/,
	com: /\;/,
	cr: /\n/,
	escape: /\\/,
	escaped: /({escape}{letter})/,
	dquote: /\"/,
	ident: /({kanji}|{mark}|{alpha}|{digit})*/,
	comment: /{com}[^\n]*{cr}/,
	string: /{dquote}([^{escape}{dquote}]|{escaped})*{dquote}/
	},{
	"{cr}":  "{line++;}",
	"{ws}+": "{}",
	"{comment}": "{}",
	"\\.": "{return DOT;}",
	"{ident}": "{return IDENTIFIER;}",
	"{string}": "{return STRING;}",
	"\\(": "{return LPAR;}",
	"\\)": "{return RPAR;}",
	"\\#": "{return SHARP;}",
	"\\'": "{return QUOTE;}"
	});
document.write(lexer.replace(/</mg,"&lt;").replace(/\n/mg,"<br>\n"));
eval(lexer);
main();

function main() {
	line = 1;
	buffer = "(a b cdef 1.23333)\n1 2";
	var t="";
	while((t = yylex())!=0) {
		document.write(t+":("+line+")"+token+"<br>");
	}
}

generateLexer関数

第1引数は、tokenの名前をスペース区切りで書きます。
第2引数は、ルール名とルールの正規表現の連想配列です。
第3引数は、アクションの正規表現文字列とアクションを決めます。

generateLexer関数から帰ってくるのはjavascriptのプログラムの文字列ですので、
evalして使ったり、htmlに貼り付けて使ってください。

出来上がったプログラムを実行するには、line変数に1を設定し、buffer変数にプログラムを入れておいて、yylex関数を呼び出します。yylex関数からはトークンの番号が帰ってきて、取得した男トークンはtoken変数に格納されて来ます。