Pixel Pedals of Tomakomai

北海道苫小牧市出身の初老の日常

トップ > 技術 > 今日はShibuya.pm #16の日です

今日はShibuya.pm #16の日です

技術

今日は夏の正規表現祭りに参加していますので、自分用にメモします。

ustreamもあります！

(Irr|R)egular Expressions / @dankogaiさん

  • 「えろい」のではなく「えらい」
  • 「命賭けるな、コード書け」
  • 正規表現の使い過ぎに注意
  • $str eq 'XXX' or $str eq 'YYY' を /^(XXX|YYY)$/ に書き直したくなる → やりすぎ
    • もしくはハッシュを使ったり、5.10 でスマートマッチ ~~ を使ったり。
  • メールアドレスの検証の正規表現 → 適当に書くと不完全。完全に書くとすごく長い
  • Regexp::Common → 便利な正規表現集。ipv4とか。
  • Regexp::Assemble → alternations (xxx|yyy|zzz) をTRIE最適化する。
    • ただし、5.10 以降は自動でTRIE最適化してくれる
    • マッチした部分を返す機能がある
  • s///sexsexsex → オプションを重複させても、一回指定したのと一緒
    • s///mixi も同じ話。
    • ただし、eだけは重複して効果がある。
  • 正規表現はPerlの、最高ともだち → 言語に組み込まれてるので自然
  • 時間が過ぎたけど小ネタ

正規表現 -もう一つのバベルの塔- - 木村浩一さん

スライドがレジュメしかない、小話形式でした。これはこれで面白い。

  • マイナーな正規表現
    • [ [ : < : ] ] [ [ : > : ] ] Tclの正規表現。Perlでは\>や\<
    • [= =] → アクセント記号付きのものも含めてマッチ。POSIX標準。
    • [. .] → アルファベットの綴りが2文字以上で1文字の文字の表現。POSIX標準。
  • ￥の話
    • Perlは￥をあまり使わなくて非常にありがたいという話
  • 幻のJPerl 5.6の話
    • Perl5になってメンテナが変更。
    • 5.0005から5.6に変わった時点でJPerlが出なくなった。なぜ？
    • 正規表現の戻り読みの拡張が厳しかった。Perlの実装が固定バイト戻るようになっていたが、日本語は1byteか2byteなのできつかった。
  • おおまかな正規表現の分類。3種類
    • POSIXのBASIC → grepなど
    • POSIXのEXTENDED → egrepやawk
    • Perl拡張 → バリエーションが多い
      • 5.004くらいまでサポートされてれば十分？
      • Javaや.Netでは戻り読みの可変長が許されたりする
  • 正規表現の本の話
    • 注釈が多くなり過ぎる。7割くらいが注釈になるんじゃないか。
    • 「続きはWEBで」で誤摩化した
  • 文字クラスとlocale
    • ハイフンでの範囲指定。
    • 例えばa-zとは？ → UTF-8などの関連で、a、A、b、B、・・・となったりする
    • ひらがなとカタカナでも同じ問題

Hello, re::engine! / @__gfx__ さん

スライドはこちら*1。

  • HTML::FillInForm::Lite → 正規↑表現↓*2で実装した高速版
  • Text::Xslate → tokenizerを正規↑表現↓で実装したもの
  • re::engine とは？ → 正規↑表現↓の実装を入れ替える仕組み。2006年。
  • re::engine::RE2を使った例 → 素数判定する正規↑表現↓
  • re::engineの利点 → コードの修正不要、CのAPIなので早い、限界を突破できる
  • 仕組み → 関数ポインタによる多態
  • 現在CPANにあるもの
    • PCRE → Perl互換の正規↑表現↓。速度もほぼ同等。
    • Oniguruma → バックトラックに強い。メモリが食いつぶされるだけでセグフォしない。
    • RE2 → Googleが開発。低機能だが速い。
    • re::engine::boost？？ → 遅い。移植はほぼ諦め
    • re::engine::Plugin → Pure Perl で実装できる仕組み
  • Q. (性器と混同しなくて)アクセントがいいですね！
  • A. なんと表現したらよいものか

正規表現の限界 / @sinya8282 さん

