ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

後方参照とか.NETの正規表現考察

一週間程前に正規表現についての記事「正規表現の“否定”について勘違いと、アンカー」を書いたばっかりですが、
その記事の最後で、グループとかキャプチャとか後方参照とかをまだ分かっていないという課題を挙げました。

というわけで、それについて調べたので、記事にします。


先にグループとかキャプチャとかが何なのかを書こうと思うのですが、これらは正規表現におけるひとかたまりの単位のことです。

まず、グループというのは正規表現のパターン文字列でグループ化の記号()を用いてグループ化された部分のこと、すなわちこれは正規表現の構文としての一つの単位だと認識しています。

たとえば"I am the (king|queen)"というパターン文字列において、まず括弧で囲まれた"(king|queen)"というグループがひとつあります。

ただし、括弧で囲まれていませんが、パターン文字列全体はひとつのグループとするという決まりがあるようで、このパターン文字列には2つのグループがあることになります。


このように、本当はグループというのは木構造になっているのですが、グループを木構造として扱わずに平坦に扱うのが普通のようです。

実装によりけりかもしれませんが、ほとんどがグループを平坦に扱っていると思います。

これは、グループを平坦に扱うと、パターン文字列内のすべてのグループに一次元的な番号を割り振ることができて、後述する後方参照という仕組みを簡単に利用できるようになるためだと思います。


グループにはそれぞれ番号が割り振られます。

どのように割り振られるかというと、これも実装によりけりかもしれませんが、普通は幅優先探索の順番だと思います。



そして、キャプチャという単位があります。

しかし、それ以前にキャプチャという機能が正規表現エンジンにはあって、そこからキャプチャという単位が出来ていると思われるので、そこを説明します。


難しい話ではありません。
多くの正規表現エンジンでは、パターン検索を行ってマッチした文字列をキャプチャします。

キャプチャというのは、パターン文字列には前述のようにグループがいくつかあるわけですが、
マッチした文字列からそれぞれのグループに対応するような一部分を抜き出して保存しておく機能です。


たとえば、"I am the (king|queen)"というパターン文字列で"I am the king"にマッチさせたとします。

マッチしたということは、ようするに"I am the king"という文字列がパターン文字列と同じ構造になっているということです。

その構造というのは、"I am the "という文字列のあとに"king"もしくは"queen"という文字列が続くという構造です。

正規表現のパターン文字列は、その構造を記号で表現したものに過ぎません。


というわけで、パターン文字列と実際の文字列の構造が一致しているわけですから、
パターン文字列のなかの各々のグループに対応する部分が、実際のマッチ文字列の中にあるということです。

その部分だけを独立させて保存するのがキャプチャという機能で、保存されたものひとつひとつがキャプチャという単位であります。

たとえば、上のような例だと、グループ"I am the (king|queen)"に対応するキャプチャ"I am the king"があって、
グループ"(king|queen)"に対応するキャプチャ"king"があります。

まあ、言い方を変えれば、グループはパターンに基づいた単位で、キャプチャは実際のマッチ文字列に基づいた単位ですね。


上の例だと、グループとキャプチャが1対1で対応しているのですが、実はそうとも限りません。

量指定子をパターンに用いた場合、1体1ではなくなるのです。


たとえば"I am (very)+ kind"というパターン文字列を考えますが、
グループは全体と、"(very)"の部分の2つしかありません。

記号+によって"(very)"が1回以上繰り返されるという意味にはなっていますが、あくまでも"(very)"のグループは1つだけです。


しかし、このパターンで検索して、"I am very very kind"にマッチさせることが可能ですが、このときマッチ文字列にはグループ"(very)"に対応する部分というのが、2つあるわけです。

このような場合、"(very)"という1つのグループに対して、2つのキャプチャがあるということになります。

つまりグループとキャプチャが1体1ではありません。


また、キャプチャがひとつもないということもあります。

上のパターン文字列の+*に変えると、"I am kind"という文字列にもマッチしますが、このときグループ"(very)"に対応するキャプチャは1つもありませんね。




蛇足ですが.NET Frameworkにおけるパターンマッチがどういうアプローチを取っているかも書きます。

正規表現の勉強中はずっとPowershellで実証していました。


System.Text.RegularExpression.Regexクラスが、パターン文字列を使用して任意の文字列内を検索したりできるクラスになっています。

普通に検索する場合はMatchメソッドを使います。
すると、戻り値にMatchクラスのインスタンスが来ます。


