parser_combinators.cr

require "benchmark"

module Parser(T)
  def self.char(a : Char)
    CharParser.new(a)
  end

  def self.int
    IntParser.new
  end

  def self.skip_whitespace
    SkipWhitespace.new
  end

  def self.combine(&block : ParserCombinator -> T) forall T
    Combinator(T).new(block)
  end

  abstract def parse(reader : Char::Reader) : Success(T) | Failure

  struct Combinator(T)
    include Parser(T)

    def initialize(@block : ParserCombinator -> T)
      @combinator = ParserCombinator.new
    end

    def parse(reader : Char::Reader) : Success(T) | Failure
      @combinator.reader = reader
      value = @block.call(@combinator)
      succeed value, @combinator.reader
    end
  end

  class ParserCombinator
    property! reader : Char::Reader

    def parse(parser : Parser(T)) : T forall T
      result = parser.parse(reader)
      case result
      in Success
        @reader = result.reader
        result.value
      in Failure
        raise "Failed to parse at #{result.reader.current_char.inspect}"
      end
    end
  end

  def parse(string : String)
    reader = Char::Reader.new(string)
    result = parse(reader)
    case result
    in Success
      result.value
    in Failure
      raise "Failed to parse at #{result.reader.current_char.inspect}"
    end
  end

  def succeed(value : T, reader : Char::Reader)
    Success(T).new(value, reader)
  end

  def fail(reader : Char::Reader)
    Failure.new(reader)
  end

  record Success(T), value : T, reader : Char::Reader
  record Failure, reader : Char::Reader

  struct CharParser
    include Parser(Char)

    def initialize(@char : Char)
    end

    def parse(reader : Char::Reader) : Success(Char) | Failure
      if reader.current_char == @char
        reader.next_char
        succeed @char, reader
      else
        fail reader
      end
    end
  end

  struct IntParser
    include Parser(Int32)

    def parse(reader : Char::Reader) : Success(Int32) | Failure
      value = 0
      if reader.current_char == '0'
        reader.next_char
        succeed value, reader
      elsif '0' <= reader.current_char <= '9'
        while '0' <= reader.current_char <= '9'
          value *= 10
          value += reader.current_char.to_i
          reader.next_char
        end
        succeed value, reader
      else
        fail reader
      end
    end
  end

  struct SkipWhitespace
    include Parser(Nil)

    def parse(reader : Char::Reader) : Success(Nil) | Failure
      while reader.current_char.whitespace?
        reader.next_char
      end
      succeed nil, reader
    end
  end
end

int = Parser.int

mul = Parser.combine do |c|
  a = c.parse(int)
  c.parse(Parser.skip_whitespace)
  c.parse(Parser.char('*'))
  c.parse(Parser.skip_whitespace)
  b = c.parse(int)
  a * b
end

plus = Parser.combine do |c|
  a = c.parse(mul)
  c.parse(Parser.skip_whitespace)
  c.parse(Parser.char('+'))
  c.parse(Parser.skip_whitespace)
  b = c.parse(mul)
  a + b
end

calc = Parser.combine do |c|
  a = c.parse(plus)
  a
end

string = "3 * 4 + 5 * 6"
p = P.new

p! calc.parse(string)
p! p.parse(string)

Benchmark.ips do |x|
  x.report("parser combinator") do
    calc.parse(string)
  end
  x.report("manual") do
    p.parse(string)
  end
end

class P
  getter reader : Char::Reader

  def initialize
    @reader = Char::Reader.new("")
  end

  def parse(string : String) : Int32
    @reader = Char::Reader.new(string)
    parse_plus
  end

  def parse_plus
    a = parse_mul
    skip_whitespace
    check '+'
    skip_whitespace
    b = parse_mul
    a + b
  end

  def parse_mul
    a = parse_number
    skip_whitespace
    check '*'
    skip_whitespace
    b = parse_number
    a * b
  end

  def parse_number
    value = 0
    if reader.current_char == '0'
      reader.next_char
      0
    elsif '0' <= reader.current_char <= '9'
      while '0' <= reader.current_char <= '9'
        value *= 10
        value += reader.current_char.to_i
        reader.next_char
      end
      value
    else
      raise "Failed to parse at #{reader.current_char.inspect}"
    end
  end

  def check(char : Char) : Nil
    if reader.current_char == char
      reader.next_char
    else
      raise "Failed to parse at #{reader.current_char.inspect}"
    end
  end

  def skip_whitespace
    while reader.current_char.whitespace?
      reader.next_char
    end
  end
end