Vimmerに捧げる正規表現の基礎中の基礎

  • Author: MURAOKA Taro
  • Date: 2019/12/01
  • vim
  • regexp

スパルタン正規表現とも言える、基礎から解説する正規表現です。

正規表現はVimに限らずコンピューター上でのテキスト操作において非常に強力です。 しかし学習の難しさも非情で多くのIT技術者、Vimmerが正規表現に苦しんでいるのを幾度となく目の当たりにしています。 ただ正規表現は本当にそんなに難しいのでしょうか。

いいえそんなことはありません。 正規表現は本来とても簡単な原理で学習も容易なのです。 にも関わらず難しいと思われてしまうのは、原理を理解しないまま外見上の機能をそのまま覚えようとするからです。 本記事では正規表現の原理にフォーカスし解説することで、Vimを含む様々な正規表現実装の利用難度を適切にしようという記事です。

本記事は Vim Advent Calendar 2019 の1日目の記事です。

「正規表現」はもともと形式言語という言語学の一分野の研究から生まれました。 言語学というのは言葉を科学的に研究する学問です。 形式言語はその中でも形式的な言語、構文などの定義が明確で曖昧さのない言語を指しています。 正規表現は正規言語という形式言語に分類される言語を表すために考え出されました。

正規言語の特徴を簡単に言うと「決定性有限オートマトンによって受理可能」ということになります。 決定性有限オートマトンは省略してDFAと表記されることがあるので、以下ではDFAと書きましょう。 「DFAによって受理可能」とは「非決定性オートマトンによって受理可能」ともいえます。 非決定性オートマトンも長いですし省略してNFAと表記されますので以下ではNFAと書きましょう。 本来この関係は逆で「NFAならDFA」なのですが、ここでは無視します。

(有限オートマトンについての簡単な説明を補足しておきました)

ところでNFAってVimmerには見覚えあるかもしれません。 :help NFA に書かれている通り、 Vimの新しい正規表現エンジンはNFAエンジンです。 あらゆるNFAはDFAに変換可能です。 故にNFAは正規言語を受理可能といえます。 平たく言えばNFAを使えば正規表現エンジンが作れるよ、 ということで実際にVimはNFAで正規表現エンジンを実装しています。

この「正規言語とはDFAによって受理可能であること」という性質が、 正規表現でどのようなパターンマッチを行えるか、何ができないかを決定しています。 たとえば「無限にネストするカッコの対応を考慮したパターンマッチ」や 「無限にネストするXMLタグを考慮したパターンマッチ」は本来の正規表現では決してできません。 DFAのFの部分の「有限」が無限にネストしうる言語を表現できなくしています。 ちなみに「プッシュダウンオートマトン」を用いれば容易に実現可能です。 オートマトンに無限のスタックを組み合わせた構造で 「有限」という制限を克服しています。

逆に考えれば「定数段までのネストを考慮したパターンマッチ」は DFAでも十分に行えるということになります。 以下に「1から3段の () の組にマッチする正規表現」を示します。 なおこの例の正規表現の中の空白は見やすくするためのものなので無視してください。

  • 1段: ( [^()]* )
  • 2段: ( [^()]* \( ( [^()]* ) [^()]* \)* )
  • 3段: ( [^()]* \( ( [^()]* \( ( [^()]* ) [^()]* \)* ) [^()]* \)* )

1段の正規表現を分解して解説すると次のようになります。

  1. ( で始まり
  2. 間に ( 及び ) 以外の文字を任意個含み = [^()]*
  3. ) で終わる

2段の正規表現を同様に分解して解説すると次のようになります。

  1. ( で始まり
  2. 間に ( 及び ) 以外の文字を任意個含み = [^()]*
  3. 次のパターンを任意個含む(0個の場合もありうる)
    1. ( で始まり
    2. 間に ( 及び ) 以外の文字を任意個含み = [^()]*
    3. ) で終わり
    4. ( 及び ) 以外の文字を任意個含む = [^()]* (2の役割)
  4. ) で終わる

