Interpreter

A Stellar Hiker

2015-01-02

C++, Design Pattern

解释器

当你需要实现一个简单的语言时，就使用解释器模式定义语法的类，并用一个解释器解释句子。每个语法规则都用一个类代表。

适用性

当有一个语言需要解释执行，并且你可将该语言中的句子表示为一个抽象语法树时，可使用解释器模式。最适用于文法简单并且效率并不是关键问题时。

结构

Interpreter Class

AbstractExpression - 声明一个抽象的解释操作，这个接口为抽象语法树中所有的节点所共享。
TerminalExpression - 实现与文法中的终结符相关联的解释操作。一个句子中的每个终结符需要该类的一个实例。
NonterminalExpression - 对文法中的每一条规则 $R::=R_1R_2...R_n$ 都需要一个NonterminalExpression类。为从 $R_1$ 到 $R_n$ 的每个符号都维护一个AbstractExpression类型的实例变量。为文法中的非终结符实现解释操作。解释一般要递归地调用表示 $R_1$ 到 $R_n$ 的那些对象的解释操作。
Context - 包含解释器之外的一些全局信息。
Client - 构建（或被给定）表示该文法定义的语言中一个特定的句子的抽象语法树。该抽象语法树由NonterminalExpression和TerminalExpression的实例装配而成。调用解释操作。

协作：
Client创建（或被给定）一个句子，它是NonterminalExpression和TerminalExpression的实例的一个抽象语法树，然后初始化上下文并调用解释操作。
每一非终结符表达式节点定义相应子表达式的解释操作。而各终结符表达式的解释操作构成了递归的基础。
每一节点的解释操作用上下文来存储和访问解释器的状态。

示例

