Basic arithmetic parser & evaluator using RACC

.gitignore

*~
*.tab.rb
coverage

calc.rb

require File.join(File.dirname(__FILE__), "../racc/calc_parser.tab")

module Calc
  class Tokenizer
    def initialize(str = nil)
      @str = str
    end

    def <<(str)
      @str ||= ""
      @str += str
    end

    def next
      return if @str.nil?

      eat_whitespace
      c = shift_str

      case c
      when nil then [false, nil]
      when '=' then [:EQ, c]
      when '(' then [:LPAREN, c]
      when ')' then [:RPAREN, c]
      when '+' then [:PLUS, c]
      when '-' then [:MINUS, c]
      when '*' then [:STAR, c]
      when '/' then [:FSLASH, c]
      when "," then [:COMMA, c]
      when "\n" then [:NEWLINE, c]
      when /[0-9]/ then number(c)
      when /[A-Za-z_]/ then symbol(c)
      else raise StandardError, "unknown character #{c.inspect}"
      end
    end

    private

    def shift_str
      c = @str[0]

      if c
        c = c.chr
        @str = @str[1..-1]
      end

      c
    end

    def eat_whitespace
      m = @str.match(/^([ \r\t]+)/)

      if m
        @str = @str[m[1].length..-1]
      end
    end

    def symbol(c)
      m = (c + @str).match(/^([A-Za-z_][A-Za-z0-9_]*)/)

      @str = @str[(m[1].length - 1)..-1]
      case m[1]
        when "if" then [:IF, m[1]]
        when "else" then [:ELSE, m[1]]
        when "end" then [:END, m[1]]
        else [:SYMBOL, m[1]]
      end
    end

    def number(c)
      m = (c + @str).match(/^([0-9]+)/)

      @str = @str[(m[1].length - 1)..-1]
      [:NUMBER, m[1].to_f]
    end
  end

  class Interpretter
    def initialize(parser = Parser.new(Tokenizer.new), env = nil)
      @parser = parser
      @env = env || { "false" => false, "true" => true }
    end

    def []=(symbol, value)
      @env[symbol] = value
    end

    def [](symbol)
      @env[symbol]
    end

    def evaluate(input)
      # @parser.parse(input.split).collect { |e| e.evaluate(self) }
      @parser.parse(input).evaluate(self)
    end
  end
end

calc_parser.y

# http://gist.github.com/178048
class Calc::Parser

token NUMBER SYMBOL PLUS MINUS FSLASH STAR LPAREN RPAREN EQ IF ELSE END COMMA NEWLINE

prechigh
  right LPAREN RPAREN
  left EQ COMMA
  left EQ NEWLINE
  left STAR FSLASH
  left PLUS MINUS
preclow

rule
  expression:
    LPAREN expression RPAREN      { result = val[1] }
  | atom                          { result = val[0] }
  | statement_list                { result = val[0] }
  | assignment                    { result = val[0] }
  | condition                     { result = val[0] }
  | expression PLUS expression    { result = BinOp.new(val[1], val[0], val[2]) }
  | expression MINUS expression   { result = BinOp.new(val[1], val[0], val[2]) }
  | expression STAR expression    { result = BinOp.new(val[1], val[0], val[2]) }
  | expression FSLASH expression  { result = BinOp.new(val[1], val[0], val[2]) }

  statement_list:
    expression COMMA expression { result = StatementList.new(val[0], val[2]) }
  | expression NEWLINE expression { result = StatementList.new(val[0], val[2]) }

  condition:
    IF expression expression END      { result = Conditional.new(val[1], val[2]) }
  | IF expression expression ELSE expression END { result = Conditional.new(val[1], val[2], val[4]) }

  atom:
    NUMBER     { result = Atom.new(val[0]) }
  | SYMBOL     { result = Var.new(val[0]) }

  assignment:
    SYMBOL EQ expression   { result = Assignment.new(val[0], val[2]) }

---- header
  require 'calc/expressions'

---- inner
  def initialize(tokenizer)
    super()

    @tokenizer = tokenizer
  end

  def parse(str)
    @tokenizer << str
    do_parse
  end

  def next_token
    @tokenizer.next
  end

calc_spec.rb

require File.join(File.dirname(__FILE__), "spec_helper.rb")

