If you're tempted to create your own simple language in order to solve some specialized problem, then the Interpreter design pattern might be a reasonable choice.
Also, if you don't know what the AST tree is or if you're curious what the SQL language and the Interpreter pattern have in common, you should definitely read this article.
In the introduction to building a math parser I already mentioned the Reverse Polish notation, also called "postfix notation". Its main advantage is unambiguity: you can simply read expression from left to right and calculate its value at the same time. You have to neither set up operators priorities nor use parenthesis.
There are many implementations of Reverse Polish notation parser available, but most of them seem to be too complicated. So I decided to write a very simple RPNParser Ruby class (RPN comes from "Reverse Polish notation").
Writing test code is a worthwhile practice and building a parser is a good example to prove this claim. 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.
We're going to show how easily can our parser be tested using the RSpec framework.
The example implementation of a math parser is going to be written in Ruby because of its simplicity. We are going to introduce complete and ready to use source code, together with comments and notes.
In general, parser is a program that determines whether its input is valid, referring to the given grammar. So, if we would like to parse math expression, we have to set a formal grammar first. The most convenient way to do this is to write the context-free grammar's production rules using EBNF (Extended Backus-Naur Form) notation.
We're going to show how to describe simple expressions with context-free grammar. If it sounds scary to you, don't panic! We're going to do it step by step.
Everyone knows how to calculate value of a simple math expression, like "2 + 3 * 7". But not every programmer knows how to write a program that would accomplish the same task.
We are going to build a math parser in Ruby, but first we need to consider evaluating math expressions in general.