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 defines a language which contains reverse Polish expressions like:
plus ::= expression expression '+'
minus ::= expression expression '-'
variable ::= 'a' | 'b' | 'c' | ... | 'z'
digit ::= '0' | '1' | ... '9'
number ::= digit | digit number a b + Following the interpreter pattern there is a class for each grammar rule.
a b c + -
a b + c a - -
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
Interpreterterm 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.
usingSystem;usingSystem.Collections.Generic;namespaceOOP;classProgram{staticvoidMain(){varcontext=newContext();varinput=newMyExpression();varexpression=newOrExpression{Left=newEqualsExpression{Left=input,Right=newMyExpression{Value="4"}},Right=newEqualsExpression{Left=input,Right=newMyExpression{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());}}classContext{publicStack<string>Result=newStack<string>();}interfaceIExpression{voidInterpret(Contextcontext);}abstractclassOperatorExpression:IExpression{publicIExpressionLeft{privateget;set;}publicIExpressionRight{privateget;set;}publicvoidInterpret(Contextcontext){Left.Interpret(context);stringleftValue=context.Result.Pop();Right.Interpret(context);stringrightValue=context.Result.Pop();DoInterpret(context,leftValue,rightValue);}protectedabstractvoidDoInterpret(Contextcontext,stringleftValue,stringrightValue);}classEqualsExpression:OperatorExpression{protectedoverridevoidDoInterpret(Contextcontext,stringleftValue,stringrightValue){context.Result.Push(leftValue==rightValue?"true":"false");}}classOrExpression:OperatorExpression{protectedoverridevoidDoInterpret(Contextcontext,stringleftValue,stringrightValue){context.Result.Push(leftValue=="true"||rightValue=="true"?"true":"false");}}classMyExpression:IExpression{publicstringValue{privateget;set;}publicvoidInterpret(Contextcontext){context.Result.Push(Value);}}Another example:
usingSystem;usingSystem.Collections.Generic;namespaceInterpreter{classProgram{interfaceIExpression{intInterpret(Dictionary<string,int>variables);}classNumber:IExpression{publicintnumber;publicNumber(intnumber){this.number=number;}publicintInterpret(Dictionary<string,int>variables){returnnumber;}}abstractclassBasicOperation:IExpression{IExpressionleftOperator,rightOperator;publicBasicOperation(IExpressionleft,IExpressionright){leftOperator=left;rightOperator=right;}publicintInterpret(Dictionary<string,int>variables){returnExecute(leftOperator.Interpret(variables),rightOperator.Interpret(variables));}abstractprotectedintExecute(intleft,intright);}classPlus:BasicOperation{publicPlus(IExpressionleft,IExpressionright):base(left,right){}protectedoverrideintExecute(intleft,intright){returnleft+right;}}classMinus:BasicOperation{publicMinus(IExpressionleft,IExpressionright):base(left,right){}protectedoverrideintExecute(intleft,intright){returnleft-right;}}classVariable:IExpression{privatestringname;publicVariable(stringname){this.name=name;}publicintInterpret(Dictionary<string,int>variables){returnvariables[name];}}classEvaluator{privateIExpressionsyntaxTree;publicEvaluator(stringexpression){Stack<IExpression>stack=newStack<IExpression>();foreach(stringtokeninexpression.Split(' ')){if(token.Equals("+"))stack.Push(newPlus(stack.Pop(),stack.Pop()));elseif(token.Equals("-")){IExpressionright=stack.Pop();IExpressionleft=stack.Pop();stack.Push(newMinus(left,right));}elsestack.Push(newVariable(token));}syntaxTree=stack.Pop();}publicintEvaluate(Dictionary<string,int>context){returnsyntaxTree.Interpret(context);}}staticvoidMain(string[]args){Evaluatorevaluator=newEvaluator("w x z - +");Dictionary<string,int>values=newDictionary<string,int>();values.Add("w",5);values.Add("x",10);values.Add("z",42);Console.WriteLine(evaluator.Evaluate(values));}}}Implementation in Java
publicclassInterpreter{@FunctionalInterfacepublicinterfaceExpr{intinterpret(Map<String,Integer>context);staticExprnumber(intnumber){returncontext->number;}staticExprplus(Exprleft,Exprright){returncontext->left.interpret(context)+right.interpret(context);}staticExprminus(Exprleft,Exprright){returncontext->left.interpret(context)-right.interpret(context);}staticExprvariable(Stringname){returncontext->context.getOrDefault(name,0);}}}While the interpreter pattern does not address parsing, a parser is provided for completeness.
privatestaticExprparseToken(Stringtoken,ArrayDeque<Expr>stack){Exprleft,right;switch(token){case"+":// It's necessary to remove first the right operand from the stackright=stack.pop();// ...and then the left oneleft=stack.pop();returnExpr.plus(left,right);case"-":right=stack.pop();left=stack.pop();returnExpr.minus(left,right);default:returnExpr.variable(token);}}publicstaticExprparse(Stringexpression){ArrayDeque<Expr>stack=newArrayDeque<Expr>();for(Stringtoken:expression.split(" ")){stack.push(parseToken(token,stack));}returnstack.pop();}Finally evaluating the expression "w x z - +" with w = 5, x = 10, and z = 42.
publicstaticvoidmain(finalString[]args){Exprexpr=parse("w x z - +");Map<String,Integer>context=Map.of("w",5,"x",10,"z",42);intresult=expr.interpret(context);System.out.println(result);// -27}}Another example:
importjava.util.Map;interfaceExpression{publicintinterpret(Map<String,Expression>variables);}importjava.util.Map;classNumberimplementsExpression{privateintnumber;publicNumber(intnumber){this.number=number;}publicintinterpret(Map<String,Expression>variables){returnnumber;}}importjava.util.Map;classPlusimplementsExpression{ExpressionleftOperand;ExpressionrightOperand;publicPlus(Expressionleft,Expressionright){leftOperand=left;rightOperand=right;}publicintinterpret(Map<String,Expression>variables){returnleftOperand.interpret(variables)+rightOperand.interpret(variables);}}importjava.util.Map;classMinusimplementsExpression{ExpressionleftOperand;ExpressionrightOperand;publicMinus(Expressionleft,Expressionright){leftOperand=left;rightOperand=right;}publicintinterpret(Map<String,Expression>variables){returnleftOperand.interpret(variables)-rightOperand.interpret(variables);}}importjava.util.Map;classVariableimplementsExpression{privateStringname;publicVariable(Stringname){this.name=name;}publicintinterpret(Map<String,Expression>variables){if(variables.get(name)==null){// Either return new Number(0).return0;}else{returnvariables.get(name).interpret(variables);}}}While the interpreter pattern does not address parsing a parser is provided for completeness.
importjava.util.Map;importjava.util.Stack;classEvaluatorimplementsExpression{privateExpressionsyntaxTree;publicEvaluator(Stringexpression){Stack<Expression>expressionStack=newStack<Expression>();for(Stringtoken:expression.split(" ")){if(token.equals("+")){ExpressionsubExpression=newPlus(expressionStack.pop(),expressionStack.pop());expressionStack.push(subExpression);}elseif(token.equals("-")){// it's necessary remove first the right operand from the stackExpressionright=expressionStack.pop();// ..and after the left oneExpressionleft=expressionStack.pop();ExpressionsubExpression=newMinus(left,right);expressionStack.push(subExpression);}elseexpressionStack.push(newVariable(token));}syntaxTree=expressionStack.pop();}publicintinterpret(Map<String,Expression>context){returnsyntaxTree.interpret(context);}}Finally evaluating the expression "w x z - +" with w = 5, x = 10, and z = 42.
importjava.util.Map;importjava.util.HashMap;publicclassInterpreterExample{publicstaticvoidmain(String[]args){Stringexpression="w x z - +";Evaluatorsentence=newEvaluator(expression);Map<String,Expression>variables=newHashMap<String,Expression>();variables.put("w",newNumber(5));variables.put("x",newNumber(10));variables.put("z",newNumber(42));intresult=sentence.interpret(variables);System.out.println(result);}}Implementation in JavaScript
As JavaScript is dynamically typed, we do not implement an interface.
// Nonterminal expressionclassPlus{a;b;constructor(a,b){this.a=a;this.b=b;}interpret(context){returnthis.a.interpret(context)+this.b.interpret(context);}}// Nonterminal expressionclassMinus{a;b;constructor(a,b){this.a=a;this.b=b;}interpret(context){returnthis.a.interpret(context)-this.b.interpret(context);}}// Nonterminal expressionclassTimes{a;b;constructor(a,b){this.a=a;this.b=b;}interpret(context){returnthis.a.interpret(context)*this.b.interpret(context);}}// Nonterminal expressionclassDivide{a;b;constructor(a,b){this.a=a;this.b=b;}interpret(context){returnthis.a.interpret(context)/this.b.interpret(context);}}// Terminal expressionclassNumber{a;constructor(a,b){this.a=a;}interpret(context){returnthis.a;}}// Terminal expressionclassVariable{a;constructor(a){this.a=a;}interpret(context){returncontext[this.a]||0;}}// ClientclassParse{context;constructor(context){this.context=context;}parse(expression){lettokens=expression.split(" ");letqueue=[];for(lettokenoftokens){switch(token){case"+":varb=queue.pop();vara=queue.pop();varexp=newPlus(a,b);queue.push(exp);break;case"/":varb=queue.pop();vara=queue.pop();varexp=newDivide(a,b);queue.push(exp);break;case"*":varb=queue.pop();vara=queue.pop();varexp=newTimes(a,b);queue.push(exp);break;case"-":varb=queue.pop();vara=queue.pop();varexp=newMinus(a,b);queue.push(exp);break;default:if(isNaN(token)){varexp=newVariable(token);queue.push(exp);}else{varnumber=parseInt(token);varexp=newNumber(number);queue.push(exp);}break;}}letmain=queue.pop();returnmain.interpret(this.context);}}varres=newParse({v:45}).parse("16 v * 76 22 - -");console.log(res)//666Implementation in PHP
Example 1:
/** * AbstractExpression */interfaceExpression{publicfunctioninterpret(array$context):int;}/** * TerminalExpression */classTerminalExpressionimplementsExpression{/** @var string */private$name;publicfunction__construct(string$name){$this->name=$name;}publicfunctioninterpret(array$context):int{returnintval($context[$this->name]);}}/** * NonTerminalExpression */abstractclassNonTerminalExpressionimplementsExpression{/** @var Expression $left */protected$left;/** @var ?Expression $right */protected$right;publicfunction__construct(Expression$left,?Expression$right){$this->left=$left;$this->right=$right;}abstractpublicfunctioninterpret(array$context):int;publicfunctiongetRight(){return$this->right;}publicfunctionsetRight($right):void{$this->right=$right;}}/** * NonTerminalExpression - PlusExpression */classPlusExpressionextendsNonTerminalExpression{publicfunctioninterpret(array$context):int{returnintval($this->left->interpret($context)+$this->right->interpret($context));}}/** * NonTerminalExpression - MinusExpression */classMinusExpressionextendsNonTerminalExpression{publicfunctioninterpret(array$context):int{returnintval($this->left->interpret($context)-$this->right->interpret($context));}}/** * Client */classInterpreterClient{protectedfunctionparseList(array&$stack,array$list,int&$index){/** @var string $token */$token=$list[$index];switch($token){case'-':list($left,$right)=$this->fetchArguments($stack,$list,$index);returnnewMinusExpression($left,$right);case'+':list($left,$right)=$this->fetchArguments($stack,$list,$index);returnnewPlusExpression($left,$right);default:returnnewTerminalExpression($token);}}protectedfunctionfetchArguments(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);}returnarray($left,$right);}protectedfunctionparseListAndPush(array&$stack,array$list,int&$index){array_push($stack,$this->parseList($stack,$list,$index));}protectedfunctionparse(string$data):Expression{$stack=[];$list=explode(' ',$data);for($index=0;$index<count($list);$index++){$this->parseListAndPush($stack,$list,$index);}returnarray_pop($stack);}publicfunctionmain(){$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.phpfunctionloadClass($className){require_once__DIR__."/$className.php";}spl_autoload_register('loadClass');(newInterpreterClient())->main();//result: -16Example 2: Based on the example above with another realization of the client.
/** * Client */classInterpreterClient{publicfunctionparseToken(string$token,array&$stack):Expression{switch($token){case'-':/** @var Expression $left */$left=array_pop($stack);/** @var Expression $right */$right=array_pop($stack);returnnewMinusExpression($left,$right);case'+':/** @var Expression $left */$left=array_pop($stack);/** @var Expression $right */$right=array_pop($stack);returnnewPlusExpression($left,$right);default:returnnewTerminalExpression($token);}}publicfunctionparse(string$data):Expression{$unfinishedData=null;$stack=[];$list=explode(' ',$data);foreach($listas$token){$data=$this->parseToken($token,$stack);if(($unfinishedDatainstanceofNonTerminalExpression)&&($datainstanceofTerminalExpression)){$unfinishedData->setRight($data);array_push($stack,$unfinishedData);$unfinishedData=null;continue;}if($datainstanceofNonTerminalExpression){if($data->getRight()===null){$unfinishedData=$data;continue;}}array_push($stack,$data);}returnarray_pop($stack);}publicfunctionmain(){$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:
<?phpinterfaceexpression{publicfunctioninterpret(array$variables);publicfunction__toString();}classnumberimplementsexpression{private$number;publicfunction__construct($number){$this->number=intval($number);}publicfunctioninterpret(array$variables){return$this->number;}publicfunction__toString(){return(string)$this->number;}}classplusimplementsexpression{private$left_op;private$right_op;publicfunction__construct(expression$left,expression$right){$this->left_op=$left;$this->right_op=$right;}publicfunctioninterpret(array$variables){return($this->left_op->interpret($variables)+$this->right_op->interpret($variables));}publicfunction__toString(){return(string)("Left op: {$this->left_op} + Right op: {$this->right_op}\n");}}classminusimplementsexpression{private$left_op;private$right_op;publicfunction__construct(expression$left,expression$right){$this->left_op=$left;$this->right_op=$right;}publicfunctioninterpret(array$variables){return($this->left_op->interpret($variables)-$this->right_op->interpret($variables));}publicfunction__toString(){return(string)("Left op: {$this->left_op} - Right op: {$this->right_op}\n");}}classvariableimplementsexpression{private$name;publicfunction__construct($name){$this->name=$name;}publicfunctioninterpret(array$variables){if(!isset($variables[$this->name]))return0;return$variables[$this->name]->interpret($variables);}publicfunction__toString(){return(string)$this->name;}}?>And the evaluate.php:
<?phprequire_once('expr.php');classevaluatorimplementsexpression{private$syntaxTree;publicfunction__construct($expression){$stack=array();$tokens=explode(" ",$expression);foreach($tokensas$token){if($token=="+"){$right=array_pop($stack);$left=array_pop($stack);array_push($stack,newplus($left,$right));}elseif($token=="-"){$right=array_pop($stack);$left=array_pop($stack);array_push($stack,newminus($left,$right));}elseif(is_numeric($token)){array_push($stack,newnumber($token));}else{array_push($stack,newvariable($token));}}$this->syntaxTree=array_pop($stack);}publicfunctioninterpret(array$context){return$this->syntaxTree->interpret($context);}publicfunction__toString(){return"";}}// main code// works for it:$expression="5 10 42 - +";// or for it://$expression = "w x z - +";$variables=array();$variables['w']=newnumber("5");$variables['x']=newnumber("10");$variables['z']=newnumber("42");print("Evaluating expression {$expression}\n");$sentence=newevaluator($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).
