Wikibooks

Interpreter

< Computer Science Design Patterns

Flyweight Computer Science Design Patterns
Interpreter 		Iterator
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 BNF

The following Backus–Naur form 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 that contains Reverse Polish Notation expressions like: 

a b +
a b c + -
a b + c a - -
Implementation in C#

This structural code demonstrates the Interpreter patterns, which using a defined grammar, provides the interpreter that processes parsed statements. 

using System;
using System.Collections.Generic;

namespace OOP;

class Program
{
    static void Main()
    {
        var context = new Context();
        var input = new MyExpression();

        var expression = new OrExpression
        {
            Left = new EqualsExpression
            {
                Left = input,
                Right = new MyExpression { Value = "4" }
            },
            Right = new EqualsExpression
            {
                Left = input,
                Right = new MyExpression { Value = "four" }
            }
        };

        input.Value = "four";
        expression.Interpret(context);
        // Output: "true" 
        Console.WriteLine(context.Result.Pop());

        input.Value = "44";
        expression.Interpret(context);
        // Output: "false"
        Console.WriteLine(context.Result.Pop());
    }
}

class Context
{
    public Stack<string> Result = new Stack<string>();
}

interface IExpression
{
    void Interpret(Context context);
}

abstract class OperatorExpression : IExpression
{
    public IExpression Left { private get; set; }
    public IExpression Right { private get; set; }

    public void Interpret(Context context)
    {
        Left.Interpret(context);
        string leftValue = context.Result.Pop();

        Right.Interpret(context);
        string rightValue = context.Result.Pop();

        DoInterpret(context, leftValue, rightValue);
    }

    protected abstract void DoInterpret(Context context, string leftValue, string rightValue);
}

class EqualsExpression : OperatorExpression
{
    protected override void DoInterpret(Context context, string leftValue, string rightValue)
    {
        context.Result.Push(leftValue == rightValue ? "true" : "false");
    }
}

class OrExpression : OperatorExpression
{
    protected override void DoInterpret(Context context, string leftValue, string rightValue)
    {
        context.Result.Push(leftValue == "true" || rightValue == "true" ? "true" : "false");
    }
}

class MyExpression : IExpression
{
    public string Value { private get; set; }

    public void Interpret(Context context)
    {
        context.Result.Push(Value);
    }
}

Another example: 

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
public class Interpreter {
    @FunctionalInterface
    public interface Expr {
        int interpret(Map<String, Integer> context);
        
        static Expr number(int number) {
            return context -> number;
        }
        
        static Expr plus(Expr left, Expr right) {
            return context -> left.interpret(context) + right.interpret(context);
        }
        
        static Expr minus(Expr left, Expr right) {
            return context -> left.interpret(context) - right.interpret(context);
        }
        
        static Expr variable(String name) {
            return context -> context.getOrDefault(name, 0);
        }
    }
}

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

    private static Expr parseToken(String token, ArrayDeque<Expr> stack) {
        Expr left, right;
        switch(token) {
        case "+":
            // It's necessary to remove first the right operand from the stack
            right = stack.pop();
            // ...and then the left one
            left = stack.pop();
            return Expr.plus(left, right);
        case "-":
            right = stack.pop();
            left = stack.pop();
            return Expr.minus(left, right);
        default:
            return Expr.variable(token);
        }
    }
    public static Expr parse(String expression) {
        ArrayDeque<Expr> stack = new ArrayDeque<Expr>();
        for (String token : expression.split(" ")) {
            stack.push(parseToken(token, stack));
        }
        return stack.pop();
    }

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

    public static void main(final String[] args) {
        Expr expr = parse("w x z - +");
        Map<String, Integer> context = Map.of("w", 5, "x", 10, "z", 42);
        int result = expr.interpret(context);
        System.out.println(result);        // -27
    }
}

Another example: 

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 JavaScript

As JavaScript is dynamically typed, we do not implement an interface. 

// Nonterminal expression
class Plus {
    a;
    b;
    constructor(a, b) {
        this.a = a;
        this.b = b;
    }
    interpret(context) {
        return this.a.interpret(context) + this.b.interpret(context);
    }
}
// Nonterminal expression
class Minus {
    a;
    b;
    constructor(a, b) {
        this.a = a;
        this.b = b;
    }
    interpret(context) {
        return this.a.interpret(context) - this.b.interpret(context);
    }
}
// Nonterminal expression
class Times {
    a;
    b;
    constructor(a, b) {
        this.a = a;
        this.b = b;
    }
    interpret(context) {
        return this.a.interpret(context) * this.b.interpret(context);
    }
}
// Nonterminal expression
class Divide {
    a;
    b;
    constructor(a, b) {
        this.a = a;
        this.b = b;
    }
    interpret(context) {
        return this.a.interpret(context) / this.b.interpret(context);
    }
}
// Terminal expression
class Number {
    a;
    constructor(a, b) {
        this.a = a;
    }
    interpret(context) {
        return this.a; 
    }
}
// Terminal expression
class Variable {
    a;
    constructor(a) {
        this.a = a;
    }
    interpret(context) {
        return context[this.a] || 0;
    }
}
// Client
class Parse {
    context;
    constructor(context) {
        this.context = context;
    }
    parse(expression) {
        let tokens = expression.split(" ");
        let queue = [];
        for (let token of tokens) {
            switch (token) {
                case "+":
                    var b = queue.pop();
                    var a = queue.pop();
                    var exp = new Plus(a, b);
                    queue.push(exp);
                break;
                case "/":
                    var b = queue.pop();
                    var a = queue.pop();
                    var exp = new Divide(a, b);
                    queue.push(exp);
                break;
                case "*":
                    var b = queue.pop();
                    var a = queue.pop();
                    var exp = new Times(a, b);
                    queue.push(exp);
                break;
                case "-":
                    var b = queue.pop();
                    var a = queue.pop();
                    var exp = new Minus(a, b);
                    queue.push(exp);
                break;
                default:
                    if (isNaN(token)) {
                        var exp = new Variable(token);
                        queue.push(exp);   
                    } else {
                        var number = parseInt(token);
                        var exp = new Number(number);
                        queue.push(exp);
                    }
                break;
            } 
        }
        let main = queue.pop();
        return main.interpret(this.context);
    }
}
var res = new Parse({v: 45}).parse("16 v * 76 22 - -");
console.log(res)
//666
Implementation in PHP

