Computer Science Design Patterns/Interpreter

Table of content

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

Examples

The following Reverse Polish notation example illustrates the interpreter pattern. The grammar: expression ::= plus | minus | variable | number plus ::= expression expression '+' minus ::= expression expression '-' variable ::= 'a' | 'b' | 'c' | ... | 'z' digit ::= '0' | '1' | ... '9' number ::= digit | digit number defines a language which contains reverse Polish expressions like:

a b + a b c + - a b + c a - - Following the interpreter pattern there is a class for each grammar rule.

Cost

This pattern is not expensive. It dramatically reduces the business code so there is only few code to handle.

Creation

If the code already exists, this pattern is a little expensive.

Maintenance

This pattern is very easy to maintain. There is no additional cost due to the pattern.

Removal

This pattern is easy to remove with refactoring operations from your IDE.

Advises

Use the Interpreter term to indicate the use of the pattern to the other developers.

Implementations

Implementation in C#

using System;
using System.Collections.Generic;
 
namespace Interpreter
{
    class Program
    {
        interface IExpression
        {
            int Interpret(Dictionary<string, int> variables);
        }
 
        class Number : IExpression
        {
            public int number;
            public Number(int number) { this.number = number; }
            public int Interpret(Dictionary<string, int> variables) { return number; }
        }
 
        abstract class BasicOperation : IExpression
        {
            IExpression leftOperator, rightOperator;
 
            public BasicOperation(IExpression left, IExpression right)
            {
                leftOperator = left;
                rightOperator = right;
            }
 
            public int Interpret(Dictionary<string, int> variables)
            {
                return Execute(leftOperator.Interpret(variables), rightOperator.Interpret(variables));
            }
 
            abstract protected int Execute(int left, int right);
        }
 
        class Plus : BasicOperation
        {
            public Plus(IExpression left, IExpression right) : base(left, right) { }
 
            protected override int Execute(int left, int right)
            {
                return left + right;
            }
        }
 
        class Minus : BasicOperation
        {
            public Minus(IExpression left, IExpression right) : base(left, right) { }
 
            protected override int Execute(int left, int right)
            {
                return left - right;
            }
        }
 
        class Variable : IExpression
        {
            private string name;
 
            public Variable(string name) { this.name = name; }
 
            public int Interpret(Dictionary<string, int> variables)
            {
                return variables[name];
            }
        }
 
        class Evaluator
        {
            private IExpression syntaxTree;
 
            public Evaluator(string expression)
            {
                Stack<IExpression> stack = new Stack<IExpression>();
                foreach (string token in expression.Split(' '))
                {
                    if (token.Equals("+"))
                        stack.Push(new Plus(stack.Pop(), stack.Pop()));
                    else if (token.Equals("-")){
                        IExpression right = stack.Pop();
                        IExpression left = stack.Pop();
                        stack.Push(new Minus(left, right));
                    }else
                        stack.Push(new Variable(token));
                }
                syntaxTree = stack.Pop();
            }
 
            public int Evaluate(Dictionary<string, int> context)
            {
                return syntaxTree.Interpret(context);
            }
        }
 
        static void Main(string[] args)
        {
            Evaluator evaluator = new Evaluator("w x z - +");
            Dictionary<string, int> values = new Dictionary<string,int>();
            values.Add("w", 5);
            values.Add("x", 10);
            values.Add("z", 42);
            Console.WriteLine(evaluator.Evaluate(values));
        }
    }
}

Implementation in Java

import java.util.Map;
interface Expression {
    public int interpret(Map<String, Expression> variables);
}

import java.util.Map;
class Number implements Expression {
    private int number;
    public Number(int number) {
        this.number = number;
    }
    public int interpret(Map<String, Expression> variables) {
        return number;
    }
}

import java.util.Map;
class Plus implements Expression {
    Expression leftOperand;
    Expression rightOperand;
    public Plus(Expression left, Expression right) {
        leftOperand = left;
        rightOperand = right;
    }
    public int interpret(Map<String, Expression> variables) {
        return leftOperand.interpret(variables) + rightOperand.interpret(variables);
    }
}

import java.util.Map;
class Minus implements Expression {
    Expression leftOperand;
    Expression rightOperand;
    public Minus(Expression left, Expression right) {
        leftOperand = left;
        rightOperand = right;
    }
    public int interpret(Map<String, Expression> variables)  {
        return leftOperand.interpret(variables) - rightOperand.interpret(variables);
    }
}

import java.util.Map;
class Variable implements Expression {
    private String name;
    public Variable(String name) {
        this.name = name;
    }
    public int interpret(Map<String, Expression> variables) {
        if (variables.get(name) == null) {
            // Either return new Number(0).
            return 0;
        } else {
            return variables.get(name).interpret(variables);
        }
    }
}

