QuotientZoneExclusion

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