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

一歩先 "読む" 正規表現 ~先読みを理解せよ~

分析・アルゴリズム 正規表現

はじめまして、北の双剣エンジニアです。

このブログにおいては、実は相当前の記事に、写真にちょっぴり映り込んでいました。こうして記事を書くのは初になりますね。

Speeeでどんな事をしているかと申しますと、社内システム開発を中心に、ゴリゴリとバックエンドでコードを書いています。その一方で、フロントエンド側でも、Webページ構築・デザインに(一部ながら)関わっていたりと、双剣の名の通り、ハイブリッドなフィールドが最大の武器です。

こんな側面もあり、自分はエンジニア&デザイナ、両方の観点で見れるような、技術知識の橋渡し的な役目でありたいと思います。どうぞよろしくお願い致します。

 

今回取り上げるのは、みんな大好き正規表現です。その中でも、『一見ピンとこない、わかりづらい』けど、マスターするとより記述の幅が広がる、『先読み』を解説していきたいと思います。

正規表現

今更説明する必要もないと思いますが、正規表現は、定義されたパターンに沿った文字列を表現する手法です。

例えば以下のような例。

/^https?:\/\/(([^\.]+)\.)?speee\.jp/

例えばこの正規表現は、弊社 speee.jp の主なWebページのURLにマッチします。サブドメインが存在する場合は、第2グループで参照できます。

正規表現そのものについては、ここでは詳しく説明しません。そういうお話は各言語のリファレンスや入門サイトに譲るとして、本記事では一見では分かりにくい、ちょっと込み入った要素を取り上げてみます。

ちなみに本記事ではJavaScript(ECMAScript 5)でコードを記述しておりますので、特筆しない限り、基本的な正規表現はJSに準拠しています。

間違いだらけの否定の書き方

正規表現の記述に慣れてくると、パターンマッチの中に『 否定条件も入れたい!』と思うことでしょう。

そこで活躍するのは、以下の記述で表現できる否定先読みです。

(?!PATTERN)

でも、『否定』という言葉ばっかりに目が輝いてしまい、『先読み』という言葉をおろそかにしてしまうと、どツボにはまります。以前は私もはまりました…。

例題

シンプルに、こんな例を考えてみます。

さんざん出尽くした例ですが、分かりやすさはピカイチなので、Meには犠牲になってもらいましょう

  • "Windows 8""Windows XP" などと入力された時、Windowsバージョン (8, XP) を取得したい。
  • ただし Windows Me にはマッチしない。

悪い例

var regexp = /^Windows (?!Me|.+)$/i;

regexp.exec("Windows 8.1");     // null
regexp.exec("Windows XP");      // null
regexp.exec("Windows Me");      // null

初心者がやらかしがちな間違い方です。プログラミングで、if文の書き方が染み付いている人によくある例。

『(?!) で"Me"を否定して、それ以外の文字をグループにマッチさせるんでしょ?』ってことで、"?!"を演算子のように使ってしまいたくなる気持ちはわかります。しかしこれはハズレです。

こう書いてしまった場合、Meどころか、どんな文字のバージョンもマッチしなくなってしまいます。 なぜそうなるのか、しっかり「先読み」という概念を理解しておきましょう。

『先を読む』という考え方

もっとシンプルな例題

実際に図解で『先読み』の動きを読み解いてみます。 まずはもっと単純な例から。

/b[aeiou]t/

この正規表現は、 bat, bet, bit, bot, but の各単語にマッチします。2文字目が母音の時にマッチする、というものです。

ではこのマッチを図にしてみます。

正規表現=有限オートマトンなので、本来は状態遷移図も定義されているのですが、ここで理解を目的とするため割愛し、簡略化した図で表現してみます

特に難しいところはありませんね。正規表現に沿って、1文字目が「b」、2文字目が「a,e,i,o,u」のいずれか、3文字目が「t」となれば、マッチとみなされます。

例えば「robot」のように対象文字列が長い文字列なら、照合開始位置を2文字目に移動して再びマッチング、同様に3文字目に移動…と、開始位置を移動して、繰り返し走査していくのが、基本的なパターンマッチの考え方です。

