arith.rb

require_relative 'parser'

class Arithmetic
  include ParserCombinators

  def root
    expression
  end

  def expression
    alt(ref(:addition), ref(:term))
  end

  def addition
    binary(:term, str("+"))
  end

  def term
    alt(ref(:multiplication), ref(:factor))
  end

  def multiplication
    binary(:factor, str("*"))
  end

  def factor
    alt(ref(:number), ref(:paren_expression))
  end

  def number
    alt(str("0"), seq(chr("1-9"), rep(chr("0-9"), 0)))
  end

  def paren_expression
    seq(str("("), ref(:_), ref(:expression), ref(:_), str(")"))
  end

  def binary(arg, op)
    rhs = rep(seq(ref(:_), op, ref(:_), ref(arg)), 1) do |(_, *matches)|
      matches
        .map { |(_, _, op, _, right)| [op, right] }
    end

    seq(ref(arg), rhs) do |(_, left, rhs)|
      rhs.reduce(left) do |left, (op, right)|
        [:binary, op, left, right]
      end
    end
  end

  def _
    rep(str(" "), 0)
  end
end

class RefCachedArithmetic < Arithmetic
  def ref(name)
    @ref_cache ||= {}

    -> state {
      @ref_cache[name] ||= __send__(name)
      @ref_cache[name].call(state)
    }
  end
end

class NodeCachedArithmetic < Arithmetic
  def ref(name)
    @node_cache ||= {}
    @ref_cache  ||= {}

    -> state {
      key = [name, state.offset]

      unless @node_cache.has_key?(key)
        @ref_cache[name] ||= __send__(name)
        @node_cache[key] = @ref_cache[name].call(state)
      end

      @node_cache[key]
    }
  end
end

class PrecArithmetic < Arithmetic
  def prec(base, *parsers)
    -> state {
      parse_at_level(state, base, parsers, 0)
    }
  end

  # Parses left-recursive operators
  def parse_at_level(state, base, parsers, level)
    _, state = ref(:_).call(state)
    node, state = base.call(state)
    return if !state
    _, state = ref(:_).call(state)
    
    while true
      result = parsers[level..-1].each_with_index do |parser, idx|
        op_node, after_op = parser.call(state)
        if after_op
          next_level = level+idx+1
          next_node, state = parse_at_level(after_op, base, parsers, next_level)
          return if !state
          node = [:binary, op_node, node, next_node]
          break :ok
        end
      end

      if result == :ok
        # carry on
      else
        break
      end
    end

    return node, state
  end

  def base_expression
    alt(ref(:number), ref(:paren_expression))
  end
  
  def expression
    prec(base_expression, str("+"), str("*"))
  end
end

class RefCachedPrecArithmetic < PrecArithmetic
  def ref(name)
    @ref_cache ||= {}

    -> state {
      @ref_cache[name] ||= __send__(name)
      @ref_cache[name].call(state)
    }
  end
end

bench.rb

require_relative 'arith'
require 'benchmark/ips'
require 'pp'

expression = "399 + 422 * (778 * (851 * 867 * 454 * 599 + 408 * 300 + 988 * 610 * 164 * 315 + 930 * 14) * (608 + ((849))) * (81) + 102 * 768 + (50) + 967 * 263 + 251) + (744)"

a = Arithmetic.new.parse(expression)
b = PrecArithmetic.new.parse(expression)
if a != b
  puts "Arithmetic"
  pp a
  puts "PrecArithmetic"
  pp b
  exit 1
end

Benchmark.ips do |bm|
  bm.report "combinators" do
    Arithmetic.new.parse(expression)
  end

  bm.report "prec" do
    PrecArithmetic.new.parse(expression)
  end

  bm.report "prec ref cache" do
    RefCachedPrecArithmetic.new.parse(expression)
  end

  bm.report "ref cache" do
    RefCachedArithmetic.new.parse(expression)
  end

  bm.report "node cache" do
    NodeCachedArithmetic.new.parse(expression)
  end
end

parser.rb

module ParserCombinators
  State = Struct.new(:string, :offset) do
    def peek(n)
      string[offset ... offset + n]
    end

    def read(n)
      State.new(string, offset + n)
    end

    def complete?
      offset == string.size
    end
  end

  def parse(string)
    node, state = root.call(State.new(string, 0))

    if state and state.complete?
      node
    end
  end

  def str(string, &action)
    -> state {
      chunk = state.peek(string.size)

      if chunk == string
        node = [:str, chunk]
        node = action.call(node) if action
        [node, state.read(string.size)]
      end
    }
  end

  def chr(pattern, &action)
    -> state {
      chunk = state.peek(1)

      if chunk =~ %r{[#{pattern}]}
        node = [:chr, chunk]
        node = action.call(node) if action
        [node, state.read(1)]
      end
    }
  end

  def seq(*parsers, &action)
    -> state {
      matches = []

      parsers.each do |parser|
        node, state = state && parser.call(state)
        matches << node if state
      end

      if state
        node = [:seq, *matches]
        node = action.call(node) if action
        [node, state]
      end
    }
  end

  def rep(parser, n, &action)
    -> state {
      matches = []
      last_state = nil

      while state
        last_state = state
        node, state = parser.call(state)
        matches << node if state
      end

      if matches.size >= n
        node = [:rep, *matches]
        node = action.call(node) if action
        [node, last_state]
      end
    }
  end

  def alt(*parsers, &action)
    -> state {
      parsers.each do |parser|
        node, new_state = parser.call(state)
        if new_state
          node = action.call(node) if action
          return [node, new_state]
        end
      end

      nil
    }
  end

  def ref(name)
    -> state {
      __send__(name).call(state)
    }
  end
end

Warming up --------------------------------------
         combinators    28.000  i/100ms
                prec    83.000  i/100ms
      prec ref cache   123.000  i/100ms
           ref cache    42.000  i/100ms
          node cache    66.000  i/100ms
Calculating -------------------------------------
         combinators    317.411  (± 6.0%) i/s -      1.596k in   5.048261s
                prec    930.920  (± 8.4%) i/s -      4.648k in   5.026990s
      prec ref cache      1.335k (± 8.8%) i/s -      6.642k in   5.022482s
           ref cache    529.944  (± 4.2%) i/s -      2.688k in   5.081042s
          node cache    777.744  (± 4.6%) i/s -      3.894k in   5.018599s