本を読む

読書やコンピュータなどに関するメモ

Shibuya.pmテクニカルトーク#16をustで見ました

 Shibuya.pmテクニカルトーク#16が開催されたので、ustで見ました。参加申し込みは、あいかわらず瞬殺でしたね。

 今回のテーマは「夏の正規表現祭り」。いずれもマニアックかつ現実的な話で、とても面白く視聴していました。

 以下、メモ。

Dan the (Irr|R)egular Expressionist (@dankogai)

  • 「すべての魔女を消し去りたい」
    • s/魔女//g
    • 命かけるなコード書け
  • 正規表現はついつい使いすぎる
  • 正規表現厨の典型症状
    • /^(XX|YY)$/
      • ハッシュで
      • スマートマッチもある。遅いがエレガント
    • メールアドレス
  • use Regexp::Common
    • IPv4アドレスにマッチする正規表現
  • use REgexp::Assemble
    • alteration:文字列|文字列、のパターン
      • 頭からマッチする
      • character class([])はビットマップを作る
    • TRIEを作る
    • 実はPerl 5.10以降はTRIE Optimizationしてくれる
      • どのalterationにマッチしたかまでは取れない
  • 同じ修飾子を複数指定
    • ふつうは意味がかわらない
    • eだけは、その回数だけevalする
  • JavaScriptの正規表現は弱い
  • 正規表現はPerlに自然にとけこんでいる
  • Mac OS X Lion
    • MacPortsからパッチをもってくる

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

  • 「正規表現メモ」
    • ある意味黒歴史
    • 本の執筆の話をもらったが…
  • [[:<:]]と[[:>:]]
    • Tclで使える
    • 単語の境界にマッチ
  • [= =] [. .]
    • POSIXで定義
    • ほとんどサポートされてない
    • [= =]:アクサンテギュやウムラウトが付いたものもマッチ
    • [. .]:スペイン語で、英字だと2~3文字になるが1文字扱いになるものを1文字に
  • 幻のJPerl 5.6
    • dankogai「Javaで実装されてます(嘘)」
    • あるときを境にJPerlは出なくなった
      • Perl 5.6の正規表現で戻り読みが入った
        • 日本語では1文字=1バイトと限らない
      • それだけではないが
  • 大まかな正規表現の分類:3種類(木村説)
    • POSIX基本(grep、ed)
    • POSIX拡張(egrep)
    • Perl拡張(ひとくくり)
  • 文字クラスとlocale
    • awk 4.0リリース
    • [a-z]がマッチする対象

Hello, re::engine! (@__gfx__)

  • 正規表現関連の成果
    • HTML::FillInForm::Lite
    • Text::Xslate
  • re::engine
    • Perlの正規表現演算をオーバロードできるようにする
    • Perlコアと正規表現エンジンを独立させた
  • 素数にマッチする正規表現
    • use re::engine::RE2
  • コードを修正しなくてもエンジンを差しかえられる
  • 関数ポインタをvirtual tableに入れてディスパッチ
    • PerlIOやMAGIC変数でも使われるテクニック
  • (壇上でプレゼンをgit commitとgit push)
  • re::engne::PCRE
    • PCREをPerlから利用できるw
  • re::engine::Oniguruma
    • バックトラックに強い(セグフォしない)
  • re::engine::RE2
    • 速い、ただし低機能
  • re::engne::boost
    • 遅すぎる
  • re::engine::Plugin

