Bob
Have a question related to this hub?
Alice
Got something to say related to this hub?
Share it here.
 | This article needs additional citations for verification. (November 2008) |
In computer programming, the interpreter pattern is a design pattern that specifies how to evaluate sentences in a language. The basic idea is to have a class for each symbol (terminal or nonterminal) in a specialized computer language. The syntax tree of a sentence in the language is an instance of the composite pattern and is used to evaluate (interpret) the sentence for a client.[1]: 243 See also Composite pattern.
The Interpreter [2] design pattern is one of the twenty-three well-known GoF design patterns that describe how to solve recurring design problems to design flexible and reusable object-oriented software, that is, objects that are easier to implement, change, test, and reuse.
Source:[3]
When a problem occurs very often, it could be considered to represent it as a sentence in a simple language (Domain Specific Languages) so that an interpreter can solve the problem by interpreting the sentence.
For example, when many different or complex search expressions must be specified. Implementing (hard-wiring) them directly into a class is inflexible because it commits the class to particular expressions and makes it impossible to specify new expressions or change existing ones independently from (without having to change) the class.
Expression class hierarchy and implementing an interpret() operation.Expression instances.interpret() on the AST.The expression objects are composed recursively into a composite/tree structure that is called
abstract syntax tree (see Composite pattern).
The Interpreter pattern doesn't describe how
to build an abstract syntax tree. This can
be done either manually by a client or automatically by a parser.
See also the UML class and object diagram below.
In the above UML class diagram, the Client class refers to the common AbstractExpression interface for interpreting an expression
interpret(context).
The TerminalExpression class has no children and interprets an expression directly.
The NonTerminalExpression class maintains a container of child expressions
(expressions) and forwards interpret requests
to these expressions.
The object collaboration diagram
shows the run-time interactions: The Client object sends an interpret request to the abstract syntax tree.
The request is forwarded to (performed on) all objects downwards the tree structure.
The NonTerminalExpression objects (ntExpr1,ntExpr2) forward the request to their child expressions.
The TerminalExpression objects (tExpr1,tExpr2,…) perform the interpretation directly.
This C++23 implementation is based on the pre C++98 sample code in the book.
import std;
using String = std::string;
template <typename K, typename V>
using TreeMap = std::map<K, V>;
template <typename T>
using UniquePtr = std::unique_ptr<T>;
class BooleanExpression {
public:
BooleanExpression() = default;
virtual ~BooleanExpression() = default;
virtual bool evaluate(Context&) = 0;
virtual UniquePtr<BooleanExpression> replace(String&, BooleanExpression&) = 0;
virtual UniquePtr<BooleanExpression> copy() const = 0;
};
class VariableExpression;
class Context {
private:
TreeMap<const VariableExpression*, bool> m;
public:
Context() = default;
[[nodiscard]]
bool lookup(const VariableExpression* key) const {
return m.at(key);
}
void assign(VariableExpression* key, bool value) {
m[key] = value;
}
};
class VariableExpression : public BooleanExpression {
private:
String name;
public:
VariableExpression(const String& name):
name{name} {}
virtual ~VariableExpression() = default;
[[nodiscard]]
virtual bool evaluate(Context& aContext) const {
return aContext.lookup(this);
}
[[nodiscard]]
virtual UniquePtr<VariableExpression> replace(const String& name, BooleanExp& exp ) {
if (name == this->name) {
return std::make_unique<VariableExpression>(exp.copy());
} else {
return std::make_unique<VariableExpression>(name);
}
}
[[nodiscard]]
virtual UniquePtr<BooleanExpression> copy() const {
return std::make_unique<BooleanExpression>(name);
}
VariableExpression(const VariableExpression&) = delete;
VariableExpression& operator=(const VariableExp&) = delete;
};
class AndExpression : public BooleanExpression {
private:
UniquePtr<BooleanExpression> operand1;
UniquePtr<BooleanExpression> operand2;
public:
AndExpression(UniquePtr<BooleanExpression> op1, UniquePtr<BooleanExpression> op2):
operand1{std::move(op1)}, operand{std::move(op2)} {}
virtual ~AndExpression() = default;
[[nodiscard]]
virtual bool evaluate(Context& aContext) const {
return operand1->evaluate(aContext) && operand2->evaluate(aContext);
}
[[nodiscard]]
virtual UniquePtr<BooleanExpression> replace(const String& name, BooleanExpression& exp) const {
return std::make_unique<AndExpression>(
operand1->replace(name, exp),
operand2->replace(name, exp)
);
}
[[nodiscard]]
virtual UniquePtr<BooleanExpression> copy() const {
return std::make_unique<AndExpression>(operand1->copy(), operand2->copy());
}
AndExpression(const AndExpression&) = delete;
AndExpression& operator=(const AndExpression&) = delete;
};
int main(int argc, char* argv[]) {
UniquePtr<BooleanExpression> expression;
Context context;
UniquePtr<VariableExpression> x = std::make_unique<VariableExpression>("X");
UniquePtr<VariableExpression> y = std::make_unique<VariableExpression>("Y");
UniquePtr<BooleanExpression> expression; = std::make_unique<AndExpression>(x, y);
context.assign(x.get(), false);
context.assign(y.get(), true);
bool result = expression->evaluate(context);
std::println("{}", result);
context.assign(x.get(), true);
context.assign(y.get(), true);
result = expression->evaluate(context);
std::println("{}", result);
return 0;
}
The program output is:
0
1
{{cite book}}: CS1 maint: multiple names: authors list (link)
