RubyでPackratパーサ続き

メモ化が全く効いてないという大バグを直しながらリファクタリング
（追記：メモ化絡みでロジックがまだ変。修正版は id:metanest:20090406 に）

#!/usr/local/bin/ruby19 -w
# coding:utf-8
# vi:set ts=3 sw=3:
# vim:set sts=0 noet:

require 'pp'

class Derivs
   DerivTbl = {}

   def initialize s
      @memo = Hash.new do|d, tag|
         if parser = DerivTbl[tag] then
            parser.force d
         elsif tag == :char
            if s.empty? then
               nil
            else
               [s[0, 1], Derivs.new(s[1..-1])]
            end
         elsif tag == :input
            s
         else
            raise
         end
      end
   end

   def [] term
      @memo[term]
   end
end

class Parser
   def Parser.create tag=nil, &code
      if tag and code then raise end
      unless tag or code then raise end
      (tag && ParserTop.new(tag)) or (code && ParserSub.new(code))
   end
end

class ParserTop < Parser
   def initialize tag
      Derivs::DerivTbl[tag] = self
      @memo_tag = tag
   end

   def set parser
      @func = parser
   end

   def force d
      @func.parse d
   end

   def parse d
      d[@memo_tag] or force d
   end
end

class ParserSub < Parser
   def initialize code
      @func = code
   end

   def parse d
      @func.call d
   end
end

class Parser
   def / other
      Parser.create do|d|
         self.parse d or other.parse d
      end
   end

   def !
      Parser.create do|d|
         if self.parse d then
            nil
         else
            [nil, d]
         end
      end
   end

   def *
      Parser.create do|d|
         list = []
         while r = self.parse(d) do
            sym, d = r
            list << sym
         end
         [list, d]
      end
   end

   def +
      tail_parser = self.*
      Parser.create do|d|
         if r = self.parse(d) then
            head, d = r
            r = tail_parser.parse d
            tail, d = r
            tail.unshift head
            [tail, d]
         else
            nil
         end
      end
   end

   def opt
      Parser.create do|d|
         self.parse d or [nil, d]
      end
   end
end

module ParserUtil
   def seq *parsers
      Parser.create do|d|
         result = parsers.inject [] do|list, parser|
            if r = parser.parse(d) then
               v, d = r
               list << v
            else
               break nil
            end
         end

         if result then
            if block_given? then
               [yield(result), d]
            else
               [result, d]
            end
         else
            nil
         end
      end
   end

   def char c
      Parser.create do|d|
         if r = d[:char] then
            cc, dd = r
            if cc == c then
               [cc, dd]
            else
               nil
            end
         else
            nil
         end
      end
   end

   def wrap parser
      Parser.create do|d|
         if r = parser.parse(d) then
            if block_given? then
               v, dd = r
               [yield(v), dd]
            else
               r
            end
         else
            nil
         end
      end
   end

   def success v
      Parser.create do|d|
         [v, d]
      end
   end

   def fail
      Parser.create do|d|
         nil
      end
   end

   def ref parser
      Parser.create do|d|
         if r = parser.parse(d) then
            v, dd = r
            [v, d]
         else
            nil
         end
      end
   end
end

module P
   extend ParserUtil

   Start = Parser.create :start

   Additive = Parser.create :additive
   Multitive = Parser.create :multitive
   Primary = Parser.create :primary
   Decimal = Parser.create :decimal
   DecimalChar = Parser.create :decimalChar

   Char = Parser.create do|d|
      d[:char]
   end

   # Because of priority, prefer {...} block than do...end .

   Start.set(
      seq(Additive, !Char)
   )

   Additive.set(
      seq(Multitive, char('+'), Additive){|l, _, r| l + r} / Multitive
   )

   Multitive.set(
      seq(Primary, char('*'), Multitive){|l, _, r| l * r} / Primary
   )

   Primary.set(
      seq(char('('), Additive, char(')')){|args| args[1]} / Decimal
   )

   Decimal.set(
      wrap(DecimalChar){|c| Integer c}
   )

   DecimalChar.set(
      char('0') / char('1') / char('2') / char('3') / char('4') /
      char('5') / char('6') / char('7') / char('8') / char('9')
   )
end

d = Derivs.new '(2+3)*(4+5)'
pp d[:start]