Grammars and Parsers

Let’s build a parser to math expressions. It’s better start the job in very a simple way: process addition expressions like ‘1 + 1’.

Well… As the old Chinese saying goes, “a journey of one thousand miles begins with one tiny step”.

A Little Bit About Parsers

According to Grune and Jacobs[1]:

“Parsing is the process of structuring a linear representation in accordance with a given grammar. [..] This ‘linear representation’ may be a sentence, a computer program, [..]  in short any linear sequence in which the preceding elements in some way restrict the next element”[1, p. 3].

Example of Parsing
Image via Wikipedia

“To a computer scientist ‘1 + 2 * 3’ is a sentence in the language of ‘arithmetics on single digits’ [..], its structure can be shown, for instance, by inserting parentheses: (1 + (2 * 3)) and its semantics [i.e. its meaning] is probably 7”[1, p. 7].

We use a parser to build an expression tree. This tree contains the elements of a sentence according with the structure of a given grammar and in the correct order (afterwards we will need an interpreter that uses the tree to extract the semantic of the sentence).

And in order to implement a parser, we have to:

Continue reading “Grammars and Parsers”

Advertisements

Developing an Interpreter to Math Expressions

Developing an Interpreter to Math Expressions
The support vote symbol redrawn in the SVG format.
Image via Wikipedia

We’ll start slowly, only dealing with the four binary basic operations: addition, subtraction, multiplication and division. Even though we defined a concise set of operations, I need to be even more humble in order to achieve our goals, and that’s why I’ll choose one of these operations to get started with the fun.

How about we begin with the addition operation? Sounds easy good to me. Doing that will lead the way to the remainder operations (I mean subtraction, multiplication and division operations). We can represent our math expression with a limited context-free grammar like this:

MathExp -> VariableExp | Constant | AddExp | '(' MathExp ')'
AddExp -> MathExp + MathExp
VariableExp -> a | b | ... | z
Constant -> 0 | 1 | ... | 9

Let’s write a test first (using JUnit 4): if an ordinary ‘a + b’ expression with ‘a = 2’ and ‘b = 4’ must be solved, one could think in the following API (specially if you read about the GoF Interpreter pattern):

Continue reading “Developing an Interpreter to Math Expressions”