411 REFERENCE · Wikibooks
Computer Science Design Patterns/Interpreter
Reference material by Wikibooks contributors. This retains its source identity and is not 411 news reporting.
reading 25 29 Jan, 2014 Add more illustrations. Flyweight Iterator 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).