正規表現の先後読み，アトミックグループとか

はじめに

先後読み、アトミックグループ、最左最長についてまとめます。 ここでは、mac 環境における GNU grep コマンドを用いて行います。 特に、Perl 拡張を用います

1
2
3
4
5
6
7
8
9

$ grep --version
grep (GNU grep) 3.1
Packaged by Homebrew
Copyright (C) 2017 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Written by Mike Haertel and others, see <http://git.sv.gnu.org/cgit/grep.git/tree/AUTHORS>.

1
2
3
4
5
6
7
8

grep --help
(snip)
Pattern selection and interpretation:
  -E, --extended-regexp     PATTERN is an extended regular expression
  -F, --fixed-strings       PATTERN is a set of newline-separated strings
  -G, --basic-regexp        PATTERN is a basic regular expression (default)
  -P, --perl-regexp         PATTERN is a Perl regular expression
(snip)

先読みと後読み

先読みや後読みは、検索したい文字列に条件を付け加えたいときに使ったりします。 先読みは、対象テキストのまだ評価していない右の方を覗き込んで、部分式がマッチするかどうかを調べます。 一方で、後読みは、読み終えたテキストの左の方を振り返り、マッチするかどうか調べます。
メタ文字として(? )が用いられます。

以下に、先読みと後読みの種類、正規表現と成功条件を示します。 ...は正規表現の部分式になります。

先後読みは、^や$のように位置にマッチします。

• 肯定の先読みの例

1
2

$ echo "ALICE AND ARICE" | grep  -oP '(?=ALICE)A.'
AL

この例では、右に ALICE という文字列がある位置において、A とその次の文字にマッチするという正規表現です。 具体的には、(?=ALICE)によって、右に ALICE がある位置にマッチします。 これは、ALICE の先頭位置です。 そして、その位置から、正規表現のA.がマッチするテキストを取得します。 当然ですが、(?=ALICE)が一致する位置は、右に ALICE がある位置ですので、後続のA.は必ず AL にマッチします。

• 否定の先読みの例

1
2
3

$ echo "ALICE AND ARICE" | grep  -oP '(?!ALICE)A.'
AN
AR

この例では、右に ALICE という文字列がない位置において、A とその次の文字にマッチするという正規表現です。 具体的には、(?!ALICE)は、右に ALICE がない位置にマッチします。 肯定の先読みの例とは異なり、右に ALICE がない位置はたくさんあります。 ここでは、先頭以外のすべてです。 そして、右に ALICE がない位置から、正規表現のA.がマッチするテキストを取得します。 例では、AND の AN と、ARICE の AR がそれに該当します。

• 〜じゃないを条件にするときの注意

〜じゃない場合を条件にする場合、否定の先読みや否定の後読みが使えます。 否定の先読みでは、右が〜じゃない場合、否定の後読みでは、左が〜じゃない場合です。 また、~じゃないを表す方法として、文字クラスの否定[^]があります。 しかし、この２つは表す意味が異なります。 たとえば数字じゃないは、否定文字クラスで\Dですが、正規表現\Dが成功するには「数字じゃない何か」にマッチする必要があります。 一方で、たとえば否定の先読み(?!\D)では、右が数字じゃなければ正規表現が成功します（「数字じゃない何か」がなくてもよい）。

欲張りなマッチ

*、+や?は欲張りなマッチと呼ばれます。 よく.*という形で任意の文字列へのマッチをしますが、欲張りなマッチであることを意識しないと意図しない結果を生みます

以下の例では、ダブルクウォートで囲まれた文字列を取得しますが、マッチする文字列は、“I am human"ではありません。 これは、.*がマッチできる限りマッチし続けるからです。 .*は、I にマッチした後、行最後のピリオドまでマッチを繰り返し、その役割を終えます（テキストの最後まで試行したので）。 そして、正規表現の"とテキストのマッチを試みますが、当然、マッチしません（テキストはすでにピリオドまで進んでいるので）。 そこで、正規表現エンジンはバックトラックと呼ばれる巻き戻しを行い、テキストの位置をピリオドの直前まで巻き戻しを行い、正規表現の"とピリオドを比較します。 ここでは、マッチしないので、さらにバックトラックを行い、テキストの位置を"の直前まで巻き戻し、正規表現の"と比較を行います。結果、マッチが成功するので、結果が例のようになります。

