背景
プログラム言語Mokkosuには正規表現のライブラリが存在しない。最近正規表現技術入門という本を読み、正規表現の実装について触れる機会があったので、試しに最小の正規表現エンジンを作ってみることにした。また最近Scalaを勉強中なので、Scalaのコードも併記することにした。
二つの実装
正規表現技術入門によると、正規表現のエンジンは大きく分けて次の二種類に分類される。
- DFA型
- VM型
DFA型とは、正規表現を等価なDFA（決定性オートマトン）に変換してマッチングを行う手法である。また、VM型は正規表現をバイトコードへ変換し、そのバイトコードを実行するVM（バーチャルマシン）にてマッチングを行う手法である。
正規表現をDFAへ変換してマッチングするプログラムは以前書いたことがあったので、今回はVM型で実装を行うことにした。
正規表現のデータ構造
正規表現を一般的なメタ文字列を含むテキストから抽象構文木へ変換するのは手間なので、今回は正規表現の抽象構文木をユーザーが入力するものとする。正規表現の抽象構文木は次のデータ構造で表現する。
また、PerlやRubyなどには便利な機能がたくさん正規表現に導入されているが、それは今回扱わず、この実装は連接、選択、繰り返しの三演算だけに絞っている。
type Regex =
Empty
| Con(Regex, Regex)
| Alt(Regex, Regex)
| Star(Regex)
| Let(Char);
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を両方とも現在のものを用いる
この命令に対応するデータ構造が次のようになる。
type VMInst =
C(Char)
| J(Int)
| S(Int, Int)
| M;
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 。
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;
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 をマッチングさせる。
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'];
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)
}
この方法では不味いという意見や、実こうするのが正しいという意見があればぜひ教えて欲しい。