Generator 0.1
囲碁の棋譜フォーマット SGF の構文解析処理 (parsing / syntactic analysis) を作る前段階として、
パーサーを自動生成するパーサージェネレーターを作成しました。前々回作成した字句解析 (lexical analysis)
のクラス Lex を利用し、EBNF (Extended Backus–Naur Form) の構文解析のクラス EBNFParser
自身を生成するクラス EBNFParser を作成し、単体テストのフレームワーク Jasmine でもテストしてみました。
以下は実際に使用している EBNF の構文です。
syntax = rule, {rule}.
rule = id0, '=', alternative, '.'.
alternative = sequence, {'|', sequence}.
sequence = term, {',', term}.
term = primary.
primary = token | repeat | option | group.
token = [sp], (terminal | id).
terminal = sq, character, {character}, sq.
id0 = [sp], letter, {letter | digit}.
id = letter, {letter | digit}.
option = '[', alternative, ']'.
repeat = '{', alternative, '}'.
group = '(', alternative, ')'.
letter = lower | upper.
character = symbol | letter | digit.
symbol = '=' | ',' | '.' | '|' |
'[' | ']' | '{' | '}' | '(' | ')'.
実行結果
上記の EBNF の構文の文字列を EBNFParser に渡し、EBNFParser 自身のパーサーのコードを以下の通り生成しました。
字下げは Aptana Studio 等の IDE で簡単にできるのでジェネレーターの中では行っていません。
ここに結果が入ります。
ドキュメント
JsDoc Toolkit で作成したドキュメントはこちら。
ソース
generatortest01.html
このソースコードは Jasmine のサンプル SpecRunner.html から大部分を持ってきました。前半はスタイルシートとスクリプトを読み込んでいる部分です。
<head>
<meta charset="UTF-8">
<title>JavaScriptでプログラミング - Generator 0.1</title>
<link type="text/css" rel="stylesheet" href="lib/jasmine-1.3.1/jasmine.css">
<link type="text/css" rel="stylesheet" href="css/spec.css">
<link type="text/css" rel="stylesheet" href="css/shCoreEclipse.css">
<link type="text/css" rel="stylesheet" href="css/shThemeEclipse.css">
<script type="text/javascript" src="js/XRegExp.js"></script>
<script type="text/javascript" src="js/shCore.js"></script>
<script type="text/javascript" src="js/shBrushJScript.js"></script>
<script type="text/javascript" src="js/shBrushXml.js"></script>
<script type="text/javascript" src="js/shBrushCss.js"></script>
<script type="text/javascript" src="lib/jasmine-1.3.1/jasmine.js"></script>
<script type="text/javascript" src="lib/jasmine-1.3.1/jasmine-html.js"></script>
<!-- include source files here... -->
<script type="text/javascript" src="js/generator01/source01.js"></script>
<script type="text/javascript" src="js/generator01/lex02.js"></script>
<script type="text/javascript" src="js/generator01/generator01.js"></script>
<!-- include spec files here... -->
<script type="text/javascript" src="js/generator01/sourcespec01.js"></script>
<script type="text/javascript" src="js/generator01/lexspec02.js"></script>
<script type="text/javascript" src="js/generator01/generatorspec01.js"></script>
後半は Jasmine によるテスト結果を HTML 上で展開するレポーターと呼ばれる部分です。前回から変更ありません。
<script type="text/javascript">
SyntaxHighlighter.all();
(function() {
var jasmineEnv = jasmine.getEnv();
jasmineEnv.updateInterval = 1000;
var htmlReporter = new jasmine.HtmlReporter();
jasmineEnv.addReporter(htmlReporter);
jasmineEnv.specFilter = function(spec) {
return htmlReporter.specFilter(spec);
};
var currentWindowOnload = window.onload;
window.onload = function() {
if (currentWindowOnload) {
currentWindowOnload();
}
execJasmine();
};
function execJasmine() {
jasmineEnv.execute();
}
})();
</script>
generator01.js
クラス EBNFParser のソースコードです。パーサーを生成するためのツールです。以下の部分では HTML にある EBNF の構文から
EBNFParser クラスの一番上位のメソッド syntax() を呼び出してパーサーを生成し HTML に格納しています。
window.onload = function() {
// define EBNF syntax
var syntax = document.querySelector('#syntax');
var ebnf = new EBNFParser(syntax.innerHTML, "EBNF", "0.1");
// get element from HTML and set text (code)
var result = document.querySelector('#ebnf');
result.innerHTML = ebnf.syntax();
};
以下コードはパーサーで解析した結果からコードを生成する部分です。ランナーと命名しています。
この部分を変更することでジェネレーター、インタープリターなどさまざまな出力を行うことができます。
/**
* Parser Runner (Generator) for EBNF Syntax
* @param {String} n - number of match
* @param {Object} match[] - array of parsed result
* @param {String} parser - caller method name
* @return {Float} generated code
* @since 0.1
*/
EBNFParser.prototype.run = function(n, match, parser) {
var code = "";
if (parser == "syntax") {
code += "/**\n";
code += " * @fileOverview " + this.name + "Parser - " + this.name + " Parser Object\n";
code += " * @version " + this.ver + "\n";
code += " * @author EBNFParser written by Nonki Takahashi\n";
code += " */\n";
code += "\n";
code += "/**\n";
code += " * " + this.name + " Parser Generator Object\n";
code += " * @this {" + this.name + "Parser}\n";
code += " * @param {String} syntax syntax object for generate parser\n";
code += " * @param {String} name name of the parser\n";
code += " * @param {String} ver version of the parser\n";
code += " * @property {String} buf syntax buffer\n";
code += " * @property {Integer} ptr syntax buffer pointer\n";
code += " * @property {String} name name of the parser\n";
code += " * @property {String} ver version of the parser\n";
code += " * @since " + this.ver + "\n";
code += " */\n";
code += this.name + "Parser = function(syntax, name, ver) {\n";
code += "this.name = name;\n";
code += "this.ver = ver;\n";
code += "// inherit the methods of class Lex\n";
code += "Lex.call(this, syntax);\n";
code += "};\n";
code += this.name + "Parser.prototype = new Lex();\n";
code += "\n";
for (var i = 0; i <= n; i++) {
code += match[i];
}
} else if (parser == "rule") {
code += "/**\n";
code += " * " + match[0] + "\n";
code += " * @returns {String} code generated if matched, null if not matched\n";
code += " * @since " + this.ver + "\n";
code += " */\n";
code += this.name + "Parser.prototype." + match[0] + " = function() {\n";
code += "var match = [];\n";
code += "var save = this.ptr;\n";
code += "var n = -1;\n";
code += match[2];
code += "if (!match[n]) {\n";
code += "this.ptr = save;\n";
code += "return null;\n";
code += "}\n";
code += "return this.run(n, match, \"" + match[0] + "\");\n";
code += "};\n\n";
} else if (parser == "alternative") {
var i = 0;
code += match[i];
for ( i = 2; i <= n; i += 2) {
code += "if (!match[n--]) {\n";
code += match[i];
code += "}\n";
}
} else if (parser == "sequence") {
var i = 0;
code += match[i];
for ( i = 2; i <= n; i += 2) {
code += "if (match[n]) {\n";
code += match[i];
code += "}\n";
}
} else if (parser == "term") {
code += match[0];
} else if (parser == "primary") {
code += match[0];
} else if (parser == "option") {
code += match[1];
code += "match[++n] = true;\n";
} else if (parser == "repeat") {
code += "while(match[n]) {\n";
code += match[1];
code += "}\n";
code += "match[++n] = true;\n";
} else if (parser == "group") {
code += match[1];
} else if (parser == "id0") {
for (var i = 0; i <= n; i++)
code += match[i];
} else if (parser == "id") {
code += "match[++n] = this.";
for (var i = 0; i <= n; i++)
code += match[i];
code += "();\n";
} else if (parser == "terminal") {
code += "match[++n] = this.ch(";
for (var i = 0; i <= n; i++)
code += match[i];
code += ");\n";
} else if (parser == "letter") {
code += match[0];
} else if (parser == "symbol") {
code += "this.sp();\n";
code += match[0];
} else if (parser == "character") {
code += match[0];
}
return code;
};
これ以外の部分は上記の実行結果のように自動生成可能なパーサーです。今回は自動生成したものではなく、
手入力したものを残してあります。実行結果と比較すると、手入力のほうがいろいろ自由が利き、
自動生成したコードはちょっと無駄が多いのが分かると思います。全体の詳細は、リンク先をご覧下さい。
source01.js
クラス Source のソースコードです。Lex, Parser の対象となるテキストを格納するクラスです。前回から変更ありません。
リンク先をご覧下さい。
lex02.js
クラス Lex のソースコードです。字句解析のためのツールです。前回から変更ありません。
リンク先をご覧下さい。
sourcespec01.js
このソースでは Source のテスト仕様を定義しています。前回から変更ありません。
describe("Source 仕様 0.1", function() {
var exp = "1+2=";
var src;
beforeEach(function() {
src = new Source(exp); // Lexer and Parser Source
});
it("eod() は false を返す", function() {
expect(src.eod()).toBeFalsy();
});
describe("先頭でpush()しptr++したとき、", function() {
beforeEach(function() {
src.rewind();
src.push();
src.ptr++;
});
it("pop(true)後、ptrは 0 を返す", function() {
var p = src.ptr;
src.pop(true);
expect(src.ptr).toEqual(0);
});
it("pop(false)後、ptrは 1 を返す", function() {
var p = src.ptr;
src.pop(false);
expect(src.ptr).toEqual(1);
});
});
});
lexspec02.js
このソースでは Lex のテスト仕様を定義しています。前回から変更ありません。
describe("Lex 仕様 0.2", function() {
var exp = "1+2=";
var la;
beforeEach(function() {
la = new Lex(exp); // Lexical Analiser
});
it("eod() は false を返す", function() {
expect(la.eod()).toBeFalsy();
});
it("digit() は '1' を返す", function() {
expect(la.digit()).toEqual('1');
});
it("upper() は null を返す", function() {
expect(la.upper()).toBe(null);
});
it("lower() は null を返す", function() {
expect(la.lower()).toBe(null);
});
it("sp() は null を返す", function() {
expect(la.sp()).toBeFalsy();
});
it("sq() は null を返す", function() {
expect(la.sq()).toBeFalsy();
});
it("ch('1') は '1' を返す", function() {
expect(la.ch('1')).toEqual('1');
});
describe("3文字読んだ時点で、", function() {
beforeEach(function() {
la.rewind();
la.digit();
la.ch('+');
la.digit();
});
it("eod() は false を返す", function() {
expect(la.eod()).toBe(false);
});
it("digit() は null を返す", function() {
expect(la.digit()).toBe(null);
});
it("upper() は null を返す", function() {
expect(la.upper()).toBe(null);
});
it("lower() は null を返す", function() {
expect(la.lower()).toEqual(null);
});
it("ch('=') は '=' を返す", function() {
expect(la.ch('=')).toBe('=');
});
});
describe("4文字読んだ時点で、", function() {
beforeEach(function() {
la.rewind();
la.digit();
la.ch('+');
la.digit();
la.ch('=');
});
it("eod() は true を返す", function() {
expect(la.eod()).toBeTruthy();
});
});
});
generatorspec01.js
このソースでは Generator のテスト仕様を定義しています。新規に追加しました。
describe("Generator 仕様 0.1", function() {
var g = new EBNFParser("syntax = {line, nl}.", "Test", "0.1");
var code = "/**\n";
code += " * @fileOverview TestParser - Test Parser Object\n";
code += " * @version 0.1\n";
code += " * @author EBNFParser written by Nonki Takahashi\n";
code += " */\n";
code += "\n";
code += "/**\n";
code += " * Test Parser Generator Object\n";
code += " * @this {TestParser}\n";
code += " * @param {String} syntax syntax object for generate parser\n";
code += " * @param {String} name name of the parser\n";
code += " * @param {String} ver version of the parser\n";
code += " * @property {String} buf syntax buffer\n";
code += " * @property {Integer} ptr syntax buffer pointer\n";
code += " * @property {String} name name of the parser\n";
code += " * @property {String} ver version of the parser\n";
code += " * @since 0.1\n";
code += " */\n";
code += "TestParser = function(syntax, name, ver) {\n";
code += "this.name = name;\n";
code += "this.ver = ver;\n";
code += "// inherit the methods of class Lex\n";
code += "Lex.call(this, syntax);\n";
code += "};\n";
code += "TestParser.prototype = new Lex();\n";
code += "\n";
code += "/**\n";
code += " * syntax\n";
code += " * @returns {String} code generated if matched, null if not matched\n";
code += " * @since 0.1\n";
code += " */\n";
code += "TestParser.prototype.syntax = function() {\n";
code += "var match = [];\n";
code += "var save = this.ptr;\n";
code += "var n = -1;\n";
code += "while(match[n]) {\n";
code += "match[++n] = this.line();\n";
code += "if (match[n]) {\n";
code += "match[++n] = this.nl();\n";
code += "}\n";
code += "}\n";
code += "match[++n] = true;\n";
code += "if (!match[n]) {\n";
code += "this.ptr = save;\n";
code += "return null;\n";
code += "}\n";
code += "return this.run(n, match, \"syntax\");\n";
code += "};\n\n";
it("syntax() は " + code + " を返す", function() {
expect(g.syntax()).toEqual(code);
});
});
テスト結果