Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
In software engineering, a design pattern is a general reusable solution to a commonly occurring problem within a given context in software design. A design pattern is not a finished design that can be transformed directly into code. It is a description or template for how to solve a problem that...
. The interpreter pattern specifies how to evaluate sentences in a language. The basic idea is to have a class
Class (computer science)
In object-oriented programming, a class is a construct that is used as a blueprint to create instances of itself – referred to as class instances, class objects, instance objects or simply objects. A class defines constituent members which enable these class instances to have state and behavior...
for each symbol (terminal or nonterminal) in a specialized computer language. The syntax tree
Abstract syntax tree
In computer science, an abstract syntax tree , or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code. The syntax is 'abstract' in the sense that it...
of a sentence in the language is an instance of the composite
Composite pattern
In software engineering, the composite pattern is a partitioning design pattern. The composite pattern describes that a group of objects are to be treated in the same way as a single instance of an object. The intent of a composite is to "compose" objects into tree structures to represent...
pattern and is used to evaluate (interpret) the sentence.
Reverse Polish notation is a mathematical notation wherein every operator follows all of its operands, in contrast to Polish notation, which puts the operator in the prefix position. It is also known as Postfix notation and is parenthesis-free as long as operator arities are fixed...
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.
import java.util.HashMap;
interface Expression {
public int interpret(HashMap variables);
}
class Number implements Expression {
private int number;
public Number(int number) { this.number = number; }
public int interpret(HashMap variables) { return number; }
}
class Plus implements Expression {
Expression leftOperand;
Expression rightOperand;
public Plus(Expression left, Expression right) {
leftOperand = left;
rightOperand = right;
}
public int interpret(HashMap variables) {
return leftOperand.interpret(variables) + rightOperand.interpret(variables);
}
}
class Minus implements Expression {
Expression leftOperand;
Expression rightOperand;
public Minus(Expression left, Expression right) {
leftOperand = left;
rightOperand = right;
}
public int interpret(HashMap variables) {
return leftOperand.interpret(variables) - rightOperand.interpret(variables);
}
}
class Variable implements Expression {
private String name;
public Variable(String name) { this.name = name; }
public int interpret(HashMap variables) {
if(nullvariables.get(name)) return 0; //Either return new Number(0).
return variables.get(name).interpret(variables);
}
}
While the interpreter pattern does not address parsing a parser is provided for completeness.
import java.util.HashMap;
import java.util.Stack;
class Evaluator implements Expression {
private Expression syntaxTree;
public Evaluator(String expression) {
Stack expressionStack = new Stack;
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(HashMap context) {
return syntaxTree.interpret(context);
}
}
Finally evaluating the expression "w x z - +" with w = 5, x = 10, and z = 42.
import java.util.HashMap;
public class InterpreterExample {
public static void main(String[] args) {
String expression = "w x z - +";
Evaluator sentence = new Evaluator(expression);
HashMap variables = new HashMap;
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);
}
}
Design Patterns: Elements of Reusable Object-Oriented Software is a software engineering book describing recurring solutions to common problems in software design. The book's authors are Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides with a foreword by Grady Booch. The authors are...
Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...