ちなみに、正規表現で与えられたパターンが主導となり、対象文字列に順にマッチングしていくこのエンジンは、『従来型NFA(Nondeterministic Finite Automaton) と呼ばれるエンジンです。Perl, PCRE, JS, PHP, Ruby, .NET, Java...と、ほとんどのプログラミング言語でこのエンジンが採用されています。

テキスト主導型の『DFA(Deterministic Finite Automaton)エンジン (awk, egrepなどが採用) もありますが、先読みが使えるのはNFAのみです。MSDN: 正規表現の動作の詳細 では、.NETでの詳しい実装と共に、その仕組みの詳細が書かれています。

先読みの考え方

では、否定先読みを使って、2文字目が a, i, u の時にマッチさせない』ようにするにはどうすればよいのでしょうか?以下のように書きます。

/b(?![aiu])[aeiou]t/

これが否定先読みの正しい使い方になります。2文字目の文字クラスの前に、否定先読みが入ってきました。

同様に、図にして考えて見ましょう。

2文字目に入る前に、何やら怪しい「!」マークがありますね。ここが先読みの部分です。

先読みの処理が入ると、現在走査している位置はそのままに、 新たな先読みのマッチング[aiu]が同じ位置から始まります。 図で言えば、「!」から続く雲の吹き出しが、『先読み』に該当する部分です。

先読み (?!) の中で進行する正規表現の走査位置は、元々の走査位置とは別のものになります。なので、この例では[aiu]で2文字目を走査し終えたら、元々の走査位置(1文字目終了時点)まで戻ってきます。これが『先読み』の先読みたる所以です。

先読みを行った結果、マッチした場合のみ、元の走査位置から、続く文字クラスのパターンマッチが行われます。マッチしなかった場合は、その時点で走査を打ち切ります。

プログラマ向けに、極端に噛み砕いて言えば、先読み=サブルーチンと解釈しても良いかもしれません。
「この先があるパターンにマッチするかどうか、真偽値を返す"関数"を呼び出して、もしFALSEならbreak」しているようなもの、と考えれば、ある程度分かり易くなるのではないでしょうか?

『否定』先読みとは?

先読みの中では、パターンが [aiu] と定義されています。この図では対象文字列が"bit"、つまり "i" がマッチしているので、先の関数の理解に倣って考えてみると TRUE ですね。

しかし、否定先読みはその結果を『否定』しています。となると、最終結果としては「FALSE」。つまり、先読みパターンにマッチした場合に、元々の走査を打ち切るということになります。

図でもわかる通り、(?![aiu])へのマッチによって、その時点で走査は打ち切られますので、[aeiou]はチェックすらされません。結果的に、"bet""bot" のみが全体のパターンにマッチする、という結果になります。

ちなみに

『肯定』先読みも勿論ありますヨ。

(?=PATTERN)

はじめの例題の正解

さて、先読みの動きを理解したところで、やっとはじめの例題の正解です。以下の通り。

var regexp = /^Windows (?!Me)(.+)$/i;

regexp.exec("Windows 8.1");     // ["Windows 8.1", "8.1"]
regexp.exec("Windows XP");      // ["Windows XP", "XP"]
regexp.exec("Windows Me");      // null

概念をちゃんと理解して見れば、なるほど、と頷けるかと思います。グループもちゃんと、先読みと後方参照で分けてあげましょう。

間違い例の /^Windows (?!Me|.+)$/i 場合は、ORのせいで「.+の時にアンマッチ」という条件になってしまっているため、どんなバージョンを入れてもマッチしなくなった、というカラクリです。

やってTRY

では、より実践的なものにTRYしてみましょう。

問題

  • Windowsのローカルファイルのパスが与えられた時に、そのファイルがあるフォルダのパスを抜き出す正規表現を書け。
  • ただし、セキュリティ確保のため、そのファイルのフォルダがドライブルートおよび、Windowsフォルダ以下の場合は、マッチに失敗するものとする。
    • [OK] C:\Program Files\iTunes\iTunes.exe
    • [OK] C:\Users\SoukenEngineer\Documents\Program.c
    • [NG] C:\
    • [NG] C:\Windows\System32\regedit.exe

