左・右再帰と Wirth VM

一個以上の項目をコンマで区切った単純なリストを、 左再帰と右再帰のそれぞれで Yacc 風に記述してみましょう。 話を単純化するため、 item の FIRST 集合はコンマを含まず、 item の FOLLOW 集合と fold_left および foldright の FOLLOW 集合には重なりがないものとします。

/*  "a,b,c" => [seq, [seq, 'a', 'b'], 'c'] */
fold_left : fold_left ',' item  { [seq, $1, $3]; }
          | item                { $1; }
          ;

/*  "a,b,c" => [seq, 'a', [seq, 'b', 'c']] */
foldright : item ',' foldright  { [seq, $1, $3]; }
          | item                { $1; }
          ;

両方ともに LL(1) 文法で書き直すことができます。 どちらの場合でも、 構文を書き直したものを使うため、 生成規則の構文木と欲しい抽象構文木が一致しなくなります。 PEG のように左辺記号で構文木を作るやりかたでは対応できません。 そこで、 相続属性・合成属性としてスタックを使うことにします。 属性文法をあからさまに記入するとうるさくなるので、 属性は暗黙のまま生成規則に渡して戻すものとします。 さらに入力記号をスタックにプッシュし続けていくものとします。 ブレースで囲んだ合成式で、 スタックの末尾から指定個数をポップして、 データ構造を作ってスタックにプッシュすることにします。 こうすることで、 LR オートマトンの reduce 動作の真似が可能になります。 ところで、 LL(1) 文法では、 FIRST 集合と FOLLOW 集合によってどの生成規則を摘要するのかが決定します。 この性質があるので、 LL(1) 文法の構文から LR 遷移表を生成すると、 必ず GOTO 遷移先が 1 つに限定されます。 これが、 スタックから記号を指定個数ポップするだけで良い理由です。

fold_left : item { $1 = pop(1); $1; } foldleft1 ;
foldleft1 : ',' item { $1, $2, $3 = pop(3); [seq, $1, $3]; } foldleft1 | ε ;

foldright : item { $1 = pop(1); $1; } foldrigh1 ;
foldrigh1 : ',' item foldrigh1 { $1, $2, $3 = pop(3); [seq, $1, $3]; } | ε ;

これを、 Wirth VM で動かしてみます。 これまでの終端記号命令 TERMINAL を SHIFT 命令に、 非終端記号命令 NONTERMINAL は APPL 命令に名称を変更します。 APPL 命令は記号ではなく番地を使って、 継続を作ってから番地へジャンプします。 EMPTY 命令はそのままで、 さらに REDUCE 命令を追加します。 命令は 3 オペランド形式です。 suc は一致中の飛び先番地、 alt は不一致中の飛び先番地です。 番地ゼロは特殊な意味をもち、 命令ポインタがゼロになると継続摘要をします。 REDUCE 命令の pop 数は、 スタックの末尾から取り除く個数、 合成ラベルは実装依存ですが、 ここでは取り除いた個数の先頭にラベルをつけたタプルにしてスタックの末尾にプッシュするという簡易動作を考えておきます。 REDUCE 命令は EMPTY 命令と同様に状態を一致状態にします。 今回は使いませんが、 空規則の際のスタック上の記号数を揃える目的で、 EMPTY 命令の第三オペランドには記号を指定できるようにして、 空規則のための記号をスタックへプッシュできるようにしておきます。

           shift     suc,   alt, 終端記号
           appl      suc,   alt, 番地
           empty     suc,     0, (ゼロまたは記号)
           reduce    suc, pop数, 合成ラベル

通常、 コンマ等の区切り記号を合成結果に残すことはないので、 合成の単純化のため、 VM にはあらかじめ shift 命令でスタックへのプッシュを除外する記号を指定できるものとしておきます。 foldright は生成規則から直訳した再帰呼び出しのままの記述です。 fold_left は末尾再帰なのでループにしています。 コンマ記号をシフト対象から除外したので、 REDUCE 命令でスタックからポップする個数が 2 個へ変わります。

vm = WirthVM.new
vm.exclude = {:COMMA => true}
label = {:fold_left => 1, :foldright => 6, :item => 12}
def insn(addr, opcode, x, y, z) WirthVM::Instruction.new(opcode, x, y, z) end
vm.program = [
  insn( 0, :trap,    0,  0, 0),
#fold_left:
  insn( 1, :appl,    2,  0, label[:item]),
  insn( 2, :shift,   3,  5, :COMMA),
  insn( 3, :appl,    4,  0, label[:item]),
  insn( 4, :reduce,  2,     2,:seq),
  insn( 5, :empty,   0,  0, 0),
#foldright:
  insn( 6, :appl,    7,  0, label[:item]),
  insn( 7, :shift,   8, 11, :COMMA),
  insn( 8, :appl,    9,  0, label[:item]),
  insn( 9, :appl,   10,  0, 7),
  insn(10, :reduce,  0,     2,:seq),
  insn(11, :empty,   0,  0, 0),
#item:
  insn(12, :shift,   0,  0, :IDENT),
]
p vm.advance(label[:fold_left], [
  [:IDENT,'a'], [:COMMA], [:IDENT,'b'], [:COMMA], [:IDENT,'c'], [:RPAREN], [:EOF]
], 0).matched #=> [:seq, [:seq, [:IDENT, "a"], [:IDENT, "b"]], [:IDENT, "c"]]
p vm.advance(label[:foldright], [
  [:IDENT,'a'], [:COMMA], [:IDENT,'b'], [:COMMA], [:IDENT,'c'], [:RPAREN], [:EOF]
], 0).matched #=> [:seq, [:IDENT, "a"], [:seq, [:IDENT, "b"], [:IDENT, "c"]]]

VM は Packrat 版を元にしています。 LL(1) 文法用としてメモライズ機構を除去し、 バックトラックによる環境戻しを簡易版にしています。 さらに、 継続とスタックを Array オブジェクトにプッシュ・ポップする方式に変更しました。

class WirthVM
  class Instruction
    attr_accessor :opcode, :x, :y, :z
    def initialize(f, a, b, c) @opcode, @x, @y, @z = f, a, b, c end
  end

  attr_accessor :exclude, :program

  def initialize()
    @program = []
    @exclude = {}
    @exp = nil
    @matched_ques = false
  end

  def matched?() @matched_ques end
  def matched() @exp end

  def advance(ip, input, tp)
    @matched_ques = matched_ques = false
    kont, exp = [], []
    while ip > 0 || ! kont.empty?
      insn = @program[ip > 0 ? ip : kont[-1]]
      x, y = insn.x, insn.y
      case insn.opcode
      when :shift
        matched_ques = (insn.z == input[tp][0])
        if matched_ques
          @exclude.member?(insn.z) or exp << input[tp]
          tp += 1
        end
      when :reduce
        e = exp.slice!(exp.size - y ... exp.size)
        e.unshift insn.z if insn.z
        exp.push e
        matched_ques = true
      when :empty
        exp.push insn.z if Symbol === insn.z
        matched_ques = true
      when :appl
        if ip > 0
          kont.push(kont, exp.size, tp, ip)
          x = y = insn.z
        elsif matched_ques
          kont, _, _, ip = kont.pop(4)
        else
          kont, ep, tp, ip = kont.pop(4)
          exp[ep ... exp.size] = []
        end
      else
        raise "instruction error #{ip} #{insn.opcode}"
      end
      ip = matched_ques ? x : y
    end
    @exp = matched_ques ? exp[0] : nil
    @matched_ques = matched_ques
    self
  end
end