Quotient Zone Exclusion

Interpreter

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

At first sight it seems a little hard to find uses for this pattern. The example in GoF is a regular expression matching interpreter which most of us either take for granted or do without. However, the first sentence of the motivation gives a clue as to how to use this pattern:

If a particular type of problem occurs often enough, then it might be worthwhile to express instances of the problem as sentences in a simple language.

Examples

• Simple pattern matching
• Building a GUI widget based on a set of properties or a resource bundle
• Graph drawing program
• Processing an XML document
• Anything that requires parsing

Warning: this pattern is not Parser. It specifically does not address the issue of parsing your sentence.

Method:

First define your grammar, and then construct a class hierarchy that describes your grammar. Each rule is a class; each symbol in the rule is an instance of the class.

Example: Graph Drawing

Suppose your are writing a graph drawing application. You want to graph simple functions such as y = 2x^2 + ln x + 1. This is a simple sentence in mathematics. The grammar may be described something like

  constant   ::= '0'|'1'| ... |'9'| {'0'|...|'9'}* |
         {'0'|...|'9'}*'.'{'0'|...|'9'}*
  variable   ::= 'x'
  add        ::= expression '+' expression
  subtract   ::= expression '-' expression
  multiply   ::= expression '*' expression
  divide     ::= expression '/' expression
  power      ::= expression '^' expression
  unary      ::= '-'expression | 'ln('expression')' |
                         'sin('expression')'|...|'function('expression')'
  expression ::= constant | variable | add | subtract | multiply |
 divide | power | unary | '('expression')'

There are two types of expression class: those that represent terminal expressions (they hold no references to further expression classes) e.g. constant and variable, and non-terminal classes which are typically rules that represent compound expressions.

Classes representing the binary operators add, subtract, multiply, divide and power may be written as

     public class Addition extends AbstractExpression {
       private AbstractExpression left, right ;
       public Addition(AbstractExpression left,
        AbstractExpression right) {
 this.left = left ;
 this.right = right ;
       }
     }

while those representing unary expressions will be similar but take a single AbstractExpression?. Finally:

     public class Constant extends AbstractExpression {
       private double value ;
       public Constant(double value) {
 this.value = value ;
       }
     }

and the class representing the variable has nothing in it so far.

     public class Variable extends AbstractExpression {
       public Variable() {}
     }

As mentioned above, the problem this pattern does not address is that of parsing sentences in the grammar. Specifically it provides no way to get from the equation y = 2 * x^2 + ln(x) + 1 to its class representation. This is someone else's problem. The class representation looks something like:

                Addition
        _________/    \_________
                  /       \
   Multiplication                  Addition
      /      \        /    \ 
      Constant        Power     Logarithm  Constant
        / \      |
        /   \      |
       /    \               |
 Variable  Constant  Variable

Where the lines represent is a member of.

Finally, we must implement an interpret method for each concrete subclass of AbstractExpression?. In this case we shall make interpret a member function of the concrete subclasses. It will take a double as its single parameter. The way the graph drawing program will use this structure is as follows. Suppose it wants to graph the equation above with the x-range from 0 to five, plotting points every 0.1. Then it would call interpret on the structure above for each value of x from 0 to 5 in intervals of 0.1. Let the top addition class be a field called function. The the program would do

for (double x = 0; x<=5; x += 0.1) {      
  double y = function.interpret(x) ;    
  plot(x, y) ;  
}

Now, the interpret function is implemented as:

public class Addition {
  double interpret (double x) {
    return left.interpret(x) + right.interpret(x) ;
  }
}

public class Logarithm {
  double interpret (double x) {
    return Math.log(expression.interpret(x)) ;
  }
}

public class Constant {
  double interpret (double x) {
    return value ;
  }
}

public class Variable {
  double interpret (double x) {
    return  x ;
  }
}

That's all there is to it!

Here are some consequences:

• It is easy to implement the grammar
• It is easy to change the grammar
• Complex grammars are hard to maintain
• It is easy to add new ways of interpreting sentences

Implementation details:

• No hints about parsing
• Don't have to put interpret in the expression classes; we can use Visitor, for example, or Iterator
• We can share terminal symbols using Flyweight