Math Parser, Part 4: Tests

November 10, 2008 / category: Parsing / 8 comments

Writing test code is a worthwhile practice and building a parser is a good example to prove this claim. We have seen previously that the Parser class consists of many methods and each method is a part of a chain in top-down analysis. It won't be a good idea to start writing the parser from scratch, add all methods we think necessary and then run the code for the first time. Instead of tempting fate, we should write tests for every line of code we create.

The parser code was showed in the previous part at once. The fact is that I wrote it step by step, adding a new functionality and test code every time. I run the test often and fix any errors as soon as they appeared, before proceeding to the next functionality. Perhaps illustrating this process would be very instructive for those not familiar with test driven development, but I meant to focus on the parser itself. Anyway, here is the test code I wrote:

My eBook: “Memoirs of a Software Team Leader”
Read more »


require 'parser'

describe Parser do
  before(:each) do
    @parser = Parser.new
  end

  it 'should compute 5 when given 2 + 3' do
    @parser.parse('2 + 3').should == 5
  end

  it 'should compute 6 when given 2 * 3' do
    @parser.parse('2 * 3').should == 6
  end

  it 'should compute 89 when given 89' do
    @parser.parse('89').should == 89
  end

  it 'should raise an error when input is empty' do
    lambda {@parser.parse('')}.should raise_error()
  end

  it 'should omit white spaces' do
    @parser.parse('   12        -  8   ').should == 4
    @parser.parse('142        -9   ').should == 133
    @parser.parse('72+  15').should == 87
    @parser.parse(' 12*  4').should == 48
    @parser.parse(' 50/10').should == 5
  end

  it 'should treat dot separated floating point numbers as a valid input' do
    @parser.parse('2.5').should == 2.5
    @parser.parse('4*2.5 + 8.5+1.5 / 3.0').should == 19
    @parser.parse('5.0005 + 0.0095').should be_close(5.01, 0.01)
  end

  it 'should handle tight expressions' do
    @parser.parse('67+2').should == 69
    @parser.parse(' 2-7').should == -5
    @parser.parse('5*7 ').should == 35
    @parser.parse('8/4').should == 2
  end

  it 'should calculate long additive expressions from left to right' do
    @parser.parse('2 -4 +6 -1 -1- 0 +8').should == 10
    @parser.parse('1 -1   + 2   - 2   +  4 - 4 +    6').should == 6
  end

  it 'should calculate long multiplicative expressions from left to right' do
    @parser.parse('2 -4 +6 -1 -1- 0 +8').should == 10
    @parser.parse('1 -1   + 2   - 2   +  4 - 4 +    6').should == 6
  end

  it 'should calculate long, mixed additive and multiplicative expressions from left to right' do
    @parser.parse(' 2*3 - 4*5 + 6/3 ').should == -12
    @parser.parse('2*3*4/8 -   5/2*4 +  6 + 0/3   ').should == -1
  end

  it 'should return float pointing numbers when division result is not an integer' do
    @parser.parse('10/4').should == 2.5
    @parser.parse('5/3').should be_close(1.66, 0.01)
    @parser.parse('3 + 8/5 -1 -2*5').should be_close(-6.4, 0.01)
  end

  it 'should raise an error on wrong token' do
    lambda {@parser.parse('  6 + c')}.should raise_error()
    lambda {@parser.parse('  7 & 2')}.should raise_error()
    lambda {@parser.parse('  %')}.should raise_error()
  end

  it 'should raise an error on syntax error' do
    lambda {@parser.parse(' 5 + + 6')}.should raise_error()
    lambda {@parser.parse(' -5 + 2')}.should raise_error()
  end

  it 'should return Infinity when attempt to divide by zero occurs' do
    @parser.parse('5/0').should be_infinite
    @parser.parse(' 2 - 1 + 14/0 + 7').should be_infinite
  end

  it 'should compute 2 when given (2)' do
    @parser.parse('(2)').should == 2
  end

  it 'should compute complex expressions enclosed in parenthesis' do
    @parser.parse('(5 + 2*3 - 1 + 7 * 8)').should == 66
    @parser.parse('(67 + 2 * 3 - 67 + 2/1 - 7)').should == 1
  end

  it 'should compute expressions with many subexpressions enclosed in parenthesis' do
    @parser.parse('(2) + (17*2-30) * (5)+2 - (8/2)*4').should == 8
    @parser.parse('(5*7/5) + (23) - 5 * (98-4)/(6*7-42)').should be_infinite
  end

  it 'should handle nested parenthesis' do
    @parser.parse('(((((5)))))').should == 5
    @parser.parse('(( ((2)) + 4))*((5))').should == 30
  end

  it 'should raise an error on unbalanced parenthesis' do
    lambda {@parser.parse('2 + (5 * 2')}.should raise_error()
    lambda {@parser.parse('(((((4))))')}.should raise_error()
    lambda {@parser.parse('((2)) * ((3')}.should raise_error()
    lambda {@parser.parse('((9)) * ((1)')}.should raise_error()
  end
end

Test code is written in the format accepted by the RSpec framework (any other test framework could be used as well). Each test covers the other part of functionality: those parts that come directly from the parser specification (like "it should compute 6 when given 2 * 3") and those part that might go wrong, like "it should calculate long additive expressions from left to right". Test code has to be stored in a file, e.g. parser_spec.rb. To run the spec, type this at the command line:

