正規表現技術入門　備忘録（第1章）

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

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

作者: 新屋良磨,鈴木勇介,高田謙
出版社/メーカー: 技術評論社
発売日: 2015/04/14
メディア: 単行本（ソフトカバー）
この商品を含むブログ (1件) を見る

である。上の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を含むこと

を意味する。

マッチングの種類

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

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

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

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

部分一致がデフォルトな状況でのマッチングの種類の明示

マッチングの種類	正規表現
部分一致	regex
完全一致	^regex$
前方一致	^regex
後方一致	regex$

完全一致がデフォルトな状況でのマッチングの種類の明示

マッチングの種類	正規表現
部分一致	regex
完全一致	.regex.
前方一致	regex.*
後方一致	.*regex

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

キャプチャ

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

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

がある。

順番で指定する方法

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

名前で指定する方法

順番で指定する方法は、単純な一方、正規表現の変更に弱い。そこで、名前付きキャプチャを使う。名前付きキャプチャでは、サブパターンに好きな名前をつけて、その名前経由でサブマッチを取得することができる。PerlやRubyでは(?)という構文でサブパターンに名前をつけることができる。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)」という正規表現は２箇所の「a」にしかマッチしない。先読み部分の正規表現「(?=..a)」はあくまで３文字先にaが来るという位置にマッチするためだ。

再帰

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

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

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

後方参照

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

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

第２章　正規表現の歴史
第３章　プログラマのための一歩進んだ正規表現
第４章　DFA型エンジン
第５章　VM型エンジン
第６章　正規表現エンジンの三大技術動向
第７章　正規表現の落とし穴
第８章　正規表現を超えて

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

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

正規表現とは何か

正規表現の演算