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

AbstractExpression (RegularExpression)

declares an abstract Interpret operation that is common to all nodes in the abstract syntax tree.

TerminalExpression (LiteralExpression)

implements an Interpret operation associated with terminal symbols in the grammar.
an instance is required for every terminal symbol in a sentence.

NonterminalExpression (AlternationExpression, RepetitionExpression, SequenceExpressions)

one such class is required for every rule R ::= R₁ R₂ ... R_n in the grammar.
maintains instance variables of type AbstractExpression for each of the symbols R₁ through R_n.
implements an Interpret operation for nonterminal symbols in the grammar. Interpret typically calls itself recursively on the variables representing R₁ through R_n.

Context

contains information that's global to the interpreter.

Client

builds (or is given) an abstract syntax tree representing a particular sentence in the language that the grammar defines. The abstract syntax tree is assembled from instances of the NonterminalExpression and TerminalExpression classes.
invokes the Interpret operation.

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

step 1: implement the tree classes.
Test the class in the python interactive interface, the running result could be like this.
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