正規表現技術入門――最新エンジン実装と理論的背景

番外編●特別コラム［知っておきたい］正規表現にまつわる基本Q＆A

プログラミングの世界には実に多くの技術や方法論が溢（あふ）れていますが，その中でも「正規表現」はかなり特別な存在です。文字列のパターンを簡単な式で記述できる正規表現は，文字列処理をはじめ，さまざまな場面で活躍してくれるとても便利な道具です。プログラマの相棒となってから久しい正規表現ですが，多くの人々に知られている一方，正規表現に纏（まつ）わる疑問や間違った知識が多いのも事実です。

本記事では，そんな正規表現に関するよくある疑問やあれこれに，2015年4月発売の『正規表現技術入門――最新エンジン実装と理論的背景』（新屋 良磨/鈴木 勇介/高田 謙著，技術評論社）の著者の一人がQ＆A形式で答えます。

*（アスタリスク）は，「任意の文字列」（ワイルドカード）を表す正規表現？

Q：正規表現って便利ですよね。

rm -rf *

などなど，シェルでのファイル操作で重宝しています。

A：（！）

A：はい，正規表現は便利ですね。だけど，よくある勘違いなのですが，*は「任意の文字列」を表す正規表現ではありません。

Q：ええっ，本当ですか？ でも，良く次のような文章をWeb上で見かけるのですが......。

42は2進法では101010で，ASCIIコードでは*に当たる。正規言語（パターンマッチ）で*の文字は任意（＝万物）の文字列と置き換えられる「ワイルドカード」として用いられることが多いので，*＝「42」が万物の答えなのではないかという説がある。

A：「生命，宇宙，そして万物についての究極の疑問の答え= 42」という有名な小説のネタですね。確かに*はASCIIコード的に言うと「42」番めの記号ですし，正規表現では*は「繰り返し」を表す演算子なのですが，*単体ですべての文字列を表すわけではありません。どうも上の間違った一節はWikipediaの2005年9月11日（日）10:38版の記事から追加されて，それが広まったようです（注1）。

Q：そうなのですね。でも，シェルでrm -rf *を実行すると，実際に「すべてのファイル」を消してくれますよ？これってファイル名をパターンマッチングしているってことじゃないのでしょうか？

A：それはグロブ（glob）と呼ばれるシェル組み込みのパス名を展開するためのプログラムの機能ですね。

昔々UNIX V6では，ワイルドカードパターンを展開する/etc/globと言うプログラムがあった。その後すぐに，この機能はシェルに組み込まれるようになった。

今日では，この機能をユーザプログラムからも実行できるよう，glob（3）というライブラリルーチンも存在している。

Man page of GLOBより。

グロブでは*は「任意の文字列」に?は「任意の1文字」にマッチするのですが，正規表現では.が「任意の1文字」に.*が「任意の1文字の任意回数の繰り返し=任意の文字列」にマッチします。

正規表現とグロブは，どちらも*や?が特別な文字（メタ文字）だったり，どちらも文字クラス[0-9]が使えたり，確かに似ている点が多いのですが，実は正規表現の方がグロブよりもパターンの表現力が高いんです。

注1）

この一節は，2012年1月3日（火）07:32に削除されています。

正規表現でメールアドレスを表現できる？

Q：なるほど，正規表現の方がパターンの表現力が高いのですね。そういえば「正規表現メールアドレス」で検索するといろんなページでメールアドレスを表現する正規表現が紹介されていますし，正規表現はそれほどに表現力が高いということですか？

A： いいえ。正規表現ではメールアドレスを厳密に表現することは不可能です。

Q：えぇ!! 不可能だなんて言い切っちゃうことができるんですか？

A：はい。「RFCによる厳密な文法の定義」ではメールアドレスは再帰的な構文（ネストしたコメント）を含みます。正規表現では再帰的な構文を表現することはできないのです。

Q：なるほど......。あれ？ でも，なぜ正規表現では再帰的な構文は表現でいないんでしょうか。そもそも，「再帰的な構文」って何でしたっけ？

A：それを理解してもらうには，正規表現によるパターンマッチングがどのようにして処理されているかも含め，正規表現のしくみと理論的背景をきちんと解説する必要があります。また，PerlやRubyなどの一部の正規表現では再帰的な構文も表現できる拡張機能を持っていたりするので，「普通の正規表現ではメールアドレスは表現できない」と言うべきかもしれません。この辺りの解説も必要になりますね。

Q：「再帰的な構文」「拡張機能」「普通の正規表現」...うぅ，メールアドレス関連の話題はなかなかに複雑なんですね......。

A：とは言え，「コメントには対応しない，あるいはメールアドレスから事前にコメントを削除する」や「メールアドレスの大まかなバリデーションに使えれば良い」など現実的な妥協策を採用すればメールアドレスを表現する正規表現を（拡張機能を使わずに）シンプルに書くことは十分可能です。

たとえば，「HTML5」からは<input type=email></input>というメールアドレスのバリデーションを行ってくれるインプット要素（図1）を使うことができるのですが，HTML5では次の正規表現をメールアドレスのバリデーションに用いています。

