Interpreter Pattern

Problem

Certain problems occur often, in a well-defined and well-understood domain.

Solution

If the domain of these problems were characterized with a language, the problems could easily be solved with an interpretation engine. Map a problem's domain to a language, the language to a grammar, and the grammar to a hierarchical design.

Related Patterns

Composite
State
Flyweight (to share terminal symbols)

Discussion

This pattern suggests modeling the domain of a problem as a recursive grammar. Each rule can reference other rules or terminate (a leaf node in a tree structure). When a problem can easily be represented in this manner, the Interpreter pattern defines a useful solution.

Examples

Musical notation used by musicians is an example of a language and grammar to be interpreted by the Interpreter (the musicians themselves).

Code

This code snippet is an interpreter for Roman Numerals. They are outputted as a decimal number.

var Context = function(input){
  this.input = input;
  this.output = 0;
}
Context.prototype.startsWith = function(str){
  return this.input.substr(0, str.length) === str;
}

var Expression = function(name, one, four, five, multiplier){
  this.name = name;
  this.one = one;
  this.four = four;
  this.five = five;
  this.multiplier = multiplier;
}
Expression.prototype.interpret = function(context){
  if(context.input.length == 0) return;
  else if(context.startsWith(this.nine)){
    context.output += (9*this.multiplier);
    context.input = context.input.substr(2);
  }
  else if(context.input.startsWith(this.four)){
    context.output += (4*this.multiplier);
    context.input = context.input.substr(2);
  }
  else if(context.input.startsWith(this.five)){
    context.output += (5*this.multiplier);
    context.input = context.input.substr(1);
  }
  while(context.input.startsWith(this.one)){
    context.output += (1*this.multiplier);
    context.input = context.input.substr(1);
  }
}

function run(){
  var roman = "MCMXXVIII";
  var context = new Context(roman);
  var tree = [];

  tree.push(new Expression("thousand", "M", " ", " ", " ", 1000));
  tree.push(new Expression("hundred",  "C", "CD", "D", "CM", 100));
  tree.push(new Expression("ten",      "X", "XL", "L", "XC", 10));
  tree.push(new Expression("one",      "I", "IV", "V", "IX", 1));

  for(var i = 0; i < tree.length; i++) tree[i].interpret(context);

  console.log(roman + "=" + context.output);
}