パーサジェネレータ Gin を使って正規表現(っぽい)文字列を処理してみた

はじめに

Gin は Boost.Spirit 風のパーサを JavaScript でお手軽にかけるライブラリです。EBNF っぽく文法を書くことができ、Spirit のようにセマンティックアクションを使ってゴリゴリと文法を解析、その場で計算等もすることができます。また、すべて JavaScript ベースで書かれていて、拡張も簡単です。
今回は Gin を用いて音声認識エンジン Julius で記述文法認識させるために必要な voca ファイル、および grammar ファイルを生成してみようと思います。ファイル扱ったりするので、Node.js ベースの内容となります。あと個人的に作った Node.js アドオンもちょっと使います。

できるようになること

正規表現っぽい感じの文字列を追加するとそれを Gin で解析して、よしなに文法（grammarファイル）と読み方（vocaファイル）を生成します。

// 文法を覚えさせる
JuliusData.add('(電気|ライト|照明|エアコン)を?(つけ(て(下さい)?|ろ))');

// シンボル的なものの追加もできる
JuliusData.addSymbol('NUMBER', [1, 2, 3, 4, 5]);
JuliusData.add('エアコン<NUMBER>度');

// grammar / voca ファイル生成
JuliusData.makeGrammarFile('kaden');
JuliusData.makeVocaFile('kaden');

で、次のようなファイルが吐き出されます。
kaden.grammar

S	: NS_B ROOT_0 ROOT_1 ROOT_2 NS_E
ROOT_0	: WORD_0
ROOT_1	: WORD_1
ROOT_2	: WORD_2
WORD_0	: WORD_0_0
WORD_0	: WORD_0_1
WORD_0	: WORD_0_2
WORD_0	: WORD_0_3
WORD_1	: NOISE
WORD_1	: WORD_1_LOOP
WORD_2	: WORD_2_0 WORD_2_1
WORD_2_1	: WORD_2_1_0 WORD_2_1_1
WORD_2_1	: WORD_2_1_2
WORD_2_1_1	: NOISE
WORD_2_1_1	: WORD_2_1_1_LOOP
WORD_2_1_1_LOOP>: WORD_2_1_1_LOOP_0
S	: NS_B ROOT_3 ROOT_4 ROOT_5 NS_E
ROOT_3	: WORD_3
ROOT_4	: WORD_4
ROOT_5	: WORD_5
WORD_4	: NUMBER

kaden.voca

% NS_B
<s>>silB
% NS_E
<s>>silE
% NOISE
<sp>	sp
% WORD_0_0
電気	d e N k i
% WORD_0_1
ライト	r a i t o
% WORD_0_2
照明	sh o: m e i
% WORD_0_3
エアコン	e a k o N
% WORD_1_LOOP
を	w o
% WORD_2_0
つけ	ts u k e
% WORD_2_1_0
て	t e
% WORD_2_1_1_LOOP_0
下さい	k u d a s a i
% WORD_2_1_2
ろ	r o
% NUMBER
1	i ch i
2	n i
3	s a N
4	y o N
5	g o
% WORD_3
エアコン	e a k o N
% WORD_5
度	d o

実際に mkdfa でコンパイルできます。generate でテストすると次のような文章ができます。

 <s> エアコン 1 度 <s>
 <s> エアコン <sp> つけ て <sp> <s>
 <s> エアコン を つけ ろ <s>
 <s> エアコン 3 度 <s>
 <s> エアコン を つけ て <sp> <s>
 <s> ライト を つけ ろ <s>
 <s> 照明 <sp> つけ ろ <s>
 <s> 電気 を つけ て 下さい <s>
 <s> 電気 を つけ ろ <s>
 <s> エアコン 2 度 <s>

ここで書いたグループ化、選択（?）、シンボルの利用の他にも、繰り返し（+、*、{num}、{min, max}）が使えます。

JuliusData.add('ほむ{2}マジ(ほむ)+');

正規表現とは異なり、直前の字句の塊を繰り返しとするので、"ほむ{2}" の部分は "ほむむ" でなく "ほむほむ" として扱われます。

環境

Node.js 0.6.9
node-mecab
node-voca

Node.js アドオン化

Gin の末尾に２行追加します。

for (var x in Gin)
	exports[x] = Gin[x];