describe Calc::Interpretter do
  subject { Calc::Interpretter.new }

  { "true" => true,
    "false" => false,
    "1 + 1" => 2,
    "2 - 2" => 0,
    "3 * 3" => 9,
    "4 / 4" => 1,
    "1 * 2 + 3" => 5,
    "1 + 2 * 3" => 7,
    "(1 + 2) * 3" => 9,
    "1 * (2 + 3)" => 5,
    "(1 + 2 * 3) + 4" => 11,
    "1 - (2 + 3 * 4)" => -13,
    "a = 3" => 3,
    "if true 3 end" => 3,
    "if(1) 3 end" => 3,
    "if true 3 else 2 end" => 3,
    "if false 3 else 2 end" => 2,
    "if 0 3 else 2 end" => 3,
    "if(1 + 2) 3 else 2 end" => 3,
    "2 + if false 3 else 2 + 2 end + 4" => 10,
    "1, 2, 3" => 3,
    "1\n2\n3" => 3,
    "if(false) 1, 2, 3 else 4, 5, 6 end" => 6,
  }.each do |input, output|
    context input.inspect do
      it "returns #{output}" do
        subject.evaluate(input).should == output
      end
    end
  end

  context 'with variables' do
    before(:each) do
      subject.evaluate("a = 1")
      subject.evaluate("b = 2")
      subject.evaluate("c = 3")
    end

    { 'a + b' => 3,
      'a - b' => -1,
      'a * b' => 2,
      'a / b' => 0.5,
      "a * b + c" => 5,
      "a + b * c" => 7,
      "(a + b) * c" => 9,
      "a * (b + c)" => 5,
      '(a + b) * b' => 6,
      "a = b" => 2,
      "a = b + c" => 5,
      "xyz = a + b" => 3
    }.each do |input, output|
      context input.inspect do
        it "returns #{output}" do
          subject.evaluate(input).should == output
        end
      end
    end
  end

  context 'when given the statement list' do
    { "a = 1, b = 2, c = 3" => 3.0,
      "a = 1\nb = 2\nc = 3" => 3.0
    }.each do |input, output|
      context input.inspect do
        it "returns #{output}" do
          subject.evaluate(input).should == output
        end

        { "a" => 1.0, "b" => 2.0, "c" => 3.0 }.each do |var, value|
          it "assigns #{value} to #{var}" do
            subject.evaluate(input)
            subject.evaluate(var).should == value
          end
        end
      end
    end
  end
end

expressions.rb

module Calc
  class Atom
    def initialize(v)
      @value = v
    end

    def evaluate(scope)
      @value
    end
  end

  class Assignment
    def initialize(var, val)
      @variable = var
      @value = val
    end

    def evaluate(scope)
      scope[@variable] = @value.evaluate(scope)
    end
  end

  class Var
    attr_accessor :name

    def initialize(name)
      @name = name
    end

    def evaluate(scope)
      scope[self.name]
    end
  end

  class BinOp
    attr_accessor :op, :a, :b

    def initialize(op, a, b)
      @op = op
      @a = a
      @b = b
    end

    def evaluate(scope)
      a = @a.evaluate(scope)
      b = @b.evaluate(scope)

	 # a.collect { |e| e.send(@op, b) }
      a.send(@op, b)
    end
  end

  class Conditional
    attr_accessor :condition, :true_expr, :false_expr

    def initialize(condition, true_expr, false_expr = nil)
      @condition = condition
      @true_expr = true_expr
      @false_expr = false_expr
    end

    def evaluate(scope)
      if @condition.evaluate(scope)
        @true_expr.evaluate(scope)
      elsif @false_expr
        @false_expr.evaluate(scope)
      end
    end
  end

  class StatementList
    attr_accessor :first, :rest

    def initialize(first, rest)
      @first = first
      @rest = rest
    end

    def evaluate(scope)
      @first.evaluate(scope)
      @rest.evaluate(scope)
    end
  end
end

Rakefile

require 'spec/rake/spectask'

file "racc/calc_parser.tab.rb" => [ "racc/calc_parser.y" ] do |t|
  sh("racc -t racc/calc_parser.y")
end

spec_prereq = [ "racc/calc_parser.tab.rb" ]

desc "Run all specs in spec directory (excluding plugin specs)"
Spec::Rake::SpecTask.new(:spec => spec_prereq) do |t|
  # t.spec_opts = ['--options', "\"#{RAILS_ROOT}/spec/spec.opts\""]
  t.spec_files = FileList['spec/**/*_spec.rb']
end

namespace :spec do
  desc "Run all specs in spec directory (excluding plugin specs)"
  Spec::Rake::SpecTask.new(:rcov => spec_prereq) do |t|
    # t.spec_opts = ['--options', "\"#{RAILS_ROOT}/spec/spec.opts\""]
    t.rcov = true
    t.rcov_opts = lambda do
      IO.readlines("#{File.dirname(__FILE__)}/spec/rcov.opts").map {|l| l.chomp.split " "}.flatten
    end
    t.spec_files = FileList['spec/**/*_spec.rb']
  end
end

rcov.opts

--exclude "spec/*,/Library/*" 

spec_helper.rb

$: << File.expand_path(File.join(File.dirname(__FILE__), "../lib"))

require 'spec'
require 'calc'