Interpreter Design Pattern

Monday, November 12, 2012

Interpreter Design Pattern

Definition

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

AbstractExpression declares an interface for executing an operation
TerminalExpression implements an Interpret operation associated with terminal symbols in the grammar (An instance is required for every terminal symbol in the sentence).
NonterminalExpression One such class is required for every rule R ::= R1R2...Rn in the grammar. It maintains instance variables of type AbstractExpression for each of the symbols R1 through Rn and implements an Interpret operation for nonterminal symbols in the grammar. Interpret typically calls itself recursively on the variables representing R1 through Rn.
Context contains information that is 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. Client invokes the Interpret operation

Applicability

The Interpreter pattern is used exhaustively in defining grammars, tokenize input and store it.
A specific area where Interpreter can be used are the rules engines.
The Interpreter pattern can be used to add functionality to the Composite pattern.

Consequences

Map a domain to a language, the language to a grammar, and the grammar to a hierarchical object-oriented design.
Decouple the underlying expressions from the grammar.

Downsides

As the grammar becomes more complicated, the maintenance effort is increased.
The Interpreter pattern has a limited area where it can be applied. We can discuss the Interpreter pattern only in terms of formal grammars but in this area there are better solutions and this is the reason why this pattern is not so frequently used. This pattern can be applied for parsing light expressions defined in simple grammars and sometimes in simple rule engines.

Sample Code
Classic Interpreter pattern example

Interpreter pattern using C# ExpressionTree example

Related Patterns

Interpreter can use State to define parsing contexts.
The abstract syntax tree of Interpreter is a Composite (therefore Iterator and Visitor are also applicable).
Terminal symbols within Interpreter’s abstract syntax tree can be shared with Flyweight.
The pattern does not address parsing. When the grammar is very complex, other techniques (such as a parser) are more appropriate.