^[a-zA-Z0-9.!#$%&'*+/=?^_`{|}~-]+@[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?(?:\.[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?)*$

メールアドレスに関しては妥当性の怪しい「オレオレ正規表現」がWeb上に大量に転がっている現状です。特別な事情がない限りは，HTML5が用いている上の正規表現のような「出所と方針」がしっかりとした正規表現を使うのが無難でしょう。だいたい，文法的に正しいメールアドレスでも，実際に存在するメールアドレスかどうかなんていうのはそれこそ送ってみないとわからないわけです。必要以上に問題を複雑に捉える必要はありません;-）

正規表現エンジンの実装がいっぱいあるのはなぜ？ 違いはあるの？

Q：なるほど，それを聞いて安心しました。ところで「PerlやRubyなどの一部の正規表現では......」と説明がありましたが，正規表現の機能って処理系によって違うのですか？

A：とても良い点に気づきましたね。はい，違います。正規表現マッチングを行うプログラム（処理系）のことを正規表現エンジンと呼び，大別して

• オートマトンという計算モデルを基本とするDFA型（図2）
• 仮想マシンによるバックトラック処理を基本とするVM型（図3）

の2種類の正規表現エンジンがあります。DFA型かVM型かでサポートしてる機能や性能にも違いが出てきますし，同じタイプの正規表現エンジンでも実装の個性が出てきます。

Q：へぇ，DFA型とVM型かあ，知らなかった。なんか格好良い名前ですね。ところで，DFA型とVM型はどっちが優れているんですか？

A：そこは正規表現ユーザにとって気になるところですよね。でも，DFA型とVM型は目指す方向が異なっているので，一概に「こっちが優れている」と言い切ることはできません。が，大雑把には「性能重視のDFA型」と「機能重視のVM型」と言ったところでしょうか。

Q：ふむふむ。それぞれどんなしくみなのかちょっと興味が湧いてきました。でも，正規表現のユーザが正規表現エンジンの違いやしくみなんて理解する必要はありませんよね？

A：正規表現エンジンのしくみを知らなくても正規表現を使うことはできます。しかし，正規表現エンジンのしくみを知ってると正規表現をより上手に使うことができるんです。正規表現を使ったテキストの抽出（キャプチャ）の細かい部分は，VM型のキモであるバックトラック処理を踏まえないとなかなか理解することができません。それだけでなく，VM型かDFA型かでマッチングの実行時間が大きく変わるなんて場合もあります。また，エンジンのしくみを理解するということは，自然に効率的な正規表現の書き方を理解することにもつながるのです。

［書籍紹介］正規表現技術入門――最新エンジン実装と理論的背景

Q＆Aはいかがでしたか。2015年4月発売の『正規表現技術入門――最新エンジン実装と理論的背景』では，正規表現の基礎から始まり，正規表現の歴史/しくみ/実装/理論などなど幅広い話題を丁寧に解説していきます。正規表現の話題がここまで網羅的に纏められている書籍は，（和書洋書問わず）本書の他にはありません。

正規表現を知らない人やもっと知りたい人へ

「最新エンジン実装と理論的背景」という何だか重そうなサブタイトルですが，本書は正規表現をもっと知りたい人のための入門書です。本書の大きな特徴は，この「正規表現エンジンのしくみと理論的背景」の解説をきちんと行っている点にあります。「正規表現技術入門」では大まかに図4の流れで正規表現の技術を解説していきます。

正規表現エンジンのしくみと理論的背景は「正規表現を上手に使える」ようになるための役に立つ知識となります。「正規表現を既に知っている」という読者でも，正規表現エンジンのしくみや理論背景を踏まえた上での技術解説には得るものが多いのではないでしょうか。

各話題をその道のエキスパートが担当

本書では正規表現の話題を幅広く扱っています。たとえば，本章においては

• 正規表現技術全般やDFA型エンジンの解説は著者新屋（正規表現・オートマトン理論の研究者）
• VM型エンジンの解説は著者高田（Rubyの組み込み正規表現エンジン「鬼雲」開発者）
• JavaScriptの正規表現事情やVMのJIT技術の解説は著者鈴木（WebKitコミッタ/JavaScriptエンジン「iv」開発者）

らが，それぞれ執筆を担当しています（注2）。本書全体を通して，図やコード/例題をふんだんに盛り込み，一貫して初学者のために丁寧でわかりやすい解説を心懸けました。

とくに，VM型エンジンの解説を行う章では，ごくシンプルなVM実装のサンプルから始め，最終的に鬼雲の実際のソースコードを眺めつつ詳細な解説に踏み込んでいきます。鬼雲開発者ならでは章になりますので，興味のある方はチェックしてみてください。

注2）

さらに，正規表現エンジンの実装技術および正規表現の数学的背景，それぞれの先進的な話題について2名の方にご寄稿いただきました。

• 「ビットパラレル手法によるマッチング」 喜田拓也氏（北海道大学）
• 「正規性の魅力 ――正規言語の『より高度な数学的背景』」 浦本武雄氏（京都大学 数理解析研究所）

いずれも，これまでの正規表現の書籍では扱われていない話題となっています。