読者です 読者をやめる 読者になる 読者になる

kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

Rubyで作るPEGパーザコンビネータ

調子に乗ってRubyでもPEGパーザコンビネータ書いてみた。Rubyは素人(コード自動生成とかにしか使ってない)なので、もうちょっとこうした方がいいよ、とか、こうした方がRubyっぽいよ、とかあったら教えてください。

module PEGParserCombinator
  class Parser
    def initialize(&parser)
      @parser = parser
    end
    def [](input)
      @parser[input]
    end
    alias parse []
    def /(that)
      Parser.new{|input| self[input] || that[input] }
    end
    def ^(that)
      Parser.new{|input|
        (r1 = self[input]) && (r2 = that[r1[1]]) && [[r1[0], r2[0]], r2[1]]
      }
    end
    def apply(&f)
      Parser.new{|input| (r = self[input]) && [f[r[0]], r[1]]}
    end
    def opt
      self / string("").apply{|p| nil}
    end
    def *
      Parser.new{|input|
        rs = []
        while (r = self[input])
          rs << r[0]
          input = r[1]
        end
        [rs, input]
      }
    end
    def +
      (self ^ self.*).apply{|p| p[1].insert(0, p[0])}
    end
    def not
      Parser.new{|input| (r = self[input]) ? false : [nil, input]}
    end
    def and
      self.not.not
    end
  end
  def string(param)
    Parser.new{|input| 
      input.index(param) == 0 ? [param, input[param.length..-1]] : false
    }
  end
  def any
    Parser.new{|input| input.length > 0 ? [input[0, 1], input[0..-1]] : false }
  end
  def rule(&block)
    Parser.new{|input| block.call[input]}
  end
end

使い方は以下のような感じ。ruleメソッドに渡されるブロックによって式を囲むことによって、評価を遅延させている。

include PEGParserCombinator
S = rule { (A ^ string("b").not).and ^ string("a").+ ^ B ^ string("c").not }
A = rule { string("a") ^ A.opt ^ string("b") }
B = rule { string("b") ^ B.opt ^ string("c") }
p S[ARGV[0]]