The Office Uchida, School of Computer

コンピュータを学習する人の学校:パソコンキャンパス、プログラミングキャンパス
ホームCプログラマ徹底養成コース中級コース 第13問/上級コース 第6問
文字の拡大

中級コース 第13問/上級コース 第6問:字句解析

問題:文字列をある規則にしたがって切り出す処理を字句解析と呼びます。ここでは、簡単な字句解析を行うプログラムを 作ることを考えます。

たとえば、次の文章があるとします。

This is a pen.

これを空白で区切ると、「This」、「is」、「a」、「pen.」という字句に分けることができます。

また、次の例は、インターネットのWebサーバーのアクセスログなどに残される日付の例です。

01/May/2006:03:41:09 +0900

これを、/(スラッシュ)および:(コロン)、空白を区切り記号として、切り出すと「01」、「May」、「2006」、「03」、「41」、「09」、「+0900」 となります。

さらに、次の例をご覧下さい。

+++@this####is@@@a@@+++pen.

+および@、#を区切り記号として、切り出すと「This」、「is」、「a」、「pen.」という字句に分けることができます。

さて、次のプログラムは、この処理を実際に行うプログラムです。そのために、Tokenizerという型のプログラムを作成します。 Tokenizerのプログラムの部分を赤く示しています。

Sample list  tsamp.c
#include<stdio.h>

#include"Tokenizer.h"

int main( void )
{
	char token[ 1000 ];
	char *text = "this is a pen.";

	Tokenizer *t = setUpTokenizer( text, " " );

	while( hasMoreToken( t ) )
	{
		getToken( t, token, 1000 );
		printf( "[%s]\n", token );
	}

	freeTokenizer( t );

	return 0;
}

まず、ヘッダファイルTokenizer.hに、字句解析処理に必要な構造体、関数のプロトタイプ宣言がありますので、それをインクルードします。 Tokenizer型は、この字句解析を行うための型です。その型を指すポインタtを定義します。 そして、setUpTokenizer関数の引数に、解析するテキストと区切り記号を指定して、字句解析を行うためのデータを作成します。 そして、setUpTokenizer関数は、そのデータへのポインタを返しますから、それをtに格納します。

hasMoreToken関数は、まだ、切り出す字句があるかどうか検査し、切り出す字句があれば真(1)、なければ偽(0)を返します。

getToken関数は、実際に字句を切り出して、それを引数であるtokenに格納します。第3引数には、tokenの要素数を指定します。

「01/May/2006:03:41:09 +0900」を区切り記号:/および空白で区切る場合には次のようにデータを定義します。

char *text = "01/May/2006:03:41:09 +0900";

Tokenizer *t = setUpTokenizer( text, "/: " );

このプログラムでは、字句解析の対象となる文字列もsetUpTokenizer関数の引数に記述することもできます。

Tokenizer *t = setUpTokenizer( "01/May/2006:03:41:09 +0900", "/: " );

さて、それでは、これを実現するTokenizer型、setUpTokenizer関数、dumpTokenizer関数、hasMoreToken関数、getToken関数、 freeTokenizer関数を作成してください。参考のため、各関数の プロトタイプ宣言を示します。dumpTokenizer関数は、Tokenizer型のデータを見やすく表示するプログラムです。 freeTokenizer関数は、確保したTokenizer型の領域を解放する関数です。

Tokenizer *setUpTokenizer( char *atext, char *asep );
void dumpTokenizer( Tokenizer *t );
int hasMoreToken( Tokenizer *t );
char *getToken( Tokenizer *t, char *token, int size );
void freeTokenizer( Tokenizer *t );

ただし、字句解析する文字列には、日本語コードはないものとしてプログラムを作成してください。日本語のことを考えると、文字コードの 問題が出てきて多少厄介になってしまいます。


学習ポイント
  1. 構造体の設計の方法とその使い方について学習する
  2. 文字列とそれに関連するポインタの使い方について学ぶ
  3. typedefで新しい型を定義する方法を学ぶ

本問題に対するFAQ

質問1この問題の解決の糸口と文字列サンプルプログラム
質問2バッファオーバーフローに対する対策
質問3この問題で作成するプログラムの全体像

