読者です 読者をやめる 読者になる 読者になる

正規表現に関する妄言 ― モノイドなんじゃね

雑記

妄言です.

当てにしないで下さい.



最近, 正規表現について妄想することが色々あるのです. その中で思ったのですが, 正規表現って僕には構造がややこしすぎます.

とてもとてもややこしい.

例えば, 論理演算と同じ構造が入るかどうか考えてみます. 尚, ココで言う正規表現は, ECMA-262で定義されている動作をするものとします. つまりJavaScript正規表現です. また, 「マッチする」かどうかという時に, 文字列全体のマッチを無意識に仮定しています. (つまり/a/というのは/^a$/のつもり)

OR演算, これは当然, pattern|patternですね. /foo|bar|baz/なら, "foo"か"bar"か"baz"にマッチします. 「か」なので, OR演算でいいですね.

NOT演算, これはlookaheadの否定マッチかな. /foo(?!bar)/なら, fooにマッチするけどfoobarのfooにはマッチしません. マッチ「しない」ので否定でしょう.

いやいや, ちょっと待ってよ. NOTって一項演算子だよね. NOT a = /.(?!a)/でいいのかな? /.(?!a)/は「aの前の文字にマッチ『しない』」 うーん... なんか気持ち悪い...



待て待て, 文字が並んだものを考えるからややこしいんだよ! 一文字ずつの演算にしよう.

もう一回OR演算を考えなおそう. a OR b = /[ab]/ うん, これでいいじゃない.

じゃぁNOT演算は, NOT a = /[^a]/ これは, 「a『以外』の文字にマッチする」 おお, すごく自然だ.


では, AND演算, これは何でしょう. うーん... うーん...

論理演算としての性質が成り立って欲しいわけです. ええ, ド・モルガンの法則です.

NOT (a AND b) == (NOT a) OR (NOT b)

式変形

a AND b = NOT ((NOT a) OR (NOT b))
        = NOT (/[^a]/ OR /[^b]/)
        = NOT ( [[a以外]][[b以外]] )
        = NOT ( [[すべての文字]] )
        = [[何にもマッチしない]]

えええっ...

ちょっと待ってよー><

そもそも, aにマッチしてかつbにマッチしてって... 重ねあわせ!? 文字の重ねあわせ!? 量子力学!?





行き詰った....


ORのことは一度忘れて, a AND b = /ab/ってやってみることにしよう. あ, 非可換だ. なんかヤバイ.

ド・モルガン(ざ・りたーんず!

a OR b = NOT ((NOT a) AND (NOT b))
       = NOT (/[^a]/ AND /[^b]/)
       = NOT (/[^a][^b]/)

はうあー

NOTの引数は一文字だって自分で言ったじゃないですかー!!!

そもそも, 一文字しばりをするなら, AND演算が閉じていないじゃないですかー!!!

やだなーもう!!!





論理演算入らないのかも. あきらめ肝心!!! ブーリアン無理ぽ!!!





もうちょっと問題を簡単にしよう. 二項演算子が2つあって, それらに強い関係があると仮定するから頭がこんがらがるんだよ!

まず, pattern|patternの演算子. REGEXORとでも名づけましょう.

/foo/ REGEXOR /bar/ = /foo|bar/

/a|b/は/b|a/と等価ですね. (キャプチャーするかどうかとかを忘れたら.) ですから, REGEXORは取り敢えず可換です. 単位元はどうなるのか...

e REGEXOR a == a REGEXOR e == a

となるようなe, 噛み砕くと, 「eにマッチするかaにマッチするか」というのが, 「aにマッチするか」と等価. eにマッチするかを調べる必要がない... どんな文字列もeにマッチしない, そういうe.

e = /.(?!.*)/ 

でいいんじゃないか? おそらく, これはどんな文字列にもマッチしない. (反例あったら言って下さい!!!)

e = //

だと思った人, いい線いってるけどダメだね. そもそも空の正規表現は許されてなくて, 書くとしたら

e = /(?:)/
// same as: e = new RegExp('')

って成るだろうけど, これは「空文字」という文字列にマッチするからね.

分かったこと: a REGEXOR b = /a|b/ は(取り敢えず)可換で, 単位元は/.(?!.*)/, 結合法則を満たす.

逆元ってあるのかな? /a|b/も/b|a/も何にもマッチしない, そういうb. 待って待って!!! /a/が何か文字列strにマッチして, /a|b/がstrにマッチしなくなることってあるの!?!? 無い... よね... 逆元ないじゃん. あ, 但し, /(?:)/ REGEXOR /(?:)/ = /(?:)/ってなるね. ああ, 宜しい宜しい.




あと, 単純に「繋げる」演算子も考えられるよね. a REGEXSEQ b = /ab/みたいなん. ああ, REGEXSEQって名付けるよ.

/foo/ REGEXSEQ /bar/ = /foobar/

非可換であることは明らかだね. /ab/と/ba/はもちろん違う. 単位元eは... /ae/が/a/と等価なの... eは何にもマッチしない... あれっ これがさっきのやつだ!!! という訳で,

分かったこと: a REGEXSEQ b = /ab/は, 非可換で, 単位元はnew RegExp('') == /(?:)/, 結合法則を満たす.


あ, そうそう. キャプチャーとか.execの返り値とかは無視するよ. あそこら辺は難しいし僕も分からないからね.



んでもって, さっきのREGEXORの単位元/.(?!.*)/と, REGEXSEQの関係を見てみよう.

/.(?!.*)/ REGEXSEQ pattern = /.(?!.*)pattern/ = /.(?!.*)/
pattern REGEXSEQ /.(?!.*)/ = /pattern.(?!.*)/ = /.(?!.*)/

まず最初のは, どんな文字列にもマッチしない→patternって続くから, これはやっぱり何にもマッチしない. 二つ目のも, 何にもマッチしない. よって, どっちもREGEXORの単位元に等しい.

REGEXSEQの逆元? /ab/が空文字にのみマッチする, そういうb. a=b=/(?:)/ならそうだけど, そうじゃないときには逆元ないね.


もう一回まとめ
REGEXOR /a|b/は(もちろん正規表現で閉じていて,) 結合法則を満たし, 単位元は/.(?!.*)/, 単位元以外の可逆元は多分無い. 可換.
REGEXSEQ /ab/は(これも閉じていて,) 結合法則を満たし, 単位元は/(?:)/, これも単位元以外の可逆元は無し. 非可換.




後は...

/[abcd]/なんてのは/(a|b|c|d)/とほとんど一緒だからREGEXORでいいや. あれ, ちょっと待ってよ. /[^abcd]/はどうすれば? これって「a,b,c,dどれでもない文字一文字」だよね. これはREGEXORじゃ無理じゃん! 見なかったことにしよう.

/[a-z]/は/[abcd...z]/でおk.

あとめんどくさいのは/a{1,3}/みたいな奴か. こういう範囲を持ったのってなんか上手く代数的構造になりそうだけどめんどっちーな. 今日はやめやめ.



まとめ.

結局, REGEXORもREGEXSEQも, 単位元以外のやつに逆元がない. 結合律を満たして単位元を持つ二項演算子やからモノイドやー! モノイドが2つ入るような構造ってなんて言うんかいな?