ref: 鬼車 正規表現 Version 5.9.1
ref: Ruby Freaks Lounge: 第6回 Ruby M17N 事始め:正規表現編
\g と \k について今までちゃんとわかってなかったけれど、少しわかったような気になったのでメモ。Ruby というより鬼車の話なので、PHP でも使えるかもしれない。試してないけど。
田中哲スペシャル \g の基本
\g で参照される括弧の中身がそこにそのまま書かれたと思えばいい。
re = /\A(?<foo>abc...def)\g<foo>\z/ # \g<foo> を展開して考える # /\A(?<foo>abc...def)abc...def\z/ と同じ意味 p "abc123defabc123def".match(re) # マッチ p "abc123defabc456def".match(re) # マッチ p "abc123def" .match(re) # 非マッチ
\g は再帰的に参照できる
自分自身を \g で再帰的に参照することができる。相互再帰も可能。
re = /\A(?<foo>abc\g<foo>|def)\z/ # 'abc' \g<foo> か 'def' にマッチする # /\A(abc)*def\z/ と同じ意味 p "def" .match(re) # マッチ p "abcdef" .match(re) # マッチ p "abcabcdef".match(re) # マッチ p "abc" .match(re) # 非マッチ
括弧の対応判定
\g の再帰を使って、括弧の対応が判定できる。
re = /\A(?<foo>\(\g<foo>*\))\z/ # '(' \g<foo> ')' か空文字列にマッチする p "()" .match(re) # マッチ p "(()())".match(re) # マッチ p "(()()" .match(re) # 非マッチ
回文判定 (その 1)
0 と 1 からなる文字列が回文になっているかどうか。
re = /\A(?<foo>0\g<foo>0|1\g<foo>1|)\z/ p "00" .match(re) #=> マッチ p "0110" .match(re) #=> マッチ p "01000010".match(re) #=> マッチ p "0100001" .match(re) #=> 非マッチ
こういう回文判定は、非決定性プッシュダウンオートマトン (文脈自由文法と等価) では判定できるけれど、決定性プッシュダウンオートマトン (文脈自由文法よりは小さい) で判定できない問題らしいです (参考) *1 。確かに、文脈自由文法の規則そのままって感じですよね。
S -> 0S0 | 1S1 | ε
ちなみに、0 と 1 だけでなく、任意の文字についての回文判定もできる。後述。
後方参照 \k の基本
\k で指示される括弧にマッチした文字列にマッチする。\1 や \2 と同じ。
re = /\A(?<foo>abc...def)\k<foo>\z/ # /\A(abc...def)\1\z/ と同じ意味 p "abc123defabc123def".match(re) # マッチ p "abc123defabc456def".match(re) # 非マッチ
\k はネストレベルを指定できる
ここが難しい。\g は再帰的に参照でき、この再帰にはコールスタックのようなものがある (ネストレベルといわれる) 。\k は \k
re = /\A(?<foo>(?<bar>.)\g<foo>|\k<bar-1>)\z/ p "abca".match(re) # 非マッチ p "abcb".match(re) # 非マッチ p "abcc".match(re) # マッチ re = /\A(?<foo>(?<bar>.)\g<foo>|\k<bar-2>)\z/ p "abca".match(re) # 非マッチ p "abcb".match(re) # マッチ p "abcc".match(re) # 非マッチ re = /\A(?<foo>(?<bar>.)\g<foo>|\k<bar-3>)\z/ p "abca".match(re) # マッチ p "abcb".match(re) # 非マッチ p "abcc".match(re) # 非マッチ
最初にマッチする例 ("abcc".match(re)) では、以下のようにマッチが進んでいる。と思う。
- ネストレベル 0 。(?
.)\g が選択されて、'a' が bar に束縛される。foo を再帰的に呼び出す (ネストレベルが上がる) 。 - ネストレベル 1 。(?
.)\g が選択されて、'b' が bar に束縛される。foo を再帰的に呼び出す (ネストレベルが上がる) 。 - ネストレベル 2 。(?
.)\g が選択されて、'c' が bar に束縛される。foo を再帰的に呼び出す (ネストレベルが上がる) 。 - ネストレベル 3 。(?
.)\g が選択されて、'c' が bar に束縛される。foo を再帰的に呼び出す (ネストレベルが上がる) 。 - ネストレベル 4 。もう文字がないので (?
.)\g にも \k にもマッチしない。バックトラックでネストレベル 4 を抜ける。 - ネストレベル 3 。\k
が選択される。\k は、「現在のネストレベル - 1」のネストレベルで bar に束縛された文字列にマッチする。ここではネストレベル 2 (= 3 - 1) で束縛された 'c' のこと。一致するのでマッチを返す。
ちなみに \k
回文判定 (その 2)
ネストレベル付きの \k を使うと、任意の文字の回文判定ができる。
re = /\A(?<foo>(?<bar>.)\g<foo>\k<bar+0>|)\z/ # (?<bar>.)\g<foo>\k<bar+0> か空文字列にマッチする p "1234554321" .match(re) #=> マッチ p "123123321321".match(re) #=> マッチ p "123455432" .match(re) #=> 非マッチ
対応する (?
ちなみに、これを \k
XML (みたいなもの) の判定
とてもややこしい。
re = %r(\A (?<name> \w+ ){0} (?<stag> < \g<name> > ){0} (?<etag> </ ( \k<name+1> | dummy ) >){0} (?<element> \g<stag> \g<element>? \g<etag> ){0} \g<element> \z)x p re.match("<foo><bar><baz></baz></bar></foo>") #=> マッチ p re.match("<foo><bar><baz></baz></bar></BOO>") #=> 非マッチ
これがなぜ \k
... --- element -+- stag --- name
|
+- etag
^ N-1 ^ N ^ N+1 <== ネストレベルetag のネストレベル N から見ると、それに対応する name のネストレベルは N + 1 。別の言い方をすると、「etag のネストレベル + 1」=「element のネストレベル + 2」=「stag のネストレベル + 1」=「name のネストレベル」ということ。だと思う。
余談: 左再帰は禁止
/(?<foo>x|\g<foo>\+\g<foo>)/ #=> never ending recursion: /(?<foo>x|\g<foo>\+\g<foo>)/
なんでかと言われると、正直よくわかってないので困る。
余談: 同じ名前が複数あった場合
なかなか気持ち悪いけれど、同じ名前を同じネストレベルに複数回定義できる。その名前を \k で参照する場合は、どれかと一致すればマッチするみたい。
re = /\A(?<foo>.)(?<foo>.)\k<foo>\k<foo>\z/ p "abaa".match(re) # マッチ p "abab".match(re) # マッチ p "abba".match(re) # マッチ p "abbb".match(re) # マッチ p "abbc".match(re) # 非マッチ
まとめ
むずかしすぎだよね。
