正規表現からのコンパイル

ここでは、正規表現からVMの命令列への変換 (コンパイル) を実装します。そして、公開するAPIを整理して、正規表現エンジンとしての実装を完成させます。

正規表現のコンパイル

正規表現からVMの命令列への変換は、正規表現の抽象構文木を再帰的に辿っていくことで行います。

それぞれの抽象構文木の型について、次のようにしてコンパイルしていきます。

`Literal[value]`

char命令に対応しているので、[:char, value]にコンパイルします。

`Concat[children]`

childrenを順番にコンパイルしていきます。

`Choice[children]`

children = [child1, child2]のように2要素の場合で考えます。このとき、次のようにコンパイルします。

+--------o [:push, (*1)]
|          ... child1のコンパイル結果 ...
| +------o [:jump, (*2)]
+-|-> (*1) ... child2のコンパイル結果 ...
  +-> (*2) ... 続くコンパイル結果 ...

childrenが3要素以上ある場合も同様に、最後の要素以外にはpush命令とjump命令を配置するようにします。

`Repetition[child, :star]`

次のようにコンパイルします。

+-o +-> (*2) [:push, (*1)]
|   |        ... childのコンパイル結果 ...
|   +------o [:jump, (*2)]
+-----> (*1) ... 続くコンパイル結果 ...

`Repetition[child, :plus]`

次のようにコンパイルします。 :starと比べてpush命令の位置が変わっているだけです。

+---> (*2) ... childのコンパイル結果 ...
| +------o [:push, (*1)]
+-|------o [:jump, (*2)]
  +-> (*1) ... 続くコンパイル結果 ...

`Repetition[child, :question]`

次のようにコンパイルします。 :starのコンパイル結果からjump命令が無くなったもので、単純になっています。

+------o [:push, (*1)]
|        ... childのコンパイル結果 ...
+-> (*1) ... 続くコンパイル結果 ...

コンパイルの実装

それでは、これらのコンパイルを実装します。

実装はKantanRegex::Compilerクラスで行います。このクラスはコンパイルの度に生成されて、コンパイル中のprogramを管理します。

class KantanRegex::Compiler
  def initialize
    @program = []
  end

  attr_reader :program

  # 命令を`program`に追加するメソッド。
  # `insn`はinstructionの略。
  # 返り値は追加した命令の`program`上のインデックス。
  def insn(*insn)
    index = @program.size
    @program << insn
    index
  end

  def compile_root(tree)
    compile(tree)
    insn :match
  end

  private def compile(tree)
    case tree
    in KantanRegex::Literal[value]
      insn :char, value
    in KantanRegex::Repetition[child, :star]
      push_index = insn(:push, nil) # まだジャンプ先が分からないのでひとまず`nil`を入れている
      compile child
      insn :jump, push_index
      @program[push_index][1] = @program.size
    in KantanRegex::Repetition[child, :plus]
      start_index = @program.size
      compile child
      insn :push, @program.size + 2
      insn :jump, start_index
    in KantanRegex::Repetition[child, :question]
      push_index = insn(:push, nil) # まだジャンプ先が分からないのでひとまず`nil`を入れている
      compile child
      @program[push_index][1] = @program.size
    in KantanRegex::Choice[children]
      jump_indices = []
      children.each_with_index do |child, i|
        is_last = i == children.size - 1
        unless is_last
          push_index = insn(:push, nil) # まだジャンプ先が分からないのでひとまず`nil`を入れている
        end
        compile child
        unless is_last
          jump_index = insn(:jump, nil) # まだジャンプ先が分からないのでひとまず`nil`を入れている
          jump_indices << jump_index
          @program[push_index][1] = @program.size
        end
      end
      jump_indices.each do |jump_index|
        @program[jump_index][1] = @program.size
      end
    in KantanRegex::Concat[children]
      children.each { compile _1 }
    end
  end

  def self.compile(tree)
    compiler = KantanRegex::Compiler.new
    compiler.compile_root(tree)
    compiler.program
  end
end

insnという命令を追加するメソッドや、コンパイルの起点となるcompile_rootメソッドを持っています。

実際に抽象構文木を辿るのはcompileメソッドで、このメソッドのcase ... inで先ほど説明したコンパイルの方法を実装しています。 Choiceの場合がやや複雑ですが、注意深く処理を追えば何をやっているのか理解できると思います。

公開APIの実装

最後に、公開APIであるKantanRegexクラスとKantanRegex#matchメソッドを実装します。これは、ここまで実装してきたものを使えば簡単に実装できます。

require_relative './ast.rb'
require_relative './parser.rb'
require_relative './backtrack_vm.rb'
require_relative './compiler.rb'

class KantanRegex
  def initialize(pattern)
    @program = Compiler.compile(Parser.parse(pattern))
  end

  def match(input)
    BacktrackVM.exec(@program, input)
  end
end

これをirbから読み込んで使ってみましょう。

irb(main):001> load './kantan-regex/kantan-regex.rb'
=> true
irb(main):002> KantanRegex.new('(a|ab)c').match('abc')
=> 0...3
irb(main):003> KantanRegex.new('a*ab').match('aaab')
=> 0...4
irb(main):004> KantanRegex.new('a*ab').match('bc')
=> nil

前の章で説明した選択や繰り返しが正しく実装されていないといけない例も、上手く動作しているように見えます。

これにてkantan-regexの実装はひとまず完了となります。おつかれさまでした。

作って学ぶ正規表現エンジン