VM型の正規表現エンジンを実装する ref: http://qiita.com/yyu/items/84b1a00459408d1a7321

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

file4.txt

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

file9.txt

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

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