正規言語でもコンパイルがしたい！(1): コンパイルの理論

概要

正規表現のコンパイルの方法はあまり知られていません。そのため、自分の学習も兼ねて説明します。何回かに分けて、様々なトピックについて詳しく説明していきます。

1. コンパイルの理論
2. 各言語・ライブラリーにおけるコンパイル処理の実装
3. 自分でコンパイル処理を実装する (予定)

対象読者

正規表現を触ったことはあり、基本的な概念 (*, ?, +, 部分マッチ など) は知っているが、内部で何が起きているかを詳しくは知らない人向けです。

はじめに: コンパイルって何?

正規表現によるマッチングを行う際には、以下の作業を行う必要があります。
(1) 正規表現をパース (構文解析) して、コンピューターが処理しやすい形に変換する。
(2) (1) で変換した結果できたものを使って、文字列に対してマッチング処理を行う。

ここでは、このうち (1) をコンパイルと呼びます。コンパイル処理は以下の理由で、パターンに対してあらかじめ 1 回だけ行っておくのが良いとされています。

1. コンパイル処理には時間がかかる
2. 単にパースを行うだけでなく、様々な前処理をして、文字列へのマッチングが高速にできるようにすることができる

ここでは 2. が重要です。

コンパイル先色々

コンパイルする先として様々なものが考えられます。
以降 $L$ はマッチされる (パターンではない方の) 文字列の長さとします。
また $n$ は文脈によって、正規表現の長さやコンパイル先のオブジェクトの大きさなどとします。(使われるときには明示します。)

オートマトン

コンピューター科学の教科書でよく見るのはこの方法。
以下のような状態遷移図の上で、初期状態 (矢印が書いてある頂点) から終了状態 (二重丸がついている頂点) へ、与えられた文字列について、その文字と同じラベルのついた辺を順番に (うまく) 辿っていくことで到達できればその文字列はマッチした扱い (受理) になり、そうでなければマッチしなかった扱い (拒絶) になります。

例えば、以下のような状態遷移図 (NFA (non-deterministic finite automaton) と呼ばれます) は、正規表現 a(ab)*c?a? に対応し、この正規表現にマッチする文字列を全て受理し、それ以外の文字列を拒絶します。(初期状態 S0, 終了状態 S1, S3, S4)
例えば、文字列 aaba は正規表現 a(ab)*c?a? にマッチしますが、この文字列に対して NFA の状態遷移を見ます。

1. 状態 S0 から開始する。
2. 最初の文字 a を読み、状態 S1 に遷移する。
3. 次の文字 a を読み、状態 S2 に遷移する。a というラベルがついた辺は S1 -> S4 にもあるが、ここでは S2 の方を選択する。
4. 次の文字 b を読み、状態 S1 に遷移する。
5. 最後の文字 a を読み、状態 S4 に遷移する。状態 S4 は終了状態の一つであるため、文字列 aaba は受理された。

また、文字列を読まずに遷移することを許した特殊な遷移 (ε-遷移) を含めたオートマトンも考えることができます。こういったオートマトンは ε-NFA と呼ばれます。例えば、以下の ε-NFA は同様に正規表現 a(ab)*c?a? に対応し、この正規表現にマッチする文字列を全て、およびそれらに限り受理します。

再び文字列 aaba を例として、この文字列に対して ε-NFA の状態遷移を見ます。

1. 状態 S0 から開始する。
2. 最初の文字 a を読み、状態 S1 に遷移する。
3. 次の文字 a を読み、状態 S2 に遷移する。
4. 次の文字 b を読み、状態 S1 に遷移する。
5. 文字を読まずに ε というラベルの遷移を行い、状態 S3 に遷移する。
6. 最後の文字 a を読み、状態 S4 に遷移する。状態 S4 は終了状態の一つであるため、文字列 aaba は受理された。

