LoginSignup
27
29

More than 5 years have passed since last update.

@yyu(吉村 優)in株式会社リクルートマーケティングパートナーズ

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

Last updated at Posted at 2015-05-04

背景

プログラム言語Mokkosuには正規表現のライブラリが存在しない。最近正規表現技術入門という本を読み、正規表現の実装について触れる機会があったので、試しに最小の正規表現エンジンを作ってみることにした。また最近Scalaを勉強中なので、Scalaのコードも併記することにした。

二つの実装

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

  • DFA型
  • VM型

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

正規表現のデータ構造

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

regex.mok
type Regex = 
    Empty
|   Con(Regex, Regex)
|   Alt(Regex, Regex)
|   Star(Regex)
|   Let(Char);
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にて紹介されているものを用いる。
このVMは次のような構成となる。

  • スレッド
  • 二つのレジスタ
    PC
    次に実行するバイトコードの位置
    SP
    マッチを行う文字の位置

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

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

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

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

regex.mok
type VMInst =
    C(Char)
|   J(Int)
|   S(Int, Int)
|   M;
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

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

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

文字（$c$）
char $c$
連接（$e_1 e_2$）
$e_1$の命令列
$e_2$の命令列
選択（$e_1 \mid e_2$）
$\hspace{35px}$split $L_1$ $L_2$
$L_1$ : $e_1$の命令列
$\hspace{35px}$jmp $L_3$
$L_2$ : $e_2$の命令列
$L_3$ :
繰り返し（$e*$）
$L_1$ : split $L_2$ $L_3$
$L_2$ : $e$の命令列
$\hspace{35px}$jmp $L_1$
$L_3$ :

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

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

実装

次のように実装した 1 。

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;
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 をマッチングさせる。

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'];
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について知っている方や、こういうのを思いついたという意見があればコメントなどで連絡してほしい。

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

この実装だと例えば正規表現(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行目2のjmp 0へ進みます。ところが、jmp 0で最初へ戻ると、またsplit 1, 5なので2行目が実行されてしまいます。このまま無限ループへ突入して終わらなくなってしまいます。
これについては色々考えてみましたが、任意の正規表現reについて(re)*と((re)*)*は同じという性質から、((re)*)*を(re)*へ変換する処理を入れて解決することにしました。具体的には次のようなコードになります。

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)
}

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

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

  2. バイトコードは0から始まるので4は5行目のコードとなる。 ↩

27
29
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
27
29