Doc.19 字句解析ツールre2c

絶版の某雑誌を読んでいたところ、こんな印象に残る文章がありました。「プログラマが作成したい3大テーマとは、ゲーム、プログラム言語、OSではないか」。・・・なるほど。自分もその意見には賛成でして、不思議と人を焚きつけて止まない、魅力があると思っています。

 

ところがプログラム言語を検索してみると一見さんお断りで専門用語ばかり。さらに残念なことは、国内のre2cやflexなどのツールについてまとまった情報がないことも原因ではないかと思っています(2008/11現在。このドキュメントでは学問的な話は避けてとおり、少し反則技ですが、嘘も交えてアウトラインだけでも伝えればと書いたものです(^^;。おいしいとこ取りをしたせいで中身はスカスカですけど、もしちゃんとした知識がほしいのでしたら推薦図書のyacc/lexの項目を参考にして頂ければと思います。

re2cについて

さて、これらのツールについては初めての方もいらっしゃると思いますので最初の嘘をつかせていただきます。大雑把に次のようなものだと思ってください。re2cは、テキストファイル(ソースコードなど)の文字列を、切り分けるツールである。どこで使うのか、使い方なども含めた細かい話は少しづつ明らかにしていきます。とりあえず最初はこれだけ抑えといてください。

迷いの森へご案内

たとえば、とあるテキストファイルの内容が「数字とコンマで区切られたcsv形式」であって、書式が正しいかチェックをしたいコードを書いてみようと思い立ちます。

・正しいcsvファイルの例。

1,2,3,42,500

・これは不正解。コンマ続いちゃダメ。

,,1,2,3,42,500

・これも不正解。数字以外もダメ。

1,2,a,42a,500

数字は可変長・・・その後コンマは出てくる・・・そんなキーワードを頼りに書いてみたところ、自分はこんな感じのラフスケッチになりました。擬似コード使っているのでそのままコンパイルはできません。

int main()
{
	// ファイルを開く
	// ファイルの内容をメモリにコピーする

	i=0;
	while(i<ファイルの最後まで)
	{
		// 1文字取り出します
		c = buf[i++];
		
		switch(c)
		{
		case 数字:
			// TODO
			break;
		
		case コンマ:
			// TODO
			break;
		
		case ファイルの終端:
			// TODO
			break;
		
		default:
			// エラー
			break;
		}
	}
	
	// 調べた結果を表示する
}

しかしこれには罠があり、仕様追加すると関数が広大になってしまう傾向にあります。たとえば、ダブルクォートで囲まれた文字列と、数字の間に少数点を入れるとどうなるでしょうか。どう改善すればいいのか、ちょっと考えてみてください。

・正しいcsvファイルの例。

1,2,3.14195,"PAI",4,5

・不正解特集。

1,2,"aaa,3,4
1,2,"aaa,3,2,"4
1,2,.3,4
(ほか一杯・・・)

何がいけなかったのだろう

ポイントとしては1文字毎の処理でコードを考えたのが原因ではないかと思います。見方をがらりと変えるには、文字という概念から離れてトークンと呼ばれる、文字の集合で考えてみるといいようです。

・csvファイルをトークン毎に見る

enum
{
	TOKEN_ITEM,	// 項目(数字、文字列)
	TOKEN_COMMA,	// コンマ
	TOKEN_END,	// ファイルの終端。もしくは改行
	TOKEN_ERR,
}

 int main()
{
	// ファイルを開く
	// ファイルの内容をメモリにコピーする

	for(;;)
	{
	 	token = yylex();
	 	if(token != TOKEN_ITEM)
		{
			goto Err;
		}
		
		token = yylex();
		if(token == TOKEN_COMMA)
		{
			continue;
		}
		
		if(token == TOKEN_END)
		{
			goto Ok;
		}
		else
		{
			goto Err;
		}
	}
	
	// 調べた結果を表示する
}

たしかにyylex関数に分業させて、トークンごとにチェックできればうまく行きそうな気がしてきます。複雑なところは自分で作るのではなく、ツールにおまかせです。re2cは、つまるところyylex関数の中身を作ってくれるC言語のソースコードジェネレータというわけです。ちなみになぜ関数名がyylexなのかというと、この後すぐに登場するbisonと連帯させるための、デフォルトの固定名であることは覚えといてください。

re2cの登場

始めはコードを書くより、妙に違和感があって苦労するかもしれません。でもこれからずっと使えるツールと考えれば、それほど悪くない取引だと思っています。ダウンロード先より実行ファイルを入手してください。

re2cで文字列"abc"のチェック

具体的な使い方です。ここでは一旦、csvの話は置いといて「とある文字列が"abc"と等しいか」チェックをする簡単なプログラムを書いてみます。以下、サンプルコードです。

・main.re

#include <stdio.h>
#include <stdlib.h>

//---------------------------------------------------------------------------
#define YYMARKER			yymarker

enum {
	TOKEN_ABC,
	TOKEN_ERR,
};

//---------------------------------------------------------------------------
char* yyin;
char* yyold;
char* yymarker;


//---------------------------------------------------------------------------
int yylex(void)
{
start:
	yyold = yyin;


/*!re2c

	re2c:define:YYCTYPE  = "char";
	re2c:define:YYCURSOR = yyin;
	re2c:yyfill:enable   = 0;
	re2c:indent:top      = 1;

	"abc"		{ return TOKEN_ABC; }
	.		{ return TOKEN_ERR; }
*/
}
//---------------------------------------------------------------------------
int main(int argc, char** argv)
{
	char* pBuf = "abc";


	yyin = pBuf;
	printf("yylex = %d\n", yylex());

	return 0;
}

このファイルに対して次のコマンドを実行します。

re2c.exe -i -o main.c main.re

生成されたmain.cを読むと、コメントアウトされていた/*!re2c〜*/までの部分が置き換わっていることがわかります。以下、その結果です。flexというツールもre2cとほぼ同じ機能を持っていますが、あちらは状態遷移に圧縮テーブルを使っているので理解しずらいかも。こちらは比較的読みやすいコードではないかと思っています。

・main.c(抜粋)

//---------------------------------------------------------------------------
int yylex(void)
{
start:
	yyold = yyin;



	{
		char yych;

		yych = *yyin;
		switch (yych) {
		case '\n':	goto yy2;
		case 'a':	goto yy3;
		default:	goto yy5;
		}
yy2:
		yyin = YYMARKER;
		goto yy4;
yy3:
		yych = *(YYMARKER = ++yyin);
		switch (yych) {
		case 'b':	goto yy6;
		default:	goto yy4;
		}
yy4:
		{ return -1; }
yy5:
		yych = *++yyin;
		goto yy4;
yy6:
		yych = *++yyin;
		switch (yych) {
		case 'c':	goto yy7;
		default:	goto yy2;
		}
yy7:
		++yyin;
		{ return  0; }
	}

}

・実行結果

a.exe
yylex = 1

ソースコードの解説です。マニュアルみてもイマイチわからない場合はコードを生成してみて、差異がどのように変わるか見比べるのもいいかもしれないです。

/*!re2c

	re2c:define:YYCTYPE  = "char";
	re2c:define:YYCURSOR = yyin;
	re2c:yyfill:enable   = 0;
	re2c:indent:top      = 1;

	"abc"		{ return TOKEN_ABC; }
	.		{ return TOKEN_ERR; }
*/

それぞれの項目の意味は以下のとおりです。

YYCTYPE入力の型
YYCURSOR入力の変数名
yyfill入力のバッファがあふれた時の処理。詳しくは不明(爆
indentインデントが変わるだけ。付けると見栄えがよくなる

前半の"abc"という文字が見つかった場合、後半のアクション部分{ return TOKEN_ABC; } を実行せよ、という意味です。括弧の中身はC言語を書くことができて、"abc"の部分はベタテキスト以外にも、正規表現が可能です。

re2cで変数の代入文チェック

もう1つ練習台です。

・入力文字列

abc = 123

・期待するトークン列

TOKEN_VAR TOKEN_EQ TOKEN_NUM

・main.re

#include <stdio.h>
#include <stdlib.h>

//---------------------------------------------------------------------------
#define YYMARKER			yymarker

enum {
	TOKEN_NUM,
	TOKEN_VAR,
	TOKEN_STR,
	TOKEN_EQ,
	TOKEN_ERR,
};

//---------------------------------------------------------------------------
char* yyin;
char* yyold;
char* yymarker;


//---------------------------------------------------------------------------
int yylex(void)
{
start:
	yyold = yyin;


/*!re2c

	re2c:define:YYCTYPE  = "char";
	re2c:define:YYCURSOR = yyin;
	re2c:yyfill:enable   = 0;
	re2c:indent:top      = 1;

	ws		=	[\r\t ]+;
	lf		=	[\n];
	digit		=	[0-9]+;
	letter		=	[a-zA-Z_];
	var		=	letter(letter | digit | '.')*;
	str		=	('"').+('"');
	other		=	.;

	digit		{ return TOKEN_NUM; }
	var		{ return TOKEN_VAR; }
	str		{ return TOKEN_STR; }
	'='		{ return TOKEN_EQ;  }
	ws		{ goto start;       }
	other		{ return TOKEN_ERR; }
*/
}
//---------------------------------------------------------------------------
int main(int argc, char** argv)
{
	char* pBuf = "abc = 123";
	yyin = pBuf;

	printf("yylex = %d\n", yylex());
	printf("yylex = %d\n", yylex());
	printf("yylex = %d\n", yylex());

	return 0;
}

・結果

a.exe
yylex = 1
yylex = 3
yylex = 0

re2cでcsvの書式チェック

先ほど保留にしていたcsvについてはこうなりました。

・main.re

#include <stdio.h>
#include <stdlib.h>

//---------------------------------------------------------------------------
#define YYMARKER			yymarker

enum {
	TOKEN_ITEM,
	TOKEN_COMMA,
	TOKEN_END,
	TOKEN_ERR,
};

//---------------------------------------------------------------------------
char* yyin;
char* yyold;
char* yymarker;


//---------------------------------------------------------------------------
int yylex(void)
{
start:
	yyold = yyin;


/*!re2c

	re2c:define:YYCTYPE  = "char";
	re2c:define:YYCURSOR = yyin;
	re2c:yyfill:enable   = 0;
	re2c:indent:top      = 1;

	ws		=	[\r\t ]+;
	lf		=	[\n];
	digit		=	[0-9]+;
	num		=	digit('.'digit*)?;
	letter		=	[a-zA-Z_];
	str		=	('"').+('"');
	end 		=	[\000];
	other		=	.;

	num		{ printf("num\n");    return TOKEN_ITEM;  }
	str		{ printf("str\n");    return TOKEN_ITEM;  }
	","		{ printf("commna\n"); return TOKEN_COMMA; }
	end		{ printf("end\n");    return TOKEN_END;   }
	ws		{ printf("ws\n");     goto start;         }
	other		{ printf("other\n");  return TOKEN_ERR;   }
*/
}
//---------------------------------------------------------------------------
int main()
{
	// ファイルのメモリコピーは省略します
	int   token;
	char* pBuf = "1,2,3.14195,\"PAI\",4,5";

	yyin = pBuf;

	for(;;)
	{
	 	token = yylex();
	 	if(token != TOKEN_ITEM)
		{
			goto Err;
		}
		
		token = yylex();
		if(token == TOKEN_COMMA)
		{
			continue;
		}
		
		if(token == TOKEN_END)
		{
			goto Ok;
		}
		else
		{
			goto Err;
		}
	}

Ok:
	printf("ok\n");
	return 0;

Err:
	printf("Err\n");
	return -1;
}

・結果

re2c.exe -i -o main.c main.re
gcc main.c
a.exe
num
commna
num
commna
num
commna
str
commna
num
commna
num
end
ok

ほかにも、本家のre2c-x.x.x-src.zipの中にはexamples, lessonsというサンプルがたくさん入っています。ぜひ参考にしていただければと思います(特にC言語のソースコードをターゲットにしたものは必見。ここまでわかればre2cとはどういうものか、はっきり言えます。re2cは、テキストファイル(ソースコードなど)の文字列を、正規表現で切り分け、トークンを返すツールである、です。このような処理のことを字句解析といいます。

Doc.20 構文解析ツールbison(1)に続きます・・・。

履歴

  • 2008/11/01

Last-modified: 2008-11-03 (月) 08:19:39 (4377d)