正規表現の最適化1

下らないことを考えてみた。

正規表現で、繰り返しを表す記号（数量子とか言うらしい）には、*とか、?とか、+とか、{a,b}とか、いろいろある。また、その中にも最長一致とか最短一致とか強欲なマッチとかいろいろな種類がある。

とりあえず、最長・最短・強欲の種別は無視するとして、*・?・+・{a,b}の指定に関して、正規表現を最適化することについて考えてみた。

*は0回以上の繰り返しを表す。すなわち機械的に{0,}に置き換えることができる。同様に、+は{1,}に、?は{1,0}に置き換えることができる。また、{a,b}の形式でbが省略された場合は、bに十分大きな値（例えばINT_MAX）が指定されたと考えれば、全ての数量子は{a,b}の形に正規化することができる。

そこまではいい。問題はここから。

α{a,b}{c,d}と指定されたら何が起きるのか、ということについて考えてみる。この指定の直接的な意味としては、正規表現αが、最低a回・最大b回繰り返し、かつ、それが最低c回・最大d回繰り返すということになる。つまり二重の繰り返しになるということだ。

だが、素直に考えるとこれは無駄である。例えば、α{0,1}{0,INT_MAX}と指定された場合は、内側の{0,1}の指定は全く意味が無くただの無駄以外の何物でもない。すなわち、α{0,INT_MAX}と最適化してあげるのが妥当である。

同じように、α{2,3}{4,5}と指定された場合にはα{8,15}としてあげることができるはずである。そうすれば、マッチを行う際の処理効率が大幅に向上するはずだ。（まぁ、元よりこんなアホな指定をする人間が悪いという考え方もあるのだが）

そう考えると、一般的にα{a,b}{c,d}と指定された場合は、α{a*c,b*d}と変換してあげることができるような気がする。

しかし、よく考えるとこの変換には無理がある。例えば、α{20,21}{2,3}という指定について考えてみる。この場合、先の変換公式に従うとα{40,63}という形になるのだが、実はα{20,21}{2,3}とα{40,63}とは等しくないのである。

すなわち、α{40,63}とした場合は、正規表現αが最低40回・最大63回繰り返すと言うことを意味しているのだが、α{20,21}{2,3}とした場合は、αが40回・41回・42回・60回・61回・62回・63回のいずれかの繰り返しになると言うことを意味する。よって、この変換は成立しない。

よくよく考えると、ある特定の条件が成立した場合だけα{a,b}{c,d}をα{a*c,b*d}に変換できるということに気がついた。だが、その条件については、今日はもう疲れたからまた今度書くことにする。