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

ハードウェアエンジニアの備忘録

電子工学(半導体物性)→応用光学・半導体プロセス→アナログ回路→C/C++→C#/.NETと低レイヤーから順調に(?)キャリアを登ってきているハードウェアエンジニアの備忘録。ブログ開始時点でiOSやサーバーサイドはほぼ素人です。IoTがマイブーム。

正規表現技術入門 備忘録(第1章)

業務アプリでオートコンプリートとかその辺りを触っている関係で正規表現技術入門という本を読んでいる。正規表現は全くの未経験なので、まずは深いところはスキップして、基本的なところを抑えていこうと思う。なお、現時点で正規表現の専門的な知識は必要としていないので、第1章だけの備忘録になる。

正規表現技術入門 ――最新エンジン実装と理論的背景 (WEB+DB PRESS plus)

正規表現技術入門 ――最新エンジン実装と理論的背景 (WEB+DB PRESS plus)

正規表現とは何か

正規表現は英語で「regular expression」と言い、一種の表現(ものの書き方)である。 例えば、

0|1|2|3|4|5|6|7|8|9

というのも一種の正規表現で、0から9までの数字という意味を表している。 同様に、

1(0|1|2|3|4|5|6|7|8|9)

と書けば、10から19までの2桁の数字を意味する。このように丸括弧は正規表現を部品ごとに区切るために使われる。

もう少し複雑な例を見てみる。

03-[0-9][0-9][0-9][0-9]-[0-9][0-9][0-9][0-9]

という正規表現は03から始まる電話番号を表している。さらに、数学でx+x+x+xを4xと記述できるように、正規表現[0-9][0-9][0-9][0-9]は[0-9]{4}と短く書くことができる。{4}が4回繰り返すことを示していて、これを量指定子(quantifier)などとよんだりする。よって、上の例は、

03-[0-9]{4}-[0-9]{4}

さらには、

03(-[0-9]{4}){2}

[0-9]は\dとも書けるので最終的には

03(-\d{4}){2}

とかける。

正規表現において、特別な意味を持ったメタ文字と意味を持たないリテラルが存在する。上の例で言うと、[]-\dなどがメタ文字、0や9がリテラルだ。

さて、このような正規表現は実際にはどのように使われているのだろうか。身近なところでは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])?)*$

という正規表現が使われている。

正規表現の演算

正規表現の基本演算は

  • 連接
  • 選択
  • 繰り返し

である。上のHTML5正規表現のように[a-zA-Z0-9]と[a-zA-Z0-9-]{0,61}などとつなげて構成する。このつなげる演算を連接と呼ぶ。連接には特に演算子として特別な記号はない。hatenaという文字はhとaとtと、、を連接し成り立っているが、当たり前なため記号はないということだ。 正規表現A|BはAもしくはBという意味を表す。この|で並べる演算を選択もしくは和と呼ぶ。 次に繰り返しだが、正規表現\dは任意の長さの数字列を表現している。は0回以上、いくらでも繰り返されているパターンを表現する。

演算子の結合順位

四則演算で、掛け算の優先順位が高いように演算子にも順位があり、それは
繰り返し > 連接 > 選択
というものだ。

正規表現シンタックスシュガー

本来、正規表現には上記の3演算だけで事足りるはずだが、3演算だけで書くと複雑になってしまう場合がある。その場合に、簡単に書くための構文が追加されている。それがシンタックスシュガーだ。

プラス演算

+は1回以上の任意回の繰り返しを意味する。ab+cという正規表現があった時、acは該当せず、abcやabbbcなどのように少なくとも1文字以上のbを含んだ文字列を表現する。ab*cという正規表現は0回の繰り返しも含まれ、acという文字列にもマッチする。

疑問符演算

?をパターンの後ろにつけることで、パターンの0回か1回の繰り返しを表す。0回か1回の繰り返しというのは現れるか現れないかとも言い換えられる。例えば、https?://hogehoge.jpはHTTPとHTTPSのどちらもマッチする。s?となっておりあってもなくても良いからだ。

範囲量指定子

演算子{n,m}はn回からm回までの繰り返しを実現する演算子である。例えば、x{1,5}はxの1から5回の繰り返しを表し、x|xx|xxx|xxxx|xxxxxという正規表現と同様の表現になる。x{3,3}のように最小と最大の数字を同じ数字に揃えれば、ピッタリ3回の繰り返しを表現する。この場合、x{3}ともかける。範囲量指定子には{1, 3}のようにスペースを入れたり、{3,1}などと最大最小を逆転した書き方をしてはならない。

ドット

ドットは任意の一文字を表す。たとえばr.*eはrで始まり、eで終わる全部の文字列がマッチする。

文字クラス

0から9までの数字は[0-9]、小文字のみのアルファベットは[a-z]、大文字のみのアルファベットは[A-Z]、大文字も小文字も含むアルファベットは[a-zA-Z]と表す。文字クラスにおける[]の内部では-は範囲指定の記号として特別扱いされる。[a-z]のようにハイフンの前後に表現したい文字範囲の先頭と末尾の文字を記述することで文字範囲を表現する。^は否定を意味する。[^0-9A-Za-z]と書けば、数字やアルファベット以外の文字にマッチする。

エスケープシーケンス

