dan kogai 前座なのか… せいきひょうげんってえろいの？ それってえらい！ すべての魔女を、消し去りたい $universe = s/魔女//g; まどかネタ無双 正規表現の使いすぎに対する注意喚起 スマートマッチは5.10から使える ~~ しかし、まだ遅い メールアドレスの正規表現 検証なんて、あるわけない アングルブラケットは正規表現ではマッチ出来ない perldoc -q mail IPv4へのマッチ よくある間違い \d{4}.\d{4}.\d{4}.\d{4} ちゃんと書こうとすると use Regexp::Common を使おう！ my $re_ipv4 = $RE{net}{IPv4} alteration (a|b|c|d)は[abcd]の4倍以上のコスト O(mn)のオーダー 人の手で最適化するのは無理 Regexp::Assembleで最適化しよう 実はPerl 5.10以降はTRIE Optimizationしてくれる しかし、Regexp::Assembleで無いと出来ないこともある キーワードをリンクにする、などの数のオーダーがより大きくなったときはText::DartsとText::Txを！ s///sexsexsex... ！？ 意味のある文字を指定したときは、何個あっても一つ指定したことと同じ eだけは重ねると、evalした結果を再度evalすることになる 正規表現のないPerlはコブのないラクダ 現在のいろいろな言語での正規表現の表現は、ほぼPerlに通じている Javaの正規表現はちょっと例外(ちょっと弱い) LionのPerl 5.12.3 木村浩一 正規表現 - もう一つのバベルの塔 - という話はやりません ずごー 「正規表現メモ」の人 実はある意味「黒歴史」 マイナーな演算子 [[:<:]] と [[:>:]] Tclで使える正規表現 [= =] [. .] どちらもPOSIXに定義されているメタ文字 [=e=] -> 普通のeだけじゃなくて、アクセント記号が付いたeにもマッチ ウムラウトなどを逐一書かずに一回で済ませられる [. .] -> スペイン語では、書くときは二文字だけど一文字と見なす物があるので、それを扱う \ Emacsの正規表現 -> バックスラッシュが山のように出てくる Perlではバックスラッシュ＋記号というメタ文字は3くらいから使わなくなった ラリーに感謝 (幻の？)Jperl 5.6 「Javaで実装されています！」(笑 日本語対応されたPerl ver4まではかなりしっかりメンテナンスされていた 5になってからメンテナが変わった 5.0005 -> 5.6 でJPerlが出なくなった 正規表現に戻り読みが入った 注目しているところから固定長だけ前に向かって読む 日本語では、EUC-JPでもShift-JISでも、「一文字」が何バイトなのか決定出来ない -> 固定長が保証出来ない 「Perl 5が出なかったら今のプログラミング言語ってどうなってんたんだろう」 by dan 正規表現の分類 POSIX BASIC grep, ed等で使う Extended egrep, awkで使う Perl拡張 一口で「Perl拡張」とはいうものの… Javaや.NETだと、戻り読みが可変長を許すので、ライブラリによって挙動が違ってくる 本を書くときに悩んだこと 注釈が酷いことになる 「ピリオドは一文字にマッチします。ただし…云々」 文字クラスとlocaleの悩ましい話 gawkがつい最近更新された [abcd]と[a-d]の違いとlocaleは相性が悪い 普通に考えればASCIIコード順だが、LinuxなどではUTF-8などにするとa->A->b->B->z->Zになる カタカナとひらがなで微妙にずれたり もう面倒くさいので、文字クラスで指定されたときはASCIIと同じ挙動にする、と決めたらしい @__gfx__ Hello, re::engine! Xslateを書いてる HTML::FillInForm::Lite HTML::FillInFormがコンパイルが必要だったので、正規表現で実装した Text::Xslate - tokenazer re::engineとは？ Perlの正規表現演算をオーバーロード出来るようにした物 プラガブルにしたよーとの記事が2006ごろ Perlコアと正規表現エンジンを独立させた Perl6への布石だったと思われる 素数判定のexample メリット コードを修正しなくてもエンジンを差し替えられるのがメリット CレベルのAPIなので高速 m//だけでなくs//やsplit//なども How it works 関数ポインタを格納したregexp_engineをvirtual tableにして関数をディスパッチ Virtual Table in regexp.h re::engine::PCRE re::engine::Oniguruma バックトラックに強い -> 正規表現の限界を突破する re::engine::RE2 Google製 複雑な正規表現だとPerl組み込みより早い re::engine::boost boost::regex::boost 遅すぎて話にならない(100倍くらい) 他の正規表現エンジンを簡単に試せるのが凄い 世界最速grepの正規表現エンジンのバインディングもcomming soon @sinya8282 正規表現の限界 nkfの河野先生の研究室にいました I ラブ 正規表現 私は正規表現が好きだ 正則表現について 基本: 連接、選択、へいほう 糖衣構文 .^$[]{}()?+ 基本3演算で表現出来ない演算もReal Workdでは使われている (?{ code }) 基本は三つだけ 三つの演算子しかないのなら単純で非力？ とある否定の正規表現(レジェックス) /a*/にマッチしない正規表現は/.*[^a].*/ この程度は人間でも作れる /abc/の否定は？/abc|efg/の否定は？/.*abc.*/は？ 正規表現を書く人間側に限界が… 何故否定の正規表現を書くのが難しいのか 正規表現からDFAから作ることとほぼ同義 正規表現の否定 <=> DFAの受理状態と非受理状態を入れ替えればいい 実はDFAからも等価な正規表現を作ることが出来る 正規表現 -> NFA -> DFA -> 否定のDFA -> GNFA -> 否定の正規表現 最悪計算量がexp()に 実は任意の正規表現の否定表現を生成するツールがない 実装した！ /abc/ -> /((a?|ab)|((([[^a]|a[^b])|ab[^c])|abc.).*)/ キャプチャーしているのでだめ by dan この世には正規表現で表現出来ない物がある 文脈自由文法 再帰的構造 正規表現は括弧の対応が取れない 四則演算など PCREには(?R)で再帰が使えるので何とかなる ただし、Irregular Expression 「とある再帰の正規表現」 再帰の深さを限定すれば有限 文字列の長さがNなら、たかだかN会の再帰 上限をNにした -> 前の長さ*2+35 の漸化式 つまり 35*((2^n+1)-1) 140文字以内の完全な四則演算 (140-1)/2 = 69会の再帰が上限 (35*(2^70)-1) -> 40ゼタバイト Q. 否定の正規表現を作るツールは？ A. 作ったのでこの後の発表でお楽しみに！ Q. pureな正規表現にこだわることの利点 A. DFAに変換出来る -> DFAの最適化 / 並列マッチングが出来たりする LT 僕の考えた世界最強の正規表現エンジン @shinya8282 世の中にはいろいろな正規表現エンジンがある PCRE RE2 鬼車 ずば抜けた特徴を持たせたい 速度！ Regen -> Regular Expression Generator 正規表現から色々"生成" x86ネイティブコード etc... 限界まで高速化したい DFAベースのマッチング 動的なコード生成 by Xbyak 並列DFAマッチング 機械語レベルでの最適化(なう) まだ単体でもライブラリとしても使えるレベルにはなっていない 再帰と否定の生成系としては使える Plaggerで覚えたPerlの正規表現 yusukabe UNIX pipe programming for web <- Plagger Filter::EntryFullText フィードを出力していないページの更新情報を扱う 30個のエロYAML！ エロサイトを購読 -> Plagger -> etc... リビドー駆動がよいよ！ Regexp::Assembleとかその辺の話 Yappo 正規表現を駆使して住所を抽出 郵便局のデータを用いた 都道府県はまだいいけど、市町村は正規表現を圧縮しないととてもじゃない Trieの方がAssembleより4倍くらい速い # ここで時間切れ 再帰的正規表現 JSON Validator TAKESAKO JavaScript Object Notation XSS等が怖いのでValidateが必要 僕と契約して、（ｒｙ sugyan Quine ruBy Perl版作りました！ JavaScript版も Quine -> 自身の完全なコードを出力するプログラム evalを使う 色を変える -> ANSI escape sequence セリフはuuencodeでごまかす use utf8;と書きたくないので変なことをする 整形 無駄に変換、空白を入れる、()を入れる 正規表現もちょっとだけ使ったよ 色々なものを正規に表現してみよう 「/RegEx/」というサイト 「電話番号」の例->残念な物が多い Number::Phone::JPを使おう 郵便番号も正規表現に出来るのでは？ 000-0000 〜999-9999のうち98.6%は実際には使われていない Number::Zipcode::JP 誰得？俺得！ DBで引いてパターンマッチより若干速いよ！！