質問1:この問題は難しすぎてどこから手をつけてよいのか分かりません。いったいどこから手をつけたら良いのですか。

 まず、文字列の扱いに慣れましょう。なぜなら、このプログラムのポイントは文字処理だからです。 ここでは、次の手順で文字列の扱いについて説明します。

  1. 先頭の区切り記号を読み飛ばすプログラム(区切り記号が1文字の場合)
  2. 先頭の区切り記号を読み飛ばすプログラム(区切り記号が複数文字の場合)
  3. strchr関数を用いて区切り記号を認識するプログラム
  4. 先頭の区切り記号を読み飛ばすプログラム(strchrを用いた場合)
  5. 最初に見つかった字句を抜き取るプログラム
  6. 最初に見つかった字句を抜き取るプログラム(字句が一つもない場合の対策)
  7. まとめと注意

1. 先頭の区切り記号を読み飛ばすプログラム(区切り記号が1文字の場合)

 次のプログラムは"---this---is-a-pen."というテキストの先頭から区切り文字'-'を スキップし、最初の字句の位置まで、ポインタpを移動させている例です。

Sample list  skipchar.c
#include<stdio.h>

int main( void )
{
	char *text = "---this---is-a-pen.";
	char *p;

	p = text; /* pはtextの先頭文字を指す */
	while( *p == '-' ) p++; /* pの指している先が'-'ならpを次に進める */

	printf( "text:「%s」\n", text );
	printf( "   p:「%s」\n", p );

	return 0;
}

 このプログラムの実行結果は、次のようになります。

text:「---this---is-a-pen.」
   p:「this---is-a-pen.」

 さて、textを次のようにします。

char *text = "this---is-a-pen.";

 このときの実行結果は、次のようになり、スキップすべき区切り記号がなくてもpが正しく最初の字句の先頭に位置づけられている ことが確認できます。

text:「this---is-a-pen.」
   p:「this---is-a-pen.」

2. 先頭の区切り記号を読み飛ばすプログラム(区切り記号が複数文字の場合)

 しかし、区切り文字は'-'の一文字だけではありません。たとえば、'-', '*', '+'が区切り文字の場合には次のようにすればよいでしょう。

Sample list  skipchar.c
#include<stdio.h>

int main( void )
{
	char *text = "+*+**this*--*is-a-pen.";
	char *p;

	p = text; /* pはtextの先頭文字を指す */
	while( *p == '-' || *p == '*' || *p == '+' ) p++; /* *pが'-','*','+'ならpを次に進める */

	printf( "text:「%s」\n", text );
	printf( "   p:「%s」\n", p );

	return 0;
}

 このプログラムの実行結果は、次のようになります。

text:「+*+**this*--*is-a-pen.」
   p:「this*--*is-a-pen.」

3. strchr関数を用いて区切り記号を認識するプログラム

 しかし、区切り記号は、個々の文字の形式('-', '*', '+')ではなく、文字列の形で与えられます("-*+")。 また、上記のプログラムのようにいちいち論理演算子||で記述するのも面倒です。そこで、標準ライブラリの<string.h>の int strchr( char *str, char c )関数を使いましょう。 これは、文字列strの中に文字cがあれば真(1)を返し、なければ偽(1)を返します。

 まず、このstrchrをテストするプログラムを紹介しましょう。

Sample list  strchr_test.c
#include<stdio.h>
#include<string.h>

int main( void )
{
	printf( "a    : %s\n", strchr( "-*+", 'a' )?"YES":"NO" );
	printf( "-    : %s\n", strchr( "-*+", '-' )?"YES":"NO" );
	printf( "*    : %s\n", strchr( "-*+", '*' )?"YES":"NO" );
	printf( "+    : %s\n", strchr( "-*+", '+' )?"YES":"NO" );
	printf( "NULL : %s\n", strchr( "-*+", '\0' )?"YES":"NO" );
	printf( "@    : %s\n", strchr( "-*+", '@' )?"YES":"NO" );

	return 0;
}

 このプログラムの実行結果は、次のようになります。

a    : NO
-    : YES
*    : YES
+    : YES
NULL : YES
@    : NO

 ここで注意すべきは、比較する文字がNULL文字のときも、strchr関数は真(1)を返すということです。実は、 これは後で分かりますが、大変便利なのです。(反面、不便なときもありますが)

4. 先頭の区切り記号を読み飛ばすプログラム(strchrを用いた場合)

 それでは、strchr関数を用いてプログラムを書き直して見ましょう。

