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