`kantan-regex`の仕様

ここでは、これから実装する正規表現エンジン (kantan-regex) の仕様を確認していきます。いわゆる正規表現と大差あるわけではありませんが、詳細な仕様を把握しておくことは、実装する上では重要となります。

API: `KantanRegex`

KantanRegexを唯一の公開されているクラスとします。

KantanRegex.newにパターンを表す文字列を渡すことで、正規表現オブジェクトを生成できます。さらに、KantanRegex#matchにマッチ対象の文字列を渡すことで、最初にマッチした文字列の範囲 (Rangeオブジェクト) を返します。

re = KantanRegex.new('fizz|buzz')

re.match('foo fizz bar') #=> 4...8

実装を単純にするために、サポートする正規表現のパターンの構文はかなり絞ったものになっています。具体的には、kantan-regexでは次の構文をサポートしています。

文字クラス ([abc]) や行の先頭・末尾 (^と$)、後方参照などの機能は、今回は (一旦) 実装しない方針とします。

文字リテラルは (いわゆる) 通常の文字です。一部のパターン中で意味を持つ文字を除いて、そのまま書いた文字が文字リテラルとして扱われます。そして、文字リテラルはその文字自身にマッチするパターンとなります。

パターン中で意味を持つ文字には次のようなものがあります。

これらの文字にマッチするパターンを書きたいときのために、バックスラッシュ\を使ってエスケープすることができます。加えて、バックスラッシュ自身も\\のようにしてエスケープできることにします。

括弧を使ってパターンをグループ化できます。これは次の繰り返しや分岐の適用される範囲を示すために利用できます。

基本的な繰り返しの記号 (演算子) として次のものをサポートします。

?はあまり繰り返しの記号としては考えないかもしれませんが、0回以上1回以下の繰り返しと考えることで一般化できます。

また、繰り返しは貪欲にマッチします。つまり、可能な限り多く繰り返すようにマッチします。

例えばパターンa*に対して文字列"aaaa"をマッチする場合、先頭からaaやaaaというように中途半端なところまででマッチが完了することはなく、aaaaまでのすべてのaがマッチします。

選択の記号|を使うことで、複数のパターンのいずれかにマッチするパターンを書けます。例えば、a|b|cがaまたはbまたはcにマッチするパターンです。

選択は左側から優先的にマッチをしていきます。例えばパターンa|aaに対して文字列"aa"をマッチする場合、一番左側のパターンaが優先されて先頭から1文字の"a"のみにマッチします。

また、複数のパターンを並べることで、連続してマッチするパターンを書けます。例えば、abは文字aとbの並びにマッチするパターンです。

これらのグループ化、繰り返し、選択、連接を組み合わせてパターンを記述できます。例えば(a|b)*aba(a|b)*というパターンは、abaという並びがどこかに存在する、aとbからなる文字列の部分にマッチするパターンです。

また、選択と繰り返しでは繰り返しの方が優先順位が高いです。そのため、a|b*はa|(b*)の意味になります。連接と繰り返しも同様で、a*bc*は(a*)b(c*)の意味になります。