これでアドオン化は完了で、次のようにサンプルを使うことができます。

var Gin = require('./node_addon/gin/gin.js');

var calc = new Gin.Grammar({
	Expr: / Term ([+] Term:add | [-] Term:sub)* /,
	Term: / Fctr ([*] Fctr:mul | [/] Fctr:div)* /,
	Fctr: / $INT:push | [(] Expr [)] /
}, "Expr", Gin.SPACE);

var calcAction = {
	_stack: [],
	push: function (v) { this._stack.push(v); },
	pop: function () { return this._stack.pop(); },
	add: function (v) { var b = this.pop(), a = this.pop(); this.push(a + b); },
	sub: function (v) { var b = this.pop(), a = this.pop(); this.push(a - b); },
	mul: function (v) { var b = this.pop(), a = this.pop(); this.push(a * b); },
	div: function (v) { var b = this.pop(), a = this.pop(); this.push(a / b); }
};

var input = "1 + (2 - 3) * 4";
var match = calc.parse(input, calcAction);
if (match && match.full)
	console.log(input + " = " + calcAction.pop());

process.on('uncaughtException', function(err) {
    console.log(err);
});

$ node hoge
1 + (2 - 3) * 4 = -3

お手軽ですね！
Gin の詳しい使い方は本家に任せるとしてここでは簡単な説明をします。まず、EBNF 風に正規表現を用いて Gin.Grammar を作ります。"[ ]" で囲まれたもの及び Predefined Parser ($INT のようなもの（後述））が終端記号となります。パースする際、第１引数に文字列、第２引数にセマンティックアクションを行うためのオブジェクトを指定します。オブジェクト内部には結果を保持することができるので後で取り出せば計算等もできてしまうという寸法です。

Predefined Parser の追加

上のサンプルで「$INT」というものが出てきました。これは Predefined Parser として Gin の中で定義されている、整数値にマッチするシンボルです。
Gin v.0.90 のソースコードの 557 行目辺りをみると、いくつか事前に定義されたものが書いてあります。例えば JS_STRING を見てみると、

Gin.JS_STRING = new Gin.Parser.Action(
  new Gin.Parser.RegExp(/"(?:[^\\"]|\\.)*"|'(?:[^\\']|\\.)*'/),
  Gin.Utils.unquote
);

こんな風になっています。第1引数はパースする文字列を正規表現で定義し、第2引数では、ここでマッチした内容をあと処理するための関数を指定しています。ちなみに、この JS_STRING では、ダブルクォートもしくはシングルクォートされた文字列にマッチするようになっています。所望のものがこの Predefined Parsers の中になければ自分で作ってしまえば簡単に利用できます。今回は次のような２つのシンボルを作ってみました。

Gin.STRING = new Gin.Parser.Action(
  new Gin.Parser.RegExp(/(?:[^\(\)\|\*\+\{\}\?<>])+/),
  String
);
Gin.SYMBOL = new Gin.Parser.Action(
  new Gin.Parser.RegExp(/[a-zA-Z0-9_-]+/),
  String
);

コード全容

上で定義した $STRING や $SYMBOL を利用してゴリゴリと書いてみます。適当な一時オブジェクトに格納してから処理を行ったのでゴリゴリ感でてしまってちょっとアレ感あります。

/* ------------------------------------------------------------------------- */
// node ライブラリの読み込み
/* ------------------------------------------------------------------------- */
var Gin   = require('./node_addon/gin/gin.js');
var MeCab = require('./node_addon/mecab/build/Release/mecab');
var ICU   = require('./node_addon/icu/build/Release/icu');
var fs    = require('fs');

/* ------------------------------------------------------------------------- */
// 便利関数など
/* ------------------------------------------------------------------------- */
/**
 * 文字列を n 回繰り返す. (String.prototype 拡張)
 * @param[in] num 繰り返し回数
 */
String.prototype.repeat = function( num ) {
	for(var i = 0, buf = ""; i < num; ++i) buf += this;
	return buf;
}

/**
 * 文字列をvoca形式に変換する. (String.prototype 拡張)
 */
String.prototype.toVoca = function() {
	return ICU.kana2voca(MeCab.str2kana(this.toString()));
	// return this.toString();
}

