今までに書き忘れてたけど 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]