第6回　Ruby M17N 事始め：正規表現編

はじめに

今回は、今話題の正規表現について、その歴史と限界、そして限界を越えた先までを解説します。なお、るりまやるびまの記事もあわせて読んでみてください。

正規表現とは

さて、正規表現はもともと1940年代に神経生理学者によって生まれ[1]⁠、数学者[2]や言語学者、情報工学者たちによって理論的背景が研究されてきました。これを最初にコンピュータで用いたのがKen Thompsonによるqed[3]で、それ以降正規表現はテキスト処理に欠かせないツールとして愛されてきました[4]⁠。

基本的な演算

正規表現では、量化・連結・選言という3つの演算を用いて、目当ての文字列群だけを識別する規則を記述します[5]⁠。

量化：: 語を繰り返す。一般に用いられる演算子*から、スター演算とも言う。結合則は強い。
連接：: 語と語をつなぐ。
選言：: ある語か別の語かのどちらか。結合則は弱い。

演算子

Rubyでは、さまざまな演算子を用いて規則を記述します。GNU regexベースの1.8.7と鬼車ベースの1.9.1で機能が異なるので対応するマニュアルを参照してください。

具体的には後述しますが、1.9系では戻り読み「(?<= ... )」や否定戻り読み「(?<! ... )」等の機能が追加されており、より複雑な規則を記述できます。また、Ruby M17Nへの対応も行われています。

基本的な正規表現

簡単な物から見ていきましょう。まず、自然数を表す文字列にマッチする正規表現はどうなるでしょうか。/[0-9]+/だと001等も入ってしまいますね。つまり、最初の文字は[1-9]で、2文字目以降は[0-9]になります。0を忘れずに加えると、/[1-9][0-9]*|0/となります。

しかし、これでもまだ不十分です。なぜかというと、"001"の最初の1文字だけにマッチしてしまうのです。今までの物をグループ化した上で、文字列先頭にマッチする¥A、文字列末尾にマッチする¥zを加えた、/¥A([1-9][0-9]*|0)¥z/が正解です。

数値をカンマで区切る

大きな数値を表記する際は、しばしば3桁おきにカンマで区切ることがあります。原始的に書くならば以下のような感じでしょうか。

str = "1000000"
ary = []
n = 0; new = []
str.split(//).reverse.each do |x|
  new.push(x)
  new.push(',') if (n += 1) % 3 == 0
end
p new.reverse.join #=> "1,000,000"

しかし、これだと少し大がかりすぎます。正規表現を使ってみると、例えば以下のようになります。数字の後に3の倍数個数字が末尾まで続いている場合、間にカンマを入れるという仕組みです。(?: ... )は「キャプチャしない括弧」と言ってマッチした内容を後から参照できるようにしません。

str = "1000000"
1 while str.gsub!(/([0-9])((?:[0-9]{3})+)¥z/, '¥1,¥2')
p str #=> "1,000,000"

先読み

さて、本来正規表現には量化・連接・選言の3つの演算しかないのですが、ツールとしての利便性を追求した結果、最近の実装ではその枠を超えた機能が追加されています。その1つが先読み(?= ... )と否定先読み(?! ... )で、これはEcmaScript 3rd Editionの正規表現にも含まれているのでなかなか使える機能です。これを用いると今までのは、1行で書けるようになってしまいます。

p "1000000".gsub(/([0-9])(?=(?:[0-9]{3})+¥z)/, '¥1,')
#=> "1,000,000"

戻り読み

ここまでできてしまうと、置換文字列に残った¥1が気になってくるのではないでしょうか。Ruby 1.9やJRuby、IronRubyには戻り読み(?<= ... )が実装されており、これを用いると置換文字列の¥1もなくすことができます。

# Ruby 1.9やJRuby、IronRuby等限定
p "1000000".gsub(/(?<=[0-9])(?=(?:[0-9]{3})+¥z)/, ',')
#=> "1,000,000"

Quoted string

もう1つ、二重引用符でくくられた文字列について考えてみましょう。CやRuby等で用いられる"hoge"というやつです。すぐに思いつくのは/¥A"[^"]*"¥z/ではないでしょうか。しかし、これは"hoge¥"fuga"といったエスケープされた引用符に対応できません。これに対応するには、[^"]を[^"¥¥]に変え、エスケープを特別扱いする必要があります。つまり、/¥A"([^"¥¥]|¥¥.)*"¥z/これが1つの正解です。