/* ------------------------------------------------------------------------- */
// Gin による構文解析
/* ------------------------------------------------------------------------- */

//! Julius の形式に変換するための Grammar
var Voca = new Gin.Grammar({
	Expr     : / ((Group|Symbol|String)(MinMax|Repeat|Plus|Asterisk|Question)?)+ /,
	Group    : / [(]:child Expr ([|]:bros Expr)* [)]:unchild /,
	MinMax   : / [{] $INT:min [,] $INT:max [}] /,
	Repeat   : / [{] $INT:repeat [}] /,
	Plus     : / [+]:plus /,
	Asterisk : / [*]:asterisk /,
	Question : / [?]:question /,
	Symbol   : / [<] $SYMBOL:symbol [>] /,
	String   : / $STRING:string /
}, 'Expr', Gin.SPACE);

//! 文字列ノードのタイプ
const NODE_TYPE = {
	STRING   : 0,
	SYMBOL   : 1
};

//! 文字列ノードの繰り返しタイプ
const REPEAT_TYPE = {
	NONE         : 0, // 繰り返しなし
	MIN_AND_MAX  : 1, // 繰り返しの最小/最大数を設定
	ONE_OR_MORE  : 2, // ０回以上の繰り返し
	ZERO_OR_MORE : 3  // １回以上の繰り返し
};

/**
 * 文字列ノードクラス.
 * 各ノードの情報を格納する（e.g. 繰り返し回数、次のノード、子ノード）
 */
function Node() {
	this.str    = '';
	this.id     = '';
	this.repeat = REPEAT_TYPE.NONE;
	this.type   = NODE_TYPE.STRING;
	this.parent = null;
	this.child  = null;
	this.next   = null;
	this.min    = -1;
	this.max    = -1;
	this.isNextBros   = false;
}

/**
 * Gin の Semantic Action を引き受けるハンドラ.
 */
var Handler = function() {
	//! 最初のノード位置
	this.first = new Node();

	//! 現在のノード位置
	this.node = this.first;
}
Handler.prototype = {
	//! 現在のノード位置 or 次の位置へ文字列ノードを追加
	string: function(v) {
		if (this.node.str !== '' || this.node.child !== null) {
			this.node.next = new Node();
			this.node.next.parent = this.node.parent;
			this.node = this.node.next;
		}
		this.node.str = v;
	},
	//! 現在のノード位置 or 次の位置へ数字ノードを追加
	symbol: function(v) {
		if (this.node.str != '' || this.node.child != null) {
			this.node.next = new Node();
			this.node.next.parent = this.node.parent;
			this.node = this.node.next;
		}
		this.node.str  = v;
		this.node.type = NODE_TYPE.SYMBOL;
	},
	//! 最小繰り返し回数を設定
	min: function(v) {
		this.node.repeat = REPEAT_TYPE.MIN_AND_MAX;
		this.node.min = v;
	},
	//! 最大繰り返し回数を設定
	max: function(v) {
		this.node.repeat = REPEAT_TYPE.MIN_AND_MAX;
		this.node.max = v;
	},
	//! 固定繰り返し回数を設定
	repeat: function(v) {
		this.node.repeat = REPEAT_TYPE.MIN_AND_MAX;
		this.node.min = this.node.max = v;
	},
	//! １回以上繰り返しに設定
	plus: function(v) {
		this.node.repeat = REPEAT_TYPE.ONE_OR_MORE;
	},
	//! ０回以上繰り返しに設定
	asterisk: function(v) {
		this.node.repeat = REPEAT_TYPE.ZERO_OR_MORE;
	},
	//! ０回か１回出現に設定
	question: function(v) {
		this.node.repeat = REPEAT_TYPE.MIN_AND_MAX;
		this.node.min = 0;
		this.node.max = 1;
	},
	//! 自分の次のノードが兄弟ノードかどうかを記憶
	bros: function(v) {
		this.node.isNextBros = true;
	},
	//! 子要素を設定し現在のノード位置を子ノードへ移動
	child: function(v) {
		this.node.next = new Node();
		this.node.next.parent = this.node.parent;
		this.node.next.child = new Node();
		this.node.next.child.parent = this.node.next;
		this.node = this.node.next.child;
	},
	//! 現在のノード位置を親ノードへ移動
	unchild: function(v) {
		this.node = this.node.parent;
	}
};