Example 1: 

/**
 * AbstractExpression
 */
interface Expression
{
    public function interpret(array $context): int;
}

/**
 * TerminalExpression
 */
class TerminalExpression implements Expression
{
    /** @var string */
    private $name;

    public function __construct(string $name)
    {
        $this->name = $name;
    }

    public function interpret(array $context): int
    {
        return intval($context[$this->name]);
    }
}

/**
 * NonTerminalExpression
 */
abstract class NonTerminalExpression implements Expression
{
    /** @var Expression $left */
    protected $left;

    /** @var ?Expression $right */
    protected $right;

    public function __construct(Expression $left, ?Expression $right)
    {
        $this->left = $left;
        $this->right = $right;
    }

    abstract public function interpret(array $context): int;
    
    public function getRight()
    {
        return $this->right;
    }

    public function setRight($right): void
    {
        $this->right = $right;
    }
}

/**
 * NonTerminalExpression - PlusExpression
 */
class PlusExpression extends NonTerminalExpression
{
    public function interpret(array $context): int
    {
        return intval($this->left->interpret($context) + $this->right->interpret($context));
    }
}

/**
 * NonTerminalExpression - MinusExpression
 */
class MinusExpression extends NonTerminalExpression
{
    public function interpret(array $context): int
    {
        return intval($this->left->interpret($context) - $this->right->interpret($context));
    }
}

/**
 * Client
 */
class InterpreterClient
{
    protected function parseList(array &$stack, array $list, int &$index)
    {
        /** @var string $token */
        $token = $list[$index];

        switch($token) {
            case '-':
                list($left, $right) = $this->fetchArguments($stack, $list, $index);
                return new MinusExpression($left, $right);
            case '+':
                list($left, $right) = $this->fetchArguments($stack, $list, $index);
                return new PlusExpression($left, $right);
            default:
                return new TerminalExpression($token);
        }
    }

    protected function fetchArguments(array &$stack, array $list, int &$index): array
    {
        /** @var Expression $left */
        $left = array_pop($stack);
        /** @var Expression $right */
        $right = array_pop($stack);
        if ($right === null) {
            ++$index;
            $this->parseListAndPush($stack, $list, $index);
            $right = array_pop($stack);
        }

        return array($left, $right);
    }

    protected function parseListAndPush(array &$stack, array $list, int &$index)
    {
        array_push($stack, $this->parseList($stack, $list, $index));
    }

    protected function parse(string $data): Expression
    {
        $stack = [];
        $list = explode(' ', $data);
        for ($index=0; $index<count($list); $index++) {
            $this->parseListAndPush($stack, $list, $index);
        }

        return array_pop($stack);
    }

    public function main()
    {
        $data = "u + v - w + z";
        $expr = $this->parse($data);
        $context = ['u' => 3, 'v' => 7, 'w' => 35, 'z' => 9];
        $res = $expr->interpret($context);
        echo "result: $res" . PHP_EOL;
    }
}

// test.php

function loadClass($className)
{
    require_once __DIR__ . "/$className.php";
}

spl_autoload_register('loadClass');

(new InterpreterClient())->main();
//result: -16

Example 2: Based on the example above with another realization of the client. 

/**
 * Client
 */
class InterpreterClient
{
    public function parseToken(string $token, array &$stack): Expression
    {
        switch($token) {
            case '-':
                /** @var Expression $left */
                $left = array_pop($stack);
                /** @var Expression $right */
                $right = array_pop($stack);
                return new MinusExpression($left, $right);
            case '+':
                /** @var Expression $left */
                $left = array_pop($stack);
                /** @var Expression $right */
                $right = array_pop($stack);
                return new PlusExpression($left, $right);
            default:
                return new TerminalExpression($token);
        }
    }

    public function parse(string $data): Expression
    {
        $unfinishedData = null;
        $stack = [];
        $list = explode(' ', $data);
        foreach ($list as $token) {
            $data = $this->parseToken($token, $stack);
            if (
                ($unfinishedData instanceof NonTerminalExpression) &&
                ($data instanceof TerminalExpression)
            ) {
                $unfinishedData->setRight($data);
                array_push($stack, $unfinishedData);
                $unfinishedData = null;
                continue;
            }
            if ($data instanceof NonTerminalExpression) {
                if ($data->getRight() === null) {
                    $unfinishedData = $data;
                    continue;
                }
            }
            array_push($stack, $data);
        }

        return array_pop($stack);
    }

    public function main()
    {
        $data = "u + v - w + z";
        $expr = $this->parse($data);
        $context = ['u' => 3, 'v' => 7, 'w' => 35, 'z' => 9];
        $res = $expr->interpret($context);
        echo "result: $res" . PHP_EOL;
    }
}

Example 3: 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).


 

To do:
Add more illustrations.


  Flyweight Computer Science Design Patterns
Interpreter 		Iterator  


You have questions about this page?
Ask it here:


Create a new page on this book:


Retrieved from "https://en.wikibooks.org/w/index.php?title=Computer_Science_Design_Patterns/Interpreter&oldid=4287814"