/*
在C++中实现对布尔表达式进行操作和求值。
在这个语言中终结符是布尔变量，即常量true和false。非终结符表示包含运算符and,or和not的布尔表达式。
文法定义如下：
BooleanExp ::= VariableExp | Constant | orExp | AndExp | NotExp | '(' BooleanExp ')'
AndExp ::= BooleanExp 'and' BooleanExp
OrExp ::= BooleanExp 'or' BooleanExp
NotExp ::= 'not' BooleanExp
Constant ::= 'true' | 'false'
VariableExp ::= 'A' | 'B' | ... | 'X' | 'Y' | 'Z' 
在这里我们定义布尔表达式上的两个操作。求值和替换。
*/
#include <cstring>
#include <iostream>
#include <unordered_map>
class VariableExp;
//---------------------------------------------------
// Context定义从变量到布尔值的一个映射。true和false。
class Context
{
public:
	bool look_up(const char* name) const;
	void assign(VariableExp* var, bool val);
protected:
	std::unordered_map<const char*, bool> m_inner;
};
//---------------------------------------------------
// BooleanExp为所有定义一个布尔表达式的类定义了一个接口。
class BooleanExp
{
public:
	BooleanExp(){}
	virtual ~BooleanExp(){}
	virtual bool evaluate(Context&) = 0;
	virtual BooleanExp* replace(const char*, BooleanExp&) = 0;
	virtual BooleanExp* copy() const = 0;
};
//---------------------------------------------------
// Constant表示常量。
class Constant : public BooleanExp
{
public:
	Constant(bool val){m_value = val;}
	virtual bool evaluate(Context& aContext)
	{
		return m_value;
	}
	virtual BooleanExp* replace(const char* name, BooleanExp& exp)
	{
		return exp.copy();
	}
	virtual BooleanExp* copy() const
	{
		return new Constant(m_value);
	}
protected:
	bool m_value;
};
//---------------------------------------------------
// VariableExp表示一个有名变量。
class VariableExp : public BooleanExp
{
public:
	VariableExp(const char* name)	// 以变量的名字作为参数。
	{
		m_name = strdup(name);
	}
	virtual ~VariableExp(){}
	const char* get_name() const {return m_name;}
	virtual bool evaluate(Context& aContext)	// 求一个变量的值，返回他在当前上下文中的值。
	{
		return aContext.look_up(m_name);
	}
	virtual BooleanExp* replace(const char* name, BooleanExp& exp)	// 用一个表达式替换一个变量时，检查是不是确是自己。
	{
		if (strcmp(name, m_name) == 0) {return exp.copy();}
		else {return new VariableExp(m_name);}
	}
	virtual BooleanExp* copy() const	// 拷贝一个变量返回一个新的VariableExp。
	{
		return new VariableExp(m_name);
	}
protected:
	char* m_name;
};
//---------------------------------------------------
// 表示由两个布尔表达式与操作得到的与表达式。
class AndExp : public BooleanExp
{
public:
	AndExp(BooleanExp* op1, BooleanExp* op2)
	{
		m_operand1 = op1;
		m_operand2 = op2;
	}
	virtual ~AndExp(){}
	virtual bool evaluate(Context& aContext)	// 求操作数的值的逻辑与。
	{
		return m_operand1->evaluate(aContext) && m_operand2->evaluate(aContext);
	}
	virtual BooleanExp* replace(const char* name, BooleanExp& exp)	// 递归调用操作数的replace。
	{
		return new AndExp(m_operand1->replace(name, exp), m_operand2->replace(name, exp));
	}
	virtual BooleanExp* copy() const	// 递归调用操作数的copy。
	{
		return new AndExp(m_operand1->copy(), m_operand2->copy());
	}
protected:
	BooleanExp* m_operand1;
	BooleanExp* m_operand2;
};
//---------------------------------------------------
// 表示由两个布尔表达式与操作得到的或表达式。
class OrExp : public BooleanExp
{
public:
	OrExp(BooleanExp* op1, BooleanExp* op2)
	{
		m_operand1 = op1;
		m_operand2 = op2;
	}
	virtual ~OrExp(){}
	virtual bool evaluate(Context& aContext)	// 求操作数的值的逻辑或。
	{
		return m_operand1->evaluate(aContext) || m_operand2->evaluate(aContext);
	}
	virtual BooleanExp* replace(const char* name, BooleanExp& exp)	// 递归调用操作数的replace。
	{
		return new OrExp(m_operand1->replace(name, exp), m_operand2->replace(name, exp));
	}
	virtual BooleanExp* copy() const	// 递归调用操作数的copy。
	{
		return new OrExp(m_operand1->copy(), m_operand2->copy());
	}
protected:
	BooleanExp* m_operand1;
	BooleanExp* m_operand2;
};
//---------------------------------------------------
// 表示由一个布尔表达式与操作的到的取非表达式。
class NotExp : public BooleanExp
{
public:
	NotExp(BooleanExp* op) {m_operand = op;}
	virtual bool evaluate(Context& aContext)	// 求操作数的值的逻辑或。
	{
		return !(m_operand->evaluate(aContext));
	}
	virtual BooleanExp* replace(const char* name, BooleanExp& exp)	// 递归调用操作数的replace。
	{
		return new NotExp(m_operand->replace(name, exp));
	}
	virtual BooleanExp* copy() const	// 递归调用操作数的copy。
	{
		return new NotExp(m_operand->copy());
	}
protected:
	BooleanExp* m_operand;
};
//---------------------------------------------------
// Context的实现
bool Context::look_up( const char* name ) const
{
	if (!name) return false;
	if (m_inner.count(name))
	{
		return m_inner.at(name);
	}
	return false;
}
void Context::assign( VariableExp* var, bool val )
{
	if (!var) return;
	m_inner.insert(std::make_pair(var->get_name(), val));
}
//---------------------------------------------------
int main()
{
	// (true and x) or (y and (not x))
	BooleanExp* expression;
	Context context;
	VariableExp* x = new VariableExp("x");
	VariableExp* y = new VariableExp("y");
	expression = new OrExp(new AndExp(new Constant(true), x), new AndExp(y, new NotExp(x)));
	context.assign(x, false);
	context.assign(y, true);
	bool result = expression->evaluate(context);
	std::cout << (result ? "true" : "false") << std::endl;
	// 用新的表达式替换变量y。
	VariableExp* z = new VariableExp("z");
	NotExp not_z(z);
	BooleanExp* replacement = expression->replace("Y", not_z);
	context.assign(z, true);
	result = replacement->evaluate(context);
	std::cout << (result ? "true" : "false") << std::endl;
	system("Pause");
}

优点

将每一个语法规则表示成一个类，方便于实现语言。
因为语法由许多类表示，所以你可以轻易地改变或扩展此语言。
通过在类结构中加入新的方法，可以在解释的同时增加新的行为，例如打印格式的美化或者进行复杂的程序验证。

用途和缺点

当你需要实现一个简单的语言时，使用解释器。
当你有一个简单的语法，而且简单比效率更重要时，使用解释器。
可以处理脚本语言和编程语言。
当语法规则的数目太大时，这个模式可能会变得非常繁杂。在这种情况下，使用解析器/编译器的产生器可能更合适。

解释器

适用性

结构

示例

优点

用途和缺点

相关模式