タグ : PCRE

PCREは無限の括弧の対応が取れる ~ 再帰も、ネストも、あるんだよ.

追記
ご指摘があり, どうやらPCREはPerl互換正規表現エンジン実装の1つに過ぎないということでタイトルは正確には「Perlの正規表現は無限の括弧の対応が取れる」かもしれません.

こんなの絶対おかしいよ

はい. PCRE すごいです.

僕が正規表現と戯れ始めたのはちょうど1年前. その時, 最初に @shinji_kono 先生に賜った 言葉が

正規表現は たかが 括弧の対応が取れないんですよ.

もうちょっと正確にいうと, 正規表現では

  • (a)
  • (((a)))
  • ((aaa)((bbb)((cc)(d))))
  • (()(()())()(()))()()

のような任意のネストを認めた開き括弧と閉じ括弧の対応がとれない.

というのも, 開き括弧を読み取った時点で, それに対応する閉じ括弧が現れるまで開き括弧の個数 を覚えて置かなければならないからです. 正規表現は 有限 オートマトンで認識できる言語しか表現できないので, 任意個(無限)の括弧に対応した 有限 オートマトンは作れないという話ですね. (もっと強力なプッシュダウン・オートマトン なら可能ですが.)

 

 

ところが

タイトルの通り, PCREさんだとそれが可能です(Perl 5.10からだそうです).

 

(?R)

という構文が正規表現に拡張機能として導入されており, これは パターン全体 を表現するそうです. つまり,

パターンの内部にそのパターン自身を埋め込める

はい. 再帰ですね. PCRE の manual では,

This PCRE pattern solves the nested parentheses problem (assume the PCRE_EXTENDED option is set
so that white space is ignored):

\( ( [^()]++ | (?R) )* \)

という正規表現が紹介されており, この正規表現は空白を無視すると

  • まず, 開括弧にマッチ
  • 続いて
    • 括弧以外の文字列にマッチ(++は貪欲なマッチングで, バックトラックを行わない. これもPerl5.10からの新機能)
    • もしくは, 全体のパターンにマッチ(再帰).

の0回以上の繰り返し.

  • 最後に閉括弧にマッチ.

短いのに恐ろしい記述力ですね. (てか初見じゃ意味不

これで 括弧のネストに対応できる! 再帰で! 1

 

つまり

正規表現2パーサーが書ける じゃないか! と, 思ったら 404 Blog Not Found で既に紹介されていました. (さすが正規表現フェチ ;-)

perl – parser書くならgoto

こちらは (??{ code }) という正規表現にコードを埋め込む, 動的正規表現という機能を使ってますね.

正規表現好きということなら, Perlの正規表現はしっかりチェックしないといけないなぁ. (強烈…)

http://perldoc.jp/docs/perl/5.10.0/perlreref.pod

 

 

おまけ

今日はじめて知ったんですが,

% man pcrepattern

とすると, PCRE の syntax manual が読めます(OS X だと標準で pcre が入ってます). これは便利. というかこれで今回の再帰構文も知りました.

ちゃんと読んでみよっと.

 

 

Footnotes:

1 もちろん 無限 というのは記述力的にという意味で, 実際はスタックの制限で再帰マッチングにはかぎりがあるのですが. (ツッコムのは野暮です:-p

2 もちろん,PCREの拡張を使って.pureな正規表現ではないですね.

 

 

 
Better Tag Cloud