こんにちは、hachi8833です。最近PEG（Parsing Expression Grammar）という形式言語で遊んでいます。正規表現に似ているせいか、私にとっては楽しいおもちゃです。
PEGについて
参考: Parsing Expression Grammar - Wikipedia
PEGについて詳しくはWikipediaに譲りますが、PEGで仕様を記述して、それをPEGパーサージェネレータで変換するとパーサー（parser: 構文解析器）のコードを生成できます。
Wikipediaにはさまざまな言語用のPEGパーサージェネレータが紹介されています。私の場合は、以下のpointlander/pegという、Go言語用のPEGパーサージェネレータを使っています。
PEGと正規表現
自分にとってPEGは、正規表現ですべてに名前（ルール名）を付けて書いているような感じです。
以下はごくシンプルなPEGの例です。整数を認識し、00はエラーになります。
int_zero <- '0'
int <- [1-9][0-9]*
Integer
<- int
/ int_zero
このとき、[1-9]と[0-9]*の間にスペースがあってもなくても挙動は変わりません（少なくともpointlander/pegでは）。
PEGパーサージェネレータは正規表現ライブラリと用途が違うことは承知ですが、PEGは名前付けを推しているのと、ルール間にスペースを許容しているおかげで、正規表現に比べて汚くなりにくいと個人的に感じています。
PEGの/
PEGの最大の特徴は、先ほどの例にも登場した/という記法です。
int_zero <- '0'
int <- [1-9][0-9]*
Integer
<- int
/ int_zero
/に相当する概念は、BNFや正規表現にはありません。
BNFや正規表現では並列を|を用いて表します。
PEGでは並列に/を用いますが、重要な違いは、PEGでは並列の順序が重要になることです。「マッチしない場合は/を試行する」形で記述します。
並列の|であれば項を入れ替えても結果は変わりませんが、PEGの/では項を入れ替えると結果が変わる可能性があります。
そのおかげで解釈が一意になる代わりに、記述の順序も考える必要があります。
PEGと正規表現の大きな違い
ここからが本題です。
いわゆるsnake_case文字列の末尾に数値がある場合に、その数値をキャプチャしたいとします。この場合、スネークケースの末尾には_を置けないようにしたいとします。
参考: スネークケース (snake case)とは｜「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典
正規表現であれば、以下のようにnumで末尾の数値を問題なくキャプチャできます。
# Rubyの正規表現の場合
^[a-z]([_a-z0-9]*[_a-z])*(?<num>[0-9]+)?$
しかし、同じ要領で以下のPEGを書いてみたところ、末尾の数値をまったくキャプチャできませんでした。
tail_num
<- [0-9]
name_snakecase
<- [a-z] [_a-z0-9]* tail_num?
以下のように、シンプルな末尾数値すらtail_numでキャプチャできません。
#例: 'name1' の場合以下の結果を期待していた
name_snakecase "name"
tail_num "1"
上を期待していたのですが、実際には以下のようにname_snakecaseに全部吸い込まれてしまいます。
#実際に 'name1'を与えた場合
name_snakecase "name1"
当然ながら、以下のように途中に数値やアンダースコアがある名前の末尾数値もキャプチャできません。
#例: name1_name2
name_snakecase "name1_name2"
おかしいなと思い続けていたのですが、ふと冒頭のWikipedaを開いてみるとこんなことが書かれていました。
ゼロ個以上、1個以上、省略可能の場合、それぞれゼロ個以上、1個以上、ゼロ個または1個の e が続くものとして入力を消費する。PEGにおける繰り返しは常に貪欲でありマッチし続ける限り入力を消費するが、それだけではなく、正規表現とは異なりバックトラックしない（正規表現では貪欲にマッチするものの、失敗するともっと短いマッチを試すためにバックトラックする）。例えば、a* という表現は 'a' が連続する限り入力文字列を消費し、(a* a) という表現は最初の (a*) が全ての 'a' の並びを消費してしまうため、最後の (a) にマッチする 'a' がなくなるので、常に失敗する。
Wikipediaより（強調は筆者）
なるほど道理で！
勝手知ったる正規表現のつもりで書いていましたが、PEGの繰り返しはバックトラックしないんですね。
先ほどの例で言うと、[a-z] [_a-z0-9]*の部分がname1やname1_name2の末尾数値を残さずに全部食べちゃっていたということです。
tail_num
<- [0-9]
name_snakecase
<- [a-z] [_a-z0-9]* tail_num?
正規表現のバックトラックについては以下の記事をどうぞ。
今回の解決法
どう書けばいいのか試行錯誤した結果、どうやら以下のようにすることで途中で数値を食べられることなくtail_numでキャプチャできるようになりました。
tail_num <- [0-9]+
name_snakecase
<- [a-z] ( [a-z]+ / [_]+ [a-z]* / [0-9]+ [a-z_]+ )* tail_num
/ [a-z] ( [a-z]+ / [0-9_]+ [a-z]+ )
以下のパターンを認識でき、末尾数値も正しくキャプチャできました。
# 末尾数値のないパターン
n
n_nn___nn_n
n_n1n__1_n1n_n
# 末尾数値のあるパターン
n1
n_1
n_1_1_n1_n1_1_1_n_n_1
# エラーになるべきパターン
_n
n_
n1_
nn_n_1_
n_1_1_n1_n1_1_1_n_n_1_
果たしてこれが最適なのか、まだ悩んでいます。PEG強者に聞いてみたいところです。お気づきの点がありましたら@hachi8833までお知らせください。
PEGの順序
試しに以下のように最下部の行を1つ上の行と入れ替えると、上述の末尾数値があるスネークケースはたちまちエラーになります。
tail_num <- [0-9]+
name_snakecase
<- [a-z] ( [a-z]+ / [0-9_]+ [a-z]+ )* # 末尾に数値があってもこの次に進まない
/ [a-z] ( [a-z]+ / [_]+ [a-z]* / [0-9]+ [a-z_]+ )* tail_num
PEGの/で順序が重要なことを痛感しました。