Recursive Descent Parser For Ruby - RDParser

A work of genius by Dennis Ranke (see original post at http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/174842 ). I want to keep this for posterity, but can't wait to see if this gets improved / extended, etc.


class RDParser
   attr_accessor :pos
   attr_reader :rules

   def initialize(&block)
     @lex_tokens = []
     @rules = {}
     @start = nil
     instance_eval(&block)
   end

   def parse(string)
     @tokens = []
     until string.empty?
       raise "unable to lex '#{string}" unless @lex_tokens.any? do |tok|
         match = tok.pattern.match(string)
         if match
           @tokens << tok.block.call(match.to_s) if tok.block
           string = match.post_match
           true
         else
           false
         end
       end
     end
     @pos = 0
     @max_pos = 0
     @expected = []
     result = @start.parse
     if @pos != @tokens.size
       raise "Parse error. expected: '#{@expected.join(', ')}', found 
'#{@tokens[@max_pos]}'"
     end
     return result
   end

   def next_token
     @pos += 1
     return @tokens[@pos - 1]
   end

   def expect(tok)
     t = next_token
     if @pos - 1 > @max_pos
       @max_pos = @pos - 1
       @expected = []
     end
     return t if tok === t
     @expected << tok if @max_pos == @pos - 1 && !@expected.include?(tok)
     return nil
   end

   private

   LexToken = Struct.new(:pattern, :block)

   def token(pattern, &block)
     @lex_tokens << LexToken.new(Regexp.new('\\A' + pattern.source), block)
   end

   def start(name, &block)
     rule(name, &block)
     @start = @rules[name]
   end

   def rule(name)
     @current_rule = Rule.new(name, self)
     @rules[name] = @current_rule
     yield
     @current_rule = nil
   end

   def match(*pattern, &block)
     @current_rule.add_match(pattern, block)
   end

   class Rule
     Match = Struct.new :pattern, :block

     def initialize(name, parser)
       @name = name
       @parser = parser
       @matches = []
       @lrmatches = []
     end

     def add_match(pattern, block)
       match = Match.new(pattern, block)
       if pattern[0] == @name
         pattern.shift
         @lrmatches << match
       else
         @matches << match
       end
     end

     def parse
       match_result = try_matches(@matches)
       return nil unless match_result
       loop do
         result = try_matches(@lrmatches, match_result)
         return match_result unless result
         match_result = result
       end
     end

     private

     def try_matches(matches, pre_result = nil)
       match_result = nil
       start = @parser.pos
       matches.each do |match|
         r = pre_result ? [pre_result] : []
         match.pattern.each do |token|
           if @parser.rules[token]
             r << @parser.rules[token].parse
             unless r.last
               r = nil
               break
             end
           else
             nt = @parser.expect(token)
             if nt
               r << nt
             else
               r = nil
               break
             end
           end
         end
         if r
           if match.block
             match_result = match.block.call(*r)
           else
             match_result = r[0]
           end
           break
         else
           @parser.pos = start
         end
       end
       return match_result
     end
   end
end


To use:

parser = RDParser.new do
   token(/\s+/)
   token(/\d+/) {|m| m.to_i }
   token(/./) {|m| m }

   start :expr do
     match(:expr, '+', :term) {|a, _, b| a + b }
     match(:expr, '-', :term) {|a, _, b| a - b }
     match(:term)
   end

   rule :term do
     match(:term, '*', :dice) {|a, _, b| a * b }
     match(:term, '/', :dice) {|a, _, b| a / b }
     match(:dice)
   end

   def roll(times, sides)
     (1..times).inject(0) {|a, b| a + rand(sides) + 1 }
   end

   rule :dice do
     match(:atom, 'd', :sides) {|a, _, b| roll(a, b) }
     match('d', :sides) {|_, b| roll(1, b) }
     match(:atom)
   end

   rule :sides do
     match('%') { 100 }
     match(:atom)
   end

   rule :atom do
     match(Integer)
     match('(', :expr, ')') {|_, a, _| a }
   end
end

puts "#{parser.parse(supply_string_here)}"