Super Technique 講座

有限状態機械

「有限状態機械(有限オートマトン)」とは、計算モデルの1つである。これは本来コンピュータ科学の中でも「計算論」に属する話題であり、通常のコンピュータを形式化したチューリング機械よりも能力の低い計算モデルなのだが、アルゴリズムとしてこの形式化を利用することが出来、しかもこの「有限状態機械」は広い応用を持っている。いわゆる「正規表現」を処理するライブラリはこの「有限状態機械」の典型的な応用なのだが、それ以外にもプログラマとして知っていると、アルゴリズムの可読性と処理速度を上げるヒントを得られるアイデアである。


有限状態機械とは?

「有限状態機械」とは、コンピュータ科学(とは言っても数学寄りの奴)の「計算論」を教科書を読むと、ほぼ一番最初に載っている奴である。大概「計算論」の教科書というと、「オートマトン」「文脈自由文法」「チューリング機械」「非決定性問題」(あとあれば「計算量理論」)といった構成になっているものだが、この「計算論」とは実はコンピュータが「計算」と言っているのはどういうことであり、その「計算」に出来ることと出来ないことは何か、ということを研究したコンピュータの数学的基礎に関する分野である。

この研究は1930年代に一応の結論(いわゆる「ゲーデルの不完全性定理」)が出て、コンピュータなどはまだ影も形もないにも関わらず、すでに「コンピュータに出来ること」の範囲は数学的には結論が出てしまっているのである! この文書は別に専門書ではないので、平たく言うと、コンピュータでは「あるプログラムが正しく書けているか」を一般的に検証することはできない、という結論が得られるのだ。だから我々プログラマは将来に亙って失業せずに済むのである(笑。けど永遠にバグと戦い続ける運命にある...)。

この計算論の冒頭に位置する「有限状態機械」(あるいは「有限オートマトン」、もっと略して単に「オートマトン」)とは、コンピュータのモデルの一つだが、我々が知っているコンピュータよりも随分能力が低いものである。しかし、一応「計算のようなこと」が出来るモデルなのである。

ではオートマトンはどうやって出来ているのだろう? オートマトンとは「入力に従って別な「状態」に遷移することのできる「状態」の集合」である。つまり、いくつかの(有限な)状態があり、それらは入力の種類によって、「ある入力では状態Aへ」、「別な入力では状態Bへ」、それぞれ「状態0」から遷移する、という風な構造になっている。だから、ただ一つの「最初の状態」(よく q0と表記する)から、さまざまな入力によって状態を遷移させながら、最終的に「受理状態」(複数あってよいから普通は「受理状態の集合」。よく qFと表記する)へ遷移し、最終的にどの「受理状態」に到達したかによって、結果が得られるという一連の「機械」なのである。

ということはオートマトンは一種のテーブルである。つまり、「状態」ごとに「入力」に対応した「次の状態」の表がある。この表に従って「最初の状態」から「入力」を受け付けていって、いくつかある「受理状態」に到達したら、それで遷移が終了し、どの「受理状態」かによって、その「入力の系列」について何かの結論が得られるわけである。これは大変有効なプログラミングの技法である。つまり、何かの入力が適切なものであるかどうかを、このオートマトンによって判定できるのである。一番端的な応用はいわゆる「正規表現」であり、「正規表現」は一連の入力を受け付けて、それが「正規表現」で表されたものであるかどうかを判定する。この機構はオートマトンの現実的に重要な応用なのである。


正規表現とは?

数学的に見ると、いわゆる「正規表現」は次の3つしかない。

  1. 「連接」。ある文字の次にある文字が続くこと。これを「ab」で表記する。つまり、文字 a の次に文字 b が来ることである。
  2. 「選択」。ある文字か別な文字のどちらかであること。これを「a|b」で表記する。つまり、文字 a か文字 b であることを示す。
  3. 「閉包」。ある文字の0回以上の繰り返しであることである。これを「a*」と表記する。つまり、文字 a が0回以上繰り返されるのだから、「a」「aaa」「aaaaaaa」はすべてこの正規表現と一致する。この時、「」(文字がない)とも一致することに注意しなくてはならない(「0回以上」だからね)。

