Packrat 解析器を Wirth VM で (その2)

以前の Ierusalimschy VM 用に作った Parsing Expression Grammar DSL の PEG モジュールを、 Packrat 化 Wirth VM でも利用できるようにします。 PEG モジュールは grammar モジュール関数のブロック中で、 Ruby の式を使って PEG を記述できるようにしてあります。 プラスで seq、 論理和で alt、 角括弧で閉包を指定し、 論理否定で否定先読み、 二重論理否定で先読みを記述します。 非終端記号は id 関数、 終端記号は q 関数か any 関数を使って記述します。 終端記号は文字列、 文字範囲、 もしくは、 文字列と文字範囲の配列を指定します。 PEG モジュールはそのまま修正不要で、 WirthVM でも利用可能です。

vm = WirthVM.new
vm.declare PEG::grammar {
  # S1 <- "a" ("bc" / "bed" / "be") "f"
  id(:S1) <- q("a") + (q("b") + q("c") | q("b") + q("e") + q("d") | q("b") + q("e")) + q("f")
  # S2 <- "a" "bc"? "d"
  id(:S2) <- q("a") + (q("b") + q("c"))['?'] + q("d")
  # S3 <- "a" "bc"* "d"
  id(:S3) <- q("a") + (q("b") + q("c"))['*'] + q("d")
  # S4 <- "a" "bc"+ "d"
  id(:S4) <- q("a") + (q("b") + q("c"))['+'] + q("d")
  # S5 <- "a" &"bc" .. "d"
  id(:S5) <- q("a") + !!(q("b") + q("c")) + any + any + q("d")
  # S6 <- "a" !"bc" .. "d"
  id(:S6) <- q("a") + !(q("b") + q("c")) + any + any + q("d")
}
vm.advance(:S4, "abcbcbcd", 0)
puts '%p %s' % [vm.match?, list_to_string(vm.matched)]

PEG::grammar モジュール関数は、 ブロック中の式を木に変換して配列に並べて返します。 WirthVM の declare メソッドで、 木の配列から命令列を生成していきます。 木のトップの左辺は PEG の非終端記号です。 それを label と rlabel インスタンス変数の記号表に登録し、 右辺から命令列を生成します。

  def declare(grammar)
    @program << Instruction.new(:trap, 0, 0, 0) if @program.empty?
    grammar.each do |decl|
      @label[decl.lhs] = @program.size
      @rlabel[@label[decl.lhs]] = decl.lhs
      generate(decl.rhs)
    end
  end

式の節 (m) は、 PEG の演算子 (fn) ・左辺 (lhs) ・右辺 (rhs) の組になっています。 左辺と右辺をそれぞれ深さ優先で辿っていって、 演算子に基づいて命令列を program インスタンス変数に書き込んでいきます。 split 命令類を書き込むときは、 左辺から命令列を生成した後に split 命令か empty 命令にアドレスの穴埋めをします。 これは、 節に最初に訪れたとき、 左辺から戻ったとき、 右辺から戻ったときで、 それぞれ命令生成が必要になることを意味します。 そのため、 命令生成に継続を使い、 継続の step 欄でどこから節に訪れたのかを区別することにします。 最初に訪れたとき、 step 欄はゼロになり、 左辺から戻ったとき 1、 右辺から戻ったとき 2 にします。 左右の辺から戻ったとき、 さらに top 欄で節の演算子に合わせて生成した命令部分の先頭アドレスを使うことができます。 以上の仕掛けを利用して、 命令生成ループの中で、 節の演算子で場合分けし、 さらに演算子の中で step による場合分けをおこないます。 そして、 それぞれの場合に、 その 1 に書いた変換パターンに沿って命令を生成していきます。

  def generate(m)
    kont = [m, 0, 0, nil]
    while not kont.nil?
      m, step, top, kont = kont
      _0 = @program.size
      _1, _2, _3 = _0 + 1, _0 + 2, _0 + 3
      _4, _5 = _0 + 1, _0
      case m.fn
      when :lit
        @program << Instruction.new(:terminal,    _1,  0,  m.lhs)
      when :any
        @program << Instruction.new(:terminal,    _1,  0,  :any)
      when :id
        @program << Instruction.new(:nonterminal, _1,  0,  m.lhs)
      when :seq
        kont = [m.lhs, 0, 0, [m.rhs, 0, 0, kont]]
      when :alt
        if 0 == step
          kont = [m.lhs, 0, 0, [m, 1, _0, [m.rhs, 0, 0, [m, 2, _0, kont]]]]
          @program << Instruction.new(:split,  0,  0, _1)
        elsif 1 == step
          @program << Instruction.new(:end,    0,  0,  0)
          @program[top].y = _4
        elsif 2 == step
          @program[top].x = _5
        end
      when :and, :not
        if 0 == step
          kont = [m.lhs, 0, 0, [m, 1, _0, kont]]
          opcode = :and == m.fn ? :lookahead : :looknot
          @program << Instruction.new(opcode,  0,  0, _1)
        else
          @program << Instruction.new(:end,    0,  0,  0)
          @program[top].x = _4
        end
      when :ques
        if 0 == step
          kont = [m.lhs, 0, 0, [m, 1, _0, kont]]
          @program << Instruction.new(:split,  0, _1, _2)
          @program << Instruction.new(:empty,  0,  0,  0)
        else
          @program << Instruction.new(:end,    0,  0,  0)
          @program[top].x = _4
          @program[top + 1].x = _4
        end
      when :star
        if 0 == step
          kont = [m.lhs, 0, 0, [m, 1, _0, kont]]
          @program << Instruction.new(:split, _0, _1, _2)
          @program << Instruction.new(:empty,  0,  0,  0)
        else
          @program << Instruction.new(:end,    0,  0,  0)
          @program[top + 1].x = _4
        end
      when :plus
        if 0 == step
          kont = [m.lhs, 0, 0, [m, 1, _0, kont]]
          @program << Instruction.new(:split, _1,  0, _3)
          @program << Instruction.new(:split, _1, _2, _3)
          @program << Instruction.new(:empty,  0,  0,  0)
        else
          @program << Instruction.new(:end,    0,  0,  0)
          @program[top + 2].x = _4
        end
      end
    end
    @program << Instruction.new(:end,    0,  0,  0)
  end