/**
 * Gin による構文解析結果から Julius の grammar 形式、voca 形式を生成する.
 * 解析結果（Nodeクラス）は兄弟/子供を持つので、再帰的に子供を調べる
 *
 * @param[in] firstNum      grammar や voca で用いる ID 番号
 * @param[in] firstNode     Gin によって解析された結果のノード
 * @param[in] parentId      (再帰で使用) 親の ID. （e.g. WORD_5 など）
 * @param[in] brosIds       (再帰で使用) 兄弟要素走査中の ID の束
 * @return                  {grammar, voca, num} 構造体
 */
function makeJuliusFormat(firstNum, firstNode, parentId, brosFlag) {
	var num = firstNum;
	var gramStr = '', vocaStr = '';

	// 最上位ノードの場合
	if (parentId === undefined) {
		// ルートとなる文法を作成する
		// 繰り返し用に最上位ノードの場合は ROOT_N --> WORD_N という対応付けをする
		var rootGramStr = '';
		gramStr += 'S\t: NS_B ';
		for (var node = firstNode, n = firstNum; node; node = node.next) {
			if (node.child !== null || node.str !== '') {
				rootGramStr += 'ROOT_' + n + '\t: WORD_' + n + '\n';
				gramStr += 'ROOT_' + n + ' ';
				++n;
			}
		}
		gramStr += 'NS_E\n';
		gramStr += rootGramStr;
	}

	// ノードを順に走査（next）
	for (var node = firstNode; node; node = node.next) {
		// 子ノードがいないかつ空ノード（頭とか）は無視
		if (node.child === null && node.str === '') continue;

		// 自身の ID を設定 (最上位ノードかどうかで場合分け）
		var id, parentId2;
		if (parentId === undefined) {
			parentId2 = 'ROOT_' + num;
			id = 'WORD_' + num;
		} else {
			parentId2 = parentId;
			id = parentId + '_' + num;
		}

		// 繰り返しに対応する grammar を作る
		var loopId = id + '_LOOP', tmpId = id + '_TMP';
		switch (node.repeat) {
			case REPEAT_TYPE.NONE:
				break;
			case REPEAT_TYPE.MIN_AND_MAX:
				for (var i = node.min; i <= node.max; ++i) {
					if (i === 0)
						gramStr += id + '\t: NOISE\n';
					else
						gramStr += id + '\t: ' + (loopId + ' ').repeat(i) + '\n';
				}
				id = loopId;
				break;
			case REPEAT_TYPE.ZERO_OR_MORE:
				gramStr += id + '\t: NOISE\n';
				gramStr += id + '\t: ' + loopId + '\n';
				gramStr += id + '\t: ' + id + ' ' + loopId + '\n';
				id = loopId;
				break;
			case REPEAT_TYPE.ONE_OR_MORE:
				gramStr += id + '\t: ' + loopId + '\n';
				gramStr += id + '\t: ' + id + ' ' + loopId + '\n';
				id = loopId;
				break;
			default:
				throw new Error("ERROR! Invalid REPEAT_TYPE.");
				break;
		}

		// 再帰処理
		// 子ノード（= child）がいるとき（= 自分の str は空）、子ノードを走査
		if (node.child !== null) {
			// 文法を作成
			// isNextBros が設定されているノードの時はそこの位置がセパレータとなる
			gramStr += id + '\t: ';
			for (var child = node.child, m = 0; child; child = child.next, ++m) {
				gramStr += id + '_' + m + ' ';
				if (child.isNextBros === true) {
					gramStr += '\n' + id + '\t: ';
				}
			}
			gramStr += '\n';

			var result;
			// 親IDに自分のIDをひもづける
			result = makeJuliusFormat(0, node.child, id);
			gramStr += result.grammar;
			vocaStr += result.voca;
			++num;
		}


		// 子ノードがいないが空でないノードの場合(= 終端ノード)は voca を書きだして次へ
		if (node.child === null && node.str !== '') {
			// MeCab と ICU を用いて Julius の voca 形式に変換
			// Symbol なら voca 形式に登録せずに grammar に追加
			switch (node.type) {
				case NODE_TYPE.STRING:
					vocaStr +=
						'% ' + id + '\n' +
						node.str + '\t' + node.str.toVoca() + '\n';
					break;
				case NODE_TYPE.SYMBOL:
					gramStr += id + '\t: ' + node.str + '\n';
					break;
				default:
					throw new Error("ERROR! Invalid NODE_TYPE.");
					break;
			}
			++num;
		}

	}
	return {grammar: gramStr, voca: vocaStr, num: num};
}

