.NET Frameworkの正規表現で括弧の対応をとる方法 #PowerShell

正規表現の実装の中には括弧の対応をとることができるものがある。Ruby（鬼雲）など再帰による方法は馴染みやすかったものの、.NET Frameworkの方法がよく分からなかったので整理した。

本記事のコードはPowerShellで動作するので、ターミナルを開いて手軽に試してほしい。

PS C:\Users\User> $PSVersionTable

Name                           Value
----                           -----
PSVersion                      5.1.17134.228
PSEdition                      Desktop
PSCompatibleVersions           {1.0, 2.0, 3.0, 4.0...}
BuildVersion                   10.0.17134.228
CLRVersion                     4.0.30319.42000
WSManStackVersion              3.0
PSRemotingProtocolVersion      2.3
SerializationVersion           1.1.0.1

概要

.NET Frameworkの正規表現で括弧の対応をとるには、グループ定義の均等化と呼ばれる機能を利用し、キャプチャをスタックのように扱う。最後にスタックが空になったことを確認するのにコツがいる。

記事中に登場する機能一覧

正規表現中で特別な意味を持つ記法がいくつか出てくるためまとめておく。選択・量指定子・文字クラスは省略。

アンカー: 文字列の特定の位置（文字の境界）を表す。\A は文字列の先頭、\z は文字列の末尾にマッチする。
名前付き部分式と名前付き前方参照¹: (?'name'expression) と \k'name'²。正規表現の一部を普通に丸括弧で囲むと、そこにマッチした文字列がキャプチャされ後で参照できる。括弧に名前を付けておけば、参照する際に番号よりも分かりやすくなる。
グループ定義の均等化: (?'-name'expression) または (?'name1-name2'expression)²。これは例の中で改めて説明する。
非キャプチャグループ: (?:expression)。キャプチャが不要で単に正規表現の優先順位を操作したい場合に用いる。
条件一致: (?(condition)exp_yes|exp_no)。指定した条件が成り立つ場合・成り立たない場合でパターンを切り替える。成り立たない場合のほうは、省略すると無条件で成功扱いになる。condition にキャプチャグループの番号か名前を指定すると、それがキャプチャされているかどうかで場合分けする。
否定先読み: (?!expression)。指定のパターンが文字列の先に続いていなければマッチする。
特に (?!) は「何にもマッチしない」という意味を表す。これに関しては否定先読みを使わなくても、文字列としてあり得ないパターン（文頭の前に文字がある .\A など）を書いてもいい。

括弧の対応

文字列全体で見て括弧が矛盾なく使われていることを確認する。具体的には以下の2点が必要。

開き括弧と閉じ括弧の数が等しい
文字列の途中で閉じ括弧の方が多くならない

なお ()[]{} は正規表現内でエスケープが必要なため、括弧には <> を用いる。

簡略化した例

まずは括弧だけの文字列に対処できる正規表現を示す。

$regex = [regex] "\A(?:(?'open'<)+(?'-open'>)+)*\z(?(open)(?!))"
$str = "<><<><<>>>"
$regex.Match($str).Groups

Groups   : {0, open}
Success  : True
Name     : 0
Captures : {0}
Index    : 0
Length   : 10
Value    : <><<><<>>>

Success  : False
Name     : open
Captures : {}
Index    : 0
Length   : 0
Value    :

この正規表現は、括弧の対応がとれている文字列が必ず \A(?:<+>+)*\z という正規表現にマッチすることから発展させている。見比べて複雑になっている部分が「括弧が矛盾なく使われていること」の検査となる。

括弧の対応を検査しない場合: \A(?:        < +         > +)*\z
括弧の対応を検査する場合:   \A(?:(?'open'<)+(?'-open'>)+)*\z(?(open)(?!))

(?'open'<) は普通の名前付き部分式。その後ろに + があるので、連続する "<" をひとつずつキャプチャする。.NETの場合は同じ名前でキャプチャしても上書きせず全て記憶する。

