はじめに
正規表現が文字列にマッチするかどうかを判定するプログラムを作るにあたっては、以前の記事で紹介したようにVMを用いたり、または正規表現と等価なオートマトンを用いたりする。この記事ではこれらとは別の方法として「正規表現の微分（regular expression derivative）」を用いた方法について説明し、さらにこの方法を使うことで今までの方法では触れていなかった、正規表現のある一部にマッチした文字列を抽出するサブマッチングについても紹介する。 また、この記事で紹介するコードは次のGitHubリポジトリから入手できる。
正規表現の抽象構文木
まずは、正規表現の抽象構文木を表す代数的データ型を次のように定義する。
sealed trait Regex
object Regex {
case class Var(n: String, r: Regex) extends Regex
case class Let(l: Char) extends Regex
case class Alt(r1: Regex, r2: Regex) extends Regex
case class Star(r: Regex) extends Regex
case class Con(r1: Regex, r2: Regex) extends Regex
case object Epsilon extends Regex
case object Empty extends Regex
}一般的な定義と概ね同じだが、いくつか違うところもある。まず、サブマッチングに用いる変数を表すVarというコンストラクタが追加されている。これはString型で表した変数名とRegex型の正規表現を受け取り、与えられた変数名でサブパターンマッチを参照できるようにする。例えば、Star(Var("x", Let('a')))という正規表現に文字列aaaをマッチさせると、変数xにはaが代入される。 また、EpsilonとEmptyというよく似たようなオブジェクトがあるが、これらは次のような意味になる。
Epsilon- 空の文字にのみマッチする正規表現
Empty- どんな文字にもマッチしない正規表現
文字列から正規表現の抽象構文木を作るパーザー
これは以前、@kmizuさんに紹介していただいた正規表現のパーザーを改造したが、ここでは文字列で表現された正規表現を先ほど定義した代数的データ型の表現へ変換することは、この記事の本質的な目標ではないのでリンクを紹介して例を挙げるのみとする。
https://github.com/y-yu/PosixRegex/blob/master/src/main/scala/RegexParser.scala
これを用いると、例えば次のような文字列で表した正規表現が次のような抽象構文木に変換される。
| 文字列で表現された正規表現 | 抽象構文木で表現された正規表現 |
|---|---|
| $(a \mid b)*$ | Star(Alt(Let(a),Let(b))) |
| $(a \mid b \mid c)*d$ | Con(Star(Alt(Alt(Let(a),Let(b)),Let(c))),Let(d)) |
| $(x:a*)b$ | Con(Var(x,Star(Let(a))),Let(b)) |
正規表現の微分
正規表現の微分とは、まずw:cwという文字列があるとする。この文字列w:cwは文字cが文字列の先頭の一文字で、cwは文字列の先頭以外の残りを表す。ここで、もしある正規表現$r$が文字列w:cwにマッチするならば、正規表現$r$を文字cで微分した正規表現$r_c$は文字列wcにマッチする。このような正規表現$r_c$を見つける操作を正規表現の微分と言うことにする。 まず、正規表現を微分する関数を定義する前に、次のような補助関数canEmptyを定義する。
object Helper {
def canEmpty(r: Regex): Boolean = r match {
case Epsilon => true
case Let(_) => false
case Alt(r1, r2) => canEmpty(r1) || canEmpty(r2)
case Con(r1, r2) => canEmpty(r1) && canEmpty(r2)
case Star(r) => true
case Empty => false
case Var(_, r) => canEmpty(r)
}
}この関数は、与えられた正規表現が空の文字列を受理するならばtrueを返し、そうでなければfalseを返すという関数である。 この関数を用いて、微分する関数derivativeは次のようなインターフェースを持つ。
object Derivative {
def derivative(r: Regex, l: Char): Regex
}正規表現rと文字cを受け取って、微分された正規表現を返す関数である。それではderivativeの具体的な実装をいくつか場合分けしながら考えていく。
簡単なものについて
次のケースについては直感的に決まる。
def derivative(r: Regex, l: Char): Regex = r match {
case Empty => Empty
case Epsilon => Empty
case Let(c) => if (c == l) Epsilon else Empty
case Var(_, r) => derivative(r, l)
}Varはいわば正規表現に名前を付けているだけなので、中身の正規表現に対して微分を行う。
正規表現の“選択”について
正規表現の選択を表す$r_1 \mid r_2$の場合について考える。これは直感的に、正規表現$r_1$と$r_2$を微分してそれの選択を取ればよいので次のようになる。
def derivative(r: Regex, l: Char): Regex = r match {
case Alt(r1, r2) => Alt(derivative(r1, l), derivative(r2, l))
}正規表現の“連結”について
この場合はやや複雑だが、先ほど定義したcanEmptyを用いて次のようになる。
def derivative(r: Regex, l: Char): Regex = r match {
case Con(r1, r2) =>
if (Helper.canEmpty(r1))
Alt(Con(derivative(r1, l), r2), derivative(r2, l))
else
Con(derivative(r1, l), r2)
}まず、連結された正規表現$r_1r_2$について考える。このプログラムの意味は、もし$r_1$が空であったら$r_2$を微分し、そうでなかったら$r_1$を微分するということでこのような定義となる。
正規表現の“繰り返し”について
正規表現$r*$はやや考える必要がある。ナイーブな実装として、正規表現$r* = \epsilon \mid rr*$を元に進めていくと、無限ループが発生してしまうためである。無限ループを回避するために、次のように定義する。
def derivative(r: Regex, l: Char): Regex = r match {
case Star(r) => Con(derivative(r, l), Star(r))
}正規表現と文字列のパーズツリー
さて、正規表現の微分をすることで、正規表現のパーズツリーを作れるようになる。このパーズツリーとは、正規表現とマッチさせる文字列によって構成されるものである。パーズツリーは次の代数的データ型で表現される。
sealed trait ParseTree
object ParseTree {
case object Void extends ParseTree
case object Nil extends ParseTree
case class Lit(l: Char) extends ParseTree
case class Pair(t1: ParseTree, t2: ParseTree) extends ParseTree
case class Left(t: ParseTree) extends ParseTree
case class Right(t: ParseTree) extends ParseTree
case class Cons(t: ParseTree, ts: ParseTree) extends ParseTree
}このままでは表示が大変なので、このパーズツリーを表示するプリティプリンターppを次のように定義する。
object Helper {
def pp(t: ParseTree): String = t match {
case Void => "()"
case Nil => "nil"
case Lit(l) => s"$l"
case Pair(t1, t2) => s"(${pp(t1)}, ${pp(t2)})"
case Left(t) => s"Left(${pp(t)})"
case Right(t) => s"Right(${pp(t)})"
case Cons(v, vs) => s"${pp(v)}: ${pp(vs)}"
}
}例えば正規表現$(a \mid b)*$に文字列abをマッチさせたとすると、次のようなパーズツリーが生成される。
Left(a): Right(b): nilこれは、まず正規表現$(a \mid b)$の選択の左側（Left）にaがマッチし、次に右側（Right）にbがマッチした、ということを示している。文字列と正規表現を使って、このパーズツリーを作るには先ほどの微分を使うことができる。
パーズツリーの生成
まず、先ほど紹介した正規表現の微分は、文字列を一文字ずつ取り出していって、その一文字ずつで正規表現を徐々に削っていくような処理であった。
\[ r_0 \xrightarrow{l_1} r_1 \xrightarrow{l_2} r_2 \xrightarrow{l_3} \cdots \xrightarrow{l_n} r_n \]パーズツリーはまず正規表現の微分を繰り返して、最終的な正規表現のパーズツリーを生成し、そこから一文字ずつ木に対して文字を挿入していくことでパーズツリーを組み立てる。
\[ v_0 \xleftarrow{l_1} v_1 \xleftarrow{l_2} v_2 \xleftarrow{l_3} \cdots \xleftarrow{l_n} v_n \]まずは、この上の図で表現するところの$v_n$に対応するパーズツリーを得る関数makeEpsを次のように定義する。
object Parse {
private def makeEps(r: Regex): ParseTree = r match {
case Star(_) => ParseTree.Nil
case Con(r1, r2) => Pair(makeEps(r1), makeEps(r2))
case Alt(r1, r2) =>
if (Helper.canEmpty(r1))
Left(makeEps(r1))
else if (Helper.canEmpty(r2))
Right(makeEps(r2))
else
throw new RuntimeException("error of he alternation in makeEps")
case Epsilon => Void
case e => throw new RuntimeException(s"error in makeEps: $e")
}
}この関数makeEpsは与えられた正規表現$r$が空を受理するならば、最初のパーズツリーを返す関数である。なぜ正規表現$r$が空を受理すると仮定しているかというと、先ほど述べたようにこのmakeEpsは微分を繰り返して文字列が尽きた時の正規表現が入力される。もし入力が尽きた時の正規表現が空を受理しないならば、正規表現のマッチングに失敗していると言えるので、パーズツリーを作ることができない。従ってこのような仮定をしている。
次に、このようにして得られた最初のパーズツリーに一文字ずつ文字を挿入していく関数injectを次のように定義する。
object Parse {
private def inject(r: Regex, l: Char, t: ParseTree): ParseTree = (r, t) match {
case (Var(_, r), t) => inject(r, l, t)
case (Star(r), Pair(v, vs)) => Cons(inject(r, l, v), vs)
case (Con(r1, r2), t) => t match {
case Pair(v1, v2) => Pair(inject(r1, l, v1), v2)
case Left(Pair(v1, v2)) => Pair(inject(r1, l, v1), v2)
case Right(v2) => Pair(makeEps(r1), inject(r2, l, v2))
case e => throw new RuntimeException(s"error of the concatenation in inject: $e")
}
case (Alt(r1, r2), t) => t match {
case Left(v1) => Left(inject(r1, l, v1))
case Right(v2) => Right(inject(r2, l, v2))
case e => throw new RuntimeException(s"error of the alternation in inject: $e")
}
case (Let(c), Void) => if (l == c) Lit(l) else throw new RuntimeException(s"error of the Letter in inject")
case e => throw new RuntimeException(s"error in inject: $e")
}
}これの説明はやや複雑なので、詳細を知りたい場合は参考文献1を参考にして欲しい。
これを用いて、最終的にパーズツリーを生成する関数parseを次のように定義する。
object Parse {
def parse(r: Regex, str: Word): Try[ParseTree] =
str match {
case Nil if Helper.canEmpty(r) => Try(makeEps(r))
case l::w => parse(Derivative.derivative(r, l), w).map(t => inject(r, l, t))
case e => Try(throw new RuntimeException(s"error in parse: $e"))
}
}サブマッチング
パーズツリーと正規表現から次のような関数submatchを用いてサブマッチングを行うことができる。
object Submatch {
type Word = List[Char]
private def flatten(t: ParseTree): Word = t match {
case Void | Nil => List()
case Left(v) => flatten(v)
case Right(v) => flatten(v)
case Cons(v, vs) => flatten(v) ++ flatten(vs)
case Pair(v1, v2) => flatten(v1) ++ flatten(v2)
case Lit(l) => List(l)
}
def submatch(t: ParseTree, r: Regex): Set[Map[String, Word]] = (t, r) match {
case (Void, Epsilon) => Set.empty
case (Lit(l), Let(c)) => if (l == c) Set.empty else throw new RuntimeException("error in submatch")
case (Nil, Star(_)) => Set.empty
case (Cons(v, vs), Star(r)) => submatch(v, r) ++ submatch(vs, Star(r))
case (Pair(v1, v2), Con(r1, r2)) => submatch(v1, r1) ++ submatch(v2, r2)
case (Left(v), Alt(r1, _)) => submatch(v, r1)
case (Right(v), Alt(_, r2)) => submatch(v, r2)
case (v, Var(n, r)) => Set(Map(n -> flatten(v))) ++ submatch(v, r)
case e => throw new RuntimeException(s"error in submatch: $e")
}
}まず、flattenはパーズツリーを文字列だけにする関数である。これを使って、正規表現の中に変数Varがある場合はそれに対応するパーズツリーをflattenしたものを追加するということをしている。 最後に、正規表現とマッチする文字列をコマンドライン引数から取れるようにして完成である。
object Main {
def main(args: Array[String]): Unit = {
val regex = RegexParser.parse(args(0))
println(regex)
val tree = regex.flatMap(Parse.parse(_, args(1).toCharArray.toList))
println(tree.map(Helper.pp))
for {
r <- regex
t <- tree
} yield println(Submatch.submatch(t, r))
}
}これを用いて、正規表現$((x:a*) \mid (b \mid c)*)*$に文字列abaaccをマッチさせると次のような結果となる。
Success(Star(Alt(Var(x,Star(Let(a))),Star(Alt(Let(b),Let(c))))))
Success(Left(a: nil): Right(Left(b): nil): Left(a: a: nil): Right(Right(c): Right(c): nil): nil)
Set(Map(x -> List(a)), Map(x -> List(a, a)))一番上が文字列から抽象構文木へ変換した正規表現であり、二番目がパーズツリー、そして一番下がサブマッチングである。
まとめ
正直、論文の全部を理解したわけではないが、ひとまずサブマッチングを搭載した正規表現のマッチングプログラムを書くことができた。論文ではさらに性能を向上させるためのテクニックが紹介されていたが、今回の記事ではナイーブな実装のみを紹介することにした。オートマトンやVMを使わずに正規表現のマッチングプログラムを書くことができて、よい経験となったと思う。
コメント
コメントを投稿