CSVの解析とその技法（状態遷移と先読み）

ほえほえ＠スプシマン @hoehoe1234

プログラミングナイト４回目で解説した状態遷移を使ったCSV（１行）の解析ルーチン。この程度であれば相互再帰を使わなくてもいけますね。バックトラックもありませんし。 pic.twitter.com/caA74UFgfn

拡大

ほえほえ＠スプシマン @hoehoe1234

これの強いところは、プログラミングなのでRFCに沿わないCSVでも状態遷移と先読みで表現できれば対応できるところです。状態遷移で書けないようであればそもそもコードに落とせないので。書き始める前の状態整理としてはとてもよいでしょう。

ほえほえ＠スプシマン @hoehoe1234

もちろん、この図が唯一の回答ではありません。自分なりに書く練習をしていけばよいのです。ポイントは「状態の抽出」でしょう。これは「レールロードダイアグラム」を書いて要点に番号を振ります。この発想があれば状態は抽出できます。

ほえほえ＠スプシマン @hoehoe1234

------項目-----------> 　↑　　　　　 ↓ +-----(,)------+ CSVですとこのように、項目の前に状態①を、項目の後に状態②を設定すればよいことが分かります。

ほえほえ＠スプシマン @hoehoe1234

項目はさらに細分化されていて、「非エスケープ」と「エスケープ」に分類されます。階層的になっていますが今回は展開して状態の③と④としました。この③と④は「項目認識中」ですので合致する文字はどんどん追加していきます。

ほえほえ＠スプシマン @hoehoe1234

項目が終わったことを認識すると（たとえばカンマを読み込んだ、DQUOTで終了した）１文字プッシュバックして次は②のカンマ待ち状態になります。CSVでは実は状態遷移は入れ子になっていますが、状態が少ないので展開して書いても十分でしょう。

ほえほえ＠スプシマン @hoehoe1234

プログラムの正しさはコードを書く前に検証できます（というか検証しなければいけません）。いろいろなCSVの１行を想定して、実際に状態遷移を動かして最後に「accept」または「error」で終るかどうかを検証するのです。これにはプログラムを書く必要はありません。

ほえほえ＠スプシマン @hoehoe1234

RFCのABNFをそのまま実装してもうまく実装できますが、バックトラックのないCSVのような解析は状態遷移＋先読み手法がもっともうまく機能する入力データ構造の一つです。お時間があれば状態遷移表を書いてみるか、または提示した状態遷移表を検証してみてください。おどろくほどうまく動くはずです。

ほえほえ＠スプシマン @hoehoe1234

これが技法というものです。頭が良くなったわけでもさして勉強したわけでもない昨日と同じ自分でもこのような簡単な「技法」を覚えるだけでCSVが「正しく解析」できるのです。手法としてはごく簡単ですのでぜひ習得してみてください。

ほえほえ＠スプシマン @hoehoe1234

もちろん、CSVの本当の問題は「CSVの体をなしていない」ということでしょう。多くはクオーディングが不十分なことに起因します。しかし、状態遷移を書いて「基本となるロジック」を確立していればそのような無法状態にも「武器」をもっていどめるのではないでしょうか？

ほえほえ＠スプシマン @hoehoe1234

これは有名なドラゴンブック（２版）ですが、複雑な文法（ドラゴン）に騎士が「技法（LALRとか）」を身にまとい戦う姿です。手法、技法とはまさにこれです。使いこなすことによりドラゴンも克服できるのです。テキストの解析には、まずは、「状態遷移と先読み」技法を覚えましょう。 おしまい。 pic.twitter.com/8N9gBXsB6R

拡大

ほえほえ＠スプシマン @hoehoe1234

技法は高度になればなるほど学習コストが増えます。ノンプロ、本職問わずに「そこそこ」まで習得するのが現実的でしょう。現実的なラインとは「持っている技法を組み合わせてそこそこむずかしい問題に対処できる」となります。CSVの解析が必要な環境でれば状態遷移と先読み手法ということになります。

ほえほえ＠スプシマン @hoehoe1234

知識・手法とその応用・組み合わせはもちろん競合するものではありません。問題に対して、①「知識なき応用は無力」ですし②「応用なき知識は無駄」です。前者は問題が解決できませんし、後者は宝の持ち腐れです。

