Rubyで簡単なCSVパーサーを作ってみる

こんにちは、開発メンバーの岡部です。
先日は社員総会で箱根に向かい、旅館の温泉でHPを全回復することができました。
子供の頃は旅行といえば、テーマパークなどが目当てだったのに、気づけば料理や温泉目当てになっていて歳をとったなぁ...と感じます。

突然ですが、最近は個人的にパーサーを実装するのにハマっています。
きっかけになったのはRui Ueyamaさんの低レイヤを知りたい人のためのCコンパイラ作成入門です。
内容については割愛しますが、簡単な演算しかコンパイルできなかったものが最終的に、馴染みのあるプログラムのコンパイルができるようになっていく過程を体験できるのでオススメです。
(完走したとは言ってない)

とはいえ、サクッとパーサー(もしくはコンパイラ)を作りたい人には、嬉しい悲鳴かなボリュームが多いかもしれません。ただ、自分としてはぜひ皆さんにもこの体験をしてみてほしいので、今回は比較的簡単に実装できるCSVのパーサーを作っていきたいと思います。

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")
# => [["Ruby", "1995"], ["Rust", "2010"]]

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

# frozen_string_literal: true

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 # a
puts f.getc # a
puts f.getc # a
puts f.getc # ,
puts f.getc # b

.getcは何度も呼び出せますが、ファイルの最後まで読み取った後に呼び出すとnilが返ります。
つまり、読み込んだ情報がnilであるかを判定すれば、ファイルの最後まで読み取ったかどうかを判定することが可能ですが、すでにFileクラスに.eof?(end of file)たる便利なメソッドが定義されているので、こちらを使用します。
untilと組み合わせることで、ファイルの最後まで簡単に読み取ることができます。

f = File.open('csv/simple.csv', 'r')
until f.eof?
  puts f.getc
end

# a
# a
# :
# i

トークンの作成

まずは構造体が作成できるように、ファイルの上部でTokenを定義しておきます。

kind: トークンの種別(start, comma(,), crlf(\n), value)
value: テキストの値(eg: a)
next: 次のトークン(構造体)

parser.rb

# frozen_string_literal: true

Token = Struct.new('Token', :kind, :value, :next)

トークンは連結リストとして作成していきます。
nextはそのために定義したフィールドです。以下の図のようにトークン同士をnextフィールドを利用して連結させていきます。

トークンを作成する処理をまとめてtokenize関数として定義したものが以下になります。

parser.rb

# frozen_string_literal: true

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を更新すると、面白いように連結リストが出来上がります。

# a,b,cの場合
#<struct Struct::Token kind=:value, value="a",
  next=#<struct Struct::Token kind=:comma, value=",",
    next=#<struct Struct::Token kind=:value, value="b",
      next=#<struct Struct::Token kind=:comma, value=",",
        next=#<struct Struct::Token kind=:value, value="c"
          next=#<struct Struct::Token kind=:crlf, value="\n",
            next=nil>>>>>>

2. データ変換(二次元配列への変換)

二次元配列として記録するために、各行の全要素を配列に格納する必要があります。

[
  ['aaa', 'bbb', 'ccc'], # 1行目
  ['ddd', 'eee', 'fff'], # 2行目
]

先にコードを見た方が理解が早いと思うので、完成形を以下に添付します。
二次元配列への変換を行う処理をまとめて 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は各行の全要素を格納する一時領域として使用しています。

# value以外のトークンが出現するまで文字列を結合しまくる
when :value
  value = ''
  while cur_token.kind == :value
    value += cur_token.value
    cur_token = cur_token.next
  end
  row.push(value)

,か\nが登場するまでが一要素となりますが、\nが登場した場合、それはCSVの一行が終了したことを示すフラグとなります。この時点で、パースした全要素を配列に格納します。
続けて、全体を格納している配列に追加すれば、最終的に二次元配列が完成します。

# 全体を格納しているrowsにrowを追加
# 合わせて一時領域rowをクリアして次の行に備える
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}"

# result: [["aaa", "bbb", "ccc"], ["ddd", "eee", "fff"], ["ggg", "hhh", "iii"]]

おぉ！期待通り、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

コードを書きたいけど作りたいものが特にないという方には、コードがゴリゴリと書けるパーサーがオススメです。パーサーを作るという過程を楽しんで頂けたのなら何よりです。