expressionparser.rb

require 'ostruct'

class Lexer
  def initialize
    @tokens = []
    @curr_token_i = -1
  end

  def scan(str)
    case str
    when /^([a-zA-Z][a-zA-Z0-9_]*)(.*)$/: push_token([:ident, $1]); scan($2)
    when /^([0-9]*[\.]?[0-9]+)(.*)$/: push_token([:numeric, $1]); scan($2)
    when /^\+(.*)$/: push_token([:plus, '+']); scan($1)
    when /^\-(.*)$/: push_token([:minus, '-']); scan($1)
    when /^\*(.*)$/: push_token([:times, '*']); scan($1)
    when /^\/(.*)$/: push_token([:divide, '/']); scan($1)
    when /^\((.*)$/: push_token([:lparen, '(']); scan($1)
    when /^\)(.*)$/: push_token([:rparen, ')']); scan($1)
    when /^\s+(.*)$/: scan($1)
    end
    @tokens
  end

  def push_token(t)
    @tokens.push(OpenStruct.new({:kind => t.first, :value => t.last}))
  end

  def next_token
    @curr_token_i += 1 unless @curr_token_i == @tokens.size
    @tokens[@curr_token_i]
  end

  def last_token 
    @curr_token_i -= 1 unless @curr_token_i <= 0
    @tokens[@curr_token_i]
  end
end


class Parser
  def initialize(data={})
    @data = data
  end

  def parse(str)
    @lexer = Lexer.new
    @lexer.scan(str)
    expr
  end

  def expr
    value = factor

    # try and do additive expr
    while t = @lexer.next_token 
      value = case t.kind
      when :plus: value + factor
      when :minus: value - factor
      else @lexer.last_token and return value
      end
    end
    value
  end

  def factor
    value = term

    # try and do multiplicative expr
    while t = @lexer.next_token
      value = case t.kind
      when :times: value * term
      when :divide: value / term
      else @lexer.last_token and return value
      end
    end
    value
  end

  def term
    t = @lexer.next_token

    case t.kind
    when :plus: term
    when :minus: -term
    when :numeric: t.value.to_f
    when :ident: @data[t.value]
    when :lparen
      value = expr
      raise 'unbalanced parens' unless @lexer.next_token.kind == :rparen
      value
    end
  end
end