「有限状態機械（有限オートマトン）」とは、計算モデルの１つである。これは本来コンピュータ科学の中でも「計算論」に属する話題であり、通常のコンピュータを形式化したチューリング機械よりも能力の低い計算モデルなのだが、アルゴリズムとしてこの形式化を利用することが出来、しかもこの「有限状態機械」は広い応用を持っている。いわゆる「正規表現」を処理するライブラリはこの「有限状態機械」の典型的な応用なのだが、それ以外にもプログラマとして知っていると、アルゴリズムの可読性と処理速度を上げるヒントを得られるアイデアである。
「有限状態機械」とは、コンピュータ科学（とは言っても数学寄りの奴）の「計算論」を教科書を読むと、ほぼ一番最初に載っている奴である。大概「計算論」の教科書というと、「オートマトン」「文脈自由文法」「チューリング機械」「非決定性問題」（あとあれば「計算量理論」）といった構成になっているものだが、この「計算論」とは実はコンピュータが「計算」と言っているのはどういうことであり、その「計算」に出来ることと出来ないことは何か、ということを研究したコンピュータの数学的基礎に関する分野である。
この研究は1930年代に一応の結論（いわゆる「ゲーデルの不完全性定理」）が出て、コンピュータなどはまだ影も形もないにも関わらず、すでに「コンピュータに出来ること」の範囲は数学的には結論が出てしまっているのである！ この文書は別に専門書ではないので、平たく言うと、コンピュータでは「あるプログラムが正しく書けているか」を一般的に検証することはできない、という結論が得られるのだ。だから我々プログラマは将来に亙って失業せずに済むのである（笑。けど永遠にバグと戦い続ける運命にある...）。
この計算論の冒頭に位置する「有限状態機械」（あるいは「有限オートマトン」、もっと略して単に「オートマトン」）とは、コンピュータのモデルの一つだが、我々が知っているコンピュータよりも随分能力が低いものである。しかし、一応「計算のようなこと」が出来るモデルなのである。
ではオートマトンはどうやって出来ているのだろう？ オートマトンとは「入力に従って別な「状態」に遷移することのできる「状態」の集合」である。つまり、いくつかの（有限な）状態があり、それらは入力の種類によって、「ある入力では状態Ａへ」、「別な入力では状態Ｂへ」、それぞれ「状態０」から遷移する、という風な構造になっている。だから、ただ一つの「最初の状態」（よく q0と表記する）から、さまざまな入力によって状態を遷移させながら、最終的に「受理状態」（複数あってよいから普通は「受理状態の集合」。よく qFと表記する）へ遷移し、最終的にどの「受理状態」に到達したかによって、結果が得られるという一連の「機械」なのである。
ということはオートマトンは一種のテーブルである。つまり、「状態」ごとに「入力」に対応した「次の状態」の表がある。この表に従って「最初の状態」から「入力」を受け付けていって、いくつかある「受理状態」に到達したら、それで遷移が終了し、どの「受理状態」かによって、その「入力の系列」について何かの結論が得られるわけである。これは大変有効なプログラミングの技法である。つまり、何かの入力が適切なものであるかどうかを、このオートマトンによって判定できるのである。一番端的な応用はいわゆる「正規表現」であり、「正規表現」は一連の入力を受け付けて、それが「正規表現」で表されたものであるかどうかを判定する。この機構はオートマトンの現実的に重要な応用なのである。
数学的に見ると、いわゆる「正規表現」は次の３つしかない。
また、この「正規表現」は「( )」を使って適切にグルーピングすることもできるのである。だから、より複雑な応用は次の通り。
(B|b)ana(na)* → banana, Banana, bana, Bananana, banananananana などと一致
しかし、実用的なレベルだと、次のような仕様が追加されていると使いやすい。だから、「正規表現」を利用するツールでは、通常次の「メタ文字」（そのまま文字指定と解釈されるのではなくて、正規表現の機能を示す文字。すでに登場は「|*()」）として、次のものを追加するのが普通である。
こんな感じで使える。
^#[ \t]*[a-zA-Z0-9_]+ → Ｃ言語プリプロセッサ・ディレクティヴ行に一致
正規表現が利用できるツールは昔からUNIXには、数多くの標準ツールとして用意されている。また、スクリプト言語だと最近のものでは、言語仕様に正規表現パターンマッチングが採用されているケースが多い。これらを使いこなすことが快適なUNIX環境の秘訣の一つである。どんなツールがあるのか見てみよう。
まあ、問題としては個々のツールで、正規表現のどの機能を実装するか、そのツールの上での表現がどうなるか、という点で統一が取れていないことであろう。つまり、ツールによって細部がちょっとづつ「癖がある」のである。この傾向は特に置換指定において甚だしい（これは厳格には正規表現の仕様ではなくて、ツールの仕様になるからね）。
ヘッダファイルは regex.h であり、libc の中に実装コードが入っている。使い方は要するに、文字列による正規表現の指定を「コンパイル」し、regex_t 型の構造体に格納する。そしてその構造体を使って具体的な入力文字列に対してパターンマッチを行う。作業後、その構造体は解放する必要がある。インターフェイスは次の通り。
当然、コンパイルに成功すれば戻り値は０である。
typedef struct
{
regoff_t rm_so; /* 一致の開始位置（実際には文字列の先頭からのバイト数） */
regoff_t rm_eo; /* 一致の終了位置（同） */
} regmatch_t;
なので、REG_NOSUB を指定せずに、ちゃんと第３・第４引数を与えてやると、正規表現に基づいた置換が出来ることになる。
当然、正規表現と文字列が一致すれば、０であり、一致しなければ０以外である（ここらへん、大変UNIX臭い仕様である）。
この regex ライブラリを利用したプログラムは次の通り。これは引数として正規表現を受け取り、標準入力から入力された文字列について一致を報告する、というものである。
#include <stdio.h>
#include <regex.h>
/* 各行処理 */
void match( regex_t *reg, char *s, int matchers, regmatch_t match[] )
{
if( regexec( reg, s, matchers, match, 0 ) != 0 ) {
printf( "not match!!\n" ); /* 不一致の場合 */
} else { /* 一致した場合には一致位置なども表示 */
int i, j;
printf( "found match!! ... matches\n" );
for( i = 0; i < matchers; i++ ) {
if( match[i].rm_so == -1 ) break; /* 念のため */
printf( "match No.%d :", i );
/* まあ、表示だけなのでこうするのが一番簡単 */
for( j = match[i].rm_so; j < match[i].rm_eo; j++ ) {
putchar( s[j] );
}
putchar( '\n' );
}
}
}
int main( int argc, char **argv )
{
regex_t reg;
char buff[256];
regmatch_t *mc;
if( argc < 2 ) { fprintf( stderr, "reg pattern\n" ); exit(1); }
/* コンパイル */
if( regcomp( ®, argv[1], REG_EXTENDED ) != 0 ) {
fprintf( stderr, "cannot compile pattern!\n" );
exit( 1 );
}
printf( "regexp infomation...\n" );
printf( "reg.allocated=%d\n", reg.allocated );
/* 筆者環境だと最低で 32byte, 大体 64byte単位で確保。 */
/* 実際には全体のマッチが mc[0] に入り、それに加えて「()」の数の分だけ必要だから
reg.re_nsub（部分文字列の数）+1 確保する必要がある。 */
if( reg.re_nsub > 0 ) {
mc = (regmatch_t *)malloc( sizeof(regmatch_t) * (reg.re_nsub+1) );
if( mc == NULL ) {
fprintf( stderr, "cannot malloc regmatch_t data\n" );
exit( 1 );
}
}
while( fgets( buff, 255, stdin ) ) {
match( ®, buff, reg.re_nsub+1, mc );
}
regfree( ® ); /* regcomp() が alloc したメモリの解放 */
}
このような正規表現ライブラリの動作は、実際にはオートマトンの動作を覆い隠して使いやすくしているものなのである。現実のオートマトンの動作と並行して解説しよう。
正規表現をオートマトンに変換する数学的基礎は次の通りである。まず、オートマトンの細かい種別について、言葉の定義をしておこう。
とはいえ、決定性オートマトンがもっとも効率良く実装できることは言うまでもない。だから、正規表現のコンパイルとは、「正規表現」を「決定性オートマトン」に変換する動作なのである。以下「自動的に変換する」という表現は、「一般の場合においてさえ、自動的に変換するアルゴリズムが存在する」という意味であり、ライブラリで実装可能なアルゴリズムによって変換が出来るということを示す。
めでたし、めでたし。だから「正規表現」は「決定性オートマトン」に変換可能であり、「決定性オートマトン」は処理効率良くパターンマッチングを実現できる。実はこの解説の中で触れた「最長一致則」は、Ｃ言語の文法にも微妙な影を落している。たとえば次のコードを見てみよう。
int a = 1; int b = 2; int x = a+++b;
さて、x の値は何だろう？ これは「a++ + b」とでも「a + ++b」とでも解釈可能な式である。しかし、Ｃコンパイラは lex が作り出すレクサの中で、正規表現を使ってシンボルを切り出ししている。この時に最長一致則に基づいて、「+++」は常に「++」と「+」に分解される。それゆえ、この式は「int x = a++ + b;」であり、値は３になる。ＯＫ？
さて、前節で大変重要なことを述べた。「ある状態の入力について、入力に応じたその遷移先がただ１つに決まる」のならば、それは「決定性オートマトン」であり、この場合には処理効率良く処理できる（バックトラッキングなしに動作を決定できる）のである。オートマトンの動作についてヒントを得たプログラムは、やはり複数の状態と、それに対する入力について、ただ１つの遷移先を持つように処理を書くべきなのである。ここで最初の応用例として、日本語漢字コードのJISをEUCに変換するプログラムを取り上げよう。
まあ、JISをEUCに変換するコードはそんなに難しいものではない。問題はJISコードが２バイトで１つの漢字コードを表すのだが、そのJISコードはすべて 0x7F 以下のASCIIコードとバッティングするコードであることである。JISが日本語を表現するルールは次の通り。
それに対してEUCのルールは次の通りである。
この処理は勿論次のように書ける。一応「文字を落さない」仕様にしてあり、日本語JISのルールに従わないエスケープシーケンスはそのまま通るようにしてある（ちょっと ungetc(3) を使っているので、これが判らない人は「ungetcってどう使う？」を参照されたい）。
int jis2euc( )
{
static int status = 0; /* 状態は２つあり、static で保存 */
int c = getchar();
if( c == EOF ) { /* ファイルエンド */
return EOF;
}
if( status == 0 ) { /* ASCII モード */
if( c == 0x1B ) { /* 開始エスケープ第１文字 */
c = getchar();
if( c == 0x24 ) { /* 開始エスケープ第２文字 */
c = getchar();
if( c == 0x42 ) { /* 開始エスケープ第３文字 */
status = 1; /* だったら正常な日本語コードが開始 */
c = getchar();
return 0x80 | c; /* EUC に変換 */
} else { /* 異常なエスケープは ungetc() して */
ungetc( c, stdin );
ungetc( 0x24, stdin );
return 0x1B; /* 最初の文字を返す */
}
} else {
ungetc( c, stdin );
return 0x1B;
}
} else { /* フツーのASCIIモード */
return c;
}
} else { /* 漢字モード */
if( c == 0x1B ) { /* 終了エスケープ第１文字 */
c = getchar();
if( c == 0x28 ) { /* 終了エスケープ第２文字 */
c = getchar();
if( c == 0x42 ) { /* 終了エスケープ第３文字 */
status = 0; /* だったらASCIIモードに戻る */
c = getchar();
return c; /* ASCIIを返す */
} else {
ungetc( c, stdin );
ungetc( 0x28, stdin );
return 0x1B;
}
} else {
ungetc( c, stdin );
return 0x1B;
}
} else { /* フツーの漢字モード */
return c | 0x80; /* EUCで返す */
}
}
}
要するに、JISの問題は漢字開始コード／漢字終了コードが３バイトでかなり冗長なことである。これは勿論、他の（外国語の）コードも含めることができるように、こういうコードになっているのである。だから、異常なエスケープシーケンスについては、それを加工せずに出力するのならば、３文字読み進んでようやく異常であることがわかる、という仕組みなのである。まあ、複雑な if 文で読みにくいこと限りない。また、このプログラムにはちょっとしたバグがある。それは ungetc(3) の仕様に関わる問題だが、ungetc(3) はもし入力ストリームがEOFになってしまうと、文字が押し戻せないのである。だから、異常なエスケープシーケンスの中で EOF になったりすると、きちんと「異常なエスケープシーケンスはそのまま透過させる」という仕様をホントは実現できていないことになる。
とはいえ、まあこれだって「状態機械」には違いない。なぜならば２つの「状態」の間を入力に応じて遷移しているのであるのだから。しかし、これはもっと判りやすく、バグの少ないかたちに直すことができる。そのためには入力主導にプログラムを直す。
状態は７つある。正常な動作は ASCII → ESCAPE1 → OPEN1 → KANJI → ESCAPE2 → OPEN2 → ASCII のサイクルを回り、ASCII と KANJI では状態を変えずに回り続ける動作もある。もし EOF が入力されたら、それで終了状態に入り、メインループが停止する。
#include <stdio.h>
#define ASCII 0
#define KANJI 1
#define ESCAPE1 2
#define ESCAPE2 3
#define OPEN1 4
#define OPEN2 5
#define END -1
void output( int c )
{
putchar( c );
}
int jis2euc( int status, int c, void (*out)(int) )
{
switch( status ) {
case ASCII:
if( c == 0x1B ) {
return ESCAPE1;
} else if( c == EOF ) {
return END;
}
(*out)(c);
return ASCII;
break;
case KANJI:
if( c == 0x1B ) {
return ESCAPE2;
} else if( c == EOF ) {
return END;
}
(*out)( c | 0x80 );
return KANJI;
break;
case ESCAPE1:
if( c == 0x24 ) {
return OPEN1;
} else if( c == EOF ) {
(*out)( 0x1B );
return END;
} else {
(*out)( 0x1B );
(*out)( c );
return ASCII;
}
break;
case ESCAPE2:
if( c == 0x28 ) {
return OPEN2;
} else if( c == EOF ) {
(*out)( 0x1B );
return END;
} else {
(*out)( 0x1B );
(*out)( c );
return KANJI;
}
break;
case OPEN1:
if( c == 0x42 ) {
return KANJI;
} else if( c == EOF ) {
(*out)( 0x1B );
(*out)( 0x24 );
return END;
} else {
(*out)( 0x1B );
(*out)( 0x24 );
(*out)( c );
return ASCII;
}
break;
case OPEN2:
if( c == 0x42 ) {
return ASCII;
} else if( c == EOF ) {
(*out)( 0x1B );
(*out)( 0x28 );
return END;
} else {
(*out)( 0x1B );
(*out)( 0x28 );
(*out)( c );
return KANJI;
}
break;
}
}
int main( )
{
int status = ASCII;
while( status != END ) {
int c = getchar();
status = jis2euc( status, c, output );
}
return 0;
}
しかし、上記のプログラムならば、もっとうまく書ける。ほとんど状態ごとの処理はつまらないものばかりなので、これだったらテーブルに直した方が良い。出力処理は細かい関数として定義し、これらを関数ポインタのかたちでテーブルエントリに格納して呼び出す。
#include/* 状態の定義 */ #define ASCII 0 #define KANJI 1 #define ESCAPE1 2 #define ESCAPE2 3 #define OPEN1 4 #define OPEN2 5 #define LASTSTATUS 5 /* 最大の状態 */ #define END -1 /* 終了状態 */ #define OTHER -2 /* 指定外の文字にマッチする */ /* 関数ポインタ経由で実行される関数たち */ void asciiout( int c ) { putchar( c ); } void kanjiout( int c ) { putchar( c | 0x80 ); } void escapeout( int c ){ putchar( 0x1B ); if( c != EOF ) putchar( c ); } void openout1( int c ) { putchar( 0x1B ); putchar( 0x24 ); if( c != EOF ) putchar( c ); } void openout2( int c ) { putchar( 0x1B ); putchar( 0x28 ); if( c != EOF ) putchar( c ); } /* 個々の入力と処理を関係づける */ struct QTableItem { int in; /* 入力文字 */ void (*proc)( int ); /* 実行される関数 ==NULL だと呼ばない */ int next; /* 次の状態 */ }; /* ある状態についてのすべての入力とその処理 */ struct QTable { int num; /* 処理の数 */ struct QTableItem qt[3]; /* 個々の入力と処理 */ }; /* さて、現実の状態の定義 */ struct QTable Tables[] = { { 3, { { 0x1B, NULL, ESCAPE1 }, { EOF, NULL, END }, { OTHER, asciiout, ASCII } } }, { 3, { { 0x1B, NULL, ESCAPE2 }, { EOF, NULL, END }, { OTHER, kanjiout, KANJI } } }, { 3, { { 0x24, NULL, OPEN1 }, { EOF, escapeout, END }, { OTHER, escapeout, ASCII } } }, { 3, { { 0x28, NULL, OPEN2 }, { EOF, escapeout, END }, { OTHER, escapeout, KANJI } } }, { 3, { { 0x42, NULL, KANJI }, { EOF, openout1, END }, { OTHER, openout1, ASCII } } }, { 3, { { 0x42, NULL, ASCII }, { EOF, openout2, END }, { OTHER, openout2, KANJI } } } }; int jis2euc( int status, int c ) { int i; if( status < 0 || status > LASTSTATUS ) { /* サニティチェック */ return END; } /* 「状態」ごとにテーブル内容を順にチェック */ for( i = 0; i < Tables[status].num; i++ ) { if( c == Tables[status].qt[i].in || /* 入力とテーブルの定義が一致 */ Tables[status].qt[i].in == OTHER ) { /* 「何でも可」 */ if( Tables[status].qt[i].proc != NULL ) { (*Tables[status].qt[i].proc)( c ); /* 必要に応じ、処理の実行 */ } return Tables[status].qt[i].next; /* 次の状態を返す */ } } return END; /* ありえない */ } int main( ) { int status = ASCII; while( status != END ) { int c = getchar(); status = jis2euc( status, c ); } return 0; }
実際には正規表現ライブラリがやっているのは、このような「テーブル作り」なのである。
さて、有限状態機械（オートマトン）が大体判ったところで、もう少し実用的な応用例を出そう。「可変長引数マクロ」で紹介している、FORTRAN風の書式を解析し、可変長引数と共に、変わった書式の printf(3) のように使う例である。「可変長引数マクロ」ではFORTRAN風書式解析をする部分は飛ばして紹介しているのだが、ここではその書式解析について述べる。
FORTRAN風書式のフォーマットについて再掲しよう。
浮動小数点値と改行指定はサボっている。申し訳ない。このサブセットの書式の例は次の通り。
10 FORMAT(5X,'output is ',3A5,2X,I4,4X,I4)
WRITE(6,10) (MESS(I),I=1,3),DATA1,DATA2
これがＣのプログラムだと次のようになるわけだ。
char *mes[] = { "test", "my", "form" };
int data1 = 10;
int data2 = 222;
fortan_write( "5X,\'output is \',3A5,2X,I4,4X,I4", mes, data1, data2 );
出力は当然両方とも次の通り。
12345678901234567890123456789012345678901234567890 output is test my form 10 222
さて、この書式を解析して、扱いやすい次の構造体に直すことをする。
#define LITERAL 0 /* '〜' に対応する、リテラルの文字列 */
#define BLANK 1 /* X に対応する、空白出力 */
#define ASCII 2 /* A に対応し、引数から文字列を出力 */
#define NUMBER 3 /* I に対応し、引数から数値を出力 */
struct Format {
int kind; /* LITERAL などの種別 */
union u {
char *mess; /* LITERAL の場合、文字列ポインタを保持 */
struct form { /* BLANK, ASCII, NUMBER の場合 */
short repeat; /* 繰り返し数(前の数値) */
short num; /* 個別の書式の表示長さ(後の数値) */
} form;
} u ;
struct Format *next; /* 次の書式指定 */
};
この構造体を malloc し、free するのはこの関数である。
/* 構造体オブジェクトの作成 */
struct Format *newFormat( void )
{
struct Format *ret;
ret = (struct Format *)malloc( sizeof(struct Format) );
if( ret == NULL ) {
fprintf( stderr, "memory exhosted!\n" );
exit(1);
}
/* 内容の０クリアまでしておく */
memset( ret, 0, sizeof(struct Format) );
return ret;
}
/* 構造体の破棄。トップレベルを指定すれば、それ以降のものも同時に破棄 */
void deleteFormat( struct Format *f )
{
struct Format *tmp;
while( f ) {
tmp = f->next; /* いわゆる cdr ダウンで破棄 */
free( f );
f = tmp;
}
}
さて、状態機械のドライバの部分は次のようになる。１文字づつ、状態機械である do_state() に渡していき、それに応じて「状態」を遷移していく。構造体の作成は一種の副作用であり、とりあえずこれを戻り値とするのが do_state() の仕様とする。つまり、parse_fmt() は１つづつ struct Format のインスタンスを取得し、それを順につないでいくのである。
struct Format *parse_fmt( char *fmt )
{
struct Format *f; /* do_state() の戻り値 */
struct Format *ret = NULL; /* parse_fmt() 戻り値のトップレベル */
struct Format *prev = NULL; /* 新たに得たインスタンスを繋ぐ位置 */
int status = 0; /* 状態 */
while( status >= 0 ) {
f = do_state( &status, *fmt ); /* 状態機械 */
if( f != NULL ) { /* 新たにインスタンスが作られた */
/* ちょっと小細工 */
if( f->kind != LITERAL ) { /* LITERAL 以外は値を修正 */
if( f->u.form.repeat == 0 ) {
f->u.form.repeat = 1;
}
if( f->u.form.num == 0 ) {
f->u.form.num = 1;
}
}
/* 連結リストに繋ぐ処理 */
if( ret == NULL ) {
ret = f;
prev = ret;
} else {
prev->next = f;
prev = f;
}
}
fmt++; /* １文字進む */
}
if( status == -1 ) { /* 正しい終了状態 */
return ret;
} else { /* 異常な書式 */
deleteFormat( ret ); /* 作成したオブジェクトの破棄 */
return NULL;
}
}
まあ、若干オシャレな関数仕様ではある。状態機械から何か値を返したい場合には、引数に参照渡しで status を渡してやるしかない。では問題の do_state()。１文字づつ処理し、１つ１つの struct Format のインスタンスが完成したら、その時だけ NULL ではなくて、完成したインスタンスを返すようにしている。
これの状態機械の遷移図はそれほど単純ではない。筆者はプログラムを書き起こす前に次のような遷移図を書くわけだ。あとはこれを睨みながら書けば良いだけである。
手描きで済まぬ...こんなもん、わかりゃいい。「０」が初期状態、「−１」が受理状態であることは言うまでもない。ただし、ここでは省略しているが、「−２」という受理状態もあり、これは入力として示した以外の「異常な入力」に対する「エラー」を示す受理状態である。つまり、「−１」に最終的に到達すれば正常な書式であり、「−２」に到達すれば書式のエラーである。
static struct Format *do_state( int *status, char c )
{
static struct Format *at = NULL; /* 現在制作中のオブジェクトを保持 */
struct Format *ret = NULL; /* 戻り値用 */
static int num = 0; /* 数値を仮置きする */
static char buff[256]; /* 文字列を仮置きする */
static char *wp = buff; /* buff の書き込み位置ポインタ */
switch( *status ) {
case 0: /* 最初の状態 */
if( isdigit( c ) ) { /* 数値なら */
num = c - '0';
*status = 3;
} else {
switch( c ) {
case '\'': /* LITERAL の開始 */
at = newFormat(); /* インスタンスの作成 */
at->kind = LITERAL;
wp = buff; /* 初期設定 */
*status = 1;
break;
case 'A': /* ASCII の開始 */
at = newFormat(); /* インスタンスの作成 */
at->kind = ASCII;
*status = 4;
break;
case 'X': /* BLANK の開始 */
at = newFormat(); /* インスタンスの作成 */
at->kind = BLANK;
*status = 2;
ret = at; /* このケースは「X」のみだから、すでに完成 */
break;
case 'I': /* NUMBER の開始 */
at = newFormat(); /* インスタンスの作成 */
at->kind = NUMBER;
*status = 4;
break;
default:
*status = -2; /* その他は異常 */
}
}
break;
case 1: /* LITERAL の処理 0 → 1 → 2 → (0,-1)*/
if( c == '\'' ) { /* 閉じ ' を見つけたら完成 */
*wp = '\0';
at->u.mess = (char *)strdup( buff );
wp = buff;
*status = 2;
ret = at;
} else { /* それまでは保持バッファに仮置き */
*wp++ = c;
}
break;
case 2: /* インスタンスが完成した状態で、終了か継続を決める */
if( c == ',' ) { /* まだある */
*status = 0;
} else if( c == '\0' ) { /* 文字列終了 */
*status = -1;
} else { /* 異常 */
*status = -2;
}
break;
case 3: /* 処理の中で数値を蓄積し続ける */
if( isdigit(c) ) { /* 数値の蓄積 */
num = num * 10 + c - '0';
} else if( c == 'X' ) { /* BLANK 処理へ */
at = newFormat(); /* インスタンスの作成 */
at->kind = BLANK;
at->u.form.repeat = num; /* repeat 数に格納 */
ret = at; /* BLANKはこれで完成 */
*status = 2;
} else if( c == 'A' ) { /* ASCII処理 */
at = newFormat(); /* インスタンスの作成 */
at->kind = ASCII;
at->u.form.repeat = num;
*status = 4;
} else if( c == 'I' ) { /* NUMBER 処理 */
at = newFormat(); /* インスタンスの作成 */
at->kind = NUMBER;
at->u.form.repeat = num;
*status = 4;
} else { /* 異常 */
*status = -2;
}
break;
case 4: /* ASCII & NUMBER 処理 0 → (3) → 4 → (5) → (0,-1) */
if( isdigit(c) ) { /* 数値ならば */
num = c - '0';
*status = 5;
} else if( c == ',' ) { /* 出力数なしで次へ */
ret = at; /* 完成！ */
*status = 0;
} else if( c == '\0' ) { /* 出力数なしで終了 */
ret = at; /* 完成！ */
*status = -1;
} else {
*status = -2; /* 異常 */
}
break;
case 5:
if( isdigit(c) ) { /* 数値を蓄積し続ける */
num = num * 10 + c - '0';
} else if( c == ',' ) { /* 出力数があって、次へ */
at->u.form.num = num; /* 仮置きから格納 */
ret = at; /* 完成！ */
*status = 0;
} else if( c == '\0' ) { /* 出力数があって終了 */
at->u.form.num = num; /* 仮置きから格納 */
ret = at; /* 完成！ */
*status = -1;
} else {
*status = -2; /* 異常 */
}
break;
default:
fprintf( stderr, "state error %d\n", *status );
exit(1);
break;
}
return ret; /* 完成ならそのオブジェクトが、未完成なら NULL が返る */
}
という具合に、これならば大変デバッグがしやすいプログラムになる。これを atoi(3) などで解析することを考えた時には、ちょっとぞっとしない。また、atoi(3) を使うと、必然的に着目位置を後戻りさせなくてはならない（要するに atoi() で数値を取得した後で、数値を読み飛ばす）。これは混乱の元である。つまり、確実に１文字づつ処理することで、複雑な書式解析を混乱から救っているのである。これは「決定性オートマトン」の大きなメリットである。
もちろん、これが書けるためには、前提として遷移図をしっかりと書いておかなくてはならない。後は遷移図を睨みながら書くだけのことであるのだが...
ちなみにオブジェクト指向言語では、このような状態機械の実装のために、デザインパターンとして「State」パターンがある。これは状態一般を抽象基底クラスとして定義し、それから派生させて個々の「状態」をクラスにする。そして、状態のドライバに当たるクラスで個々の状態のインスタンスを作成し、入力と対応するハッシュテーブルにでも仕込んで、インスタンスに「遷移状態」をセットする手続きを呼び出して、個々のインスタンスに互いの遷移先を教えてやるのである。そうすると、たとえばこんな具合になる。
ちなみに、この State デザインパターンを利用した「対戦型五目並べ」を作った。ソース・解説付きなのでぜひご参照ください。
遷移図はこんな具合だとする。
private Status createStatus( int ban ) {
Status s0, sA, sB, sQ;
Hashtable prop;
/* それぞれの「状態」オブジェクトを作成する */
try {
s0 = Status.create( "status0" );
sA = Status.create( "statusA" );
sB = Status.create( "statusB" );
sQ = Status.create( "statusQ" );
} catch( Exception e ) {
return null;
}
/* s0 に遷移図をセットする */
prop = new Hashtable();
prop.put( "aA", sA );
prop.put( "bB", sB );
prop.put( NULL, sQ );
s0.setMap( prop );
/* sAに遷移図をセットする */
prop = new Hashtable();
prop.put( "aA", sA );
prop.put( "bB", sB );
prop.put( NULL, sQ );
sA.setMap( prop );
/* sBに遷移図をセットする */
prop = new Hashtable();
prop.put( "aA", sA );
prop.put( "bB", sB );
prop.put( NULL, sQ );
sB.setMap( prop );
/* 終了状態なので、すべての入力に対し不変のように遷移図をセットする */
prop = new Hashtable();
prop.put( NULL, sQ );
sQ.setMap( prop );
/* 初期状態を返す */
return s0;
}
それぞれの「状態」をインスタンスとして生成するのがミソである。しかし、すべての状態が完成した後でないと、遷移図を正しく与えられないので、コンストラクタとしては与えることができない。まあ、ハッシュテーブルとして与えてやるのが現実的だろう。