また、この「正規表現」は「( )」を使って適切にグルーピングすることもできるのである。だから、より複雑な応用は次の通り。

(B|b)ana(na)*  → banana, Banana, bana, Bananana, banananananana などと一致

しかし、実用的なレベルだと、次のような仕様が追加されていると使いやすい。だから、「正規表現」を利用するツールでは、通常次の「メタ文字」(そのまま文字指定と解釈されるのではなくて、正規表現の機能を示す文字。すでに登場は「|*()」)として、次のものを追加するのが普通である。

字種を示す [ ]
勿論「(a|b|c|d|e|f|g)」という風にグループ化して「|」を使えば「a から g までの文字」を示すことができるのだが、これは面倒なだけである。なので、それが1文字だけの「選択」ならばもっと簡便な記法が用意されている。つまり、一種の「字の種類」と捉えて、「選択」のグループ化を「[ ]」で行うのである。この時、「[a-z]」(すべてのアルファベット小文字)のように、「-」を使って範囲を示すこともできる。この範囲は通常ASCII文字の数値としてのコードの範囲である。同様に「^a-zA-Z0-9」(いわゆる「特殊文字」)のように、この範囲を否定する書き方もできる。この「[ ]」があるために、正規表現ツールでは「|」を使うのは複数文字をグループ化して指定する場合にほとんど限られる(たとえば「(test|tmp)」のように)。
任意の1文字とマッチする 「.
これは一種のワイルドカードである。シェルの glob パターンでいうと、「?」に相当するが、シェルの「*」は正規表現では「.*」(任意の1文字の0回以上の繰り返し)に相当する。「.*」による指定は正規表現の重要なイディオムである。
行の開始を示す「^」と行の末尾を示す「$
正規表現による検索・置換ツールでは、行指向テキストをその対象とする。そのため、「行頭」「行末」が指定できると便利である。そのため、「^.*$」の正規表現は任意の「行」と一致するし、「^A.*$」ならば「A」で始まる任意の行と一致する。
1回以上の繰り返しを示す「+
古い正規表現ツール(sedなど)ではサポートされていない。「*」による「0回以上の繰り返し」だと表現がやや冗長になるケースが多い。「少なくとも1文字はこの文字がある」というケースの指定が実用的であるために、「+」によって「1回以上の繰り返し」を指定することができるようになっているツールが多い。これは数学的には当然、「A+」→「AA*」と等価である。
エスケープ文字としての「\
さてメタ文字が増えすぎた。だから、メタ文字自身を指定したい時に、その手段がないと大変不便になる。そのため、「\*」のように「\」をつけてやることで、それがメタ文字ではなくて「字の指定」(この場合には「*」という「文字」)であることを示す。これはC言語のエスケープ文字(文字列の内部で「"'」を示すために「\"\'」と書く)とほぼ同等の機能である。同様にいわゆる「\n」(改行文字)や「\t」(タブ文字)のようなお馴染みの特殊文字指定のエスケープも普通に使える。

こんな感じで使える。

^#[ \t]*[a-zA-Z0-9_]+  → C言語プリプロセッサ・ディレクティヴ行に一致

正規表現が利用できるツールは昔からUNIXには、数多くの標準ツールとして用意されている。また、スクリプト言語だと最近のものでは、言語仕様に正規表現パターンマッチングが採用されているケースが多い。これらを使いこなすことが快適なUNIX環境の秘訣の一つである。どんなツールがあるのか見てみよう。

grep, egrep
古典的なUNIXの文字列検索ツールである。grep は「-E」オプションにより、egrep はそのままで正規表現によるパターン指定ができる。
ed, ex, vi などのエディタ
これらの「古い」エディタでも、正規表現による検索&置換が可能である。元々「grep」という名前の由来は、このようなエディタで正規表現検索をするときに「g/re/p」と指定したことから来ている程である。
Emacs
当然ユーザの多くが利用しているエディタである Emacs でも使えないわけがない。「M-x isearch-forward-regexp」で正規表現で検索でき、「M-x query-replace-regexp」で正規表現による置換が可能である(もっと他にもあるが...)。
sed
sed は正規表現の置換機能だけを、ed から抜き出したツールである。これは高速で動作し、ちょっとしたプログラミング風の機能もあり、馴れると大変便利なものである。筆者は MS-DOS の時代から愛用している(昔、ASCII sed が高速で重宝した...)。癖のあるコマンド体系なので、今時のプログラマは「ぎょ!」とするかも知れないが、冗長な awk を使うよりも、筆者はこっちを好む(古いか?)。
lex
lex は本格的なプログラミングツールである。これは普通 yacc とペアにして使い、「任意の言語の構文解析部」を作るのに使う。つまり、コンパイラやインタプリタを作る場合には、ほぼ絶対的にお世話になるツールである。このうち、yacc は文脈自由文法を利用して狭い意味での「構文」を処理する部分を(パーサ)作るが、その前段階でトークンを切り出す部分(レクサ)を作るのが lex(LEXical analyzer generator)である。このトークン切り出しの指定のため、やはり正規表現でパターンを指定する。
その他スクリプト言語
正規表現を言語仕様として採り入れて、プログラムの中に正規表現パターンを記述して、パターンマッチングをするスクリプト言語は数多い。もっとも古典的なのは当然 awk であり、パターンに応じたブロックを実行することができ、スクリプト言語と言うよりも単なるテキストツールとして使っているユーザも多かろう。より本格的にスクリプト言語らしい言語で、正規表現を直接書けるものとしては、Perl や Tcl, Ruby などがあるが、今時のスクリプト言語では逆に「正規表現が使えない方が珍しい」と言っても過言ではない。JavaScript や PHP のようなWWW技術絡みの言語だって、当然使えるのである。
正規表現ライブラリ
とはいえ、コンパイラ言語の場合には、正規表現を直接プログラム内に書けるのはやや邪道である。ここは「正規表現ライブラリ」の呼出によって処理せざるを得ない。当然古典UNIXツールがあった時代から、正規表現ライブラリが存在したのであり、これは「regex」ライブラリとして知られていた(今ではフツー libc に統合されている)。これによってプログラマは正規表現の詳細動作について知らなくても、正規表現の恩恵をプログラムのレベルで受けることができるのである。

まあ、問題としては個々のツールで、正規表現のどの機能を実装するか、そのツールの上での表現がどうなるか、という点で統一が取れていないことであろう。つまり、ツールによって細部がちょっとづつ「癖がある」のである。この傾向は特に置換指定において甚だしい(これは厳格には正規表現の仕様ではなくて、ツールの仕様になるからね)。


正規表現ライブラリの使い方

ヘッダファイルは regex.h であり、libc の中に実装コードが入っている。使い方は要するに、文字列による正規表現の指定を「コンパイル」し、regex_t 型の構造体に格納する。そしてその構造体を使って具体的な入力文字列に対してパターンマッチを行う。作業後、その構造体は解放する必要がある。インターフェイスは次の通り。

int regcomp(regex_t *preg, const char *regex, int cflags);
コンパイルを担当。第2引数として正規表現を記述した文字列を与え、第1引数の構造体にコンパイルした結果を格納する。第3引数は動作の詳細に関するフラグである。指定可能な文字定数は次の通り。
REG_EXTENDED
これは拡張正規表現を使う指定である。平たく言えば、デフォルトは sed の正規表現に準じた正規表現を使うが、これを指定すると Perl 風の正規表現が使えるようになる。
REG_ICASE
実用上、大文字小文字の区別をしたくないときに、いちいち「選択」で記述するのはうっとおしい。そこで、全体的に大文字、小文字の区別をしないように指定するフラグである。
REG_NOSUB
部分文字列を記録しない。要するに regexec() でパターンマッチをした時に、具体的な一致箇所を記録する機能がある(「(〜)」で指定する)のだが、これをしないようにする。単に「全体が一致するか」だけの利用をするのならば、これを指定すると少し効率が良い。
REG_NEWLINE
これを指定しないと、行指向テキストであるとは見なされなくなる。つまり、改行コードは普通の文字であり、「^」はテキストの先頭、「$」はテキストの末尾であると解釈される。これを指定すると、改行コードによる行指向テキストであると解釈されて、「$」が(実質上)改行コードとマッチすることになる。

当然、コンパイルに成功すれば戻り値は0である。

int regexec( regex_t *preg, char *string, size_t nmatch, regmatch_t pmatch[], int eflags);
具体的な文字列と、正規表現とをパターンマッチする。つまり、第1引数に先程 regcomp() でコンパイルした結果を渡し、それと第2引数の文字列とを比較するのである。マッチすれば0を戻り値とし、マッチしなければそれ以外を返す。第5引数はやはりフラグであるが、それほど設定のメリットがあるフラグではないので、通例 0 である。第3引数、第4引数はコンパイル時に REG_NOSUB を指定しなかった場合にだけ意味があり、マッチした位置を返す構造体である regmatch_t を確保した数と、その確保された regmatch_t へのポインタを与える。そうすると、実行結果として一致した位置を返す。regmatch_t の定義は次の通りである。
typedef struct
{
   regoff_t rm_so;  /* 一致の開始位置(実際には文字列の先頭からのバイト数) */
   regoff_t rm_eo;  /* 一致の終了位置(同) */
} regmatch_t;

なので、REG_NOSUB を指定せずに、ちゃんと第3・第4引数を与えてやると、正規表現に基づいた置換が出来ることになる。

当然、正規表現と文字列が一致すれば、0であり、一致しなければ0以外である(ここらへん、大変UNIX臭い仕様である)。

void regfree(regex_t *preg);
実はコンパイルされた結果はかなり巨大なテーブルである。だから、これは使い終ったら解放しないとメモリ利用効率が悪化する。そのため、メモリを解放するための関数が用意されている。まあ、要するに regex_t 自身を直接プログラマが操作することを避けるためにあるわけだ。

この 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 したメモリの解放 */
}