正規表現の限界 (@sinya8282)

  • サイボウズ・ラボユースで正規表現エンジンの開発
  • 複雑な正規表現
  • 前提:ここでいうのはpureな正規表現
  • 基本:連接、選択、閉包の3つの演算だけで書ける
    • 簡単?
  • 否定:マッチしない正規表現
    • /a*/ → /.*[^a].*/
    • /abc/の否定は? /abc|efg/の否定は? /.*abc.*/の否定は?
    • なぜ難しいか
      • 正規表現からDFAを作ることとほぼ同義
        • 受理と非受理を入れかえればいいだけ
      • 正規表現→NFA→DFA→否定のDFA→GNFA→否定の正規表現
    • 任意の否定表現を生成するツールを作ってみた
      • (えらいことに…)
    • 否定は正規表現の限界を超えてはいない
  • 正規表現で表現できないもの
    • ネスト
      • 括弧の対応
      • 四則演算のBNF
  • 再帰の深さを限定すれば、有限の状態で表せる
    • 文字列長がNであれば再帰の深さは高々N
    • カッコの中にまた正規表現
    • レベル5だと2000文字ぐらい
    • 前のレベルの*2+35文字(漸化式)
  • 実用的には再帰回数よりマッチ対象文字列の長さで制限?
    • 140字以内の完全な四則演算を認識する正規表現:約40ゼタ文字
  • Q: 否定対応エンジン
    • A: LTで
  • Q: ピュアな正規表現にこだわるのは
    • A: DFAに変換できる。研究テーマ、DFAの並列化

LT:僕の考えた世界最強の正規表現エンジン(速けりゃイイじゃん?) (@sinya8282)

  • 実装しようとしているエンジンの紹介
  • どう実装しよう
    • 速度、速度…
    • 速度と機能は反する?
  • Regen
    • Regular Expression Gererator
    • 正規表現からいろいろなものを生成
      • x86コード、DFAグラフ、正規表現
  • 高速化
    • DFAベースのマッチング
    • コード生成(Xbyak)
    • 並列DFAマッチング
  • 期待してね
  • https://github.com/shinya8282/regen

LT:Plaggerで覚えたPerlの正規表現 (@yusukebe)

  • 2006年夏、ぼくは正規表現を覚えた
  • それ、Plaggerで
    • EFTの設定
    • 30個のエロYAML
      • いまではないサイトも
  • エロサイトも作ったよ
  • 初心者の時は既存プロダクトをいじるといいよ

Regexp::Assembleとかそのへんの話 (@yappo)

  • 住所を抜き出して位置情報を取ってGoogle Map
  • 膨大な住所情報を手作業でやってられない
  • 膨大なので圧縮したい
  • 最適化、ベンチマーク
    • だいぶ差
  • Regexp::Optimizer
    • コンパイラが通らなかった
  • Trie::Optimizer
  • だがRegexp::Asssembleをおすすめ
    • メンテされてる

再帰的正規表現 JSON Validator (@TAKESAKO)

  • PCRE拡張
    • (?(DEFINE) …) パターンを定義
    • (?R) 再帰
      • (?0)(?1)(?2) 任意のキャプチャ部分の再帰
  • 再帰的正規表現 便利

僕と契約して、(ry (@sugyan)

  • Quine
    • RubyでQB
      • 目の色が変わったり、セリフが変わったり
    • Perl版
    • JavaScript版
  • evalとprint以外は好きに書ける
  • なんとなくuse utf8って書きたくなかったので
  • 文字数を合わせる
  • ちょっとだけ正規表現使ってますw

色々なものを正規に表現してみよう (@nipotan)

  • 正規表現共有サイト
  • 電話番号
    • 残念
  • Number::Phone::JP
    • 存在しない番号にマッチしない
  • Number::Phone::JPを使ってるモジュールの例
    • Data::RuledValidator::Plugin::Japanese
  • 郵便番号
    • 存在しない番号が圧倒的に多い
  • Number::ZipCode::JP
    • 昨日CPANに上げた
  • 誰得?
    • MySQLで郵便番号をprimary keyにしたテーブルと、判定比較
      • 若干速いw
  • 適当に書かれたデタラメの正規表現に騙されないように

コメント

コメントの投稿

管理者にだけ表示を許可する

トラックバック

http://emasaka.blog65.fc2.com/tb.php/916-507bdb29

 | HOME | 

Categories

Recent Entries

Recent Comments

Recent Trackbacks

Appendix

emasaka

emasaka

フリーター。
連絡先はこのへん

Monthly


FC2Ad