回答例

まずは、パスを抜き出す正規表現を書いてみましょう。

/^(.*\\)/i

なんてことはなく、一番後ろの"\"まで抽出するだけです。*は最長一致なので、一番後ろの"\"まで文字列を取ってきます。

ドライブルートのファイルを除外する

いきなり書いてみます。(?!)の中が先読みです。

/^(?![A-Z]:\\[^\\]*$)(.*\\)/i

こんな感じで書けそうですね。先読みの中で "C:\test.txt" のような 『ドライブレター+文字列内に"\"が1ヶ所しかない文字列』 にマッチした場合は、走査を終了します。

あくまで元々の走査位置は、先頭のまま変わりません。後に続く後方参照グループに、「先読みでマッチした一部の文字列が含まれなかった!」という事態にはなりませんので、ご安心ください。

さらにWindowsフォルダ以下も除外する

/^(?![A-Z]:\\[^\\]*$)(?![A-Z]:\\Windows)(.*\\)/i

先読みが終わっても、元々の走査位置は先頭のままですから、先読みのパターンは並列して書くことができます。

よりコンパクトにするなら以下のように。

/^(?![A-Z]:\\(?:[^\\]*$|Windows))(.*\\)/i

ちょっとややこしくなってきていますが、ドライブルートの除外パターンに、『最初の"\"のパスの後が"Windows"になっている』というパターンを、ORで加えてあげています。

これでWindowsフォルダ以下が勝手に荒らされることはありませんね!!

もっと使える例

先の例は例題的なものでしたが、より現実的に、現場でも使用できる先読みの例をもう1つ挙げてみましょう。

現場で先読みが一番効果を発揮するのは、ズバリ、バリデーションです。今までパターンに起こしにくかった判定を、シンプルに書くことができます。

電話番号バリデーション

一般的に、日本の電話番号をバリデーションする場合は、以下のような記述が基本形です。

/^(\d{2,5})-(\d{1,4})-(\d{4})$/

しかし、この記述ではバリデーションとしては不十分です。このままでは、桁数が不正でも、問答無用で通ってしまいます (03-1-2345 など)。

主に日本の電話番号は10桁〜11桁。これを正しくバリデーションしようとしても、先読みが無いと、こう書かざるを得なくなります。

/^(?:(\d{2})-(\d{4})|(\d{3})-(\d{3})|(\d{4})-(\d{2})|(\d{5})-(\d{1})|(\d{3})-(\d{4}))-(\d{4})$/

これでは記述が冗長ですし、可読性も悪くなってしまいます。

肯定先読みを使用

ここで先読みの出番です。はじめの例に肯定先読みを書き足すだけで、このバリデーションをスマートに実現できます。

/^(?=(?:\d-?){10,11}$)(\d{2,5})-(\d{1,4})-(\d{4})$/

"ハイフンを除き、数字が10〜11桁連続して記述されている" 場合のみ、後ろのバリデーション処理を行う、という動きです。こうすることで、始めに書いたバリデーションの合計桁数を限定できます。

11桁の例を、携帯電話に併せてより厳密に考慮するなら、以下のようになるでしょう。

/^(?=(?:\d-?){10}$|\d{3}-\d{4})(\d{2,5})-(\d{1,4})-(\d{4})$/

先読みの使いどころ、イメージできましたでしょうか?

おわりに

今回は正規表現の中でもとっつきずらい「先読み」をざっくりと噛み砕いてみました。余談になりますが、「先読み」があれば勿論「後読み」もあります((?<=)で肯定、(?<!)で否定)。

後読みは、現時点ではJSではサポートされていないため、今回は取り上げておりませんが、ロジックを理解できれば、後読みもすぐに理解できることでしょう。

「ちょっと正規表現かじってみた」という程度ではなかなかとっつきにくい部分ですが、動きを知っていると応用範囲も広がりますので、積極的に取り入れていきましょう。