Functional programming in Crystal to implement parser combinators

5_combinators.cr

# Following: https://fsharpforfunandprofit.com/posts/understanding-parser-combinators/

require "spec"

# Result types

record Success(T), value : T, remaining : String do
  def_equals_and_hash value, remaining
end

record Failure, message : String do
  def_equals_and_hash message
end

# Parser:

struct Parser(T)
  def initialize(@parser : String -> Failure | Success(T))
  end

  def parse(str)
    @parser.call(str)
  end
end

def char_parser(char_to_match)
  Parser.new ->(str : String) {
    return Failure.new "No more input" if str.empty?

    case char = str[0]
    when char_to_match
      remaining = str[1..-1]
      Success.new(char_to_match, remaining)
    else
      Failure.new "Expecting '#{char_to_match}', got '#{char}'"
    end
  }
end

# Combinators:

# Sequence combinator
module Combinator
  def self.and(before_parser, then_parser)
    Parser.new ->(str : String) {
      case before_result = before_parser.parse(str)
      when Failure
        before_result
      when Success
        case then_result = then_parser.parse(before_result.remaining)
        when Failure
          then_result
        when Success
          and_value = {before_result.value, then_result.value}
          Success.new(and_value, then_result.remaining)
        else raise ""
        end
      else raise ""
      end
    }
  end
end

struct Parser
  def >>(other_parser)
    Combinator.and(self, other_parser)
  end
end

# Choice combinator
module Combinator
  def self.or(before_parser, or_parser)
    Parser.new ->(str : String) {
      case before_result = before_parser.parse(str)
      when Success
        before_result
      when Failure
        or_parser.parse(str)
      else raise ""
      end
    }
  end
end

struct Parser
  def |(other_parser)
    Combinator.or(self, other_parser)
  end
end

module Combinator
  def self.any_of(things)
    things.map { |t| char_parser t }
          .reduce { |acc, p| acc | p }
  end
end

# Spec:

describe "digit_parser" do
  digit_parser = Combinator.any_of '0'..'9'

  it "parse a digit" do
    "0123456789".each_char do |digit|
      digit_parser.parse(digit + "AB").should eq(Success.new(digit, "AB"))
    end
  end

  it "fail on non digit or empty input" do
    digit_parser.parse("Z").should be_a Failure
    digit_parser.parse("").should be_a Failure
  end
end


describe "letter_parser" do
  letter_parser = Combinator.any_of('a'..'z') | Combinator.any_of('A'..'Z')

  it "parse a letter" do
    ('a'..'z').each do |letter|
      letter_parser.parse(letter + "AB").should eq(Success.new(letter, "AB"))
    end
    ('A'..'Z').each do |letter|
      letter_parser.parse(letter + "AB").should eq(Success.new(letter, "AB"))
    end
  end

  it "fail on non-letter or empty input" do
    letter_parser.parse("#").should be_a Failure
    letter_parser.parse("").should be_a Failure
  end
end