オートマトンと正規表現

このような正規表現ライブラリの動作は、実際にはオートマトンの動作を覆い隠して使いやすくしているものなのである。現実のオートマトンの動作と並行して解説しよう。

正規表現をオートマトンに変換する数学的基礎は次の通りである。まず、オートマトンの細かい種別について、言葉の定義をしておこう。

決定性オートマトン(DFA)
ある「状態」に対して、入力によって即時に次の「状態」を決定できる。つまり、「ある入力」に対して遷移する状態は1つしかない。
非決定性オートマトン(NFA)
ある「状態」で、「ある入力」に対して遷移可能な状態が複数あっても良い。全体の入力によって、全体的に特定の終了状態に遷移すれば良いのである。たとえば、「a.*c」の正規表現に対する入力を考えた時、「acacac」の入力の中で「ac」「acac」「acacac」のどの入力部分パターンと一致しても構わないはずである。しかし、現実には「最長一致則」というルールがあり(これは「非決定性オートマトン」の性質による)、もっとも長い入力である「acacac」とだけ一致する。これを逆に考えると、「.*」のパターンに取ってみれば「c」が入力された時に、「.*」のパターンで処理するのか、それとも次の状態に進んで「c」として処理するのか、決定できないことになる。しかし、これは重大な問題ではなく、最長一致のルールのもとで全体で決定すれば良いことなのである。
ε動作付き非決定性オートマトン
更に非決定性オートマトンに、「入力なしで」遷移できる能力を与えておく。この「入力なしの入力」を「ε動作」と呼ぶ。