Sample list  skipchar.c
#include<stdio.h>
#include<string.h>

int main( void )
{
	char *text = "+*+**this*--*is-a-pen.";
	char *p;

	p = text; /* pはtextの先頭文字を指す */
	while( strchr( "-*+", *p ) ) p++; /* pの指している先が'-'あるいは'*', '+'ならpを次に進める */

	printf( "text:「%s」\n", text );
	printf( "   p:「%s」\n", p );

	return 0;
}

 このプログラムの実行結果は、もちろん、次のようになります。

text:「+*+**this*--*is-a-pen.」
   p:「this*--*is-a-pen.」

5. 最初に見つかった字句を抜き取るプログラム

次の仕事は、見つかった最初の字句を抜き取ることです。そのためには、次のようにすればよいでしょう。

Sample list  getToken.c
#include<stdio.h>
#include<string.h>

int main( void )
{
	char *text = "+*+**this*--*is-a-pen.";
	char *p;
	char token[ 100 ];
	char *t;

	p = text; /* pはtextの先頭文字を指す */
	while( strchr( "-*+", *p ) ) p++; /* pの指している先が'-'あるいは'*', '+'ならpを次に進める */

	/* 先頭の字句を抜き取ってtokenにセットする */
	t = token;
	while( !strchr( "-*+", *p ) ) *t++ = *p++;
	*t = '\0'; /* 最後にNULL文字をセット */

	printf( "text:「%s」\n", text );
	printf( "token:「%s」\n", token );

	return 0;
}

 このプログラムの実行結果は、次のようになります。

text:「+*+**this*--*is-a-pen.」
token:「this」

さて、ここで、字句の最後の余分な区切り記号を取って、実行してみましょう。

char *text = "+*+**this";

一見すると、thisのあとに区切り記号がないから、そのまま、その後の文字までもtokenにコピーしてしまうのではないかと 危惧するかも知れませんが、strchr関数は、文字列の最後のNULL文字が比較文字に指定されたときには、真を返すのです。そのため、 問題なくtokenに字句が格納され、プログラムは終了します。

text:「+*+**this」
token:「this」

6. 最初に見つかった字句を抜き取るプログラム(字句が一つもない場合の対策)

このプログラムで問題になるのは、区切り記号だけで字句が一つもないときです。たとえば、 textを次のように変えて実行してみたらどうなるでしょうか。

char *text = "+*+**";

 このプログラムの実行結果は、次のように明らかに不正な結果になります。ここに示した結果は、Cygwinによるもので、利用するコンパイラやOS によって実行結果の内容は多少異なります。

text:「+*+**」
token:「text:「%s」
」

 この理由は明らかですね。strchr関数が*pの値がNULL文字のときも真を返すため、pが次の文字へと移ってしまうからです。 そこで、それに対する対策を立てなければなりません。次のプログラムは、その対策を立てたものです。

Sample list  getToken.c
#include<stdio.h>
#include<string.h>

int main( void )
{
	char *text = "+*+**";
	char *p;
	char token[ 100 ];
	char *t;

	p = text; /* pはtextの先頭文字を指す */
	while( strchr( "-*+", *p ) && *p != (char)NULL ) p++; /* pが区切り記号ならpを次に進める */
	if( *p == (char)NULL )
	{
		printf( "字句無し\n" );
		exit( 1 );
	}

	/* 先頭の字句を抜き取ってtokenにセットする */
	t = token;
	while( !strchr( "-*+", *p ) ) *t++ = *p++;
	*t = '\0'; /* 最後にNULL文字をセット */

	printf( "text:「%s」\n", text );
	printf( "token:「%s」\n", token );

	return 0;
}

7. まとめと注意

 ここで示したように文字列処理プログラムを書くときのポイントを説明します。 まず、考えるべきことは、例外処理に対する対策です。たとえば、字句が1つもない場合のケースが挙げられます。 そのような場合でも、妥当な処理を行うようにする必要があります。次に、文字列処理の場合、バッファに文字を 格納することがよく行われます(このプログラムの場合、tokenがバッファになります)が、このときに、 バッファの容量を超えないようにすることが重要です。個人的に使うプログラムはともかく、商用で使う、 一般公開する場合には、その点は非常に重要です。第3のポイントは、効率です。 文字列処理は、多くの場面で使われます。ですから、あまり、効率が良くないとシステム全体のパフォーマンスを 低下させる原因になります。