While the interpreter pattern does not address parsing a parser is provided for completeness.

import java.util.Map;
import java.util.Stack;
class Evaluator implements Expression {
    private Expression syntaxTree;
 
    public Evaluator(String expression) {
        Stack<Expression> expressionStack = new Stack<Expression>();
        for (String token : expression.split(" ")) {
            if  (token.equals("+")) {
                Expression subExpression = new Plus(expressionStack.pop(), expressionStack.pop());
                expressionStack.push( subExpression );
            }
            else if (token.equals("-")) {
                // it's necessary remove first the right operand from the stack
                Expression right = expressionStack.pop();
                // ..and after the left one
                Expression left = expressionStack.pop();
                Expression subExpression = new Minus(left, right);
                expressionStack.push( subExpression );
            }
            else                        
                expressionStack.push( new Variable(token) );
        }
        syntaxTree = expressionStack.pop();
    }
 
    public int interpret(Map<String,Expression> context) {
        return syntaxTree.interpret(context);
    }
}

Finally evaluating the expression "w x z - +" with w = 5, x = 10, and z = 42.

import java.util.Map;
import java.util.HashMap;
public class InterpreterExample {
    public static void main(String[] args) {
        String expression = "w x z - +";
        Evaluator sentence = new Evaluator(expression);
        Map<String,Expression> variables = new HashMap<String,Expression>();
        variables.put("w", new Number(5));
        variables.put("x", new Number(10));
        variables.put("z", new Number(42));
        int result = sentence.interpret(variables);
        System.out.println(result);
    }
}

Implementation in PHP

In a file we have the classes and the interface, defining the logic of the program (and applying the Interpreter pattern). Now the expr.php file:

<?php
    interface expression{
        public function interpret (array $variables);
        public function __toString();
    }
    class number implements expression{
        private $number;
        public function __construct($number){
            $this->number = intval($number);
        }
        public function interpret(array $variables){
            return $this->number;
        }
        public function __toString(){
            return (string) $this->number;
        }
    }
    class plus implements expression{
        private $left_op;
        private $right_op;
        public function __construct(expression $left, expression $right){
            $this->left_op = $left;
            $this->right_op = $right;
        }
        public function interpret(array $variables){
            return ($this->left_op->interpret($variables) + $this->right_op->interpret($variables));
        }
        public function __toString(){
            return (string) ("Left op: {$this->left_op} + Right op: {$this->right_op}\n");
        }
    }
    class minus implements expression{
        private $left_op;
        private $right_op;
        public function __construct(expression $left, expression $right){
            $this->left_op = $left;
            $this->right_op = $right;
        }
        public function interpret(array $variables){
            return ($this->left_op->interpret($variables) - $this->right_op->interpret($variables));
        }
        public function __toString(){
            return (string) ("Left op: {$this->left_op} - Right op: {$this->right_op}\n");
        }
    }
    class variable implements expression{
        private $name;
        public function __construct($name){
            $this->name = $name;
        }
        public function interpret(array $variables){
            if(!isset($variables[$this->name]))
                return 0;
            return $variables[$this->name]->interpret($variables);
        }
        public function __toString(){
            return (string) $this->name;
        }
    }
?>

And the evaluate.php:

<?php
    require_once('expr.php');
    class evaluator implements expression{
        private $syntaxTree;
        public function __construct($expression){
            $stack = array();
            $tokens = explode(" ", $expression);
            foreach($tokens as $token){
                if($token == "+"){
                    $right = array_pop($stack);
                    $left = array_pop($stack);
                    array_push($stack, new plus($left, $right));
                }
                else if($token == "-"){
                    $right = array_pop($stack);
                    $left = array_pop($stack);
                    array_push($stack, new minus($left, $right));
                }else if(is_numeric($token)){
                    array_push($stack, new number($token));
                }else{
                    array_push($stack, new variable($token));
                }
            }
            $this->syntaxTree = array_pop($stack);
        }
        public function interpret(array $context){
            return $this->syntaxTree->interpret($context);
        }
        public function __toString(){
            return "";
        }
    }
    // main code
    // works for it:
    $expression = "5 10 42 - +";
    // or for it:
    //$expression = "w x z - +";
    $variables = array();
    $variables['w'] = new number("5");
    $variables['x'] = new number("10");
    $variables['z'] = new number("42");
    print ("Evaluating expression {$expression}\n");
    $sentence = new evaluator($expression);
    $result = $sentence->interpret($variables);
    print $result . "\n";
?>

And you can run on a terminal by typing php5 -f evaluator.php (or putting it on a web application).

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.