コンビネータ追加

今までに書き忘れてたけど id:kmizushima さんの http://d.hatena.ne.jp/kmizushima/searchdiary?word=*%5bPEG%5d とか id:kmizushima:20090225:1235576560 をおおいに参考にしています
先読み関係とかを追加。** 演算子による連接はとりやめ。Parser.new にブロックを渡す初期化もありに

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

require 'pp'

class Derivs
   def initialize s
      @memo = Hash.new do|d, key|
         case key
         when :start
            P::Start.call d
         when :additive
            P::Additive.call d
         when :multitive
            P::Multitive.call d
         when :primary
            P::Primary.call d
         when :decimal
            P::Decimal.call d
         when :char
            if s.empty? then
               nil
            else
               [s[0, 1], Derivs.new(s[1..-1])]
            end
         when :input
            s
         else
            raise
         end
      end
   end

   def [] term
      @memo[term]
   end
end

class Parser
   def initialize &c
      @func = c
   end

   def set a=nil, &c
      if a and c then raise end
      unless a or c then raise end
      @func = a || c
   end

   def call d
      @func.call d
   end

   def / other
      Parser.new do|d|
         self.call d or other.call d
      end
   end

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

module ParserUtil
   def seq *args
      Parser.new do|d|
         success = args.inject [] do|list, parser|
            r = parser.call d
            if r then
               v, d = r
               list << v
            else
               break nil
            end
         end

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

   def char c
      Parser.new 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.new do|d|
         if r = parser.call(d) then
            if block_given? then
               v, dd = r
               [yield(v), dd]
            else
               r
            end
         else
            nil
         end
      end
   end

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

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

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

   def opt parser
      Parser.new do|d|
         parser.cell d or success nil
      end
   end
end

module P
   extend ParserUtil

   Start = Parser.new

   Additive = Parser.new
   Multitive = Parser.new
   Primary = Parser.new
   Decimal = Parser.new
   DecimalChar = Parser.new

   Char = Parser.new 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]