VM型の正規表現エンジンを実装する

# 背景

プログラム言語[Mokkosu](http://lambdataro.sakura.ne.jp/mokkosu/)には正規表現のライブラリが存在しない。最近[正規表現技術入門](http://www.amazon.co.jp/dp/4774172707)という本を読み、正規表現の実装について触れる機会があったので、試しに最小の正規表現エンジンを作ってみることにした。また最近Scalaを勉強中なので、Scalaのコードも併記することにした。

# 二つの実装

正規表現技術入門によると、正規表現のエンジンは大きく分けて次の二種類に分類される。

- DFA型
- VM型

DFA型とは、正規表現を等価なDFA（決定性オートマトン）に変換してマッチングを行う手法である。また、VM型は正規表現をバイトコードへ変換し、そのバイトコードを実行するVM（バーチャルマシン）にてマッチングを行う手法である。
正規表現をDFAへ変換してマッチングするプログラムは以前書いたことがあったので、今回はVM型で実装を行うことにした。

# 正規表現のデータ構造

正規表現を一般的なメタ文字列を含むテキストから抽象構文木へ変換するのは手間なので、今回は正規表現の抽象構文木をユーザーが入力するものとする。正規表現の抽象構文木は次のデータ構造で表現する。
また、PerlやRubyなどには便利な機能がたくさん正規表現に導入されているが、それは今回扱わず、この実装は**連接**、**選択**、**繰り返し**の三演算だけに絞っている。

```mokkosu:regex.mok
type Regex = 
	Empty
|	Con(Regex, Regex)
|	Alt(Regex, Regex)
|	Star(Regex)
|	Let(Char);
```

```scala:regex.scala
sealed trait Regex
case object Empty extends Regex
case class Con(a: Regex, b: Regex) extends Regex
case class Alt(a: Regex, b: Regex) extends Regex
case class Star(a: Regex) extends Regex
case class Let(c: Char) extends Regex
```

# VM型による実装

VMは[Regular Expression Matching: the Virtual Machine Approach](https://swtch.com/~rsc/regexp/regexp2.html)にて紹介されているものを用いる。
このVMは次のような構成となる。

- スレッド
- 二つのレジスタ
  <dl>
    <dt>PC</dt>
    <dd>次に実行するバイトコードの位置</dd>
    <dt>SP</dt>
    <dd>マッチを行う文字の位置</dd>
  </dl>

## VMの命令とそのデータ構造

今回作成するVMには次のような命令があるものとする。

<dl>
  <dt>char <code>c</code></dt>
  <dd><em>SP</em>が指す文字と<code>c</code>を比較し、一致していれば<em>SP</em>を進め、一致していなければスレッドを終了する</dd>
  <dt>match</dt>
  <dd>マッチの成功</dd>
  <dt>jmp <code>x</code></dt>
  <dd><em>PC</em>を<code>x</code>に変更する</dd>
  <dt>split <code>x</code>, <code>y</code></dt>
  <dd>スレッドを作成し、片方は<em>PC</em>を<code>x</code>とし、もう一方は<em>PC</em>を<code>y</code>とする。<em>SP</em>を両方とも現在のものを用いる</dd>
</dl>

この命令に対応するデータ構造が次のようになる。

```mokkosu:regex.mok
type VMInst =
	C(Char)
|	J(Int)
|	S(Int, Int)
|	M;
```

```scala:regex.scala
sealed trait VMInst
case class C(c: Char) extends VMInst
case class J(x: Int) extends VMInst
case class S(x: Int, y: Int) extends VMInst
case object M extends VMInst
```

## 正規表現からバイトコードへの変換

正規表現の抽象構文木からバイトコード（命令列）への変換は次のように機械的に行える。

<dl>
  <dt>文字（$c$）</dt>
  <dd><em>char</em> $c$</dd>

  <dt>連接（$e_1 e_2$）</dt>
  <dd>$e_1$の命令列<br/>
      $e_2$の命令列</dd>

  <dt>選択（$e_1 \mid e_2$）</dt>
  <dd>$\hspace{35px}$<em>split</em> $L_1$ $L_2$<br/>
      $L_1$ : $e_1$の命令列<br/>
      $\hspace{35px}$<em>jmp</em> $L_3$<br/>
      $L_2$ : $e_2$の命令列<br/>
      $L_3$ :</dd>

  <dt>繰り返し（$e*$）</dt>
  <dd>$L_1$ : <em>split</em> $L_2$ $L_3$<br/>
      $L_2$ : $e$の命令列<br/>
      $\hspace{35px}$<em>jmp</em> $L_1$<br/>
      $L_3$ :</dd>
</dl>

例えば、正規表現`aa*bb*`をバイトコードへ変換すると次のようになる。

```
char a
split 2, 4
char a
jmp 1
char b
split 6, 8
char b
jmp 5
match
```

## 実装

次のように実装した [^1] 。

```mokkosu:regex.mok
fun nth xs n = match (xs, n) {
    (_, n) ? n < 0 -> error "nth";
    ([], _)        -> error "nth";
    (x :: _, 0)    -> x;
    (_ :: xs, n)   -> nth xs (n - 1);
};

let compile re = 
	fun loop re n = match re {
        ~Empty     -> ([], n);
		~Let(l)    -> ([C(l)], n + 1);
        ~Con(a, b) ->
		    let (c1, i1) = loop a n  in
		    let (c2, i2) = loop b i1 in
		    (c1 ++ c2, i2);
		~Alt(a, b) ->
		    let (c1, i1) = loop a (n  + 1) in
		    let (c2, i2) = loop b (i1 + 1) in
			let c = [S(n + 1, i1 + 1)] ++ c1 ++ [J(i2)] ++ c2 in
			(c, i2);
		~Star(a)   ->
			let (c, i) = loop a (n + 1) in
			([S(n + 1, i + 1)] ++ c ++ [J(n)], i + 1);
	}
	in
	let (inst, n) = (loop re 0) in
	inst;

let test c s = 
	fun loop pc sp = match (nth c pc) {
		~C(l)    -> if (nth s sp) <> l -> false
		        	else loop (pc + 1) (sp + 1);
		~M       -> true;
		~J(n)    -> loop n sp;
		~S(x, y) -> if (loop x sp) -> true
					else loop y sp;
	}
	in
	loop 0 0;
```

```scala:regex.scala
object Regex {
  def compile(re: Regex): List[VMInst] = {
    def loop(re: Regex, n: Int): (List[VMInst], Int) = re match {
      case Empty     => (Nil, n)
      case Let(c)    => (List(C(c)), n + 1)
      case Con(a, b) =>
        val (c1, i1) = loop(a, n)
        val (c2, i2) = loop(b, i1)
        (c1 ++ c2, i2)
      case Alt(a, b) =>
        val (c1, i1) = loop(a, n  + 1)
        val (c2, i2) = loop(b, i1 + 1)
        val c = List(S(n + 1, i1 + 1)) ++ c1 ++ List(J(i2)) ++ c2
        (c, i2)
      case Star(a)   =>
        val (c, i) = loop(a, n + 1)
        (List(S(n + 1, i + 1)) ++ c ++ List(J(n)), i + 1)
    }

    loop(re, 0)._1 ++ Array(M)
  }
}

object VMInst {
  def test(c: List[VMInst], s: List[Char]): Boolean = {
    def loop(pc: Int, sp: Int): Boolean = c(pc) match {
      case C(l)    =>
        if (s(sp) != l) false
        else loop(pc + 1, sp + 1)
      case M       => true
      case J(n)    => loop(n, sp)
      case S(x, y) =>
        if (loop(x, sp)) true
        else loop(y, sp)
    }

    loop(0, 0)
  }
}
```

## テスト

次のようなコードでテストを行える。このコードは正規表現`aa*bb*`に文字列 _aabb_ をマッチングさせる。

```mokkosu:regex.mok
let re1 = Con(Con(Let('a'), Star(Let('a'))), Con(Let('b'), Star(Let('b'))));
let c   = compile re1;

let b   = test c ['a', 'a', 'b', 'b', '\0'];
```

```scala:regex.scala
object TestRegex {
  def main(args: Array[String]): Unit = {
    val re1 = Con(Con(Let('a'), Star(Let('a'))), Con(Let('b'), Star(Let('b'))))
    val c   = Regex.compile(re1)

    println(VMInst.test(c, List('a', 'a', 'b', 'b', '\0')))
  }
}
```

# この実装の問題点と今後の課題

この実装はListの$n$番目の要素を取得する`nth`を多用しているのが明らかだと思う。Mokkosuの`nth`の実装を見てもらえば分かると思うが、Listの$n$番目の要素を取得するという操作は$O(n)$なので、多用するべきではない。正規表現技術入門やRegular Expression Matching: the Virtual Machine Approachではこのプログラムとは違い、Listではなく配列を使うことでランダムなアクセスを効率的に行っている。
しかし、配列などを使わず実装できる**Functional**なVMを設計するのが、おもしろい課題であると考えている。Functionalに実装できるVMについて知っている方や、こういうのを思いついたという意見があればコメントなどで連絡してほしい。

[^1]: 正規表現技術入門やRegular Expression Matching: the Virtual Machine ApproachではListではなくArrayを使っていたが、Mokkosuで配列を使う方法が不明だったので今回はListを用いた。このことについては後でも触れる。

# （追記）二重の繰り返しでスタックオーバーフロー

この実装だと例えば正規表現`(a*)*a`など、繰り返しが二重になっている正規表現をコンパイルすると次のようなバイトコードが生成されます。

```
split 1, 5
split 2, 4
char a
jmp 1
jmp 0
char a
match
```

このバイトコードはどのような文字列にマッチさせようとしても、VMがスタックオーバーフローをおこして死んでしまいます。なぜなら、3行目の`char a`で仮に失敗したとします。2行目が`split 2, 4`なので、5行目[^zo]の`jmp 0`へ進みます。ところが、`jmp 0`で最初へ戻ると、また`split 1, 5`なので2行目が実行されてしまいます。このまま無限ループへ突入して終わらなくなってしまいます。
これについては色々考えてみましたが、任意の正規表現`re`について`(re)*`と`((re)*)*`は同じという性質から、`((re)*)*`を`(re)*`へ変換する処理を入れて解決することにしました。具体的には次のようなコードになります。

[^zo]: バイトコードは`0`から始まるので`4`は5行目のコードとなる。

```scala
def compile(re: Regex): List[VMInst] = {
  def loop(re: Regex, n: Int): (List[VMInst], Int) = re match {
    case Empty     => (Nil, n)
    case Let(c)    => (List(C(c)), n + 1)
    case Con(a, b) =>
      val (c1, i1) = loop(a, n)
      val (c2, i2) = loop(b, i1)
      (c1 ++ c2, i2)
    case Alt(a, b) =>
      val (c1, i1) = loop(a, n  + 1)
      val (c2, i2) = loop(b, i1 + 1)
      val c = List(S(n + 1, i1 + 1)) ++ c1 ++ List(J(i2)) ++ c2
      (c, i2)
    case Star(Star(a)) => loop(Star(a), n)
    case Star(a)   =>
      val (c, i) = loop(a, n + 1)
      (List(S(n + 1, i + 1)) ++ c ++ List(J(n)), i + 1)
  }

  loop(re, 0)._1 ++ List(M)
}
```

この方法では不味いという意見や、実こうするのが正しいという意見があればぜひ教えて欲しい。