ほえほえ＠スプシマン @hoehoe1234

一般的に習得が比較的容易で効果が高いのは ①巧妙な制御構造を知る ②よい関数IFについて知る ③状態遷移と先読み ④再帰とループの組み合わせ ⑤定番アルゴリズム ⑥中学卒業程度の数学 ⑦モジュール分割 となり、これらを組み合わせることでかなりの難問にも対応できるようになります。

ほえほえ＠スプシマン @hoehoe1234

csvの状態遷移だけど、先読みしてunreadしないでそのままの状態で遷移を続けるほうがよさそうな感じですね。式の評価だと様々のところから呼び出されるので「式の範囲」だけを認識するためにunreadは必要そうですが、CSVのような簡易解析でよい場合は不要そうですね。あとで試してみます。

ほえほえ＠スプシマン @hoehoe1234

ファイルと同じ感覚で読んだ文字で分岐していく（各関数に入ったときにはすでに文字は読まれているという意味）状態遷移はこんな感じになります。 pic.twitter.com/y7vMHadDKh

拡大

ほえほえ＠スプシマン @hoehoe1234

こちらは最初に書いた状態遷移（各関数の頭で文字を読んで分岐）の修正版。前ツイの「関数に入ったときにすでに１文字読み込まれている版」とくらべてほとんど差がありません。 pic.twitter.com/h5U2In4lz0

拡大

ほえほえ＠スプシマン @hoehoe1234

よく考えれば１つのループで状態遷移を書けばよくて、各関数が相互呼び出しにならないので「先読みをなかったことにする必要性」はあまりありませんね。このあたりの技法については私ももっと習熟する必要性を感じます。いろいろな書き方にチャレンジしないとですね。

ほえほえ＠スプシマン @hoehoe1234

手法のまとめとしては ①まずレールロードダイアグラムで表現してみる ②ありえる要素（トークン）の種類を洗い出す ③レールロードダイアグラムの各項の前後、分岐地点が状態の候補となる ④状態が整理できたらトークンと合わせて状態遷移図／表を書いてみる ⑤入力シナリオをいくつか用意して

ほえほえ＠スプシマン @hoehoe1234

実際に頭の中で動かしてみる。という手順になるかと思います。EOL(End Of Line)の判定には色々あると思います。コレクションを使えばCountが使えますし、VBAらしさなら番兵にcverr(NO_MORE_ITEM)などを設定してもいいかと思います。

ほえほえ＠スプシマン @hoehoe1234

オブジェクト、ファイルなどではデータ以外の要素で終了が判定できます。このチェックを逐一入れるか、read関数の中に隠蔽してしまうか、また、データに番兵を入れる事により解決するか？などいろいろな方法があると思います。

ほえほえ＠スプシマン @hoehoe1234

トークンの返し方も検討が必要です。C言語ではよくトークン種別とトークンの値をペアで返しますが、今回のcsv解析ではread関数がC言語のgetchar関数の-1に相当特殊な文字を返す方法もよいでしょう。それがまさにcverrを使ったエラーで特殊状態を表す手法になると思います。

ほえほえ＠スプシマン @hoehoe1234

全体としては以前に書きましたように複数部分に分けて構成するのがよいと思います。 ①ファイルから文字コードを考慮してCSVの１行を１つの文字列とする配列を作る関数 ②１行を項目の配列に変換する関数（今回の関数） ③ヘルパー関数として「②」から２次元配列を作る関数

ほえほえ＠スプシマン @hoehoe1234

④標準ドライバー関数として①～③を呼び出すメイン関数 などを作るとよいと思います。このように分離して作ることでイレギュラーなCSVに対してもデータの特性に応じた変更を取り組みやすくなると思います。

ほえほえ＠スプシマン @hoehoe1234

①と②を分離することによりかなり処理が簡略化されると思います。①の処理はCRまたはLFを読むまでのダブルクオートの数を数えることで簡易的に判定できます。奇数であれば継続、偶数であれば改行とみなせます。行配列の最後には改行コードは付けないので②の処理を簡潔に書くことができます。