Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides
"Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language." (Gamma, E., R. Helm, R. Johnson, and J. Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Reading, MA: Addison-Wesley, 1995)
If a particular kind of problem occurs often enough, then it might be worthwhile to express instances of the problem as sentences in a simple language. Then you can build an interpreter that solves the problem by interpreting these sentences. For example, searching for strings that match a pattern is a common problem. Rather than building custom algorithms to match each pattern against strings, search algorithms could interpret a regular expression that specifies a set of strings to match. The Interpreter pattern describes how to define a grammar for simple languages, represent sentences in the language, and interpret these sentences. It uses a class to represent each grammar rule. Grammar could be represented by five classes: an abstract class RegularExpression (AbstractExpression in the thumbnail) and four subclasses LiteralExpression (TerminalExpression in the thumbnail), AlternationExpression (NonterminalExpression in the thumbnail), SequenceExpression (NonterminalExpression in the thumbnail), and RepetitionExpression (NonterminalExpression in the thumbnail). The last three classes could define variables that hold subexpressions. Every regular expression defined by this grammar is represented by an abstract syntax tree made up of instances of these classes. An interpreter can be created for these regular expressions by defining the Interpret operation on each subclass of RegularExpression. Interpret takes as an argument the context in which to interpret the expression. The context contains the input string and information on how much of it has been matched so far. Each subclass of RegularExpressioin implements Interpret to match the next part of the input string based on the current context.
This pattern has been used on the following systems: This pattern is widely used in compilers implemented with object-oriented languages (i.e. Smalltalk compilers). SPECtalk uses the pattern to interpret descriptions of input file formats. (Szafron, D. SPECTalk: An object-oriented data specification language. In Technology of Object-Oriented Languages and Systems (TOOLS 8), pp. 123-138, Santa Barbara, CA, August 1992. Prentice Hall.) The pattern is used to evaluate constraints in QOCA, a constraint-solving toolkit. (Helm, R., T. Huynh, K. Marriott, and J. Vlissides. An object-oriented architecture for constraint-based graphical editing. In Proceedings of the Third Eurographics Workshop on Object-Oriented Graphics, pp. 1-22, Champery, Switzerland, October 1992. Also available as IBM Research Division Technical Report RC 18524 (79392).)
Composite, Flyweight, Iterator, and Visitor patterns
Composite pattern, Flyweight pattern, Interpreter pattern, Iterator pattern, Visitor pattern, behavioral patterns, Gamma patterns, behavior distribution (class), interpret sentences, language parsing, grammar rules
language parsing and analysis
need to parse simple language
grammar is extensibleinterpreter is extensible
class hierarchies become unmanageablenot suited for complex languages
Test driver Test.javaSimple implementation of the pattern - TerminalExpression class. TerminalExpression.javaSimple implementation of the pattern - NonTerminalExpression class. NonterminalExpression.javaSimple implementation of the pattern - Context class. Context.javaSimple implementation of the pattern - AbstractExpression class. AbstractExpression.javaTest driver testinterpreter.cppSimple implementation of the pattern. interpreter.h