gallu’s blog

エンジニアでゲーマーで講師で占い師なおいちゃんのブログです。

状態遷移プログラム

えっと……ちょっと難しい説明になるのですが。とはいえ、ある程度のレベルのプログラマであれば知って損はないっていうか知らなきゃ損するネタなので、頑張って説明してみたいと思います。
まず、状態遷移図ってのがあります。これについてはてけとうにぐぐって(www.google.com)ください。


さて。例題としてCSVを取り上げます。且つ、例題なので簡略化します :-P
CSVの文字列を二つのモードに切り分けてみましょう。
つまり
・通常モード
・二重引用句内モード
です。


通常モードにおいて、,はデータの区切り、改行はレコードの区切りを表します。
二重引用句内モードにおいては、,も改行も「そのまんまデータとして」取り扱います。


また、
通常モードで二重引用句”が出てきた場合、二重引用句内モードに移行します。
二重引用句内モードで二重引用句”が出てきた場合、通常モードに移行します。


ここまではOKでしょうか?


さて。
通常プログラムを組むときって、多分if文を連打して、


foreach ( 対象文字 <- 文字列) {
 if (モード == 通常) {
  // 通常モード の処理
  if (対象文字 == ',') {
   データ区切りの処理
  } else
  if (対象文字 == '\n') {
   レコード区切りの処理
  } else
  if (対象文字 == '"') {
   モード = 二重引用句内
  } else {
   対象文字をデータに足しこむ
  }
 } else if (モード == 二重引用区内) {
  // 二重引用句内モード の処理
  if (対象文字 == '"') {
   モード = 通常
  } else {
   対象文字をデータに足しこむ
  }
 }
}
って感じで書くかと思うのですが。
今回はモードが2つですからまだいいのですが、これで状態がもっと沢山あったり、或いは「Aの状態からはBとCになりえて、BからはAとCとDとEになりえて、CからはBとDとEになりえて…」みたいな複雑な状態遷移図をコード化すると、なんか物凄いネストの嵐になって、可読性が低下すること請け合いです :-P


そこで状態遷移です。
私はもっぱら、クラス or 関数ポインタを用います。
今回はクラスを用いてみましょう。
クラスは、「処理クラス」を基底クラスとして、その派生クラスとして「通常モード処理クラス」と「二重引用区内モード処理クラス」を実装します。
関数ポインタ使うなら、引数と戻り値をあわせておけばOKです。
で、以下がソースになります。


// クラス宣言:っつかほとんど構造体ですが
class データクラス {
private:
 通常インスタンス;
 二重引用句内インスタンス;

 分解したCSVが保存できそうなデータタイプ
}

// 初期処理
データクラス->通常インスタンス = 通常モード処理クラス;
データクラス->二重引用区内インスタンス = 二重引用区内モード処理クラス;

処理インスタンス = 通常インスタンス; // 取り合えず初めは通常インスタンススタートってことで。
foreach ( 対象文字 <- 文字列) {
 // 処理
処理インスタンス = 処理インスタンス->処理(データクラス, 対象文字);
}

こんな感じです。
え? 短すぎてよくわかんない?
では順を追って。


まず初めは、「処理インスタンス->処理()」ってのは実際には「通常インスタンス->処理()」がcallされます。
で、通常モード処理クラス内の処理メソッドは、前述のまんま「,はデータの区切り、改行はレコードの区切り、それ以外はデータ」という処理をします。
また、二重引用句”が出てきた場合、二重引用句内モードに移行しなければならないので、returnに「データクラス->二重引用句内インスタンス」を、そうでないばあいはreturnに「データクラス->通常インスタンス」を復帰します。
同じように、二重引用句内モード処理クラスの処理メソッドも同じような処理をします。
そうすると、もし通常モードで二重引用句が出てくれば「処理インスタンス」のオブジェクトへのポインタが切り替わるので自動的にモードが二重引用区内モードに切り替わり、その処理が行われ、その逆もまたしかり、となります。


状態遷移プログラムはこんな感じでそれぞれの状態にそった処理が簡単に記述でき、割合にシンプルに処理がかけます。
っていうか、状態遷移図のそれぞれの○ごとにクラス(ないし関数)を書くだけなので、かなり複雑な状態遷移でも楽に書けます。


実際にCSVを処理するときは、私は


*set_nomal:通常モード
最も基本的な状態。以下の挙動を行う。
',' cellの区切りを意味する文字と判断する
'"' エスケープモードへのモード切替を行う
'\r' 改行だが、CR-LFの可能性を考え、CRLFモードに切り替える
'\n' 改行。一行のデータの終わりと判断する
any 通常のデータとみなす


*set_crlf:CRLFモード
CR-LFを想定しているモード
'\n' '\r\n'であったため、ここで一行のデータの終わりと判断
any '\r\n'ではなかったため、現在のデータを通常モードで再処理


*set_esp:エスケープモード
'"'や','を入れるためのモード。','はただのデータとして扱われる
'"' モード切替かデータかわからないため、エスケープチェックモードへ切り替え
any 通常のデータとみなす


*set_esp_chk:エスケープチェックモード
エスケープモード中に出てくる'"'を処理するためのモード
'"' '""'となっているため、データに'"’を追加、モードはエスケープ。
any エスケープモードから通常モードへの切り替え指示とみなす。
モードを通常に切り替え、現在のデータを通常モードで再処理


の4つのモードの切り替えで処理しています。


…って、Perlでよければサンプルコードのっけたほうがよいんですかねぇ?