「正規表現」に無限のパワーを与える"田中哲スペシャル"
先日、「正規表現」の話を書きました(d:id:atzy:20080905)が、(自称)正規表現専門家の私が、ほとんど使われていないけれど、すさまじいパワーを持つ機能を紹介しましょう。
それが「田中哲スペシャル」です。私はこれを使い始めてから肩こりは治るわ、イボ痔はよくなるわ、女の子にモテモテになるわと、人生が変わりました。
田中哲スペシャルとは
このような一風変わった名前がついているのは、田中哲(たなかあきら)さんが最初のアイデアを生み出したためです。
2002年4月3日に「鬼車」と呼ばれる正規表現ライブラリ関連で提案され，そして使えるようになりました。鬼車はRuby 1.9やらPHP5やらで利用することができます。
(ruby-dev:16732) sharing sub-regexp
簡単にいいますと「同じ表現を何度も書くのがウザイ」というものです。例えば「ホスト名(FQDN)にマッチする正規表現」というものを考えましょう。正確なものは知りませんが以下のような感じでしょうか？
[\w-]+(\.[\w-]+)+
では、例えば「ホスト名とホスト名をカンマでつないだもの」という正規表現はどうなるでしょうか？
[\w-]+(\.[\w-]+)+,[\w-]+(\.[\w-]+)+
部分式の捕獲と呼びだし
すなわち、次のような記述を許します。
(?<hostname>[\w-]+(\.[\w-]+)+),\g<hostname>
ここで新しい記法が出てきました。
| 表現 | 名前 | 説明 |
|---|---|---|
| (?<名前>任意の表現) | 名前つき捕獲式集合 | ある部分表現に名前をつける |
| \g<名前> | 部分式呼びだし | その名前をつけたところをそのまま呼び出す |
つまり、勝手に参照してくれるわけです。これによって、特に共有する正規表現が大きな場合には、全体の正規表現がかなり小さくなりますし、修正も容易になります*1。
「後方参照*2」ってのがなかったっけ？と思われる方もいるかもしれません。この後方参照は「前の部分でマッチした文字列」をダイナミックに捕獲して、それとマッチさせるものです。それとこの部分式呼出は意味が全く異なります。
鬼車では、後方参照も名前によって可能です。(Ruby 1.9を試すと分かりますが、今までのような番号による後方参照をすると怒られます。)
| 表現 | 名前 | 説明 |
|---|---|---|
| \k<名前> | 名前指定後方参照 | その名前をつけたところに(もっとも直前で)マッチした文字列にマッチする |
(?<hostname>[\w-]+(\.[\w-]+)+),\k<hostname>
と書いてしまいますと、"example.com,example.com"のように同じホスト名が繰り返されたものにマッチします。これはこれで使いでがあります。
自分自身を含む？
提案時点では田中さんは次のように書いています。
なお、目的は DFA からの変換だけなので、共有部分で後方参照やや zero width assertion など、理論的な正規表現以外のものが使えなくてもまったく問題ありません。むろん、自分自身を含むような部分パターンを参照することも必要ありません。
自分自身を含むような部分パターンなる言葉が出てきました。田中さんはここでは必要ないとされていますが、鬼車開発者の小迫さんはこれを可能としました。
これは何なのでしょうか？
再帰です。
釣り合った括弧
バッカスナウア記法をご存じでしょうか？
釣り合った括弧というのはこれで記述できます。
空文字列 ::= 括弧 ::= (括弧) 括弧 | 空文字列
左辺を右辺によって定義しています。ここで、注目すべきなのは、右辺に定義している自分自身が含まれていることです。自分自身の定義に自分自身が入っているわけです*3。
「括弧」とは、(と)で囲まれた部分に「括弧」が入っており、その直後に「括弧」がくるもの、もしくは空文字列であるということを示しています。"(())()"のようなものが釣り合った括弧となります。
部分式呼び出しと再帰
「名前つき捕獲式集合」で定義している表現の中で、自分自身の部分式呼び出しを行うことが可能です。鬼車正規表現で釣り合った括弧を書いてみましょう。
(?<kakko>\(\g<kakko>\)\g<kakko>|)
ここで、"kakko"と名前をつけられた部分式の中身は 以下のものです。
\(\g<kakko>\)\g<kakko>|
つまり自分自身の定義に自分自身が入っているわけです。
このような表現を可能にしたため、「正規表現」は新たな境地を開いたのです。
左再帰
釣り合った括弧の例に戻りますが、括弧はバッカスナウア記法によって次のように記述することも可能です。
空文字列 ::= 括弧 ::= 括弧 (括弧) | 空文字列
これは、括弧の定義の先頭に「括弧」が登場しています。これは左再帰と呼ばれる形であり、ナイーブな実装では再帰が終了しなくなります。
鬼車ではこの形を禁止しています。
(?<kakko>\g<kakko>\(\g<kakko>\))
に対しては、パーズした時点でエラーが出る("never ending recursion")ことになっています。
void recurtion(){ recurtion(); // 先頭で自分自身を呼び出す ... // 他の処理 }
などとJavaで記述すると、スタックオーバーフローが出るのと同じです。
せっかくだから俺はXMLのマッチングをするぜ
では、XMLのマッチングを考えてみましょう。ここでは簡単のためにXML属性は除いておきます。コメントとかディレクティブとかそういうものも全部無しです。空要素も名前空間のprefixもなしにしましょう。
<a>text<b>text2</b></a>
こんな感じの単純なものだけにマッチさせます。
ここでは、閉じタグがあるため後方参照も出てきます。
<(?<elem>\w+)>...<\/\k<elem>>
と記述することで、開きタグと閉じタグの対応をつけることができます。
XML ::= <文字列1>XML</文字列1と同じ> XML| 文字列2
といった形になります。「文字列2」の部分はテキストノードです。これを鬼車正規表現にしてみましょう。(テキストノードはアルファベットのみとしておきました。)
(?<xml><(?<elem>\w+)>\g<xml><\/\k<elem>\g<xml>|\w*)
しかし、これを次のようなXMLにマッチさせようとすると失敗いたします。
<a><b>text1</b>text2</a>
実は、次のような「XML」にはマッチします。
<a><b>text1</b>text2</b>
後方参照のレベル
これは、後方参照のせいです。
後方参照で利用されている\k<elem> ですが、「一番最後にマッチした」ものを利用しますから、</a>にマッチしようとしたときには、「直前はbしか覚えていないぜ！」といってbにマッチさせようとしてしくじるのです。
しかし、鬼車はこれを解決することができます。もう一度正規表現を見てみましょう。
(?<xml><(?<elem>\w+)>\g<xml><\/\k<elem>>\g<xml>|\w*)
ここで、後方参照を利用している\k<elem>で、真に参照したいものは、直前の\g<xml>の中で捕獲したものではなく、さらにその前の(?<elem>\w+)で捕獲したものです。しかし、\g<xml>の中が展開されて、その中にまた別のレベルの(?<elem>\w+)がある*4ため、そちらが直前の捕獲になってしまうわけです。
鬼車では、後方参照を利用する際、そのネストのレベルを指定することができます。このXMLの正規表現の場合は、正規表現の字面の上で同じネストレベルにある(?<elem>\w+)にマッチさせたいといえます。(つまり、同一の\g<xml>の中に直接に含まれる。)
この「同じ」ということを示すために、後方参照は次のように記述します。
(?<xml><(?<elem>\w+)>\g<xml><\/\k<elem+0>>\g<xml>|\w*)
elem+0 というのがそれです「+0」は「同じレベル」ということになります。書きたければ、深いネストや浅いネスト内での捕獲を利用できますから、elem+1だとか、elem-1だとかいったものも記述できます。
部分式呼出はネストされるため、同時に複数の部分式が実行され得ます。そこでネストレベルごとに後方参照を記憶してくれているわけであり、それを指定することができるわけです。
例
回文
"abcba"とか"abccba"とかです。
(?<kaibun>(?<w>.)\g<kaibun>\k<w+0>|.?)
関数呼出みたいなの
具体的には以下のようなもの。
func1(func2(aaa,bbb(d),c(bc)))
なお、a()という形は認めていません。
(?<value>\w+\((\g<value>,)*\g<value>\)|\w+)
さあ、明日から使いましょう………？
お願いですから、勘弁して下さい。
よい子の皆さんは使わないで下さいね*5。
追記
ふと、思い出しました。
私の大学院での最後のゼミ発表では、田中哲スペシャルの記法は難しいから、バッカスナウア記法っぽく「も」書けるようにしてはどうだろうという提案と実装*6を示したのです。
例えば、別ファイルなりで、以下のように書いておきます。
<KAKKO> ::= \(\g<KAKKO>\)\g<KAKKO>
で、Rubyなりで使うときには、\gだけを使います。
if /\g<KAKKO>/ =~ str ... end
名前付き捕獲記法では、読む人の理解が難しいですから、一行で記述するのをあきらめて、複数に分けて作ることにするというわけです。別ファイルでの定義を読み込んだときにオートマトンも生成しておいて使い回しも行えるようにします。
こうしたときに、名前空間はどうなるんだとか、いろいろな問題はあると思いますし、学問的なインパクトはかなり小さいようにも思いますけれど。それ以前に、本当にわかりやすくなるのかも微妙かもしれません。
追記2
Perlは鬼車を使っておりませんが、(??{code})という記法があります。これを利用すると、やはり再帰的な表現が記述可能です。しかし、これはもっとあくどいと思いますので、マジでやめて下さい。
用例は以下の引用のリンク先で見ることができます。
ただし、Perlの正規表現は拡張してあるので、入れ子表現にも正しくmatchするregexpも書けなくはない。
http://blog.livedoor.jp/dankogai/archives/51060214.html
そこで紹介されている、釣り合った括弧へのマッチです。
$re = qr{ \( (?: (?>[^()]+) # Non-parens w/o backtracking | (??{ $re }) # Group with matching parens )* \) }msx;
上記サイトに書き込まれているコメントによれば、Perl 5.10では、変数も(??{code})もなしで入れ子を書けるようになったそうですが、私は使い方も知りません。
*1:これを使わなくても、部分正規表現を変数に入れ、結合して正規表現を作成するという手法はあり、修正が容易になるとはいえます。しかし、完成形の正規表現自体は大きくなりますから、処理に用いるオートマトンも大きくなります。鬼車は、一つのオートマトンを使い回しているのですね。
*2:前方参照という呼び名もありますが、同じものです。
*3:形式言語論の話で言えば、「括弧」とか「空文字列」というものは非終端記号と呼ばれます。バッカスナウア記法において、この非終端記号が右辺に一つもこないものが正規表現で記述可能です。
*4:さらに言えばその後の\g<xml>の中で別の捕獲をしているかもしれない。
*5:私は使いますけど。
