Interpreter Pattern

Starting Point Analysis

In the observer pattern, we only considered assign a numeric value to a cell. In our project requirment, the cell value could be numeric or arithmatic expression that consists of number(s) and/or reference(s) to other cells. For these kinds of expression, we have to store it in the Data object so that when values of the referenced cells are changed, the referencing cell's value also can be automatically updated. There are at least two options store the express. One option is storing the expression as a string, which is assigned to a cell by user. If the expression contains a cell reference, we replace them by value of the referenced cell value. Then using the built-in function of python eval() to evaluate the string. The another option is parsing the expression as a binary tree structure. The first option has to replace the cell reference each time when a cell's value is changed before calling eval(). And more, we have to checking the lexical and syntax of a usr-typed expression string. So I prefer to use the second option.

Requirement in this phase

In this phase, I only need to build a parser which can parse a arithmatic expression into a binary tree and can evaluate this tree given the referenced cells' value. We do not consider how it related to the project. I suppose any cell reference is in the form of '$i$j', where i is a cell's row positon, j is a cell's col position.

The arithmatic expression grammer

Our parse should recognize the following grammer:

goal -> expr&END

expr -> factor&expr-tail

expr-tail ->^
expr-tail -> '+' & expr
expr-tail -> '-' & expr

factor -> term & factor-tail

factor-tail ->^
factor-tail ->'*'&factor
factor-tail ->'/'&factor

term -> number
term -> $i$j
term -> '(' & expr &')'

tokens: (, ), num, $i$j, +, -, *, /, END

Interpreter Pattern Overview

The following simple description of interpreter pattern is from the book, Design Patterns. Please see page 243-255 of this book for more details.

Intent

Given a language, define a represention for its grammar along with an interpreter that uses the representation to interpret sentences in the language.

Structure

participants

UML Design in this phase

Our arithmatic expression is also a language. So the interprter pattern is quite suitable for this phase. Based on this pattern, I design the following UML class diagram.

Steps in this phase

  1. step 1: implement the tree classes.
    Test the class in the python interactive interface, the running result could be like this.
  2. step 2: implement the scanner and parser classes.

We simply test the source code in the python interactive interface, the runing result could be like this.

References

Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides Design Patterns Elements of Reusable Object-Oriented Software Addison-Wesley, 1995