/¥A"[^"]*"¥z/ =~ '"hoge"'           #=> 0
/¥A"[^"]*"¥z/ =~ '"ho¥"ge"'         #=> nil
/¥A"(?:¥¥.|[^"¥¥])*"¥z/ =~ '"ho¥"ge"' #=> 0

指数関数的発散

ここで前述の正規表現をstrfriendで視覚化してみましょう。¥Aと¥zに対応していないのはご愛敬として、引用符内では1文字ごとに(?:[^"¥¥]|¥¥.)の分岐を行っていることがわかります。分岐にコストがかかるのは正規表現エンジンでも同じで、可能ならば減らした方がよいでしょう。

かといって、/¥A"(?:¥¥.|[^"¥¥]+)*"¥z/としてしまうと問題があります。この正規表現はマッチする際にはすぐに終わるのですが、マッチしなかった場合に著しく時間がかかります。これは多くの正規表現エンジンが用いているNFA型のエンジンで用いられている、バックトラック法に起因する問題です[6]⁠。

# 注意: 時間のかかる処理です
/¥A"(?:¥¥.|[^"¥¥]+)*"¥z/ =~ '"aaaaaaaaaaaaaaaaaaaaaaaa'

ループ展開

この問題の対処法については詳説正規表現の6.6 ループ展開（第3版ではP.256）が詳しいのでそちらを参照ください。簡単に言えば(A*)*のように二重の繰り返しが存在する場合にこの問題が起きます[7]⁠。これに対処する方法の1つにループ展開という手法があります。ループ展開では選択肢を2つにわけ、A*(BA*)*となるように構成します。この時に以下の3項目を満たすようにします。

AとBの先頭文字が異なる
Bが空文字にマッチしない
B内部ではバックトラックしない（Bがマッチする文字列の部分に、Bはマッチしない）

A、Bどちらを対応させても大丈夫な場合は出現頻度が高い方をAとするとよいでしょう。今回の場合、[^"¥¥]*は3.を満たさないので、Aを¥¥.、Bを[^"¥¥]とします。すると以下のようになり、こちらはすぐに終わります（より複雑なHTMLのコメントの例としてPerlメモ⁠）⁠。

