Pixel Pedals of Tomakomai

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

トップ > 技術 > 今日は Regex Festa の日です

今日は Regex Festa の日です

技術

今日は Regex Festa の日です

Regex Festa に来ていますので、自分のためのメモを残しておきます。

挨拶

  • wi-fiとお手洗い、喫煙所の案内
  • Opt Technologies さんについて
  • QRコード読むとアンケートあります

いろいろな正規表現、いろいろなオートマトン / @sinya8282 さん

  • 正規表現は好きだが、難しい面も面白い面もある
    • 学部の頃は世界最速のgrepを書いてたりした
    • 院では学術よりな研究
  • Shibuya.pm#16 が正規表現オンリーなイベントだった
    • 東京素晴らしい！
    • 8年の時を経て復活
  • 正規言語の魅力
  • 正規表現は難しい
  • /(\D+|<\d+>)*[!?]/ pcrepattern のマニュアルに出ている
    • VM型の正規表現と相性が悪い( * の中に + があるから)
    • pcregrep で "a" x 23 をマッチさせると、失敗する
    • リソース不足になる (21世紀なのに23文字がだめなの・・・)
    • atomic group (?> ... ) を使うと解決
      • バックトラックを抑制する
      • 共通してマッチしない表現の和だと、使えるテクニック
  • (a?){22}a{22} 長さ22から44までの a の列にマッチ
    • pcregrep は "a" x 23 は失敗。 21 個なら大丈夫 (令和だぜ・・・？)
    • grep -E なら DFA 型なのでマッチできる
    • a? のマッチの仕方が複数あるため
    • a?? にすればマッチングできる。 ?? は最短一致を先に施行する
  • 正規表現技術入門 の 7 章を見て下さい
  • Tagged NFA (TNFA)
    • 有限個のカウンタを持つ
    • キャプチャを可能にする
    • むずいので論文読んで教えて
  • 透過性の判定は難しい
    • 正規表現が同じ文字列の集合を受理するのか
  • (a|b)* と (a|bb*a)*|a*b(b|aa*b)* は等しいのか
    • NFAにして考えると、aで終わる文字とbで終わる文字の結合だとわかる
    • オートマトンを介するしかない
  • 正規表現は難しい、オートマトンはかんたん
  • 公理を使って直接証明することはできる
  • 正規表現が重宝される理由
  • 1行で書けるからかんたんとは限らない
  • オートマトンはちょろい、かわいい
    • 様々な拡張モデルの提案
    • スタックやキューなど。後者はチューリング完全だが前者は違う
    • 受理、非受理だけでなく、受理する確率や、文字列など
      • weighted automata はかっこいい
  • オートマトンはFA
    • AFA～ZFAまで全部ある（略称が被っているものもある）
    • KFAとYFAは微妙にないと言えるかも。新しいオートマトンを作るチャンス
  • 語の組合せ論
    • 部分語の出現を数える
    • 部分語の出現回数がふさわしいような言語 $L^{=}$
  • 無限集合になるかどうかを判定できるか？
    • L^{=} \{ a, b, c \} は正規表現でも文脈自由でもない
    • L^{=} \{ ba, ba, a \} は \{ \epsilon, b, bb, bab, bbb, ... \} 無限集合
    • L^{=} \{ ba, ba, a, b \} は \{ \epsilon \} 無限集合
  • 2018年に語混合言語の無限性は決定可能であることを示した
  • constrained automata
  • オートマトンはちょろいのではなく奥が深い

regex-applicative: 内部DSLとしての正規表現 / @igrep さん

  • 日本Haskellユーザーグループ をよろしく
  • 今日はHaskellについては話さない
  • regex-applicative
  • match :: RE s a -> [s] -> Maybe a
    • 完全一致のみ
    • マッチしたら Just しなければ Nothing
  • 連接は *>
    • sym 'a' *> sym 'b'
    • string "ab" と同じ
  • 選択は <|>
    • sym 'a' <|> sym 'b'
  • 繰り返しは、 many (0 回以上) と some (1 回以上)
  • optional オプショナル ? と同じ
  • マッチした値を Haskell の値に割り当てる
    • digit 数値
    • many digit 数値のリスト
  • 正規表現内で計算
    • sum <$> many digit
  • string "http" *> optional (sym 's') *> string "://"
    • some (psym (`elem` ['a'..'z'] ++ "."))
    • psym は関数が芯になるような文字はマッチする
  • マッチ結果を構造体にマッチできる
    • data Origin = Origin { ... } を定義
    • Origin <$> scheme <*> host <*> (prot <|> pure 80) (この例はschemeが正しく取れてないので注意)
    • <$> と <*> で組み立てられる
  • メリット
    • コンパイラによる型チェック
    • 文字列以外の扱いが得意
  • デメリット
    • コードが長い
    • 速度も速くない
    • String 以外にはマッチできない
  • 仕組み
    • 継続渡しで作られたNFA
    • バックトラック
  • 正規表現の分類 - DFA型とVM型
  • regex-applicative は
    • NFA をそのまま使っている
    • 文字を受け取って次の状態を渡すリストとして表す
    • s -> [Thread s r] の実行に失敗したらバックトラックする
    • findLongestPrefix 関数のような実装に役に立っている
  • 比較
    • パーサコンビネータは Applicative ベースなので似ている
      • バックトラックをするかしないかが違う
    • パーサコンビネータは部分一致できないが、部分一致できるようにするライブラリもある
    • regex-applicative は部分文字列へのマッチがかんたん