spec parser_spec.rb --format specdoc

The "--format specdoc" can be shortened to:

spec parser_spec.rb -f s

Anyway, spec output should be similar to this:

Parser
- should compute 5 when given 2 + 3
- should compute 6 when given 2 * 3
- should compute 89 when given 89
- should raise an error when input is empty
- should omit white spaces
- should treat dot separated floating point numbers as a valid input
- should handle tight expressions
- should calculate long additive expressions from left to right
- should calculate long multiplicative expressions from left to right
- should calculate long, mixed additive and multiplicative expressions from left to right
- should return float pointing numbers when division result is not an integer
- should raise an error on wrong token
- should raise an error on syntax error
- should return Infinity when attempt to divide by zero occurs
- should compute 2 when given (2)
- should compute complex expressions enclosed in parenthesis
- should compute expressions with many subexpressions enclosed in parenthesis
- should handle nested parenthesis
- should raise an error on unbalanced parenthesis

Finished in 0.018552 seconds

19 examples, 0 failures

We end up with a properly working and quite functional parser. It can be further developed or create a base for a completely different program, like some simple XML or YAML parser.

I hope you enjoyed this short series of articles. Thanks for reading!

Comments

There are 8 comments / Submit your comment

Andy
June 04, 2009 01:23 PM

Thanks a lot. Very useful series.

Bill
December 04, 2009 05:49 AM

Why not try writing your math parser in either c, c++, or java, since those languages are the most widely used in most computer science courses?

Lukasz Wrobel
December 05, 2009 07:24 AM

Because I've been writing parsers in C/C++ etc. during my studies, and now I'm doing this in Ruby just for fun.

Anyway, I'm pretty sure there are many C/C++ parsers available on the net, if this is what you were searching for. Theory remains the same across all programming languages, it's just a matter of implementation.

dragoljub
February 27, 2010 01:05 AM

it 'should treat sign before parentheses as a valid input' do

@parser.parse('-(2)').should == -2

end

right? :)

Lukasz Wrobel
March 01, 2010 09:03 PM

Well, it depends. Notice that there is no way to derive your expression from the grammar. However, a quick patch can be applied to the "number" method:

def number
  token = @lexer.get_next_token
  reverse = 1

  signs = [Token::Minus, Token::Plus]
  if signs.include?(token.kind)
    if token.kind == Token::Minus
      reverse = -1
    end

    token = @lexer.get_next_token
  end

  if token.kind == Token::LParen
    value = expression

    expected_rparen = @lexer.get_next_token
    raise 'Unbalanced parenthesis' unless expected_rparen.kind == Token::RParen
  elsif token.kind == Token::Number
    value = token.value
  else
    raise 'Not a number'
  end

  value * reverse
end

By the way, when trying to investigate the problem you described, I've found an incosistency with the grammar. What's more, even the tests reflect it. Do you know where it is?

dragoljub
March 02, 2010 12:41 AM

I'm not sure exactly which "inconsistency" you were referring to. What I've found is quite a few inconsistencies throughout the whole article.

For example, the number production in the grammar was mysteriously changed to exclude sign handling. You were changing how productions work in the code. You mixed up your code so it does not reflect your grammar (there is no component method, factor works as component, number works as factor).

All in all, you do have a "teacher-like" style and approach, but your article is far from consistent. I wouldn't say it's bad, because it is good, it can be very helpful for newcomers. It's short, it goes straight to the point, it covers all essential parts of developing a parser.

But the inconsistencies may easily mislead and confuse your readers. Also, in my opinion, Ruby is not such a good teaching tool. I hope you'd take my opinion as not offensive, but rather friendly, and, please, do take some time to edit your article.

Lukasz Wrobel
March 03, 2010 07:53 PM

First, I'd like to thank you for the time you've spent on reading the articles. I'm also far from treating your comments as offensive.

This short article series was meant - just as you've said - for newcomers. I realise that there are some incosistencies, but some of them were intentional and pretty harmless. On the contrary, disappearance of the sign handling is a good example of what I didn't plan.

The articles were meant for people unfamiliar with the topic and I think they do more good than harm. I wasn't trying to write a fully-fledged dissertation and I realise my articles are far from being proffesional. In fact, "proffesional style" is what I was trying to avoid (it doesn't justify unintentional misstatements, anyway).

And is Ruby a good teaching tool? I think it's not significantly better or worse than other programming languages. What makes it slightly easier to read is the abstraction of technical details, like pointers manipulation in C.

Unfortunately, I can't promise that I'll find time soon to update the article. But I'd like to thank you for enunciating your opinions. I can only be proud of having such attentive readers!

SK
March 05, 2012 12:44 PM

Thanks for a nice explanation.

You can use Markdown in your comments if you wish. Examples:

*emphasis*
emphasis
**strong**
strong
`inline code`
inline code
[My blog](http://lukaszwrobel.pl)
My blog
# use 4 spaces to indent
# a block of code
    def my_method(x)
      x = x + 1
    end
def my_method(x)
  x = x + 1
end

* First.
* Second.
  • First.
  • Second.

> This is a citation.
> Even more citation.

I don't agree with you.

This is a citation. Even more citation.

I don't agree with you.


Submit your comment

(required)

(optional)

(required, Markdown supported)


Preview:

My eBook: “Memoirs of a Software Team Leader”

Read more »