エスケープシーケンスは\を用いて表す。

  • \a … ベル文字
  • \f … 改ページ
  • \t … タブ
  • \n … 改行
  • \r … 復帰
  • \v … 垂直タブ
  • \d … 数字
  • \D … 数字以外
  • \w … 文字列記号
  • \W … 文字列記号以外
  • \s … スペース
  • \S … スペース以外

アンカー

位置を表すアンカーは以下の様なものがある。Sublimeの置換などでもこれは使えるので便利。

  • ^ … 行頭
  • $ … 行末
  • \A … テキスト先頭
  • \b … 文字列の間
  • \B … 文字列の間以外
  • \z … テキスト終端

キャプチャと置換

「文字列がどのようにパターンにマッチするか」という情報を使って文字列を操作するキャプチャと置換を扱う。 キャプチャの前に、正規表現マッチングについており細かい点を解説する。

文字列の部位

文字列には部位がある。接頭辞(prefix)、接尾辞(suffix)、部分文字列(substring)だ。文字列sについて文字列tがsの

  • 接頭辞であるとは、tがsの先頭の文字列であること
  • 接尾辞であるとは、tがsの末尾の文字列であること
  • 部分文字列であるとは、sがtを含むこと

を意味する。

マッチングの種類

正規表現によるマッチングには大きく分けて、以下の4種類がある。

  • 完全一致:正規表現が与えられた文字列の全体にマッチ
  • 前方一致:正規表現が与えられた文字列の接頭辞にマッチ
  • 後方一致:正規表現が与えられた文字列の接尾辞にマッチ
  • 部分一致:正規表現が与えられた文字列の部分文字列にマッチ

例えば、PythonJavaScriptの標準の正規表現では、前方一致にmatch()メソッド、部分一致にsearch()メソッドを提供している。

丸括弧を使って正規表現を部分的に括ることができるが、丸括弧でまとめられた正規表現の一部はサブパターンと呼ぶ。サブパターンにマッチした部分文字列をサブマッチと呼ぶ。

  • 部分一致がデフォルトな状況でのマッチングの種類の明示
マッチングの種類 正規表現
部分一致 regex
完全一致 ^regex$
前方一致 ^regex
後方一致 regex$
  • 完全一致がデフォルトな状況でのマッチングの種類の明示
マッチングの種類 正規表現
部分一致 regex
完全一致 .regex.
前方一致 regex.*
後方一致 .*regex

例えば、(\d+): (\w+) prime.という正規表現には(\d+)と(\w+)の2つのサブパターンが含まれている。この正規表現に対して、57: Grothendieck prime.という文字列はマッチする。このとき、(\d+)に対しては57が、(\w+)にはGrothendieckが部分文字列としてマッチしている。よって、57とGrothendieckはそれぞれ(\d+)と(\w+)に対応するサブマッチとなる。

キャプチャ

正規表現と文字列からサブマッチを抜き出すことをキャプチャという。 正規表現のあるサブパターンに対するサブマッチを取得するためには明示的に、特定のサブパターンに対するサブマッチを指定する必要がある。これには、

  • 順番で指定する方法
  • 名前で指定する方法

がある。

順番で指定する方法

サブパターンには自然な順番というものが存在する。1から順に開き括弧が左側にあるほど小さい番号を付けるという順序付けだ。たとえば、日/月/年を表す正規表現(\d{2})/(\d{2})/(\d{4})には日の2桁が1番、月の2桁が2番、年の4桁に3番という順番がつけられている。

名前で指定する方法

順番で指定する方法は、単純な一方、正規表現の変更に弱い。そこで、名前付きキャプチャを使う。名前付きキャプチャでは、サブパターンに好きな名前をつけて、その名前経由でサブマッチを取得することができる。PerlRubyでは(?)という構文でサブパターンに名前をつけることができる。Perlで書いてみると、

$day = '14/11/1988';
if ($day =~ /(?<d>\d{2})\/(?<m>\d{2}\/(?<y>\d{4})/) {
  print "$+{y} 年 $+{m} 月 $+{d} 日";
#=> 1988年 11 月 14 日

正規表現拡張機能

先読み

先読みとは、「与えられた正規表現がマッチする文字列が直後に来る位置」と正規表現を使って位置を指定することができる機能である。 マッチング対象文字列が「abracadabra」だったとして、「a(?=..a)」はどの部分文字列にマッチし得るのか。実は「a(?=..a)」という正規表現は2箇所の「a」にしかマッチしない。先読み部分の正規表現「(?=..a)」はあくまで3文字先にaが来るという位置にマッチするためだ。

再帰

再帰演算子(?R)は正規表現の全体にマッチする。つまり、

  • A(?R)|B
  • A(A(?R)|B)|B
  • A(A(A(A(A(...)|B)|B)|B)|B)|B
  • A*B

上記再帰表現を展開しているとAが0回以上続いて、Bで終わるというパターンを表現している事がわかる。

後方参照

後方参照とはキャプチャによって取得した部分文字列をその正規表現の中で参照する機能だ。 (.) \1 は任意の文字列をスペースを挟んで2回繰り返した文字列にマッチする正規表現だ。 つまり\1の部分が(.)を参照しており、 (.) (.) と等価に置き換えられる。

以上で、大体の1章の内容になる。2章以降は

といった進み方をするが、今回は一般教養として正規表現を使えるようになるのが目的だったので、一旦閉める。検索エンジンコンパイラプログラミング言語を作りたい方などは第2章以降も役に立つだろう。