Emacsと正規表現 / @tadsan さん

  • PHPには複数の正規表現エンジンがある
  • ereg (POSIX ERE、廃止), preg (PCRE), mb_ereg (鬼車)
  • 現状のPHPにはリテラルがない
    • バックスラッシュを一文字にマッチするには \\\\
  • preg ではデリミタを変更できる
    • '@ ... @i' など。後ろはパターン
    • 正規表現と競合しないものがいい
  • 内部的には正規表現結果はキャッシュしている
  • Emacsのエディタの検索機能
    • Emacsの正規表現はNFA
    • グループなど \ の前置が必要
    • [:space:] など癖がある
  • Lispでは foo-bar は1つのシンボルだが、C言語では減算
    • syntax table で変更できる
    • 逆に言うと正規表現の結果は、バッファの syntax table の値で変わる
  • 文脈によってエスケープの違いがある
    • \\ と "\\\\" みたいな
  • emacsのメジャーモードを書くには、大量にエスケープを書く必要がある
    • 読みにくい
    • rx という DSL がある (group "regexp") (repeat n m pattern) など
  • re-builder で色付けができる

ヘルプシステムで正規表現を使う / @masui さん

  • Scrapbox
    • 簡単に使える wiki
    • 正規表現を展開してヘルプシステムに使う
  • ヘルプシステムは情報が見つからないので誰も使わない
    • なぜか正規表現で解決できる
    • コールセンターに電話してしまう。3年でやめる
    • 一兆三千億円規模。書籍と同じ
  • データを網羅的に生成、それからフィルタリング
    • Generate & Test
    • 網羅してから合うものを選ぶ
  • 正規表現展開ライブラリ
    • (a|b)+ を a, ab, b, ... と展開したり
    • ユーザの質問を正規表現で書いて、展開したものであいまい検索を実行する
    • (時計|時刻)を(1?[0-9])時に(設定|セット)する
    • 回答だけではなく、実行もしてしまう
  • あいまい検索はちょろいオートマトンで実装
  • Git Help
    • 難しい git コマンドをかんたんに実行できる
    • ある文字列が初めて出現したバージョンの出し方とか
    • gitはなんでもできるが誰もそんなことは知らない（難しすぎる）
    • IME的に実装。コマンドを打つとコマンド一覧の窓が出て、実行可能
  • Helpfeel
    • ヘルプページ向けのサービス
  • GitHelp は論文投稿したがリジェクト
    • Gitを使ってないらしくリジェクト
  • http://masui.org に資料あります

正規表現の等価性判定について / @make_now_just さん

  • 正規表現の等価性は判定可能で、そのアルゴリズムの話
  • 例えば、Base64にマッチする正規表現は複雑
    • 文字列長が4の倍数と末尾の = の扱い
    • 2つの正規表現に分けたものと、等しいかチェック
  • 正規表現はDFAにでき、DFAを最小化できる。それが同型かを判定可能
    • 効率が悪い
  • 効率の良いアルゴリズム
    • DFAにはする
    • 初期状態からアルファベットのすべての文字について遷移させる
    • 受理状態がどこかで食い違ったら別
    • 割と普通の幅優先探索になる
    • 対応する状態を色付けして分類していく
    • すべての分類が一致すれば完了
  • 単純でDFAの最小化より効率的。DFAを作る時点でコストは大きい
  • NFAで判定する方法はどうか
    • NFAへの変換は楽なのでいい
    • 本当は正規表現のまま比べたいのでは
  • 正規表現の微分で判定する
  • 文脈自由言語の等価性は決定不能であることは知られている
  • 論文では、NFAを使ったものが一番早いそう

