Packrat Parsing

Packrat Parsingの論文の最初だけ読んだ。例がHaskellで書いてあっていまいちよく分からない…。遅延評価に慣れてないしなあ。
それでもArithPackrat.hsをなんとか解読してRubyで書き直してみた。
一応ちゃんと動いてるみたいだが、これがPackrat Parsingになってるかはそんなに自信が無い。

ParseResult = Struct.new(:value,:deriv)

class Deriv
  def Deriv.eval(str)
    if pr = Deriv.new(str).parse_add then
      pr.value
    else
      nil
    end
  end

  def initialize(rest_str)
    @add_value  = nil
    @mult_value = nil
    @prim_value = nil
    @dec_value  = nil
    if rest_str.empty? then
      @char_value = nil
    else
      @char_value = ParseResult.new(rest_str[0],Deriv.new(rest_str[1..-1]))
    end
  end

  def parse_add
    return @add_value if @add_value

    pr1 = parse_mult
    if pr1 then
      pr2 = pr1.deriv.parse_char
      if pr2 and pr2.value == ?+ then
        pr3 = pr2.deriv.parse_add
        if pr3 then
          @add_value = ParseResult.new(pr1.value + pr3.value, pr3.deriv)
        end
      end
    end
    @add_value ||= parse_mult

    @add_value
  end

  def parse_mult
    return @mult_value if @mult_value

    pr1 = parse_prim
    if pr1 then
      pr2 = pr1.deriv.parse_char
      if pr2 and pr2.value == ?* then
        pr3 = pr2.deriv.parse_mult
        if pr3 then
          @mult_value = ParseResult.new(pr1.value * pr3.value, pr3.deriv)
        end
      end
    end
    @mult_value ||= parse_prim

    @mult_value
  end

  def parse_prim
    return @prim_value if @prim_value

    pr1 = parse_char
    if pr1 and pr1.value == ?( then
      pr2 = pr1.deriv.parse_add
      if pr2 then
        pr3 = pr2.deriv.parse_char
        if pr3 and pr3.value == ?) then
          @prim_value = ParseResult.new(pr2.value,pr3.deriv)
        end
      end
    end
    @prim_value ||= parse_dec

    @prim_value
  end

  def parse_dec
    return @dec_value if @dec_value
    pr = parse_char
    if pr and (?0..?9).include? pr.value then
      @dec_value = ParseResult.new(pr.value - ?0,pr.deriv)
    end
    @dec_value
  end

  def parse_char
    @char_value
  end
end

def test_expr(expr)
  if Deriv.eval(expr) == eval(expr) then
    puts "ok"
  else
    puts "failed : #{expr}"
  end
end

test_expr('2*(3+4)*7')
test_expr('2+3+4*5')
test_expr('3*7+5+3')