正規表現, 面白いですね

正規表現強えぇ!!

• ある正規表現の否定も正規表現で書ける.
• ある正規表現と正規表現の積集合演算&も正規表現で書ける.
• XOR, Shuffle, Reverse, 微分, ... 色々な演算が正規表現上で定義できる!
• しかし...

悲しいお知らせ...

• この世には, 正規表現で表現できないモノがある.
• もしかして: 文脈自由文法
• 再帰的構造(ネスト)を持つ文法も文脈自由文法では表現できる!
• (文脈自由文法でも, (右/左)正規文法で書けるものは正規表現でも書ける)

正規表現の限界を超えた文法

• 正規表現は, 括弧の対応がとれない! S ::= '('S')'|ε
• たとえば: 自然数の四則演算の構文(EBNF, charactor class 使えましたっけ?).

  expr   ::= term { [+-] term }
  term   ::= factor { [*/] factor }
  factor ::= [0-9]+ | '(' expr ')'
  		

• この文法は, expr だけの規則に書き換え可能

expr   ::= ([0-9]+ | '(' expr ')')
           {[*/] ([0-9]+ | '(' expr ')')}
           {[+-] ([0-9]+ | '(' expr ')')
            {[*/] ([0-9] | '(' expr ')')}}
		

正規表現の限界を超えたPCRE

• 先の四則演算の文法(EBNF)は, PCRE の拡張文法にある再帰構文 /(?R)/ を使うことで表現可能 ↓↓
• /([0-9]+|\((?R)\))([*/]([0-9]+|\((?R)\)))*([+-]([0-9]+|\((?R)\))([*/]([0-9]+|\((?R)\)))*)*/
• これがほんとのIrregular Expression.
• 正規表現による受理/非受理の検査だけなら, 演算子の優先順位を気にする必要はない :-p
• /([0-9]+|\((?R)\))([-+*/]([0-9]+|\((?R)\)))*/
• ... これで.. 満足...?

結局正規表現で四則演算を認識するのは無理?

• PCREの再帰構文は, もちろん内部で再帰/バックトラックが行われている. これは Irregular Expression
• 結局ピュアな正規表現では単なる四則演算すら表現できない?
• 正規表現はたかが括弧の対応がとれない?
• 正規表現の限界こんなもん?

限界など!知らない!意味ない!

逆に聞こう, 無限に再帰などするのか?

• 再帰の深さを限定すれば, 有限の状態で表すことができる!
• 文字列長がNであれば, 再帰の深さはたかだかN回.
• 再帰回数による上限付きの再帰構文/(?R)/を実装しました.
• 先程の四則演算をむりやり制限付きで正規表現にしてみましょう.
• /([0-9]+|\((?R)\))([-+*/]([0-9]+|\((?R)\)))*/

再帰: LV0

• 0回の再帰(括弧によるネスト)を許した四則演算
• /([0-9]+|\(\))([*+-/]([0-9]+|\(\)))*/

再帰: LV1

• 1回までの再帰(括弧によるネスト)を許した四則演算
• /([0-9]+|\(([0-9]+|\(\))([*+-/]([0-9]+|\(\)))*\))([*+-/]([0-9]+|\(([0-9]+|\(\))([*+-/]([0-9]+|\(\)))*\)))*/

再帰: LV2

• 2回までの再帰を許した四則演算
• /([0-9]+|\(([0-9]+|\(([0-9]+|\(\))([*+-/]([0-9]+|\(\)))*\))([*+-/]([0-9]+|\(([0-9]+|\(\))([*+-/]([0-9]+|\(\)))*\)))*\))([*+-/]([0-9]+|\(([0-9]+|\(([0-9]+|\(\))([*+-/]([0-9]+|\(\)))*\))([*+-/]([0-9]+|\(([0-9]+|\(\))([*+-/]([0-9]+|\(\)))*\)))*\)))*/

再帰: LV5

• 5回までの再帰を許した四則演算
• こんなんなりました.

再帰: LV n

• 上限付き再帰は, 実際単なる正規表現の展開操作(マクロ).
• 再帰上限が0の場合の四則演算の正規表現の長さは35文字
• 再帰上限がnな正規表現の長さは「再帰上限n-1な四則演算正規表現の長さ」*2+35文字. (2箇所に再帰含む35文字の正規表現なので)
• つまり 35(2^{n+1}-1) 文字, その時のDFA状態数は3*2^{n+2}-5状態(実測値)
• 実用的には, 再帰回数よりはマッチ対象文字列の長さで制限をかける場合が多そうですね!

ヒウィッヒヒー

• 140文字以内の完全な四則演算を認識する正規表現は?
• 先の再帰表現では再帰の度に括弧'(',')'で2文字分消費する. また, 末端は少なくとも1文字以上の数列なので, (140-1)/2 = 69回が再帰上限?
• 140文字以内の完全な四則演算を認識する正規表現の長さは?
• 35(2^70-1) = 41320706725109395619805文字(約40ゼタ文字)
• そもそも140文字以内の四則演算として認められる文字列の総数は?(膨大) それらを選択でつないだ(全列挙)正規表現の長さ,状態数は?? もっと短い正規表現で書けない???(書ける)

正規表現, 本っっ当に面白いですねぇ

本当はもっと色々話したい... 盛り上がりたい!

• "先読み"を正規表現で代替するには? → 積集合演算と/.*/の追加と少々の書き換えで可能(かな?)
• Back Reference(後方参照)をなんとかピュアな正規表現で実現しようとするとどうなる? (制限を付けると可能)
• 正規表現の最小化
• NFA/DFAベースエンジンの実装と計算量
• 部分的な再帰を持つBNFを上限付き再帰表現化に自動変換, その時のサイズとか.
• 正規表現マッチングの高速化(Reverse Factor法)とか
• PEGとかも最近定義だけ知りました. 面白そう! (よくわかってない)

Any Questions?

資料

• 計算理論の基礎: DFA→正規表現変換アルゴリズム, 各種定理
• 正規表現メモ: 「ある文字列を含まない正規表現」についての説明, デモ有り(js)
• Derive Your Dreams: 「微分と微分の話：解題」, 正規表現の微分について
• Implementing Regular Expressions: RE2の作者である Russ Cox 大先生の主に実装に関する記事
• A Play on Regular Expression: 今回紹介した再帰表現を, Haskell の遅延評価を使って無限再帰も扱えるようにしたりしてます.
• Regen再帰表現, 否定表現の生成系の実装. (Documentぇ...)
• とあるさくらのジェネレータ: 画像生成