質問2:質問1で、バッファオーバーフローに対する対策を立てていないといけないといっていますが、 質問1で紹介されているプログラムは、その対策が立てられていません。どうすればよいのですか。

それでは、質問1の一番最後に紹介したプログラムにその対策を施しましょう。 2つの点に注意しなければいけません。一つは、textの範囲を超えてアクセスしないこと。もう一つは tokenの範囲を超えてデータをセットしないことです。

それでは、最初のチェックポイント(textの範囲を超えてアクセスしないこと)について検証しましょう。 まず、最初の区切り記号の読み飛ばし部分で、文字列textの最後のNULL文字をチェックしているので、ここでは問題なさそうです。 次に、字句を抜き取る部分ですが、strchr関数が文字のNULL文字の場合も真を返すので、ここでも最後のNULL文字をチェックしますので、 文字列textの領域を超えてアクセスすることはありません。しかし、文字列textの最後にNULL文字がない場合には、チェックしようがありません。

次に切り出した字句をtokenに格納する処理について考えて見ましょう。このとき、質問1の最後のプログラムは、 tokenのオーバーフロー処理を考慮していません。試しに、次のように変更して実行してみましょう。 ちなみに、次のプログラムは2つの文字列が連続して配置されていますが、C言語では、この2つの文字列は連結されて1つの文字列と なります。

char *text = "+*+**longlongtokenlonglongtokenlonglongtokenlonglongtokenlonglongtokenlong"
		 "longtokenlonglongtokenlonglongtokenlonglongtokenlonglongtoken+*+";
char token[ 5 ];

tokenの領域は5文字分(実際には最後のNULL文字がありますから4文字分)しかないのに、字句の長さは100文字程度もあります。 この実行結果は、OSやコンパイラによって異なりますが、Cygwinの場合には、次のようにエラーが出てしまいます。

Segmentation fault (core dumped)

Cygwinの場合には、エラーとなるのでまだ安心ですが、エラーにならず、そのまま実行が続いてしまうこともあります。その場合には、 別の部分でおかしな結果を引き起こし、原因の特定が難しいバグとなってしまいます。

そこで、ポインタtの位置を常にチェックし、tokenの範囲を超えたら、そこで処理を終了するように変更します。

Sample list  getToken.c
#include<stdio.h>
#include<string.h>

#define MAX_TOKEN_SIZE 5

int main( void )
{
	char *text = "+*+**longlongtokenlonglongtokenlonglongtokenlonglongtokenlonglongtokenlong"
			 "longtokenlonglongtokenlonglongtokenlonglongtokenlonglongtoken+*+";
	char *p;
	char token[ MAX_TOKEN_SIZE ];
	char *limit = token + MAX_TOKEN_SIZE; /* バッファtokenの最後の次のアドレス */
	char *t;

	p = text; /* pはtextの先頭文字を指す */
	while( strchr( "-*+", *p ) && *p != (char)NULL ) p++; /* pが区切り記号ならpを次に進める */
	if( *p == (char)NULL )
	{
		printf( "字句無し\n" );
		exit( 1 );
	}

	/* 先頭の字句を抜き取ってtokenにセットする */
	t = token;
	while( !strchr( "-*+", *p ) && t < limit )
		*t++ = *p++;
	if( t >= limit ) --t; /* バッファを越えたときの処理 */
	*t = '\0'; /* 最後にNULL文字をセット */

	printf( "text:「%s」\n", text );
	printf( "   p:「%s」\n", p );
	printf( "token:「%s」\n", token );

	return 0;
}

この実行結果は、次のようになり、tokenには、領域分だけの字句が格納されていることがわかります。

text:「+*+**longlongtokenlonglongtoken...(略)...longlongtokenlonglongtokenlonglongtokenlonglongtoken+*+」
   p:「ongtokenlonglongtoken...(略)...longlongtokenlonglongtokenlonglongtokenlonglongtoken+*+」
token:「long」

しかし、これでもまだ、問題があります。というのは、次に字句を取り出そうとすると、 次に取り出すtextの位置(ポインタp)が本来個々で取り出すべき字句の途中になっているということです。 pが最後の位置の次に位置づけられていますから、pは「ongtoken...」から始まっています。

