Rob Pike の正規表現仮想マシン

正規表現を非決定性有限オートマトン (NFA) に直訳したまま擬似並列スレッド実行することで文字列とのマッチングをおこなう Rob Pike の仮想マシンがあります。正規表現をマルチスレッド・バイトコードコンパイルして動かす方式は Ken Thompson による先例があり、Rob Pike がグループによるキャプチャをおこなえるように改良しています。Rob Pike 版は Plan9 の sam テキストエディタのために書いたのがオリジナルで、Plan9正規表現ライブラリに採用されています。この正規表現は欲張りマッチングだけで、非欲張りマッチングは使えません。

http://swtch.com/usr/local/plan9/src/libregexp/regexec.c Plan9regexp(3) ライブラリ 欲張りマッチングしかない

それを Russ Cox が非欲張りマッチングも扱えるように改良し、Google RE2 ライブラリで使っています。

Regular Expression Matching: the Virtual Machine Approach 解説と非欲張りマッチングを追加した試み

動作確認のため、Ruby へ書き直してみました。正規表現文字列を仮想コードにコンパイルし、得られたコードを Russ Cox による改良版の Rob Pike 仮想マシンで NFA を並列実行します。

正規表現コンパイラは、正規表現の文字列から抽象構文木を作り、木からコードを作る 2 パス手順にしています。コンパイラ部分を含めた全コードを Gist に置いておきます。

Ruby port from Russ Cox's pikevm in C-language.

仮想マシンの命令コードは1次元配列に並べます。Russ Cox の解説ページのコード例では命令コードを構造体として 1 スロットに 1 命令を配置しているのに対して、Ruby 版では 1 から 3 スロットの可変長命令にしています。さらに、先頭にマジックを追加しています。

code[0] = :regex        # マジック
code[1] = code.size
code[2] = 命令数

# 文字一致
code[pc + 0] = :char
code[pc + 1] = char

# 不特定文字 (.) 一致
code[pc + 0] = :any

# 一致成功
code[pc + 0] = :match

# 無条件ジャンプ
code[pc + 0] = :jmp
code[pc + 1] = ジャンプ先の PC

# 2つのスレッドに分割
code[pc + 0] = :split
code[pc + 1] = 優先度高スレッドの PC
code[pc + 2] = 優先度低スレッドの PC

# 文字ポインタ記録
code[pc + 0] = :save
code[pc + 1] = 記録箇所のオフセット

仮想マシンは、コンパイル済みのコードが、入力文字列の先頭からマッチングするかどうかをチェックし、成功したら配列を、失敗したら nil を返します。配列の要素を 2 つずつペアに使って、$0$1 を取り出すための Range を作ることができます。この Range は3ドットのものです。

code = regexp_compile "a(.*?)c"
matched = regexp_pikevm code, s
p matched
if matched
  p s[matched[0] ... matched[1]]  # $0
  p s[matched[2] ... matched[3]]  # $1
end

擬似並列実行では、split 命令によって擬似スレッドをどんどん生成しつつ、並列実行していきます。スレッドには優先度があり、スレッド・リストの先頭側の方が優先度が高く、末尾側の方が低くなっています。各スレッドは、マッチングに失敗したらそのまま停止してリストから取り除かれます。マッチングに成功したスレッドがあると、それよりも優先度の低いスレッドの実行を停止します。こうすることで、欲張りマッチングと非欲張りマッチングを並列実行で実現しています。

2015 年 9 月 25 日差し替え 以前はプログラムカウンタ進行のマルチスレッドで書いてましたが、 スレッド・キューが無駄に膨らむことがあるため、 Russ Cox のやりかたである文字列ポインタ進行方式に書き直しました。 なお、後者の場合はスレッド・キューが膨らまない代わりに、 再帰呼び出しによりスタックを消費します。

def regexp_pikevm(code, input)
  Pikevm.new(code).execute(input)
end

class Pikevm
  def initialize(code)
    @gen = 1
    @mark = Array.new(code.size) { 0 }
    @code = code
  end

  def execute(input)
    @gen = 1
    @mark.fill { 0 }
    matched = nil
    run = []
    rdy = []
    sp = 0
    addthread(run, 3, sp, [0, 0])
    while not run.empty?
      @gen += 1
      run.each do |pc, saved|
        case @code[pc]
        when :char
          if sp < input.size && input[sp] == @code[pc + 1]
            addthread(rdy, pc + 2, sp + 1, saved)
          end
        when :any
          if sp < input.size
            addthread(rdy, pc + 1, sp + 1, saved)
          end
        when :match
          matched = saved.dup
          matched[1] = sp
          break
        end
      end
      run, rdy = rdy, run
      rdy.clear
      break if sp >= input.size
      sp += 1
    end
    matched
  end

  def addthread(q, pc, sp, saved)
    return if @mark[pc] == @gen
    @mark[pc] = @gen
    case @code[pc]
    when :jmp
      addthread(q, @code[pc + 1], sp, saved)
    when :split
      addthread(q, @code[pc + 1], sp, saved)
      addthread(q, @code[pc + 2], sp, saved)
    when :save
      saved = saved.dup
      saved[@code[pc + 1]] = sp
      addthread(q, pc + 2, sp, saved)
    else
      q.push [pc, saved]
    end
  end
end