Your Guide to Design Patterns – Interpreter Pattern (Part 2)

Design Patterns - Interpreter Pattern

Last week we introduced the Interpreter pattern, which allows us to implement a simple language to use inside an application.

We need to define our simple language, and then we define a class to represent each rule of the language. We also implement an interpreter that operates on instances of these classes. This interpreter parses and executes the sentences of the language.

Interpreter Pattern: Design Example

As explained last week, we’ve decided that it will be a great new feature for our first person shooter game for players to be able to strategise and set up an entire troop deployment and attack plan for the mechanised fighting units. The players could type the commands directly in a pop-up dialog window, or to save the commands in a text file that could be run by the command interpreter.

We have already thought that a series of commands could look like the following:

with unit #number
   move x, y
   attack if enemy found
   retreat if health < 20%
end with

This will be part of the grammar of our language. Let’s start with a simplified version, with the possibility of expanding it later:

unit #number move x y

We had previously created a FightingUnit interface with a fight() method and some methods for movement. To support our new language elements, we’ll add a few more methods to the FightingUnit interface:

public interface FightingUnit {
   public void fight();
   public void turn(int degrees);
   public void advance();
   public void advance(int x, int y);
   public void retreat();
   public void retreat(int x, int y);
}

A number of concrete FightingUnit classes have been used in previous posts such as the Command pattern, so they won’t be included here.

We’ll also need a factory of some description to look up and return a FightingUnit object. A very simple stub class follows:

public class FightingUnitFactory {

   public static FightingUnit lookup(int unitNumber) {
      return new MechanisedFightingRobot("Robot", unitNumber);
   }
}

Expressions

For the sake of simplicity, we’ll call each separate token an *expression*. We’ll then create classes representing these expressions. We can see that the #number (without the hash sign), and the x and y co-ordinates for the position will be numbers, and the other tokens will be commands.

We create an interface to represent the operations of our language expressions. Currently we’ll limit it to the interpret() method as defined in the Interpreter pattern:

public interface Expression {
    public Object interpret();
}

Representing each grammar rule as a class makes the language easy to implement, change or extend. We can add extra methods to the classes in addition to the interpret() method to support any further functionality we need.

We’ll represent numbers with a NumberExpression class:

public class NumberExpression implements Expression {

   private int number;

   public NumberExpression(int number) {
      this.number = number;
   }

   public NumberExpression(String number) {
      this.number = Integer.parseInt(number);
   }

   @Override
   public Object interpret() {
      return this.number;
   }
}

We’ll represent the unitadvanceretreat, and fight expressions with their own Expression class implementations. Only the UnitExpression and the AdvanceExpression classes follow. The others are similar.

public class UnitExpression implements Expression {

   private Expression unitNumber;

   public UnitExpression(Expression unitNumber) {
      this.unitNumber = unitNumber;
   }

   @Override
   public Object interpret() {
      int unit = (Integer) unitNumber.interpret();
      FightingUnit fightingUnit = FightingUnitFactory.lookup(unit);
      return fightingUnit;
   }
}

public class AdvanceExpression implements Expression {

   private Expression xExp, yExp;
   private FightingUnit fightingUnit;

   public AdvanceExpression(FightingUnit fightingUnit, 
         Expression xExp, Expression yExp) {
      this.fightingUnit = fightingUnit;
      this.xExp = xExp;
      this.yExp = yExp;
   }

   @Override
   public Object interpret() {
      int x = (Integer)xExp.interpret();
      int y = (Integer)yExp.interpret();
      fightingUnit.advance(x, y);
      return Void.TYPE;
   }
}

The Interpreter

The Interpreter pattern specifies that we must create the language element classes with an interpret() method. The pattern does not specify how the language parser/interpreter must be implemented.

To interpret the language, we call the interpret() method on each expression type. The interpret() method is passed a context, then matches and evaluates the expressions, and returns a result. The context is an input stream containing the language sentences that must be parsed.

An unsophisticated language parser follows. It’s more important here to show the invocation of the interpret() methods than to write a more sophisticated parser. Let’s leave that as an exercise to you, the reader…

public class ExpressionParser {

   // input string is the language sentence (the context) to be parsed
   public static void parse(String input) {

      FightingUnit fightingUnit = null; 

      // splitting the string into separate tokens
      String[] token = input.split(" ");

      // brute force approach to parsing
      // first token must be "unit", followed by a number
      if (token[0].equals("unit"))
         fightingUnit = (FightingUnit) new UnitExpression(
            new NumberExpression(token[1])).interpret();
      else {
         System.out.printf("Syntax error!%n");
         return;
      }

      // third token must be "advance" or "retreat"
      // followed by two numbers, OR "fight"
      if (token[2].equals("advance"))
         new AdvanceExpression(fightingUnit, 
            new NumberExpression(token[3]), 
            new NumberExpression(token[4])).interpret();
      else if (token[2].equals("retreat"))
         new RetreatExpression(fightingUnit, 
            new NumberExpression(token[3]), 
            new NumberExpression(token[4])).interpret();
      else if (token[2].equals("fight"))
         new FightExpression(fightingUnit).interpret();
      else {
         System.out.printf("Syntax error!%n");
         return;
      }
   }
}

The parse() method is static in this example, but to support sequences of commands which could modify the global context string, it would be more flexible to make it an instance method, and instantiate a new ExpressionParser object when needed.

The client code to call the parser is very simple.

public class Client {

   public static void main(String args[]) {

      String input;

      input = "unit 12345 advance 20 30";
      ExpressionParser.parse(input);

      input = "unit 12345 retreat 520 130";
      ExpressionParser.parse(input);

      input = "unit 12345 fight";
      ExpressionParser.parse(input);

      // some syntax errors
      input = "abc 12345 xyz";  
      ExpressionParser.parse(input);
   }
}

Summary

The Interpreter pattern allows us to create a mini-language to implement some program logic such as parsing regular expressions and interpreting mathematical expressions.

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 good examples of the Interpreter pattern are the Unified Expression Language (javax.el API) used in JSP and JSF, and the Spring Expression Language (SpEL).

What’s next?

Next week, we’ll examine the last remaining GoF design pattern, the Visitor pattern. Stay tuned and keep learning!

As always, please share your comments and questions.

Leave a Comment

Your email address will not be published. Required fields are marked *

Code like a Java Guru!

Thank You

We're Excited!

Thank you for completing the form. We're excited that you have chosen to contact us about training. We will process the information as soon as we can, and we will do our best to contact you within 1 working day. (Please note that our offices are closed over weekends and public holidays.)

Don't Worry

Our privacy policy ensures your data is safe: Incus Data does not sell or otherwise distribute email addresses. We will not divulge your personal information to anyone unless specifically authorised by you.

If you need any further information, please contact us on tel: (27) 12-666-2020 or email info@incusdata.com

How can we help you?

Let us contact you about your training requirements. Just fill in a few details, and we’ll get right back to you.

Your Java tip is on its way!

Check that incusdata.com is an approved sender, so that your Java tips don’t land up in the spam folder.

Our privacy policy means your data is safe. You can unsubscribe from these tips at any time.