2段の 3-1から3-3 が、1段の 1から3 と同じになってることに気がつくでしょう。 3段も同様に2段の 3-2 の下に 1段の1から3を入れ子にすることで導き出せます。

  1. ( で始まり
  2. 間に ( 及び ) 以外の文字を任意個含み = [^()]*
  3. 次のパターンを任意個含む(0個の場合もありうる)
    1. ( で始まり
    2. 間に ( 及び ) 以外の文字を任意個含み = [^()]*
    3. 次のパターンを任意個含む(0個の場合もありうる)
      1. ( で始まり
      2. 間に ( 及び ) 以外の文字を任意個含み = [^()]*
      3. ) で終わり
      4. ( 及び ) 以外の文字を任意個含む = [^()]* (3-2の役割)
    4. ) で終わり
    5. ( 及び ) 以外の文字を任意個含む = [^()]* (2の役割)
  4. ) で終わる

同様の手順で必要な段数まで導出を繰り返せば 「定数段までのネストを考慮したパターンマッチ」 は正規表現で十分に書けることを示しました。 なおこの導出は試行錯誤で行ったわけではなく、 正規表現のできることを正確に理解し注意深く構築したものです。

大事なのは正規表現のできることを理解するその1点に尽きます。 では正規表現が受理する正規言語の定義とはなんでしょう。 正規言語は形式言語の1つですから厳密な定義があります。 ウィキペディアから引用してみます。

  1. 空の言語 0 は正規言語である。
  2. 空文字列言語 { ε } は正規言語である。
  3. a ∈ Σ である各 a について、それだけを含む単集合言語 { a } は正規言語である。
  4. A と B が正規言語であるとき、A ∪ B（和集合）も A • B（結合）も A*（クリーネ閉包）も正規言語である。
  5. それ以外の Σ 上の言語は正規言語ではない。

一見難しそうですが、示している内容は極めて簡単なので見ていきましょう。

1と2については無視して良いです。プログラムで言うところの停止条件に相当します。 正規言語は再帰的な定義となっているのでその停止条件としてこれらがあります。

5も無視して良いです。パターンにマッチしないテキストは受理しないということを言ってるに過ぎません。

3は見た目より簡単で、 前出の1段ネストの 1や3 に示した「( で始まり」「) で終わる」のような 1文字だけでマッチするものが正規言語だ、と言っています。

4は3つのことを言っています。分解してみましょう。

  1. A と B が正規言語であるとき、A ∪ B（和集合）も正規言語である。
  2. A と B が正規言語であるとき、A • B（結合）も正規言語である。
  3. A が正規言語であるとき、A*（クリーネ閉包）も正規言語である。

1は飛ばして2の結合を見ると、これは前出1段のネストの1から3が順番に評価されることを言っています。 a にマッチする /a/ と b にマッチする /b/ を連結(結合) した /ab/ は、 a と b を連結した文字列 ab にマッチするというだけのことです。

1に戻って和集合ですが、これは前出の例ではやや変則ですが [^()] が和集合に相当します。 [^()] は ( と ) を除く全ての文字の和集合という解釈になります。 a もしくは b にマッチする /a|b/ (very magic相当の記法) を定義しています。 この例では /[ab]/ でも通用しますが、 結合を考慮して /abc|xyz/ のように一般化し | を用いて説明するほうが良いでしょう。

3のクーリネ閉包はなんのことはない * で、直前の正規言語が任意回数(0回以上)マッチするということを示しています。 前出1段のネストの2の [^()]* の * や、2段のネストの2の「次のパターンを任意個含む」が相当します。

これが正規言語のすべてです。拍子抜けするほど簡単だったことでしょう。 逆に本来の正規表現はこれしかできません。 にも関わらずVimやその他のツールの正規表現エンジンは、 この正規言語の定義以上のことができるように見えます。 実際に正規言語以上のことが実装・拡張されている場合もありますが、 どんな文字にでもマッチする . や既出の [] などのように 定義の拡大解釈や表記の省略によって実現されてる部分も少なく有りません。

