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')