1
2

$ echo 'He said "I am human" and "You are human".' | grep -oP '".*"'
"I am human" and "You are human"

控え目なマッチ

先ほどの例で、“I am human"のみを取得するには、控えめなマッチを使うことで解決できます。 控えめなマッチは、*?、+?、??で表され、なるべくマッチしない試行が行われます。 始めに、正規表現の最初の"がテキストの最初の"とマッチします。
次に、正規表現の最後の"とテキストの I の比較が行われます。
マッチしないため、バックトラックが行われ、正規表現の.と I の比較が行われます。結果マッチします そして、正規表現の最後の"とテキストのスペースの比較が行われます。
マッチしないため、バックトラックが行われ、正規表現の.とスペースの比較が行われます。結果マッチします。

上記を繰り返されると、human の後の"と、正規表現の"がマッチします。

1
2
3

$ echo 'He said "I am human" and "You are human".' | grep -oP '".*?"'
"I am human"
"You are human"

欲張りなマッチは、最長マッチするのに対して、控えめなマッチは最短でマッチします。

ちなみに、上記の例では、否定文字クラスや、先読みを使っても取得できます。

1
2
3
4
5
6

$ echo 'He said "I am human" and "You are human".' | grep -oP '"[^"]*"'
"I am human"
"You are human"
$ echo 'He said "I am human" and "You are human".' | grep -oP '"(?!").*?"'
"I am human"
"You are human"

アトミックグループ

アトミックグループは、ある部分式の評価の結果を手放したくないときに利用します。 例えば、正規表現.*erは、任意の文字列の最後に er が付いたテキストとマッチします。 欲張りなマッチでもあったように*は可能な限りマッチを繰り返し、テキストを消費し尽くします。 その後、er とマッチするまでバックトラックが行われます。 これは、.*が、後続の er のために、マッチしたテキストを手放していると言えます。

1
2

$ echo tennis player | grep -oP '.*er'
tennis player

アトミックグループで指定された部分式でマッチしたテキストは、その後、テキストを手放しません（指定された部分式におけるバックトラックが行われない）。 使用されるメタ文字は(?>)です。 よって以下の例では、マッチが成功しません。 これは、(?>.*)によってテキストの最後まで繰り返しマッチが行われ、その後バックトラックが行われないからです。

1

$ echo tennis player | grep -oP '(?>.*)er'

では、(?>.*)と(?>.*?)という正規表現ではどのように結果が異なるでしょうか？

最左最長

正規表現エンジンの種類によってマッチするテキストが異なることがあります。 エンジンとは、例えば、非決定的な NFA や決定的な DFA、POSIX NFA です。 以下の例では、Perl 拡張を用いた場合と、そうでない場合の結果を示しています。 Perl 拡張では、最初にマッチした正規表現のIで、試行が終了し結果が出力されています。 一方で、普通の grep では、最初にマッチした正規表現のIで終了することなく、最後のI am aまで試行されており、その結果が出力されています。 Perl は NFA エンジンであり、最初の選択肢で成功すると、ほかの選択肢を試しません。 一方で、DFA エンジンである grep は、そもそもの試行方法が NFA とは異なるため、すべての選択肢を試行します。 POSIX NFA は、NFA とは異なり、ほかの選択肢も試すため、最後の選択肢（最長のもの）にマッチします。 しかし、NFA 比べると、最長となるほかの可能性まで試行するため、比較回数が増え、実行時間も遅くなります。

DFA および POSIX NFA は、マッチするものが左から始まる最も長いものになるので最左最長マッチと呼ばれます。

1
2
3
4

$ echo 'He said "I am human" and "You are human".' | grep -oP '(I|I am|I am human)'
I
$ echo 'He said "I am human" and "You are human".' | grep -o '\(I\|I am\|I am human\)'
I am human