PEG.jsでCSVパーサを書く

はじめに

ここ最近PEG.jsを書いていて少し慣れてきたので、今回は少し前に書いたCSVパーサを題材に解説してみます。
ここで紹介する実装が、一般的な実装の仕方ではないかも知れません。
実際にご自分で実装する楽しみを体験してみてください。
この記事に登場するPEGの用語は「用語」で解説しています。
※私の解釈で説明しているため正確ではない可能性があります。正しい説明はWikipediaや論文などをご参照ください。

用語

マッチする

マッチするとは、入力文字列が対象のパターンと一致することを言います。

成功する・失敗する

PEGで言う「成功」や「失敗」は式の評価の結果です。
あるパターンにマッチするかどうかを評価することによって、成功・失敗します。

消費する

ルールの定義に従って文字列の全体または一部が取り出され、マッチした分だけパーサの現在位置を進めることを言います。

StartRule

一番上に書いたルールはStartRuleといって、唯一PEG.jsから直接呼び出されるルールになります(C言語でいうところのmain関数のようなもの)。
StartRuleのルール名に決まりはありませんが、慣例的に「start」と名付けられることが多いようです。
また、一番上のルール以外をStartRuleに指定することも出来ます。

CSVパーサを書いてみる

PEGでは複数のルールを定義することによって、目的のパーサを記述します。
ルール(Rule)とはPEGで定義した文のことで、以下のようなものです。

helloworld = "hello" "world"

PEGでは、複数のルールを組み合わせることによって1つのパーサを作り上げていきます。

では、まず最初に記号「,」とマッチして消費するルールを定義してみましょう。

comma = ","

このルールは、,という文字列が現在の位置に現れた場合にマッチして、その文字数の分だけ消費する
という意味を持っています。

このルールの動作は以下のような感じです。
1. パーサの現在位置(インデックス)が0番で入力文字列が,abcの時、パーサは,が現れると期待して一文字読み込みます(この時点では現在位置は移動していません)
2. 読み込んだ文字列はそのルールに一致するので、,の文字数である1だけ現在位置を進めて、現在位置は1番になります(aの位置)

これでとてもシンプルなパーサができました。入力文字列が,とマッチするかどうかを判断できるパーサです。
特に必要ありませんが、StartRuleを一行目に追加します。

start = comma
comma = ","

以下のページから作ったパーサの動作を確認することが出来ます。
https://pegjs.org/online

,という入力にマッチすることを確認できるかと思います。

次に、改行コードにマッチして消費するルールを定義します。

lineBreak = "\n" / "\r\n" / "\r"

/という記号が出てきました。これは、式の「選択」を意味する演算子です。
\nまたは\r\nまたは\rにマッチします。つまりOR条件です。
選択は常に左側の式からマッチを試行し、マッチしなければ一つ右の式にマッチするかを試行していきます。
例えば、入力文字列が\nにマッチした場合、それより右の式(\r\nと\n)とマッチするかどうかは無視されます。

次に、任意の1文字にマッチして消費するルールを定義します。

char = !(comma / lineBreak) c:. { return c; }

任意の文字と書きましたが、正確には,と改行文字以外の1文字にマッチして消費するルールです。
順番に見ていきましょう。このルールには!(comma / lineBreak)とc:.の2つの式がスペースを挟んで、記述されています。
この書き方は「連接」と言って、両方の式にマッチした場合のみマッチに成功します。つまりAND条件となります。
!演算子は「否定先読み」と言い、!の右に続く式にマッチしなかった時にマッチに成功します。しかし、この演算子はマッチしたときに消費をしません。
また、他の「先読み」と付いている演算子(&肯定先読みなど)についても消費をしません。
.は任意の一文字にマッチします。それにc:と付けることで、その式にcという名前を付けています。
{と}で囲まれている部分はJavaScriptコードとして実行され、cと名前をつけた部分はJavaScriptの変数として参照することが出来ます。ここでは、return c;としているのでこのルールの戻り値としてcにマッチした値が返されます。

ここまでで、StartRuleも含め4つのルールを定義してきました。
それらのルールは、とても小さな単位で定義してきたことに気づいたでしょうか。
このように、PEGは小さなルールを組み合わせて大きなルールを定義していくというやり方が基本となっています。

次に、charルールを使って、任意の文字列にマッチするルールを定義します。

cell = s:$(char*) { return s; }

char*はcharに0回以上繰り返してマッチ・消費させることができます。
繰り返しでマッチさせた場合は配列が返りますが、$()で囲んで文字の配列を文字列として結合しています。
つまり、このルールの戻り値としては文字列が返されます。
また、この演算子は可能な限り繰り返してマッチしようとするので、例えばchar* charには必ずマッチしない点に注意してください。

ここまでのルールの定義で、,や改行文字以外の任意の文字列にマッチさせて取り出すことが出来ます。
実際に確認してみましょう。

start = cell
cell = s:$(char*) { return s; }
char = !(comma / lineBreak) c:. { return c; }
lineBreak = "\n" / "\r\n" / "\r"
comma = ","

入力:

hello world

出力:

"hello world"

1つの文字列として取り出せています。
cellは,や改行文字にマッチしないので、改行したりすると失敗することも確認できます。

入力:

hello, world

エラー:

Line 1, column 6: Expected end of input but "," found.

次に、今度はCSVの1行にマッチ・消費するルールを定義します。

recode = head:cell cs:(comma c:cell { return c; })* { return [head, ...cs]; }

このルールで変わった書き方といえば、()*の中でJavaScriptのコードを記述している所でしょう。
これは、繰り返される式comma c:cellに対してコードを実行しています。
0回以上の繰り返し()*からはその繰り返し内部でreturnされた値が利用されます。
それを踏まえると、,で区切られた任意の文字列(cell)を取り出していることが分かると思います。

これでCSVの1行をマッチ・消費することができるようになりました。確認してみましょう。

start = recode
recode = head:cell cs:(comma c:cell { return c; })* { return [head, ...cs]; }
cell = s:$(char*) { return s; }
char = !(comma / lineBreak) c:. { return c; }
lineBreak = "\n" / "\r\n" / "\r"
comma = ","

入力:

hello, world

出力:

[
   "hello",
   " world"
]

,で区切られた文字列を配列として取り出せていますね。

今度は、複数行のCSVを読み込めるようにしましょう。

recodes = head:recode rs:(lineBreak r:recode { return r; })* { return [head, ...rs]; }

前述のルールのcommaの部分がlineBreakに変わっているだけです。
これで複数行のCSVを取り出すことが出来ます。確認してみましょう。

start = recodes
recodes = head:recode rs:(lineBreak r:recode { return r; })* { return [head, ...rs]; }
recode = head:cell cs:(comma c:cell { return c; })* { return [head, ...cs]; }
cell = s:$(char*) { return s; }
char = !(comma / lineBreak) c:. { return c; }
lineBreak = "\n" / "\r\n" / "\r"
comma = ","

入力:

hello, world
yeah, 123

出力:

[
   [
      "hello",
      " world"
   ],
   [
      "yeah",
      " 123"
   ]
]

これで無事、CSVをパースすることができました。

おわりに

実はこのパーサは完全なものではありません。
CSVには""で囲まれた文字列をひと塊として扱うという仕様があります。
その仕様をここでは実装しませんでしたが、いろいろ試してみて実装してみるのも面白いと思います。

PEGは手軽にパーサを作ることができて面白いので皆さんも一度書いてみてください！