I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Design Patterns Uncovered: The Interpreter Pattern

05.11.2010
| 23750 views |
  • submit to reddit

Today's pattern is the Interpreter pattern, which defines a grammatical representation for a language and provides an interpreter to deal with this grammar.

Interpreter in the Real World 

The first example of interpreter that comes to mind, is a translator, allowing people to understand a foreign language. Perhaps musicians are a better example: musical notation is our grammar here, with musicians acting as interpreters, playing the music.

Design Patterns Refcard
For a great overview of the most popular design patterns, DZone's Design Patterns Refcard is the best place to start. 

The Interpreter Pattern

The Interpreter pattern is known as a behavioural pattern, as it's used to manage algorithms, relationships and responsibilities between objects.. The definition of Interpreter as provided in the original Gang of Four book on Design Patterns states: 

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

The following diagram shows how the interpreter pattern is modelled.

 

Context contains information that is global to the interpreter. The AbstractExpression provides an interface for executing an operation. TerminalExpression implements the interpret interface associated with any terminal expressions in the defined grammar. 

The Client either builds the Abstract Syntax Tree, or the AST is passed through to the client. An AST is composed of both TerminalExpressions and NonTerminalExpressions. The client will kick off the interpret operation. Note that the syntax tree is usually implemented using the Composite pattern

The pattern allows you to decouple the underlying expressions from the grammar. 

When Would I Use This Pattern?

The Interpreter pattern should be used when you have a simple grammar that can be represented as an Abstract Syntax Tree. This is the more obvious use of the pattern. A more interesting and useful application of Interpreter is when you need a program to produce different types of output, such as a report generator. 

So How Does It Work In Java?

I'll use a simple example to illustrate this pattern. We're going to create our own DSL for searching Amazon. To do this, we'll need to have a context that uses an Amazon web service to run our queries.

//Context 
public class InterpreterContext
{
//assume web service is setup
private AmazonWebService webService;

public InterpreterContext(String endpoint)
{
//create the web service.
}

public ArrayList<Movie> getAllMovies()
{
return webService.getAllMovies();
}

public ArrayList<Book> getAllBooks()
{
return webService.getAllBooks();

}
}

Next, we'll need to create an abstract expression: 

//Abstract Expression 
public abstract class AbstractExpression
{
public abstract String interpret( InterpreterContext context);
}

We'll have many different expressions to interpret our queries. For illustration,let's create just one: 

//Concrete Expression 
public class BookAuthorExpression extends AbstractExpression
{

private String searchString;

public BookAuthorExpression(String searchString)
{
this.searchString = searchString;
}

public String interpret(InterpreterContext context)
{
ArrayList<Book> books = context.getAllBooks();
StringBuffer result = new StringBuffer();
for(Book book: books)
{
if(book.getAuthor().equalsIgnoreCase(searchString))
{
result.append(book.toString());
}
}
return result;

}

}

Finally, we need a client to drive all of this. Let's assume that our language is of the following type of syntax: 

books by author 'author name'

The client will determine which expression to use to get our results: 

//client 
public class AmazonClient
{

private InterpreterContext context;

public AmazonClient(InterpreterContext context)
{
this.context = context;
}

/**
* Interprets a string input of the form
* movies | books by title | year | name '<string>'
*/
public String interpret(String expression)
{
//we need to parse the string to determine which expression to use

AbstractExpression exp = null;

String[] stringParts = expression.split(" ");

String main = stringParts[0];
String sub = stringParts[2];

//get the query part
String query = expression.substring(expression.firstIndexOf("'"), expression.lastIndexOf("'"));


if(main.equals("books"))
{
if(sub.equals("title")
{
exp = new BookTitleExpression(query);
}
if(sub.equals("year")
{
exp = new BookYearExpression(query);
}
}
else if(main.equals("movie"))
{
//similar statements to create movie expressions
}


if(exp != null)
{
exp.interpret(context);
}


}


public static void main(String[] args)
{
InterpreterContext context = new InterpreterContext("http://aws.amazon.com/");
AmazonClient client = new AmazonClient();

//run a query
String result = client.interpret("books by author 'John Connolly'");

System.out.println(result);
}

}

I admit the example is a bit simple, and you would probably have a more intelligent context, but that should give you the idea of how this pattern works.

Watch Out for the Downsides

Efficiency is a big concern for any implementation of this pattern. Introducing your own grammar requires extensive error checking, which will be time consuming for the programmer to implement, and needs careful design in order to run efficiently at runtime. Also, as the grammar becomes more complicated, the maintainence effort is increased. 

Other Articles in This Series
The Observer Pattern
The Adapter Pattern
The Facade Pattern
The Factory Method Pattern
The Abstract Factory Pattern
The Singleton Pattern
The Strategy Pattern
The Visitor Pattern

The Decorator Pattern
The Proxy Pattern
The Command Pattern
The Chain of Responsibility Pattern

Next Up

As we've mentioned the Composite pattern in this article when dealing with Abstract Syntax Trees, I'll cover Composite in the next article.

Tags:

Comments

Reginaldo L. Ru... replied on Tue, 2010/05/11 - 9:52am

Great article James,

but I'm little bit confused.

Shouldn't  "BookAuthorExpression" extends "AbstractExpression"?

Close Read more >>   Options >>  Visit Answers.com
 

James Sugrue replied on Tue, 2010/05/11 - 10:40am in response to: Reginaldo L. Russinholi

You're right. I've fixed that now. Thanks for spotting that 

Florian Over replied on Wed, 2010/05/12 - 3:27am

Nice Article and great series.

But:
Is there a special reason you choose the concrete ArrayList instead of the interface List in the method signature?

 

James Sugrue replied on Wed, 2010/05/12 - 10:53am in response to: Florian Over

Thanks Florian

No reason at all - it would have been better to use List :)

James

 

John Katethon replied on Thu, 2010/06/03 - 9:34am

hello,

line 60. should be  AmazonClient client = new AmazonClient(context); instead of AmazonClient client = new AmazonClient();

 

JKT

Marvin Sance replied on Wed, 2013/04/03 - 1:20am

how many non terminals or productions should have a grammar to be considerer as "simple grammar"?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.