ここで設計上の決定をしなければいけません。すなわち、字句がバッファに入りきらない場合の処理です。 このとき、2つの方法が考えられます。

  1. 抜き出した字句の次の位置を次の字句の始まりとする
  2. その字句を可能な限りtokenに格納して、入りきらなかった部分を捨てる(読み飛ばす)

「抜き出した字句の次の位置を次の字句の始まりとする」プログラムは、次のようにオーバーフローしたときに pを1つ手前に戻せばよいですね。

/* 先頭の字句を抜き取ってtokenにセットする */
t = token;
while( !strchr( "-*+", *p ) && t < limit )
	*t++ = *p++;
if( t >= limit ) { --t; --p; } /* バッファを越えたときの処理 */
*t = '\0'; /* 最後にNULL文字をセット */

実行結果は次のようになり、pが「long..」となって、次の字句の先頭が「long..」になることが分かります。

text:「+*+**longlongtokenlonglongtoken...(略)...longlongtokenlonglongtokenlonglongtokenlonglongtoken+*+」
   p:「longtokenlonglongtoken...(略)...longlongtokenlonglongtokenlonglongtokenlonglongtoken+*+」
token:「long」

「その字句を可能な限りtokenに格納して、入りきらなかった部分を捨てる(読み飛ばす)」プログラムは、次のようにすればよいですね。

	/* 先頭の字句を抜き取ってtokenにセットする */
	t = token;
	while( !strchr( "-*+", *p ) )
		if( t < limit ) /* tokenのバッファ内か? */
			*t++ = *p++; /* バッファ内ならコピーする */
		else
			p++; /* バッファ外ならpのみをスキップ */
	if( t >= limit ) --t; /* バッファを越えたときの処理 */
	*t = '\0'; /* 最後にNULL文字をセット */

実行結果は次のようになり、pが「long..」となって、次の字句の先頭が「long..」になることが分かります。

text:「+*+**longlongtokenlonglongtoken...(略)...longlongtokenlonglongtokenlonglongtokenlonglongtoken+*+」
   p:「+*+」
token:「long」

いずえれにせよ、このようなチェックを入れるとプログラムの安全性は増しますが、チェックする分だけ効率は落ちます。

質問3:質問1,2で色々説明して頂きましたが、それでもまだこの問題で作成するプログラムの全体像が見えません。もう少し詳しく具体的に教えてください。

 分かりました。ここでは、ヘッダファイル<Tokenizer.h>を作成し、さらにTokenizer型、 setUpTokenizer関数、dumpTokenizer関数、hasMoreToken関数、getToken関数、freeTokenizer関数を作成するわけですね。 そのプロトタイプ宣言は問題の中に示されています。

Tokenizer *setUpTokenizer( char *atext, char *asep );
void dumpTokenizer( Tokenizer *t );
int hasMoreToken( Tokenizer *t );
char *getToken( Tokenizer *t, char *token );
void freeTokenizer( Tokenizer *t );

 まず、Tokenizer型ですが、C言語の場合には、このような型は構造体で表現するのが一般的です (ただし、C++やJavaではクラスで実現します)。 構造体の中には、字句解析に必要なデータをすべて含めるようにします。たとえば、切り出す対象の文字列やどこまで切り出したかの位置を 記憶しておくポインタなどです。その構造体を型にするには、typedefを用います。

typedef struct
{
	/* ここに構造体のメンバの記述する */
} Tokenizer;

 上記の記述は、ヘッダファイル<Tokenizer.h>の中に入れておけばよいでしょう。 次に、setUpTokenizer関数ですが、これは、Tokenizer型のデータ領域を生成し、必要な初期設定を行い、その領域のポインタを返します。

Tokenizer *t = setUpTokenizer( text, " " );

 上記のプログラムを実行すると、次のようなイメージになります。

 dumpTokenizer関数は、構造体のデータを分かりやすく表示するようにすれば良いでしょう。

 hasMoreToken関数は、構造体の中のテキストデータの次に取り出すべき位置から、実際に次に取り出すべき字句があるかどうか 調べて、あれば真、なければ偽を返すようにすれば良いでしょう。このとき、結果的に、取り出すべき字句の先頭の区切り文字は スキップされます。

 getToken関数は、実際に字句を切り出す処理を行います。

 freeTokenizer関数は、関係する記憶域の解放を行います。