Posts from the "Parsing" category:

Interpreter Design Pattern

December 07, 2009 / category: Parsing / 3 comments

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.

Reverse Polish Notation Parser

March 22, 2009 / category: Parsing / 8 comments

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").

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. 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.

Math Parser, Part 3: Implementation

November 08, 2008 / category: Parsing / 8 comments

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.

Math Parser, Part 2: Grammar

November 05, 2008 / category: Parsing / 0 comments

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.

Math Parser, Part 1: Introduction

November 03, 2008 / category: Parsing / 2 comments

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.

My eBook: “Memoirs of a Software Team Leader”