.NETでは、前章で書いたグループという単位とキャプチャという単位、そしてマッチという単位をそれぞれクラスにしています。

マッチという単位はそのまま、マッチした文字列全体を表す単位ですね。

クラス名はそのままSystem.Text.RegularExpressionsのGroup, Capture, Matchです。


そしてなんとも不思議なんですが、CaptureをGroupが継承していて、GroupをMatchが継承しているという関係になっています。

マッチはキャプチャの特別な場合、パターン文字列全体を表すグループに対する実際のキャプチャであると言うことができるので、
CaptureをMatchが継承しているという関係は、まあ理解できます。

しかし、その継承関係の間にGroupが入っているのは、違和感があります。

前述のとおりGroupはキャプチャとは別概念です。


しかし、まあ使い方を簡単にするために仕方なくこういう関係にしたのかもしれませんけどね。

私が言っているような関係でクラスを作るなら、Matchメソッドの戻り値としてGroupのコレクションが返ってきて、それぞれのGroupクラスはCaptureのコレクションを持っていて

その中の1番目のGroupがマッチ文字列を全体を表すグループになっているので、そこのCaputreを取得したものが、全体のマッチ文字列、という感じになると思います。

つまりMatchクラスは要りません。


上の場合はまだいいんですが、MatchメソッドじゃなくてMatchesメソッドを使うと、複数のマッチ文字列があっても全部取得することができて、そのときが大問題です。

"I am (very)* kind"というパターン文字列で、"I am very very kind and I am very kind"とう文字列を検索したとします。

実際のようにMatchクラスがあるならMatchのコレクションが返ってきますが、Matchクラスがないとするなら、Groupのコレクションが返ってきて

全体のグループに対応するキャプチャが"and"の前後の2つあるわけですが、
"(very)"に対応するキャプチャが、1つ目の文に2つと、2つ目の文に1つの計3つあります。

前者はいいにしても、後者のように繰り返し回数が不明確なグループだと、キャプチャがどの場所のキャプチャなのか、
ようするに"(very)"のキャプチャのうち何番目までが1つ目の文のキャプチャで、何番目からが2つ目の文のキャプチャなのかわからないということです。

キャプチャがグループの木構造に準拠した木構造を持っているなら、全体のグループのキャプチャの1つ目の中から、グループ"(very)"のキャプチャを探すみたいにして、
その問題は理論上は解決できますが、現にキャプチャは木構造を持っていません。

木構造を持たせたとしても、考え方が複雑で面倒なので、使いやすさを重視して、マッチ文字列ごとにMatchクラスという単位を作ってしまった、といったところでしょう。

考え方が複雑で面倒っていうのは、上のような仕様になるとMatchメソッドでもMatchesメソッドでも一番親となるGroupクラスが返ってきて、
その中からCaptureのコレクションを取得するという感じになりますが、Matchメソッドを呼び出した場合、
つまり全体のキャプチャが1つにしかならない場合でもCaptureをコレクションとして扱わなければならないところなどです。


よって、MatchがGroupをいくつか保持していて、GroupがCaptureをいくつか保持しているという構造を作ったんじゃないでしょうか。

これは、全部が木構造じゃなくても、最上位のキャプチャであるマッチとそれ以外とだけは階層構造で分離させるという面で、私が今言ったアプローチと似たものがあるかもしれませんね。


まあだとしてもGroupがCaptureを継承しているのは納得がいきませんが。
…結局、疑問が解決できてないですね。

Matchクラスは、キャプチャの特別な場合だと言いましたが、MatchクラスはGroupも継承しておりグループとしての一面もあります。

具体的にいうと、GroupクラスからSuccessプロパティを継承していて、マッチしているか否かでブール値が入ります。

私は、Matchクラスのインスタンスが存在していること自体が、マッチしているという意味であって、論理的には美しいだろうと思うわけですが、やはり使いやすさ重視の構造でしょうね、これは。


Matchクラスは、Captureクラスを継承していることから分かるようにキャプチャの特別な場合としての仕事もしている一方、
MatchクラスにGroupクラスとしての仕事もさせたかったと。

それには、Groupクラスも継承させるのが手っ取り早いが、多重継承はできないのでGroupクラスを継承関係の間に挟み込んで、変な感じになってしまったという感じですかね。


なぜMatchクラスにGroupクラスとしての仕事もさせたかったのかというと、
Captureが先ほど書いたような完全な木構造を持っているなら、Matchesメソッドを呼び出して一番親となるGroupクラスが1つ返ってくるわけですが、
現に一番親となるものはMatchクラスになっているわけで、そこにGroupの仕事をさせるしか仕方ないからです。


