[ruby-dev:8389] Re: Regexp <=>

原です。

In message "[ruby-dev:8383] Re: Regexp <=>"
    on 99/11/19, EGUCHI Osamu <[e-mail]> writes:
|
|えぐち＠エスアンドイー です。

|(私の印象ですが、) NP完全とは言えないと思います。
|適切な正規化則さえ定義すれば、同じパターンにマッチする正規表現は、
|１つの form に還元されると思います。
|＃ブール代数式を加法標準形に直すのと同じ要領。
|
|ただ、この『正規化則』ったのが厄介で、regex の内部表現の変形を
|サクッっと出来なければ行けませんね。
|＃これするぐらいなら、 regex をスクラッチから書き直す方が楽？
|
|気分的には 
|
|	/abc/ | /xyz/ => /abc|xyz/
|
|が出来る Regex#| とかあれば、無理に一個の正規表現リテラルに
|表現する必要がなくって、スクリプトを書く時に楽かなと思います。
|＃正規表現の最適化出来そうだし。。。

前にも議論があったのですが、正規表現の演算を考える時はまず、それが正規
表現の文字列への適合の話か純粋に正規表現の内部の話か、区別しておかない
といけないですね。例えば /./ を前者でいうと任意の一文字以上の文字列で
すが、後者では単に任意の一文字です。演算なら
前者で言えば

  /a/ & /b/ => a も b もマッチする => /a.*b|b.*a/
  !/a/      => a にマッチしない    => /^[^a]*$/

であるし、後者で言えば(ちょっといいかげんだけど)

  /a/ & /b/ => a であり b である一文字 => 空 => /[^\x00-\xff]/
  !/a/      => a 一文字でない任意の文字列  => /|[^a]|..+/

みたいなものですから、大きな違いです。

で、/(a+)b\1/ などの参照つきの表現を考えるとそもそもいわゆる正則集合で
はないので、色々な演算についても閉じていないでしょう。上のどちらの立場
を取っても。正規形も存在しないのでは?