recursive descent expression parser

parser.rb

# expr ::= factor ( addop factor ) *
# addop ::= '+' | '-'
# factor ::= signed_term ( mulop signed_term ) *
# mulop ::= '*' | '/'
# signed_term = '-' ? term
# term ::= number | '(' expr ')'
# number ::= /[+-]\d+(\.\d*)?/

require "strscan"

class Parser

  ParseError = Class.new(StandardError)

  def initialize(s)
    @scanner = StringScanner.new(s)
  end

  def parse
    value = parse_expression
    parse_ws
    raise SyntaxError unless @scanner.eos?
    value
  end

  private
    
  def parse_expression
    value = parse_factor
    while (addop = try { parse_addop })
      value = value.send(addop, parse_factor)
    end
    value
  end

  def parse_factor
    value = parse_signed_term
    while (mulop = try { parse_mulop })
      value = value.send(mulop, parse_signed_term)
    end
    value
  end

  def parse_signed_term
    parse_ws
    sign = try { parse_literal("-") }
    value = parse_term
    value = -value if sign == "-"
    value
  end

  def parse_term
    try { parse_number} || parse_nested_expression
  end

  def parse_nested_expression
    parse_ws
    parse_literal("(")
    parse_ws
    parse_expression.tap do
      parse_ws
      parse_literal(")")
    end
  end

  def parse_number
    parse_ws
    s = parse_pattern(/[+-]?\d+(\.\d+)?/)
    Float(s)
  end

  def parse_mulop
    parse_ws
    parse_pattern(/[*\/]/)
  end

  def parse_addop
    parse_ws
    parse_pattern(/[+-]/)
  end

  def parse_ws
    parse_pattern(/ */)
  end

  def parse_pattern(pattern)
    match = @scanner.scan(pattern)
    raise ParseError unless match
    match
  end

  def parse_literal(s)
    parse_pattern(Regexp.new(Regexp.escape(s)))
  end

  def try
    @orig_scanner = @scanner.dup
    begin
      yield
    rescue ParseError
      @scanner = @orig_scanner
      nil
    end
  end

end

s = "(1 - 2) + -(-(-(-4)))"
parser = Parser.new(s)
p parser.parse
# => 3.0