タグ : Perl

Shibuya.pm 〜夏の正規表現祭り〜 で好きなこと喋ってきた.

夏だ祭りだ正規表現だ!!

ということで, 行ってきました Shibuya.pm @ mixi

僕はありがたくも「正規表現の限界」とLT・宣伝で「僕の考えた世界最強の正規表現エンジン」と2つの枠で発表させてもらいました.

「正規表現の限界」の方は, 割と皆さん面白いと行ってくれて本当に嬉しかった. 発表するまで「こんなの当たり前じゃん」とか「誰得」とか切り捨てられないかな… とかネガティブループしてたんですが, 発表してみるとやっぱり楽しかった.

計算量だとかアルゴリズム詳細とかは末尾の資料を参照してください. つっこみがあれば修正したいです.

というかつっこみがなくても修正しなくちゃな… チラッと触れて説明してないところ多いし :-)

メモメモ

以下, 心に残った言葉, 印象深かったことをメモ

最後に, 懇親会でこれを聞けて嬉しかった

「キャプチャ"する"括弧こそ特別な表記にすべきじゃないですか?」と @ さんに聞いたら, 「Perlの父 Larry もそこは後悔している」みたいなことを聞けて少しスッキリした. ダンさんも聞きまくったらしいw #shibuyapm
@sinya8282
Ryoma SHINYA

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