r = /¥A"[^"¥¥]*(¥¥.[^"¥¥]*)*"¥z/
r =~ '"aaaaaaaaaaaaaaaaaaaaaaaa'

正規表現の限界

これまでに述べたとおり、正規表現は一定の規則に沿った文字列を判別するためのツールです。しかし、正規表現で記述可能な規則には限界があります。情報処理の世界では、便利なツールにはたいてい背景に巨大な数学世界が広がっていたりするものですが、正規表現もそうで、これは形式言語理論が控えています。が、そのあたりは正規表現 - Wikipediaからたどったり、計算理論の基礎　[原著第2版]　1．オートマトンと言語を読んだりしてください。

入れ子は正規表現の属する正規文法では表現できず、文脈自由文法である必要があります。また、先に挙げた先読みや戻り読みはこの理論の枠外の機能です。

部分式呼出し

さて、Ruby 1.9で用いられている正規表現エンジン、鬼車には入れ子の表現を可能とする機能が実装されています（JRubyは鬼車のJava実装であるJoniを利用しているため対応している⁠）⁠。それが部分式呼出しで、これを用いると文脈自由文法にマッチさせることが可能になります。

具体的には、例えばカッコの対応が見れるようになります（括弧以外を含む場合はruby-list:42233⁠）⁠。

r = /¥A(?<paren>¥(¥g<paren>*¥))*¥z/
r =~ "()"       #=> 0
r =~ "(()())()" #=> 0
r =~ ")"        #=> nil

JSON

最近Web方面で引っ張りだこの、JSONも文脈自由文法です。このような複雑な正規表現を書く場合は、ヒアドキュメントを用いたり、Regexp::EXTENDEDを用いたりするとよいでしょう。

r = Regexp.compile(<<'__REGEXP__'strip, Regexp::EXTENDED)
(?<json> ¥g<object> | ¥g<array> ){0}
(?<begin-array>  ¥g<ws> ¥[ ¥g<ws> ){0}
(?<begin-object> ¥g<ws> ¥{ ¥g<ws> ){0}
(?<end-array>    ¥g<ws> ¥] ¥g<ws> ){0}
(?<end-object>   ¥g<ws> ¥} ¥g<ws> ){0}
(?<name-separator>  ¥g<ws> : ¥g<ws> ){0}
(?<value-separator> ¥g<ws> , ¥g<ws> ){0}
(?<ws> [¥x20¥t¥n¥r]* ){0}
(?<value>  false | null | true | ¥g<object> | ¥g<array> | ¥g<number> | ¥g<string> ){0}
(?<object> ¥g<begin-object> (?: ¥g<member> (?: ¥g<value-separator> ¥g<member> )* )? ¥g<end-object> ){0}
(?<member> ¥g<string> ¥g<name-separator> ¥g<value> ){0}
(?<array> ¥g<begin-array> (?: ¥g<value> (?: ¥g<value-separator> ¥g<value> )* )? ¥g<end-array> ){0}
(?<number> ¥-? ¥g<int> ¥g<frac>? ¥g<exp>? ){0}
(?<exp> [eE] [-+] [0-9]+ ){0}
(?<frac> ¥. [0-9]+ ){0}
(?<int> 0 | [1-9] [0-9]* ){0}
(?<string> " ¥g<char>* " ){0}
(?<char> [^¥x00-¥x1F"¥¥] | ¥¥ (?: ["¥¥¥/¥b¥f¥n¥r¥t] | u [0-9a-fA-F]{4} ) ){0}
¥A¥g<json>¥z
__REGEXP__
r =~ '{"foo":1,"bar":null,"baz":true}' #=> 0

後方参照

テキスト処理用の正規表現エンジンでは、たいていの場合NFA（Nondeterministic Finite Automaton, 非決定性有限オートマトン）を用いています。もう一つの方式であるDFA（Deterministic Finite Automaton, 決定性有限オートマトン）の方が高速化が可能ですが、この後方参照を実装しづらくなるためにNFAを用いるエンジンが多くなっています[8]⁠。

後方参照を用いると、例えば入れ子のないタグの対応を扱うことができるようになります。後方参照は多くの正規表現エンジンで実装されてます。

r = /¥A(?:<([^>]+)>[^<]*<¥/¥1>)*¥z/

ネストレベル付き後方参照

鬼車にはネストレベル付き後方参照という機能があります。これは部分式呼び出しによる入れ子構造へのマッチを行っている際に用います。このような場合に後方参照を用いようとすると、途中の入れ子の内側にあるキャプチャグループのために、目当てのキャプチャグループを参照できない場合があります。このような時に、後方参照のあるネストレベルから見た、対象のキャプチャグループのネストレベルを指定することで、目当ての文字列を得ることができます。これを用いると、例えば回文を表す正規表現が書けるようになります。

# http://www.geocities.jp/kosako3/oniguruma/doc/RE.ja.txt より
p /¥A(?<a>|.|(?:(?<b>.)¥g<a>¥k<b+0>))¥z/.match("reer")

XML

XML整形式もJSONと同じく文脈自由文法ですが、タグの対応のチェックが必要になる分、JSONよりも若干複雑になります。このような場合はレベル付き後方参照機能を用いることで対応できます。属性のない簡単なXML断片にマッチする正規表現は例えば以下のようになります。

r = Regexp.compile(<<'__REGEXP__'strip, Regexp::EXTENDED)
(?<element> ¥g<stag> ¥g<content>* ¥g<etag> ){0}
(?<stag> < ¥g<name> ¥s* > ){0}
(?<name> [a-zA-Z_:]+ ){0}
(?<content> [^<&]+ (¥g<element> | [^<&]+)* ){0}
(?<etag> </ ¥k<name+1> >){0}
¥A¥g<element>¥z
__REGEXP__

まとめ

今日のテキスト処理には欠かせない正規表現も、Ruby 1.9では鬼車を取り込んだことによって大幅に機能強化がなされました。これらの機能を使いこなせれば、きっと正規表現の新たな地平線を見ることができるでしょう。

もっとも、場合によってはtreetopやracc等も検討した方がよいかもしれません。正規表現は用法用量を守って正しくお使いください。