とはいえ、決定性オートマトンがもっとも効率良く実装できることは言うまでもない。だから、正規表現のコンパイルとは、「正規表現」を「決定性オートマトン」に変換する動作なのである。以下「自動的に変換する」という表現は、「一般の場合においてさえ、自動的に変換するアルゴリズムが存在する」という意味であり、ライブラリで実装可能なアルゴリズムによって変換が出来るということを示す。

  1. 正規表現は「ε動作付き非決定性オートマトン」に自動的に変換できる。
  2. 「ε動作付き非決定性オートマトン」は、「(ε動作のない)非決定性オートマトン」に自動的に変換できる。
  3. 「非決定性オートマトン」は「決定性オートマトン」に自動的に変換できる。

めでたし、めでたし。だから「正規表現」は「決定性オートマトン」に変換可能であり、「決定性オートマトン」は処理効率良くパターンマッチングを実現できる。実はこの解説の中で触れた「最長一致則」は、C言語の文法にも微妙な影を落している。たとえば次のコードを見てみよう。

int a = 1;  int b = 2;
int x = a+++b;

さて、x の値は何だろう? これは「a++ + b」とでも「a + ++b」とでも解釈可能な式である。しかし、Cコンパイラは lex が作り出すレクサの中で、正規表現を使ってシンボルを切り出ししている。この時に最長一致則に基づいて、「+++」は常に「++」と「+」に分解される。それゆえ、この式は「int x = a++ + b;」であり、値は3になる。OK?


