回文や XML にマッチする鬼車の正規表現

Ruby

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 や \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 のように相対的なネストレベルを指定しなかった場合は、\k の中で参照可能な最大の N が選ばれるみたい。\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 が同じレベルにいるので \k を指定すればよい。
ちなみに、これを \k とすると、上のどれにもマッチせず、"1234555555" なんかにマッチしてしまうようになる。その理由はさっき言ったとおり。

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 のネストレベル」ということ。だと思う。

余談: 左再帰は禁止

\g は再帰できるけど、左再帰はできない。

/(?<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) # 非マッチ

まとめ

むずかしすぎだよね。

*1:このあたりから、鬼車の正規表現は文脈自由文法を包含する、と思う。わかりやすくいうと、LALR は決定性プッシュダウンオートマトンより弱いらしいので、鬼車の正規表現は yacc よりたぶん強い。いやわかりやすくないな。