以上をまとめると、使いやすさ重視によって、Groupとしての側面とCaptureとしての側面をあわせ持つような、最上位のキャプチャを表すMatchクラスを作った、
そして多重継承のような関係をむりやり構築するためにGroupを間に挟み込んでしまった、ということです。

まあ、私自身よく整理できていないので、なんか知っていたり、考えがあったりする方がいましたらコメントください。




さて、まとまってもいないことを長々と書いてしまいましたが、この章からはまた.NETの話から一般的な話に戻して、後方参照について書きます。

キャプチャと後方参照の違いが正直よくわからないのですが、これは同義なのか、

それとも、まず特定のグループに対応する文字列をキャプチャして、それを参照するのが後方参照なのか、

はたまた、まず特定のグループに対応する文字列をキャプチャして、それをパターン文字列の中で使うことを後方参照といって、マッチさせた後でプログラムから参照するのは別物なのか…

まあ、とりあえずここでは2番目の定義、つまり後方参照というのは、同じパターン文字列内でキャプチャした文字列を表すことが出来る機能とします。


同じ3文字の単語が、スペースを1つ隔てて連続するような文字列を表すパターンはどうなるでしょうか。

これには、まず3文字の単語を表す"..."があって、スペースを隔ててそれと同じものが来るので、左のものを参照しないといけないわけです。

それには、まず3文字の単語を"(...)"みたいにグループ化することで、キャプチャを有効にします。

この3文字の単語のグループは、番号でいえば2番目になるはずです。

n番目のグループのキャプチャを、"\n"としてパターン内で参照することができます。

番号は、本記事の冒頭で述べたとおり、幅優先探索の順番が普通だと思います。


よって、"(...) \2"とすれば、左のグループ(...)と同じものがスペースの次に来るということができる…と言いたいのですが、

普通は全体のグループの番号が0番になっているので、番号が1つずれて"(...) \1"となります。

これが後方参照です。


後方参照では順番が大事なようで、上のパターンを"\1 (...)"としても、たしかにグループ"(...)"の番号は1番ですから、OKなように見えるのですが、
実装的なリアルな話で、正規表現エンジンが左から読んでいくわけですが、グループ"(...)"に対応するキャプチャが行われる前に"\1"で参照しようとしていますから、無理です。

無理というか、まだキャプチャしてないグループ、もしくは量指定子を使ったときに現れるキャプチャが存在し得ないグループを参照すると、絶対にマッチしないものとして処理されるようです、実験したところ。

空文字列にすらマッチしません。


また、1つのグループに対してキャプチャがたくさんある場合、実験したところ一番最後のキャプチャを参照するようです。

そのため、グループとキャプチャを混同しており、後方参照はあまり美しい機能であるとは言えないですね。

マッチさせた後にプログラムから参照という話なら、少なくとも.NETなどでは、クラスオブジェクトで整理されているので、キャプチャをそれぞれ参照できるんですがね。

もちろん、後方参照が実用的かどうかという問題で、かなり実用的なんでしょうけども。

量指定子があるグループにおいては、後方参照は注意してやらないと失敗しますね。


ちなみに、"\1 (...)"は無理で"(...) \1)"が可能、つまり後方から参照しているので、後方参照というんだと思います。

ただし記事「
正規表現の“否定”について勘違いと、アンカー」でも書きましたが、前方を参照しているので前方参照という名前でも呼ばれていてカオスです。


さて、参照先のグループの前で参照するのが無理というのと、グループ内部で参照するのも、もちろん無理です。

まだキャプチャされていないというのもそうですが、それ以前に再帰的な構造になってしまいます。

"(...\1)"というパターンだとすれば、一度展開して"(...(...\1)"、二度展開して"(...(...(...\1)"と、キリがないですね。

グループの0番、すなわちパターン全体を表すグループを後方参照できないもの、それは絶対に再帰的になるからです。



というわけで、.NETの話が予想以上に長くなって、最後があっさりでしたが、以上です。

これで私も、正規表現のだいたいは分かったんじゃないかと思います。

正規表現の奥が深いことは分かっていましたが、前回と今回でやはり正規表現は奥が深いなと再認識させられました。

tag: 正規表現 パターンマッチ 文字列処理 後方参照 .NET

コメント

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/427-2b8a0307
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。