Hatena::ブログ(Diary)

まめめも このページをアンテナに追加 RSSフィード

2009-04-09

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

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<foo-1> や \k<foo+1> という形で、相対的なネストレベルを指定できる。

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 。(?<bar>.)\g<foo> が選択されて、'a' が bar に束縛される。foo を再帰的に呼び出す (ネストレベルが上がる) 。
  • ネストレベル 1 。(?<bar>.)\g<foo> が選択されて、'b' が bar に束縛される。foo を再帰的に呼び出す (ネストレベルが上がる) 。
  • ネストレベル 2 。(?<bar>.)\g<foo> が選択されて、'c' が bar に束縛される。foo を再帰的に呼び出す (ネストレベルが上がる) 。
  • ネストレベル 3 。(?<bar>.)\g<foo> が選択されて、'c' が bar に束縛される。foo を再帰的に呼び出す (ネストレベルが上がる) 。
  • ネストレベル 4 。もう文字がないので (?<bar>.)\g<foo> にも \k<bar-1> にもマッチしない。バックトラックでネストレベル 4 を抜ける。
  • ネストレベル 3 。\k<bar-1> が選択される。\k<bar-1> は、「現在のネストレベル - 1」のネストレベルで bar に束縛された文字列にマッチする。ここではネストレベル 2 (= 3 - 1) で束縛された 'c' のこと。一致するのでマッチを返す。

ちなみに \k<foo> のように相対的なネストレベルを指定しなかった場合は、\k<foo+N> の中で参照可能な最大の N が選ばれるみたい。\k<foo+0> の省略形ではないので注意。

回文判定 (その 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) #=> 非マッチ

対応する (?<bar>.) と \k が同じレベルにいるので \k<bar+0> を指定すればよい。

ちなみに、これを \k<bar> とすると、上のどれにもマッチせず、"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<name+1> かすぐにわかったらすごい。ネストレベルを図にするとこう。

... --- 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 よりたぶん強い。いやわかりやすくないな。

tootoo 2009/04/10 23:38 左再帰を禁止するのは
エラーメッセージにもあるように
無限に再帰してしまうからじゃないですか?

Perl 5.10では禁止はされてませんが 一定数回数以上のループを検出してエラーが出るそうです
Rubyだと 'x' =~ /(x|\g<1>)/ は正規表現コンパイル時のエラーでマッチ自体が行われません
Perlだと 'x' =~ /(x|(?1))/ はマッチが成功しますが
'a' =~ /(x|(?1))/ だと正規表現が無限ループしたといってエラーが出ます

マッチさせる文字列に依存して例外が出るというのは
どうも使いづらい気がするので
鬼車のように最初から正規表現のエラーにしておく方がいいのかな

ku-ma-meku-ma-me 2009/04/11 01:23 単純に実装するとそうなるんですが、なんとかしようと思えばなんとかできる (はずの) 話なので、正確な理由はわかってませんでした。一応調べてみたところ、実装コストと実用性を天秤にかけて判断した結果?という感じのログがありました。

http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-dev/19737
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-dev/19738

それはそれとして、左再帰に対応してないパーサって他にもあるよなー (Parsec とか) 、勝手に左再帰除去したら不都合があるのかなー、という (鬼車に特化しない) 疑問もありました。こっちも調べたところ、除去すると構文木が変わるらしいので、それが理由なのかな。まじめに調べたり考えたりしたわけじゃないので勘違いかもしれません。

http://ja.wikipedia.org/wiki/%E5%B7%A6%E5%86%8D%E5%B8%B0

この記事によると左再帰対応ってわりと現在研究中なんですかね。とっくに枯れた分野だと思ってました。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/ku-ma-me/20090409/p1