こんにちは、開発メンバーの岡部です。
先日は社員総会で箱根に向かい、旅館の温泉でHPを全回復することができました。
子供の頃は旅行といえば、テーマパークなどが目当てだったのに、気づけば料理や温泉目当てになっていて歳をとったなぁ...と感じます。
突然ですが、最近は個人的にパーサーを実装するのにハマっています。
きっかけになったのはRui Ueyamaさんの低レイヤを知りたい人のためのCコンパイラ作成入門です。
内容については割愛しますが、簡単な演算しかコンパイルできなかったものが最終的に、馴染みのあるプログラムのコンパイルができるようになっていく過程を体験できるのでオススメです。
(完走したとは言ってない)
とはいえ、サクッとパーサー(もしくはコンパイラ)を作りたい人には、嬉しい悲鳴かなボリュームが多いかもしれません。
ただ、自分としてはぜひ皆さんにもこの体験をしてみてほしいので、今回は比較的簡単に実装できるCSVのパーサーを作っていきたいと思います。
パーサーを作るにあたって、最初にやるべきことはパース対象の形式を熟知することです。
まずはCSVのRFCを確認して、どういった形式になるのかを確認してみます。
datatracker.ietf.org
今回は簡単のためDefinition of the CSV Formatを遵守せず、部分的に抜粋した形式を採用します。
- 各行の最後にはCRLF(改行)を含む
- 1行目: 必ずヘッダー情報を含む
- 2行目: ヘッダーの項目数と同じ分だけ項目を持つ
- 以降、繰り返し...
aaa,bbb,ccc CRLF(※改行)
ddd,eee,fff CRLF(※改行)
ggg,hhh,iii CRLF(※改行)
処理の流れについて
今回、実装するパーサーは2つのステップで構成します。
- 字句解析: CSVファイルから1文字ずつ読み取り、トークン(構造体)に変換する
- データ変換: トークンを二次元配列に変換する
多くのパーサー実装では字句解析の後に構文解析を行うことが多いです。
しかし、今回のCSV形式の場合、ただテキストが,区切りで登場するのみで構造が非常にシンプルなのでAST(抽象構文木)を生成するメリットがほとんどありません。なので、構文解析は行いません。
最終的にトークンはRubyの標準ライブラリcsvに則って二次元の配列に変換します。
p CSV.read("sample.csv")
class CSV (Ruby 3.2 リファレンスマニュアル)
いざ実装
前提知識も紹介したところで、いよいよ実装に取り掛かっていきます。
まずは以下のプロジェクトを作成します。メインの処理はparser.rbに記述していきます。
開発をスムーズに行うために簡単なテストを実行可能なparser_test.rbを用意しました。Rspecを使っても良いですが、標準ライブラリのみで実装したいので、Rspecライクな記述が可能なように簡単な関数を定義してあります。
├── csv
│ └── simple.csv
├── parser.rb
└── parser_test.rb
csv/simple.csv
aaa,bbb,ccc
ddd,eee,fff
ggg,hhh,iii
parser_test.rb
require_relative 'parser'
def assert(result, expect)
if result == expect
[:pass, result, expect]
else
[:fail, result, expect]
end
end
def it(label, &block)
raise 'Block is required' unless block_given?
status, result, expect = yield block
if status == :pass
puts "[OK] #{label}"
else
puts "[FAIL] #{label} (result=#{result}, expect=#{expect})"
end
end
1. 字句解析(トークンへの変換)
ファイルから1文字ずつ読み取る
ファイルから1文字ずつ読み取るにはファイルクラスのインスタンスに対して.getcを呼び出すことで可能です。他にも1行ずつ読み込む.getsも用意されています。一度にファイル全体を読み込まないため、メモリに優しいのが嬉しいです。
f = File.open('csv/simple.csv', 'r')
puts f.getc
puts f.getc
puts f.getc
puts f.getc
puts f.getc
.getcは何度も呼び出せますが、ファイルの最後まで読み取った後に呼び出すとnilが返ります。
つまり、読み込んだ情報がnilであるかを判定すれば、ファイルの最後まで読み取ったかどうかを判定することが可能ですが、すでにFileクラスに.eof?(end of file)たる便利なメソッドが定義されているので、こちらを使用します。
untilと組み合わせることで、ファイルの最後まで簡単に読み取ることができます。
f = File.open('csv/simple.csv', 'r')
until f.eof?
puts f.getc
end
まずは構造体が作成できるように、ファイルの上部でTokenを定義しておきます。
- kind: トークンの種別(start, comma(,), crlf(\n), value)
- value: テキストの値(eg: a)
- next: 次のトークン(構造体)
parser.rb
Token = Struct.new('Token', :kind, :value, :next)
トークンは連結リストとして作成していきます。
nextはそのために定義したフィールドです。以下の図のようにトークン同士をnextフィールドを利用して連結させていきます。
トークンを作成する処理をまとめてtokenize関数として定義したものが以下になります。
parser.rb
Token = Struct.new('Token', :kind, :value, :next)
def tokenize(file)
head = Token.new(:start, '', nil)
cur_token = head
until file.eof?
value = file.getc
token = case value
when ','
Token.new(:comma, ',', nil)
when "\n"
Token.new(:crlf, "\n", nil)
else
Token.new(:value, value, nil)
end
cur_token.next = token
cur_token = token
end
head.next
end
連結リストの作成にあたり、先頭のトークンをheadと現在のトークンを管理するcur_tokenに代入しておきます。
あとはcur_token.nextに作成したトークンを記録した後にcur_tokenを更新すると、面白いように連結リストが出来上がります。
next=
next=
next=
next=
next=
next=nil>>>>>>
2. データ変換(二次元配列への変換)
二次元配列として記録するために、各行の全要素を配列に格納する必要があります。
[
['aaa', 'bbb', 'ccc'],
['ddd', 'eee', 'fff'],
]
先にコードを見た方が理解が早いと思うので、完成形を以下に添付します。
二次元配列への変換を行う処理をまとめて token2csvとして定義しました。2はtoを表現しています。
parser.rb
def token2csv(token)
cur_token = token
rows = []
row = []
until cur_token.nil?
case cur_token.kind
when :comma
cur_token = cur_token.next
when :crlf
rows.push(row)
row = []
cur_token = cur_token.next
when :value
value = ''
while cur_token.kind == :value
value += cur_token.value
cur_token = cur_token.next
end
row.push(value)
end
end
rows
end
現在のトークンを管理するためにcur_tokenを宣言しています。
何かしらの処理が完了して次のトークンを参照するには、都度、cur_tokenを更新していきます。
cur_token = cur_token.next
cur_tokenがnilになった場合、次のトークンが存在しないことを示しています。
この特性を利用して、先ほどと同じようにuntilを使うことで、全トークンの参照が行えます。
二次元配列を作るには
トークンは「a->a->a->,」というように値を保持しているで、まず一行の一要素(eg: aaa)をまとめる必要があります。
rowは各行の全要素を格納する一時領域として使用しています。
when :value
value = ''
while cur_token.kind == :value
value += cur_token.value
cur_token = cur_token.next
end
row.push(value)
,か\nが登場するまでが一要素となりますが、\nが登場した場合、それはCSVの一行が終了したことを示すフラグとなります。
この時点で、パースした全要素を配列に格納します。
続けて、全体を格納している配列に追加すれば、最終的に二次元配列が完成します。
when :crlf
rows.push(row)
row = []
cur_token = cur_token.next
これでパーサーの実装が完了しました！
csv-parser/parser.rb at master · okabe-yuya/csv-parser · GitHub
動作確認
それでは作成したパーサーの動作確認をしてみます。
tokenizeとtoken2csvをまとめて実行するcsv_parse(file)を定義しました。
さて、無事にパースできているでしょうか...。
parser.rb
def csv_parse(file)
token = tokenize(file)
token2csv(token)
end
f = File.open('csv/simple.csv', 'r')
res = csv_parse(f)
puts "result: #{res}"
おぉ！期待通り、CSVの構造を表す二次元配列になっていますね。
思ったようにパースできているようです。
テストの追加
何度も実行結果を手で確認するのは手間なので、テストを追加します。
他にも気になるパターンがあれば、同様にテストを追加して試してみてください。
parser_test.rb
it 'simple.csv' do
f = File.open('csv/simple.csv', 'r')
result = csv_parse(f)
expect = [
['aaa', 'bbb', 'ccc'],
['ddd', 'eee', 'fff'],
['ggg', 'hhh', 'iii'],
]
assert(result, expect)
end
$ ruby parser_test.rb
[OK] simple.csv
無事にテストがパスしました。
最後に
今回は簡単なCSVパーサーをRubyで実装してみました。
最終的には、50行程度のコードでCSVのパーサーが作ることができました。
たったこれだけのコードで、こんなに面白いものが作れるのは、驚きと喜びしかありません(個人的感想...)。
github.com
コードを書きたいけど作りたいものが特にないという方には、コードがゴリゴリと書けるパーサーがオススメです。
パーサーを作るという過程を楽しんで頂けたのなら何よりです。