簡単な応用〜JIS →EUC 変換

さて、前節で大変重要なことを述べた。「ある状態の入力について、入力に応じたその遷移先がただ1つに決まる」のならば、それは「決定性オートマトン」であり、この場合には処理効率良く処理できる(バックトラッキングなしに動作を決定できる)のである。オートマトンの動作についてヒントを得たプログラムは、やはり複数の状態と、それに対する入力について、ただ1つの遷移先を持つように処理を書くべきなのである。ここで最初の応用例として、日本語漢字コードのJISをEUCに変換するプログラムを取り上げよう。

まあ、JISをEUCに変換するコードはそんなに難しいものではない。問題はJISコードが2バイトで1つの漢字コードを表すのだが、そのJISコードはすべて 0x7F 以下のASCIIコードとバッティングするコードであることである。JISが日本語を表現するルールは次の通り。

  1. ASCII文字はそのまま表現する。
  2. 漢字コードを表現する場合には、特定のエスケープシーケンスを使う。漢字コードの開始をマークするのに「0x1B 0x24 0x42」のコードを使い、漢字コードの終了をマークするのに「0x1B 0x28 0x42」のコードを使う。これによって挟まれた部分は2バイトによって1文字を表す漢字の部分である。

それに対してEUCのルールは次の通りである。

  1. ASCII文字はそのまま表現する。
  2. 漢字コードを表現する場合には、JISコードの各値について、0x80 を OR したものを使う。つまり、最上位ビットを立てるのである。だから、ASCIIコードと混同されることはない。

この処理は勿論次のように書ける。一応「文字を落さない」仕様にしてあり、日本語JISのルールに従わないエスケープシーケンスはそのまま通るようにしてある(ちょっと ungetc(3) を使っているので、これが判らない人は「ungetcってどう使う?」を参照されたい)。