(?'-open'>) は名前付き部分式に似ているが、名前の前にハイフンがある。これはマッチするとキャプチャするのではなく、事前に記憶したものを新しい方から手放していく。つまり上の例は open というキャプチャがスタックの役割になる。この機能はグループ定義の均等化（balancing group definitions）と呼ばれている。もしスタックが空ならマッチが失敗するので、閉じ括弧が途中で多くなる文字列は弾かれる。

\A(?:(?'open'<)+(?'-open'>)+)*\z がマッチすると文字列の最後まで読み終わり、必ず開き括弧の数は閉じ括弧の数以上になる。これでは括弧が閉じきっていない可能性があるので、最後にスタックが空であることを確認する必要がある。それが末尾の正規表現 (?(open)(?!)) で³、「もし open がキャプチャされていたら問答無用でバックトラックする」という意味になる。複数の文法を組み合わせた表現であるものの、グループ定義の均等化を使うなら慣用表現として覚えてしまえばいい。

対応区間のキャプチャ

前の例では open でキャプチャしたものを捨てていただけだが、ハイフンの前に別の名前を書くことで対応区間（"<" ">" で囲まれた部分文字列）をキャプチャできる。

$regex = [regex] "\A(?:(?'open'<)+(?'close-open'>)+)*\z(?(open)(?!))"
$str = "<><<><<>>>"
$regex.Match($str).Groups
$regex.Match($str).Groups["close"].Captures

Groups   : {0, open, close}
Success  : True
Name     : 0
Captures : {0}
Index    : 0
Length   : 10
Value    : <><<><<>>>

Success  : False
Name     : open
Captures : {}
Index    : 0
Length   : 0
Value    :

Success  : True
Name     : close
Captures : {, , , <>...}
Index    : 3
Length   : 6
Value    : <><<>>


Index Length Value
----- ------ -----
    1      0
    4      0
    7      0
    6      2 <>
    3      6 <><<>>

普通のキャプチャと異なり、指定したパターンにマッチした部分（ここでは ">"）をキャプチャするわけではない。正規表現を見て何がキャプチャされるか推測するのは非常に難しい。

括弧以外の文字もある場合

MSDNのドキュメントの例とほぼ同じもの。括弧に続く別の文字を一緒に読み進めている。

$regex = [regex] "\A[^<>]*(?:(?:(?'open'<)[^<>]*)+(?:(?'close-open'>)[^<>]*)+)*\z(?(open)(?!))"
$str = "abc<def>ghi<jkl<mno>>pqr"
$regex.Match($str).Groups
$regex.Match($str).Groups["close"].Captures

Groups   : {0, open, close}
Success  : True
Name     : 0
Captures : {0}
Index    : 0
Length   : 24
Value    : abc<def>ghi<jkl<mno>>pqr

Success  : False
Name     : open
Captures : {}
Index    : 0
Length   : 0
Value    :

Success  : True
Name     : close
Captures : {def, mno, close}
Index    : 12
Length   : 8
Value    : jkl<mno>


Index Length Value
----- ------ -----
    4      3 def
   16      3 mno
   12      8 jkl<mno>

別の正規表現として、1文字ずつ読み込みその種類で処理を分ける方法も考えられる。このほうが簡潔で理解しやすいかもしれない。

$regex = [regex] "\A(?:(?'open'<)|(?'close-open'>)|[^<>])*\z(?(open)(?!))"
$str = "abc<def>ghi<jkl<mno>>pqr"
$regex.Match($str).Groups
$regex.Match($str).Groups["close"].Captures

その他の例

単純な括弧の対応以外にも応用してみる。キャプチャをスタックのように扱うことを意識すればいい。

XMLタグの対応

単純なものであれば、前節のものとほぼ同じ構造の正規表現で表せる。開始タグにマッチした際にその名前を別途スタックに保存しておき、期待する終了タグは前方参照で作成する。

$regex = [regex] "\A(?:(?'open'<(?'name'\w+)>)|(?'close-open'</(?'-name'\k'name')>)|\w)*\z(?(open)(?!))"
$str = "<p>aaa<em>bbb</em>ccc</p>"
$regex.Match($str).Groups
$regex.Match($str).Groups["close"].Captures

