This week we’ll continue our exploration of design patterns and look at another behavioural pattern, the Interpreter pattern.
The Gang of Four book defines the Interpreter pattern as:
“Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language.”
Understanding the Interpreter Pattern
The Interpreter pattern allows us to implement a simple language to use inside an application. We define a class to represent each rule of the language (its grammar). We also implement an interpreter that operates on instances of these classes. This interpreter parses and executes the sentences of the language.
The pattern works well when we have a simple language/grammar to implement. As the grammar gets more complex, it becomes harder to maintain. With a large number of language rules, tools like parser generators are better options. These tools can interpret expressions without building abstract syntax trees. This is more efficient and can save memory space.
We very rarely use the Interpreter pattern, because as developers we hardly ever create our own languages. To use it properly, we need to know a lot about formal grammars. Formal grammars are used to create languages.
Examples of the Interpreter Pattern
A well-known example of an interpreter is JavaScript code that runs in a web page on a browser. JavaScript is an programming language, and as such, has a grammar representation. A JavaScript interpreter uses that grammar representation to interpret and run JavaScript code. A JavaScript interpreter is built into every major browser.
SQL is another good example. An SQL interpreter is built into all relational database management systems.
In Java SE, the Interpreter pattern is used in the java.util.Pattern and java.text.Normalizer classes and all subclasses of java.text.Format.
Other examples of the Interpreter pattern are the Unified Expression Language (javax.el API) used in JSP and JSF, and the Spring Expression Language (SpEL).
Expression Hierarchy
We use the Interpreter pattern to define a class-based representation for the grammar of our language.
We create an AbstractExpression interface (or abstract class) as the root of our class hierarchy. This is used to interpret a context. The interface defines an abstract interpret() method that takes the context as a parameter. The context is an input stream (generally a string) containing the language sentences that must be parsed.
We then create concrete classes implementing the AbstractExpression interface. Each class represents an expression in our language. Each expression can be either a terminal or non-terminal expression:
- Terminal expressions are the basic elements of our language. We define these with a formal grammar.
- Non-terminal expressions (also called syntactic variables) are replaced by groups of terminal symbols based on the grammar rules. The non-terminal classes are generally implemented using a composite design pattern, while the terminal expressions are leaf objects.
A non-terminal expression may have one or more AbstractExpressions associated in it. This means it can be recursively interpreted. The interpretation process ends with a terminal expression that returns the result.
Representing each grammar rule as a class makes the language easy to implement, change or extend. We can even add extra methods to the classes (other than the interpret() method) to support extra functionality like validation and pretty printing.
The Interpreter
We also need to create an interpreter that deals with this grammar. All of the expressions need to be processed, and from them we build an Abstract Syntax Tree (AST). The AST is just a sentence defined using the syntax of our language. This sentence is the context. The interpreter then parses the AST and produces the required output.
To interpret the language, we call the interpret() method on each expression type. The interpret() method is passed the context. It then matches and evaluates the expressions, and returns a result. Each expression will affect the context, change its state, and either continue the interpretation or return the result. The context is reused by all expressions during the interpretation process.
Interpreter Pattern: Design Example
Going back to our first person shooter game, we’ve already created mechanised fighting units. We’ve also developed remote controls that allow us to command them to fight and move towards specific targets. (See the post on the Command pattern).
We now decide that it will be a great new feature for players to be able to type in a string of commands that the fighting units could interpret and run. A player could even strategise an entire troop deployment and attack plan, and save this as a small text file that could be run by the command interpreter.
We will have to define a grammar for this language. At first we’ll make it fairly small, with the possibility of expanding it later. What sort of commands would we like to run? Our first thoughts may lead us to a set of commands like:
with unit #number move x, y attack if enemy found retreat if health < 20% end with
Implementation
The code implementation of this language is somewhat long for one post, so we’ll leave this post on a cliff-hanger, and continue it in the next post.
Stay tuned, and watch out for the conclusion of the Interpreter pattern!
As always, please share your comments and questions.