(learn&think)

不浮躁，不自傲，学习，思考，总结

浅谈设计模式二十: 解释器模式(Interpreter)

| Comments

1 实例

以简单计算器为实例,计算器做加减乘除有一套自己的语言(堆栈形式),可以直接计算,那么用语法树来解释并计算计算器语言如何设计呢?

2 解释器模式(Interpreter)

2.1 目的

给予一种编程语言，为它的语法定义一种表现形式并包括一个解释器使用这个形式来解释语言中的语句。

2.2 实现

这里只以加法和减法为实例,实现简单的解释器模式来解释计算器的堆栈语言来计算结果。代码实例在这里。

2.2.1 抽象表达式类

声明一个抽象解释器操作。 

class Expression {
 public:
  virtual ~Expression() {}
  virtual int Interpret() = 0;
};

2.2.2 末端表达式类：数字表达式

int NumberExpression::Interpret() {
  return number_;
}

2.2.3 非末端表达式：加法表达式

实现加法运算的解释器操作，若被解释的对象是非末端表达式，继续递归调用非末端表达式解释器操作。 

AddExpression::AddExpression(Expression *left, Expression *right) :
    left_expression_(left), right_expression_(right) {
}

int AddExpression::Interpret() {
  return left_expression_->Interpret() + right_expression_->Interpret();
}

2.2.4 非末端表达式：减法表达式

同加法表达式一样，实现减法运算的解释器操作。 

SubtractExpression::SubtractExpression(Expression *left, Expression *right) :
    left_expression_(left), right_expression_(right) {
}

int SubtractExpression::Interpret() {
  return left_expression_->Interpret() - right_expression_->Interpret();
}

2.2.5 表达式阅读器

包含解释器的全局信息，读取用户表达式，使用解释器解释整个用户表达式语言。 

Expression* TokenReader::ReadToken(vector<string> *token_vector) {
  return ReadNextToken(token_vector);
}

Expression* TokenReader::ReadNextToken(vector<string> *token_vector) {
  string token = token_vector->at(0);
  if (token == "+" || token == "-"){
    return ReadNonTerminal(token_vector);
  } else {
    int number = atoi(token.c_str());
    token_vector->erase(token_vector->begin());
    return new NumberExpression(number);
  }
}

Expression* TokenReader::ReadNonTerminal(vector<string> *token_vector) {
  string token = token_vector->at(0);
  token_vector->erase(token_vector->begin());
  Expression *left = ReadNextToken(token_vector);
  Expression *right = ReadNextToken(token_vector);
  if (token == "+") {
    return new AddExpression(left, right);
  } else if (token == "-") {
    return new SubtractExpression(left, right);
  }
  return new NullExpression();
}

3 总结

3.1 解释器模式(Interpreter)结构

3.2 组成

  • 抽象表达式类（AbstractExpression）声明一个抽象解释器操作，它并在抽象语法书中被所有节点所共有。
  • 末端表达式类（TerminalExpression）
    1. 实现与在语法中与末端符号相关的解释操作。
    2. 在语句中每个末端符号都需要个实例。
  • 非末端表达式（NonterminalExpression）
    1. 在语法中每条规则 \(R ::= R_1R_2 .. R_n\) 都需要一个这样的类。
    2. 从 \(R_1\) 到 \(R_n\) 到的每个符号都维护抽象表达式（AbstractExpression）类型的实力变量。
    3. 实现在语法中非末端表达式的解释操作。解释器通常在 \(R_1\) 到 \(R_n\) 表示的变量中递归的自我调用。
  • 场景类（Context）包含解释器的全局信息。
  • 客户（Client）
    1. 建立（或被给予）表示语法定义的语言中特殊语句的抽象语法树。这个抽象语法书由非末端表示式类（NonterminalExpression）和末端表示式（TerminalExpression)类装配而成。
    2. 调用解释器操作。

3.3 应用场景

当一种语言需要解释并且你能把语言内语句表示成一颗抽象的语法树时，使用解释器模式。解释器模式最好应用在当：

  • 语法是简单的。对于复杂的语法，组成语法的类层次变得庞大而不可控。在这种情况下，如分析程序生成器之类的工具会是更好的选择。它们能不建立抽象语法树来分析表达式，从而节省空间和可能的时间。
  • 效率不是关键的考虑因素。最高效的解释器往往不以直接解释解析树来实现，而是先把它们转换成另外种形式。比如，正则表达式通常被转换成状态机。但即使如此，这个转换器也可以由解析起模式来实现，所以这个模式还是比较实用的。

3.4 缺点

复杂的语法很难维护。解释器模式为语法中的每条规则定义至少一个类（以 BNF 定义的语法规则可能需要多个类）。因此包含许多规则的语法很难管理和维护。其他设计模式可以应用来消除这个问题（参考 Implementation）。但是当语法非常复杂时，比如解析器或编译生成起之类的其他技术更适合。

Comments