また、各状態から各文字についてちょうど 1 個の遷移が存在するようなオートマトンを考えることもできます。このようなオートマトンは DFA (deterministic finite automaton) と呼ばれます。DFA においては、与える文字列を決めれば遷移が完全に決まるため、特に何も考えなくても高速に ($O(n + L)$ 時間で) 受理判定ができます。
例えば、以下の DFA は同様に正規表現 a(ab)*c?a? に対応し、この正規表現にマッチする文字列を全て、およびそれらに限り受理します。各状態から a, b, c の各文字に対応する矢印がちょうど 1 本出ていることに注意してください。 (複数文字がカンマで繋がっている矢印は、それぞれの文字の矢印が重なったものとみなします。)

これら 3 種類のオートマトンの表現能力は同じであることが知られています。どれか一つで表現可能な文字列の集合は、残りのオートマトンでも表現可能です。計算量は以下の通りです。($n$ はオートマトンの状態数)

オートマトンの種類	受理判定の時間計算量	受理判定の空間計算量
NFA	$O(nL)$	$O(n)$
ε-NFA	$O(nL)$	$O(n)$
DFA	$O(n+L)$	$O(n)$

この表だけ見ると DFA の効率が一番良さそうですが、同じ正規言語に対応する NFA, ε-NFA, DFA の大きさを比べると、一般には DFA の大きさは NFA, ε-NFA の大きさに関して指数関数的に増大します (つまり、 NFA, ε-NFA が $n$ 状態で実現できる正規言語は、DFA だと実現するために $2^n$ 状態程度必要になり得ます。）

VM

正規表現を命令 (instruction) の列に変換し、命令列を実行することでマッチングの判定を行う方式です。https://swtch.com/~rsc/regexp/regexp2.html で詳しく解説されています。

通常の CPU と同じく、以下の 4 種類の命令を先頭から順番に実行していきます。

• 命令ポインター (instruction pointer): 初期値は 0 です。
• 文字列ポインター: 初期値は文字列の先頭位置です。

1. char $c$: 今見ている文字が $c$ であればなにもせず、命令ポインターと文字列ポインターを 1 進める。そうでなければ文字列を拒絶する。
2. match: もう文字が残っていなければ受理する。そうでなければ拒絶する。¹
3. jmp $x$: 命令ポインターを $x$ に移動させる。
4. split $x,y$: 命令ポインターを $x$ に移動させた後の処理を実行する。同時に、命令ポインターを $y$ に移動させた後の処理を並列に実行する。これら二つのスレッドのどちらかが文字列を受理すれば全体も受理する。

例を挙げて説明します。正規表現 a(ab)*c?a? に対応するのは以下のような命令列です:

compiled.vm

0: char a
1: split 2, 5
2: char a
3: char b
4: jmp 1
5: split 6, 7
6: char c
7: split 8, 9
8: char a
9: match

文字列 aaba はこの正規表現にマッチします。この文字列をこの VM に与えると、以下のように実行されます。ただし、以下で ip は命令ポインターを、sp は文字列ポインターを表します。

1. 命令 0 を実行する。現在見ている文字は a であるため、次の命令に進む。(実行後: ip = 1, sp = 1)
2. 命令 1 を実行する。今回は 2 へジャンプする。5 へのジャンプも並列に行われるが、今回は関係ないので無視する。(実行後: ip = 2, sp = 1)
3. 命令 2 を実行する。現在見ている文字は a であるため、次の命令に進む。(実行後: ip = 3, sp = 2)
4. 命令 3 を実行する。現在見ている文字は b であるため、次の命令に進む。(実行後: ip = 4, sp = 3)
5. 命令 4 を実行する。1 へジャンプする。(実行後: ip = 1, sp = 3)
6. 命令 1 を実行する。今回は 5 へジャンプする。(実行後: ip = 5, sp = 3)
7. 命令 5 を実行する。今回は 7 へジャンプする。(実行後: ip = 7, sp = 3)
8. 命令 7 を実行する。今回は 8 へジャンプする。(実行後: ip = 8, sp = 3)
9. 命令 8 を実行する。現在見ている文字は a であるため、次の命令に進む。(実行後: ip = 9, sp = 4)
10. 命令 9 を実行する。現在見ている位置は文字列の最終位置であるため、文字列を受理する。

VM の命令列による表現能力はオートマトンと等価であることがわかっていますが、特にこの表現方法は ε-NFA と比べて以下の差異があります:

1. ε-NFA は状態とその遷移のペアの集まりですが、VM 方式では状態の代わりに命令や命令ポインターを使用して状態とその遷移を表現します。
2. VM 方式では、部分マッチングを扱うときなど、新しい命令を追加すれば対応できますが、ε-NFA ではそれは難しいです。

バックトラッキング

上の VM の意味論をただの再帰で実装する方式です。小さい例では速いことが知られていますが、パターン長が長くなると指数関数的に実行時間が増えていきます。
https://swtch.com/~rsc/regexp/regexp1.html では a?a?a?...aaa... というパターンを aa... という文字列にマッチさせる例で、パターン長や文字列長に対して指数関数的に実行時間が増えてしまうことが扱われています。

Thompson's VM

文字を一つずつ調べ、その文字まで文字列ポインターが進んでいる状態で、命令ポインターが存在し得る場所を全列挙する方式です。この計算は ε-NFA のような動的計画法²ででき、計算量は、命令の個数を $n$ とすると、$O(nL)$ 時間、$O(n)$ 空間です。

Pike's VM

Thompson's VM とほとんど同じ。ただし、以下の命令を追加することで部分マッチングを扱う機能を備えています。

• save $x$: あらかじめ用意しておいた save 用のスロット $x$ に、現在の文字列ポインターを格納する。

もとの正規表現に部分マッチングが $l$ 個あったとして、$i$ 番目 ($0 \leq i < l$) の部分マッチングの場所を特定するためには、スロット $2i$ の位置に開始位置を、$2i + 1$ の位置に終了位置を覚えさせておくことになります。

状態数は Thompson's VM のときより増えましたが、実装方針はそれほど変わりません。Thompson's VM のシミュレーション時に、過去の部分マッチングの範囲を覚えておけばよいです。同じ状態に複数の方法で到達できる場合も、部分マッチングの開始位置や終了位置はどれか一組を覚えておけば良いため、バックトラッキングと比べて圧倒的に少ないメモリで実行できます。(ip ごとにスロット用に $O(l)$ 空間持っておけば良いため、全体で $O(nl)$ 空間です。)

参考文献

• 正規表現しちへんげ！
  • 正規表現の様々な定義が、直感とともに紹介されています。「しちへんげ」というタイトルですが 17 個もの定義・特徴付けが紹介されています。個人的にはモノイドによる特徴付けと NXA が好みです。
• Implementing Regular Expressions
  • Russ Cox による高速な C++ 用正規表現ライブラリー re2 (https://github.com/google/re2) の解説記事。今回の記事の大部分はこの記事の内容を元にして書かれています。

1. https://swtch.com/~rsc/regexp/regexp2.html の説明では "Stop this thread: it found a match." と書かれています。これは、もとの資料では与えられた文字列のどこかの部分文字列にマッチするか? という問題を扱っているためです。ここでは、オートマトンの紹介で扱った問題と同じにするために、全体にマッチするかどうかだけ考えます。全体にマッチするか部分文字列にマッチするかの違いは重要で、(特に DFA を扱うときに) 取り扱いに手間がかかります。これについては後の記事で扱います。 ↩

2. 文字を与えてどこの状態に行けるか全列挙した後、そこから ε-遷移だけで行ける頂点を全列挙するタイプの動的計画法。どちらも ε-NFA の状態数を $n$ として 1 文字に対し $O(n)$ 時間で可能。 ↩