Interpreter Design Pattern in Java

1. Overview

In this tutorial, we’ll introduce one of the behavioral GoF design patterns – the Interpreter.

At first, we’ll give an overview of its purpose and explain the problem it tries to solve.

Then, we’ll have a look at Interpreter’s UML diagram and implementation of the practical example.

2. Interpreter Design Pattern

In short, the pattern defines the grammar of a particular language in an object-oriented way which can be evaluated by the interpreter itself.

Having that in mind, technically we could build our custom regular expression, a custom DSL interpreter or we could parse any of the human languages, build abstract syntax trees and then run the interpretation.

These are only some of the potential use cases, but if we think for a while, we could find even more usages of it, for example in our IDEs, since they’re continually interpreting the code we’re writing and thus supplying us with priceless hints.

The interpreter pattern generally should be used when the grammar is relatively simple.

Otherwise, it might become hard to maintain.

3. UML Diagram

Above diagram shows two main entities: the Context and the Expression.

Now, any language needs to be expressed in some way, and the words (expressions) are going to have some meaning based on the given context.

AbstractExpression defines one abstract method which takes the context as a parameter. Thanks to that, each expression will affect the context, change its state and either continue the interpretation or return the result itself.

Therefore, the context is going to be the holder of the global state of processing, and it’s going to be reused during the whole interpretation process.

So what’s the difference between the TerminalExpression and NonTerminalExpression?

A NonTerminalExpression may have one or more other AbstractExpressions associated in it, therefore it can be recursively interpreted. In the end, the process of interpretation has to finish with a TerminalExpression that will return the result.

It’s worth to note that NonTerminalExpression is a composite.

Finally, the role of the client is to create or use an already created abstract syntax tree, which is nothing more than a sentence defined in the created language.

4. Implementation

To show the pattern in action, we’ll build a simple SQL-like syntax in an object-oriented way, which will be then interpreted and return us the result.

First, we’ll define Select, From, and Where expressions, build a syntax tree in the client’s class and run the interpretation.

The Expression interface will have the interpret method:

List<String> interpret(Context ctx);

Next, we define the first expression, the Select class:

class Select implements Expression {

    private String column;
    private From from;

    // constructor

    @Override
    public List<String> interpret(Context ctx) {
        ctx.setColumn(column);
        return from.interpret(ctx);
    }
}

It gets the column name to be selected and another concrete Expression of type From as parameters in the constructor.

Note that in the overridden interpret() method it sets the state of the context and passes the interpretation further to another expression along with the context.

That way, we see that it’s a NonTerminalExpression.

Another expression is the From class:

class From implements Expression {

    private String table;
    private Where where;

    // constructors

    @Override
    public List<String> interpret(Context ctx) {
        ctx.setTable(table);
        if (where == null) {
            return ctx.search();
        }
        return where.interpret(ctx);
    }
}

Now, in SQL the where clause is optional, therefore this class is either a terminal or a non-terminal expression.

If the user decides not to use a where clause, the From expression it’s going to be terminated with the ctx.search() call and return the result. Otherwise, it’s going to be further interpreted.

The Where expression is again modifying the context by setting the necessary filter and terminates the interpretation with search call:

class Where implements Expression {

    private Predicate<String> filter;

    // constructor

    @Override
    public List<String> interpret(Context ctx) {
        ctx.setFilter(filter);
        return ctx.search();
    }
}

For the example, the Context class holds the data which is imitating the database table.

Note that it has three key fields which are modified by each subclass of Expression and the search method:

class Context {

    private static Map<String, List<Row>> tables = new HashMap<>();

    static {
        List<Row> list = new ArrayList<>();
        list.add(new Row("John", "Doe"));
        list.add(new Row("Jan", "Kowalski"));
        list.add(new Row("Dominic", "Doom"));

        tables.put("people", list);
    }

    private String table;
    private String column;
    private Predicate<String> whereFilter;

    // ... 

    List<String> search() {

        List<String> result = tables.entrySet()
          .stream()
          .filter(entry -> entry.getKey().equalsIgnoreCase(table))
          .flatMap(entry -> Stream.of(entry.getValue()))
          .flatMap(Collection::stream)
          .map(Row::toString)
          .flatMap(columnMapper)
          .filter(whereFilter)
          .collect(Collectors.toList());

        clear();

        return result;
    }
}

After the search is done, the context is clearing itself, so the column, table, and filter are set to defaults.

That way each interpretation won’t affect the other.

5. Testing

For testing purposes, let’s have a look at the InterpreterDemo class:

public class InterpreterDemo {
    public static void main(String[] args) {

        Expression query = new Select("name", new From("people"));
        Context ctx = new Context();
        List<String> result = query.interpret(ctx);
        System.out.println(result);

        Expression query2 = new Select("*", new From("people"));
        List<String> result2 = query2.interpret(ctx);
        System.out.println(result2);

        Expression query3 = new Select("name", 
          new From("people", 
            new Where(name -> name.toLowerCase().startsWith("d"))));
        List<String> result3 = query3.interpret(ctx);
        System.out.println(result3);
    }
}

First, we build a syntax tree with created expressions, initialize the context and then run the interpretation. The context is reused, but as we showed above, it cleans itself after each search call.

By running the program, the output should be as follow:

[John, Jan, Dominic]
[John Doe, Jan Kowalski, Dominic Doom]
[Dominic]

6. Downsides

When the grammar is getting more complex, it becomes harder to maintain.

It can be seen in the presented example. It’d be reasonably easy to add another expression, like Limit, yet it won’t be too easy to maintain if we’d decide to keep extending it with all other expressions.

7. Conclusion

The interpreter design pattern is great for relatively simple grammar interpretation, which doesn’t need to evolve and extend much.

In the example above, we showed that it is possible to build a SQL-like query in an object-oriented way with the help of the interpreter pattern.

Finally, you can find this pattern usage in JDK, particularly, in java.util.Pattern, java.text.Format or java.text.Normalizer.