/**
 * Voca / Grammar を保管しておく構造体
 */
var JuliusData = {
	num_     : 0,
	voca_    : '% NS_B\n<s>\tsilB\n% NS_E\n<s>\tsilE\n% NOISE\n<sp>\tsp\n',
	grammar_ : '',
	//! Julius が認識することのできる文字列を追加
	add: function(str) {
		var handler = new Handler();
		var match   = Voca.parse(str, handler);

		if (match && match.full) {
			var result  = makeJuliusFormat(this.num_, handler.first);
			this.voca_    += result.voca;
			this.grammar_ += result.grammar;
			this.num_      = result.num;
		} else {
			throw new Error('ERROR! "' + str + '" is invalid format.');
		}
	},
	/**
	 * symbol を追加.
	 * @param[in] 追加するシンボル
	 * @param[in] シンボルに対応する文字列配列
	 */
	addSymbol: function(symbol, arr) {
		if (!/[a-zA-Z0-9_-]/.test(symbol)) {
			throw new Error('ERROR! "' + symbol + '" is invalid symbol.');
		}
		this.voca_ += '% ' + symbol + '\n';
		for (var i in arr) {
			var str = arr[i].toString();
			this.voca_ += str + '\t' + str.toVoca() + '\n';
		}
	},
	//! voca ファイルを書き出す
	makeVocaFile: function(filename) {
		if (!filename) filename = 'tmp';
		fs.writeFile(filename + '.voca', this.voca_, function(err) {
			if (err) throw err;
			console.log('Create ' + filename + '.voca');
		});
	},
	//! grammar ファイルを書き出す
	makeGrammarFile: function(filename) {
		if (!filename) filename = 'tmp';
		fs.writeFile(filename + '.grammar', this.grammar_, function(err) {
			if (err) throw err;
			console.log('Create ' + filename + '.grammar');
		});
	}
};

/* ------------------------------------------------------------------------- */
// 文章の追加とファイルへの書き出し
/* ------------------------------------------------------------------------- */
// 文法を覚えさせる
JuliusData.add('(電気|ライト|照明|エアコン)を?(つけ(て(下さい)?|ろ))');
JuliusData.addSymbol('NUMBER', [1, 2, 3, 4, 5]);
JuliusData.add('エアコン<NUMBER>度');

// grammar / voca ファイル生成
JuliusData.makeGrammarFile('kaden');
JuliusData.makeVocaFile('kaden');

何とか動くものができました。
結果を保存するためのうまい構造が思いつかず適当にやってしまったので長くなってしまいましたが、一時オブジェクトを挟まないとかうまくやればもっと短くなると思います。ちなみに parse した結果の match にはパースした結果がオブジェクトや配列の形になって格納されているのでそれを使っても良いと思います。

{ value:
   [ [ '(',
       [Object],
       '|',
       [Object],
       '|',
       [Object],
       '|',
       [Object],
       ')',
       isTuple: true,
       ruleName: 'Group' ],
     [ 'を', isTuple: true, ruleName: 'String' ],
     [ '?', isTuple: true, ruleName: 'Question' ],
     [ '(', [Object], ')', isTuple: true, ruleName: 'Group' ],
     isTuple: true,
     ruleName: 'Expr' ],
  full: true,
  lastIndex: 33 }
{ value:
   [ [ 'エアコン', isTuple: true, ruleName: 'String' ],
     [ '<', 'NUMBER', '>', isTuple: true, ruleName: 'Symbol' ],
     [ '度', isTuple: true, ruleName: 'String' ],
     isTuple: true,
     ruleName: 'Expr' ],
  full: true,
  lastIndex: 13 }

おわりに

Gin で適当に文法あってるか試して Boost.Spirit に移植する流れで高速化とか良さ気。

凹みTips

C++、JavaScript、Unity、ガジェット等の Tips について雑多に書いています。