この正規言語の定義すなわち正規表現でできることと、 それ以外の拡張を見極めることがとても大事なのです(2回目)。 Vimなどのツールで利用可能な正規表現には多くのメタ文字や記法があります。 これらが定義の延長線上にあるものなのか、それ以外なのか見極めましょう(3回目)。

例えばVimにはマッチ開始位置を制御するとても便利な /\zs がありますが、 これは明らかに正規言語の定義の外です。 正規表現エンジンが受理したあとにVimの認識する開始位置をいじっており、 正規言語とはなんら関係がありません。 一方で単語の先頭にマッチする /\< は、 文字と文字の間を仮想的な文字としただけの定義の拡大解釈です。 Vimのマニュアルでは同じ /zero-width に分類される両者ですがその性質は大きく異なります。

Vim以外にも世の中にはいろんなプログラムが正規表現を採用しています。 それぞれのツールがそれぞれのニーズに従い機能の拡張や記法のバリエーションを導入しています。 そのため正規表現は学習するのも活用するのも大変難しく見えてしまいます。 しかしそれらが正規言語の定義内で実現されているのかそれともその埒外かを意識すると、 多くの場合は途端にスッキリ整理されたかのように簡単に見えてきます。

余談: 形式言語 に興味が湧いたら 形式文法 や チョムスキー階層 なども勉強すると良いでしょう。 正規言語にとどまらずプログラミング言語などコンピューターで言語を扱う際の基礎学問となっており 便利な思考ツールとして機能してくれることでしょう。 ちなみにチョムスキー階層に至ってはノーム・チョムスキー大先生が28歳のときに発表しており… もう「ヤバイ」以外の語彙を失ってしまいます。

以上、 本記事は Vim Advent Calendar 2019 の1日目の記事で Vimmerに捧げる正規表現の基礎中の基礎 でした。

補足 2019/12/01 12:20

tennnashi さんによる3行まとめ

https://vim-jp.slack.com/archives/C03C4RC9F/p1575167584318300

/ab/, /a|b/, /a*/ がプリミティブな要素で、それ以外の “正規表現は” プリミティブな要素から導出可能である
導出出来ないものは本来の正規表現ではないがユーザビリティのための拡張
そこを自身で整理出来るようになれば任意のプログラミング言語での正規表現も使いこなせるようになる
みたいな話ですね

ほんとそれ

有限オートマトンとは

有限オートマトン(以下FA)とは日本語でいうと有限状態機械といい、 基本的にできることはたった1つで「入力を受理するか拒否するか」だけです。 「入力」とは特にVimという文脈ではテキストデータに相当します。 「受理するか拒否するか」はマッチするかしないかに相当します。

FAの動作としては内部に状態がありテキストを一文字ずつ入力するたびにその内部状態が遷移(変化)していきます。 全部の入力が終わった際に終了状態になっていれば受理、なっていなければ拒否というシンプルな挙動です。 各状態は入力に対して遷移先の状態が定義されており、 1つの初期状態と0個以上の終了状態が指定されます。

この遷移の定義の方法を変えることでFAの種類がきまります。 遷移の定義方法は数学モデル的には「状態遷移関数」とも言います。 もっともシンプルな「入力文字ごとに遷移先を1つに決定する」を状態遷移関数とすると このFAは決定性オートマトン(DFA)になります。

またこのFAは非常に応用が聞いて、 遷移のたびにスタックを操作することでプッシュダウン・オートマトンになったり、 終了状態をなくして遷移のたびにテキストデータを出力するようにすることで コンバータやコンパイラといった感じの振る舞いをするムーア・マシンとなります。 またFAの状態遷移という概念はコンピューターにおいてロバスト、 バグの少ない設計手法の1つとして広く利用されています。