ミニマルな正規表現エンジンをScalaで実装してみた / @kmizu さん

  • 正規表現エンジンを自作する方法
  • アルファベット、空列、連接、和、Kleene閉包、e? e+
  • 実装は教科書的
  • ASTとNFA、NFAState、DFAなどを定義
  • パーザはASTを作る
    • 脱糖もする e? は e| 、 e+ は ee*
  • 正規表現を教科書的にNFAにする
    • 変換規則に沿って変換するだけ
  • NFAをDFAにする
    • 部分集合構成法
    • NFAの状態の集合のサブセットをDFAの状態にする
  • 300行未満で書けるので、みなさんも書きましょう

その正規表現エンジン、インタプリタで満足(satisfy)してる？！ / @blackenedgold さん

  • SATySFi
    • TeXを倒すためのもの
    • 日本語が扱えてPDFが出力される
  • ML風の関数定義、バックスラッシュのコマンド
  • インタプリタとコンパイラ
  • (第一)二村射影
  • 多段階計算
    • ステージ0でステージ1で実行されるプログラムを生成する
    • ステージ1でプログラムを実行する
  • &42 は次のステージで 42 になる。 &int 型
  • SATySFi には差ショートサーキットする論理 or and がない
  • マクロっぽいが、式から式の変換しかできない
    • eval には制約が入っている
    • 生成されたコードはコンパイルエラーにならないように型がつく
  • インタプリタの実装はDFAベースよりかんたん
  • 命令列をリストで書く (εと連接が何もしなくても手に入る)
  • SATySFiは文字がないので、文字列を文字代わりにする
  • 強欲マッチ(バックトラックは実装しない)なので、かんたん
  • これをコンパイルするのは & と ~ を適切に入れるだけ
  • コンパイルにすると、静的(stage 0)でエラーを検出できる
    • 組版で後半のページでエラーが出ると、前のページの生成が無駄になる
  • コンパイルだと正規表現は静的に与えなければならない

l3regex: TeX で実装された正規表現エンジン / @wtsnjp さん

  • l3regexの3つのポイント
    • 将来性がある
    • 実装がすごい(TeXで実装されている)
    • 実用性がすごい
  • LaTeX3プロジェクトなので将来性がある
    • LaTeX2eの光景
    • 1990 年代から作られている
  • 実装がすごい
    • TeXは名前空間がない、展開制御がない、副作用がいっぱい
    • 字句解析にチューリングマシンが必要となる言語
    • NFAベース(らしい)
    • TeXで実装するとあらゆる環境で動くので
  • 実用性 - 普通のライブラリ
    • バックスラッシュが蔵試食したりしない
    • TeX Live, MiKTeXなどでも導入される
  • 滅ぼされる言語かもしれないが、来週提出の論文には使える！

正規表現苦手なんです / @5mingame さん

正規表現のlook behindで量指定子を使いたい / @hachi8833 さん

  • (?<=...) (?=)
    • look behind に長さが違う (...|...) や ? {1, 2} .+ .* を書くことができない
    • 長さが変わってはいけない
  • ? {1, 2} がだめなのはなっとくいかない
    • (a|b) のように長さが変わらないのはいい
    • {3} とかも
  • .NET Framework の正規表現ではフルで使える
    • 最強の正規表現エンジン
    • ドキュメントも充実
  • V8 の正規表現エンジンもいける
    • 昔のJSは look behind 自体がなかった
    • 文字クラスも使えるように？
  • PCRE と Onigmo も頑張ってほしい

とある機械の右方跳躍 / @sinya8282 さん

  • 世界で知っている人10人もいない
  • right one-way-jumping automata
    • 日本語訳は shinya さんが勝手につけたもの
    • 文字列を読むときに、1文字ずつではなく飛び越える
    • 秋田大の学生が考えたもの
  • (b|a)* の DFA を右方跳躍オートマトンとして扱うと、 a と b の出現回数が同じものを受理する
  • 例えば、 baaabb は ba で計算が終わるはず
  • 「optさんが素晴らしい酎ハイを用意してくれたのでちょっと酔ってる」
  • 右方跳躍では、遷移可能な文字で一番近い文字に飛ぶ
    • 一番右まで行くと左から戻ってくる
  • 「与えられた右方跳躍オートマトンAがDFAのとき、Aの受理する文字列の集合が正規言語になるかどうか、のアルゴリズムが存在するか」は未解決