int jis2euc( )
{
   static int status = 0;  /* 状態は2つあり、static で保存 */
   int c = getchar();
   if( c == EOF ) {        /* ファイルエンド */
      return EOF;
   }
   if( status == 0 ) {     /* ASCII モード */
      if( c == 0x1B ) {       /* 開始エスケープ第1文字 */
         c = getchar();
         if( c == 0x24 ) {    /* 開始エスケープ第2文字 */
            c = getchar();
            if( c == 0x42 ) { /* 開始エスケープ第3文字 */
               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 ) {       /* 終了エスケープ第1文字 */
         c = getchar();
         if( c == 0x28 ) {    /* 終了エスケープ第2文字 */
            c = getchar();
            if( c == 0x42 ) { /* 終了エスケープ第3文字 */
               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の問題は漢字開始コード/漢字終了コードが3バイトでかなり冗長なことである。これは勿論、他の(外国語の)コードも含めることができるように、こういうコードになっているのである。だから、異常なエスケープシーケンスについては、それを加工せずに出力するのならば、3文字読み進んでようやく異常であることがわかる、という仕組みなのである。まあ、複雑な if 文で読みにくいこと限りない。また、このプログラムにはちょっとしたバグがある。それは ungetc(3) の仕様に関わる問題だが、ungetc(3) はもし入力ストリームがEOFになってしまうと、文字が押し戻せないのである。だから、異常なエスケープシーケンスの中で EOF になったりすると、きちんと「異常なエスケープシーケンスはそのまま透過させる」という仕様をホントは実現できていないことになる。

とはいえ、まあこれだって「状態機械」には違いない。なぜならば2つの「状態」の間を入力に応じて遷移しているのであるのだから。しかし、これはもっと判りやすく、バグの少ないかたちに直すことができる。そのためには入力主導にプログラムを直す。

状態は7つある。正常な動作は 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風書式の処理

さて、有限状態機械(オートマトン)が大体判ったところで、もう少し実用的な応用例を出そう。「可変長引数マクロ」で紹介している、FORTRAN風の書式を解析し、可変長引数と共に、変わった書式の printf(3) のように使う例である。「可変長引数マクロ」ではFORTRAN風書式解析をする部分は飛ばして紹介しているのだが、ここではその書式解析について述べる。

FORTRAN風書式のフォーマットについて再掲しよう。

  1. 各項目は「,」で区切られる。
  2. 項目は「'〜'」のようなそのまま出力される「リテラル文字列」か、引数を解釈して変換して出力する「出力指定」である。
  3. 「出力指定」はその出力型に応じて、「空白出力」、「文字出力」、「数値出力」がある。
  4. 「空白出力」は「10X」のようなかたちで、10文字の空白を出力する。
  5. 「文字出力」は「5A10」のようなかたちで、10文字の文字列が入っている引数を5つ使って出力する。要するにFORTRANでは、WRITE命令の引数として、配列を一種のループと共に渡すことが出来るのである。ちゃんとFORTRANの仕様に合わすとCでは実装が難しいので、このかたちで指定した時には正しく配列が5要素あることに制限する。もちろん「A50」のような指定もできる。
  6. 「数値出力」もやはり「文字出力」と同様に配列を指定できて「3I4」のように指定する。これは数値4桁の数の3要素の配列があることを指定する。勿論「I4」のように配列ではない数値も指定できる。

浮動小数点値と改行指定はサボっている。申し訳ない。このサブセットの書式の例は次の通り。

    10 FORMAT(5X,'output is ',3A5,2X,I4,4X,I4)
       WRITE(6,10) (MESS(I),I=1,3),DATA1,DATA2

これがCのプログラムだと次のようになるわけだ。

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);
   }
   /* 内容の0クリアまでしておく */
   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;
   }
}

さて、状態機械のドライバの部分は次のようになる。1文字づつ、状態機械である do_state() に渡していき、それに応じて「状態」を遷移していく。構造体の作成は一種の副作用であり、とりあえずこれを戻り値とするのが do_state() の仕様とする。つまり、parse_fmt() は1つづつ 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++;  /* 1文字進む */
   }
   if( status == -1 ) {    /* 正しい終了状態 */
      return ret;
   } else {                /* 異常な書式 */
      deleteFormat( ret ); /* 作成したオブジェクトの破棄 */
      return NULL;
   }
} 

まあ、若干オシャレな関数仕様ではある。状態機械から何か値を返したい場合には、引数に参照渡しで status を渡してやるしかない。では問題の do_state()。1文字づつ処理し、1つ1つの struct Format のインスタンスが完成したら、その時だけ NULL ではなくて、完成したインスタンスを返すようにしている。

これの状態機械の遷移図はそれほど単純ではない。筆者はプログラムを書き起こす前に次のような遷移図を書くわけだ。あとはこれを睨みながら書けば良いだけである。

手描きで済まぬ...こんなもん、わかりゃいい。「0」が初期状態、「−1」が受理状態であることは言うまでもない。ただし、ここでは省略しているが、「−2」という受理状態もあり、これは入力として示した以外の「異常な入力」に対する「エラー」を示す受理状態である。つまり、「−1」に最終的に到達すれば正常な書式であり、「−2」に到達すれば書式のエラーである。

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() で数値を取得した後で、数値を読み飛ばす)。これは混乱の元である。つまり、確実に1文字づつ処理することで、複雑な書式解析を混乱から救っているのである。これは「決定性オートマトン」の大きなメリットである。

もちろん、これが書けるためには、前提として遷移図をしっかりと書いておかなくてはならない。後は遷移図を睨みながら書くだけのことであるのだが...


State デザインパターン

ちなみにオブジェクト指向言語では、このような状態機械の実装のために、デザインパターンとして「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;
}

それぞれの「状態」をインスタンスとして生成するのがミソである。しかし、すべての状態が完成した後でないと、遷移図を正しく与えられないので、コンストラクタとしては与えることができない。まあ、ハッシュテーブルとして与えてやるのが現実的だろう。



copyright by K.Sugiura, 1996-2006