スライドはこちら。

  • ラボユースで正規表現エンジンを作っている。Mongerってなに？
  • 複雑な正規表現を見てニヤニヤしたい
  • (Pureな)正規表現の演算
    • 連接、選択|、閉包* の3つだけ
    • 糖衣 → .^$[]{}()?+
  • 簡単？ 否定の正規表現を考える
    • 正規表現が受理しない集合は正規表現で書ける
    • /a*/ の否定は /.*[^a].*/
    • /abc/ や /abc|efg/ や /.*abc.*/の否定は？
  • 否定の表現が難しい理由
  • 正規表現の否定表現を生成するツールがないっぽい → 実装した！
  • /abc/ や /abc|efg/ や /.*abc.*/の答え合わせ → 複雑...
  • /.*a.{2}/ → すんごい量
    • この結果に Regexp::AssembleRegexp::Optimizer*3 すると24GBのメモリが潰れる。。。
  • 正規表現で表現できないもの → 文脈自由文法
  • "Pureな"正規表現で再帰をしてみる
    • 再帰の回数を有限にすれば、正規表現で表せる
    • 四則演算の例: 0回、1回・・・5回(2000文字くらい)
  • マッチ回数より表現の長さ。140文字で
    • 上限は、「140 - 1 / 2」 = 69回
    • 35(2^70-1) (約40ゼタ文字)
  • 他に話したかった話
    • 先読みは書ける？ 積集合演算
    • バックリファレンスは？ → 制限を付ければ
    • 正規表現の最小化、NFA/DFAの実装と計算量などなど
  • Q. 否定の生成ツールは作った？
  • A. 公開済
  • Q. Pureにこだわる理由は？
  • A. DFAで表現できる。最適化や並列化ができるかも。今日は複雑なものが見たかっただけ。

Lightning Talks

僕の考えた世界最強の正規表現エンジン / @sinya8282 さん
  • これから実装したい正規↑表現↓ の話
  • 色んな正規表現エンジンがあり、特徴がある
  • 目指すべき特徴 → 速度、速度、速度、・・・
  • Regen(レーゲン) 正規表現ジェネレータ
  • 高速化
  • 乞うご期待！
Plaggerで覚えたPerlの正規表現 / @yusukebe さん

スライドはこちら。

  • 2006年にPlaggerで正規↑表現↓を覚えた
  • Plagger とは？ → データを収集し、プラガブルに出力
  • Filter::EntryFullText → 正規表現でとってくる箇所を指定する
  • 30個くらいエロYAML書いた → 正規表現の初歩
    • .+?, .*?
    • \d{4}/\d{2}/\d{2}
  • まとめ: リビドー駆動おすすめ
Regexp::Assembleとかその辺の話 / @yappo さん

スライドはコチラ。

  • Geography::AddressExtract::Japanizeで正規↑表現↓を使った話
    • 住所文字列を並べた正規↑表現↓ (郵便局CSVを利用)
    • 圧縮が必要 → Regexp::Assemble
    • ベンチマークとった
  • Optimizer はコンパイルが通らなかった。Trieは4倍くらい速い
  • テストが多い、メンテされてるものがいい → 弾さん曰く、Regexp::Assembleがおすすめ
  • GroongaのPerlバインディ(ゴーン 時間切れ)
再帰的正規表現 JSON Validator / @TAKESAKO さん

スライドはコチラ。

  • (?R) の話 (?0) や (?1)
  • JSON とは？ → JSのサブセット。ただしevalすると危険。
  • バリデーションが大事
    • stringやnumber、array、object、value、boolean など
    • キーは文字列
    • カンマの略はNG
    • シングルクオートはNG
    • +や-はNG
    • コメントはNG
    • 10進数のみ
    • True, Falseなど大文字は駄目
    • /をエスケープ
  • (?(DEFINE) (? regexp1) (...) ...) わかりやすい
  • (?R)がPerlでも使える
    • (?R)だと全体にマッチするので、(?0)や(?1)でグルーピングできる
    • JSONバリデータがきれいに書ける
僕と契約して、(ry / @sugyan さん

スライドはこちら。

  • QBのQuineのPerl版、JS版を作った
  • Quineの基礎 → evalの中でprint する
  • エスケープシーケンスを利用して目の色を変える
  • セリフはpack 'u' で隠す
  • use utf8の代わりに$^Hを利用
  • 形合わせ "hog" . "e" とか ( ( ) ) とか
  • 正規表現はちょっとだけ使ってます！！
色々なものを正規に表現してみよう / @nipotan さん

スライドはコチラ。

  • /RegEx/ 正規表現の共有サイト
    • 手ぬるいマッチが多い
    • Number::Phone::JP を使おう → 存在しない番号にはマッチしない
    • 巨大な正規表現
  • 郵便番号
    • 000-0000~999-9999までのうち、98.6%が使われていない
    • 昨日作った
    • 7ページ分の正規表現
  • MySQLでひくのと、正規表現で比較 → 正規表現が若干速い

懇親会

mixiさんのご好意による懇親会でした。大変ありがたいです！ 後、@TAKESAKOさん、毎回毎回ほんとお疲れさまです。

  • 乾杯の音頭: 歌代和正様
    • jcode.pl開発者
    • 最近もコードを組んでいる → 姓名判断プログラムのUnicode対応
    • Encode.pm 便利!
    • 正規表現本の1版と2版は訳者が変わった関係で「前」「後」「先」「後」の用語の使い方が逆になってるらしい
    • Shibuya.pmとTokyo.pmに乾杯！

*1:リンク修正しました。@risouさんあざす！

*2:↑と↓はアクセントの強弱を表す表現であって特殊な用語ではないので悪しからず。

*3:Thanks to @sinya8282