Groups   : {0, open, name, close}
Success  : True
Name     : 0
Captures : {0}
Index    : 0
Length   : 25
Value    : <p>aaa<em>bbb</em>ccc</p>

Success  : False
Name     : open
Captures : {}
Index    : 0
Length   : 0
Value    :

Success  : False
Name     : name
Captures : {}
Index    : 0
Length   : 0
Value    :

Success  : True
Name     : close
Captures : {bbb, close}
Index    : 3
Length   : 18
Value    : aaa<em>bbb</em>ccc


Index Length Value
----- ------ -----
   10      3 bbb
    3     18 aaa<em>bbb</em>ccc

回文

タグの対応より簡単。前半は1文字ずつスタックに保存し、後半はそれを取り出しながらマッチを試す。

$regex = [regex] "\A(?'char'.)*.?(?'-char'\k'char')*\z(?(char)(?!))"
$str = "abcdcba"
$regex.Match($str).Groups

Groups   : {0, char}
Success  : True
Name     : 0
Captures : {0}
Index    : 0
Length   : 7
Value    : abcdcba

Success  : False
Name     : char
Captures : {}
Index    : 0
Length   : 0
Value    :

文字数の比較

入れ子構造として捉える必要がないので、再帰による方法よりも正規表現を作りやすいと思う。例えば $a^n b^n c^n$（$n \ge 1$）という形⁴の文字列にマッチする正規表現は以下の通り。

$regex = [regex] "\A(?'an'a)+(?'bn-an'b)+(?'-bn'c)+\z(?(an)(?!))(?(bn)(?!))"
$str = "aaabbbccc"
$regex.Match($str).Groups

Groups   : {0, an, bn}
Success  : True
Name     : 0
Captures : {0}
Index    : 0
Length   : 9
Value    : aaabbbccc

Success  : False
Name     : an
Captures : {}
Index    : 0
Length   : 0
Value    :

Success  : False
Name     : bn
Captures : {}
Index    : 0
Length   : 0
Value    :

「最短最左」マッチ

こちらの記事に興味を持ち挑戦した。通常の正規表現は文字列中で最も左からマッチするものを優先して拾うが、そうではなく最も短くマッチするものを拾えるか？という話。簡単な例であれば前節の文字数の比較を応用していけた。

$str = "<em>あ<em>い<strong>う</strong>え</em>お<em>か</em>き</em>"   # emタグに囲まれた最短は "<em>か</em>"

$regex = [regex] "<em>(?'char'.)*?</em>"
$regex.Match($str).Value   #=> <em>あ<em>い<strong>う</strong>え</em>

$regex = [regex] "<em>(?'char'(?!<em>|</em>).)*</em>"
$regex.Match($str).Value   #=> <em>い<strong>う</strong>え</em>

$regex = [regex] "<em>(?'char'(?!<em>|</em>).)*</em>(?!.*<em>(?'-char'(?!<em>|</em>).)*</em>(?(char)|(?!)))"
$regex.Match($str).Value   #=> <em>か</em>

単純な最短マッチは、タグがネストしていることにすら気付かない
否定先読みでネストを除外したが、最左のルールによって長い文字列にマッチしてしまう
後半に否定先読みを追加し、「より短くマッチする文字列は後ろに存在しない」ことを確認する
1. 前半でタグ内の文字を1文字ずつスタックに積んである
2. 後半では別のタグ内の文字にマッチしたらスタックから降ろしていく
3. もしスタックに文字が残れば、前半のほうが長いとわかる

参考

Microsoft Developer Network (MSDN) ドキュメント

.NET Framework の正規表現
- 正規表現でのグループ化構成体

言語によって「前方参照」だったり「後方参照」だったりするが、「backreference」の訳し方の違いなだけで同じ機能を表す。 ↩
シングルクォートでなく山括弧を使用することもできる。本記事では山括弧を通常の文字として多用するので、区別しやすいようにシングルクォートを用いる。 ↩
\z との順序は交換可能。どちらも文字列の位置にマッチするだけで読み進めないため。 ↩
文脈自由文法では表せないが、Parsing Expression Grammarでは表せる。再帰が使える正規表現では、先読みと合わせれば表せるはず（→Rubyでの例）。 ↩