标签：解释器 终结符 语言 文法 模式 抽象 设计模式 表达式

文法规则和抽象语法树

解释器模式描述了如何为简单的语言定义一个文法，如何在该语言中表示一个句子，以及如何解释这些句子。在正式分析解释器模式结构之前，先来学习如何表示一个语言的文法规则以及如何构造一棵抽象语法树。

例如对于表达式 “1十2+3一4十1”，其中包含了3个语言单位，可以使用如下文法规则来定义：

expression ::value | operation
operation ::=expression '+' expression | expression '-' expression
value ::= an integer //一个整数值

该文法规则包含 3 条语句。第一条表示表达式的组成方式，其中 value 和 operation 是后面两个语言单位的定义；每一条语句所定义的字符串如 operation 和 value 称为语言构造成分或语言单位；符号 "::=" 表示 “定义为” 的意思，其左边的语言单位通过右边来进行说明和定义，语言单位对应终结符表达式和非终结符表达式。例如，本规则中的 operation 是
非终结符表达式，它的组成元素仍然可以是表达式，可以进一步分解；而 value 是终结符表达式，它的组成元素是最基本的语言单位，不能再进行分解。

在文法规则定义中可以使用一些符号来表示不同的含义，例如使用 "|" 表示或，使用 "{" 和 "}" 表示组合，使用 "*" 表示出现 0 次或多次等，其中使用频率最高的符号是表示或关系的 "|"，例如，文法规则 "boolValue::=0|1" 表示终结符表达式 boolValue 的取值可以为 0 或者 1。

除了使用文法规则来定义一个语言外，还可以通过一种称之为 抽象语法树(AbstractSyntax Tree, AST) 的图形方式来直观地表示语言的构成，每一棵抽象语法树对应一个语言实例，例如加法/减法表达式语言中的语句 "1+2+3-4+1"，可以通过如图所示的抽象语法树表示：

在该抽象语法树中，可以通过终结符表达式 value 和非终结符表达式 operation 组成复杂的语句，每个文法规则的语言实例都可以表示为一个抽象语法树，即每一条具体的语句都可以用类似上图所示的抽象语法树来表示，在图中终结符表达式类的实例作为树的叶子节点，而非终结符表达式类的实例作为非叶子节点，它们可以将终结符表达式类的实例以及包含终结符和非终结符实例的子表达式作为其子节点。抽象语法树描述了如何构成一个复杂的句子，通过对抽象语法树的分析，可以识别出语言中的终结符类和非终结符类。

解释器模式概述

解释器模式是一种使用频率相对较低但学习难度较大的设计模式，它用于描述如何使用面向对象语言构成一个简单的语言解释器。在某些情况下，为了更好地描述某些特定类型的问题，可以创建一种新的语言，这种语言拥有自己的表达式和结构，即文法规则，这些问题的实例将对应为该语言中的句子。此时，可以使用解释器模式来设计这种新的语言。对解释器模式的学习能够加深对面向对象思想的理解，并且掌握编程语言中文法规则的解释过程。

解释器模式定义如下: 定义一个语言的文法，并且建立一个解释器来解释该语言中的句子，这里的 "语言" 是指使用规定格式和语法的代码。解释器模式是一种类行为型模式。

由于表达式可分为终结符表达式和非终结符表达式，因此解释器模式的结构与组合模式的结构有些类似，但在解释器模式中包含更多的组成元素，其结构如图所示:

从上图中可以看出，在解释器模式结构图中包含以下4个角色:

• AbstractExpression(抽象表达式)：在抽象表达式中声明了抽象的解释操作，它是所有终结符表达式和非终结符表达式的公共父类。
• TerminalExpression(终结符表达式)：是抽象表达式的子类，它实现了与文法中的终结符相关联的解释操作，在句子中的每一个终结符都是该类的一个实例。通常，在一个解释器模式中只有少数几个终结符表达式类，它们的实例可以通过非终结符表达式组成较为复杂的句子。
• NonterminalExpression(非终结符表达式)：也是抽象表达式的子类，它实现了文法中非终结符的解释操作，由于在非终结符表达式中可以包含终结符表达式，也可以继续包含非终结符表达式，因此其解释操作一般通过递归的方式来完成。
• Context(环境类)：环境类又称为上下文类，它用于存储解释器之外的一些全局信息，通常它临时存储了需要解释的语句。

在解释器模式中，每一种终结符和非终结符都有一个具体类与之对应，正因为使用类来表示每一条文法规则，所以系统将具有较好的灵活性和可扩展性。对于所有的终结符和非终结符，首先需要抽象出一个公共父类，即抽象表达式类，其典型代码如下：

class AbstractExpression {
public:
	virtual void interpret(Context ctx) = 0;
};

终结符表达式和非终结符表达式类都是抽象表达式类的子类。对于终结符表达式，其代码很简单，主要是对终结符元素的处理，其典型代码如下：

class TerminalExpression : public AbstractExpression {
public:
	void interpret(Context ctx) {
		// 终结符表达式的解释操作
	}
};

对于非终结符表达式，其代码相对比较复杂，因为可以通过非终结符将表达式组合成更加复杂的结构，对于包含两个操作的元素的非终结符表达式类，其典型代码如下：

class NoterminalExpression : public AbstractExpression {
public:
	NoterminalExpression(AbstractExpression* left, AbstractExpression* right) {
		_left = left;
		_right = right;
	}

	void interpret(Context ctx) {
		// 递归调用每一个组成部分的 interpret() 方法
		// 在递归调用时指定组成部分的连接方式，即非终结符的功能
	}

private:
	AbstractExpression* _left;
	AbstractExpression* _right;
};

除了上述用于表示表达式的类以外，通常在解释器模式中还提供了一个环境类 Context，用于存储一些全局信息。在 Context 中可以包含一个 std::map 或 std::vector 等类型的集合对象来存储一系列公共信息，例如变量名与值的映射关系(key/value)等，用于在进行具体的解释操作时从中获取相关信息。其典型代码片段如下：

class Context {
public:
	void assign(const string& key, const string& value) {
		// 往环境类中设值
	}

	string lookup(const string& key) {
		// 获取存储在环境类中的值
	}

private:
	map<string, string> hash;
};

当系统无须提供全局公共信息时可以省略环境类，也可根据实际情况决定是否需要环境类。

总结

解释器模式为自定义语言的设计和实现提供了一种解决方案，它用于定义一组文法规则并通过这组文法规则来解释语言中的句子。虽然解释器模式的使用频率不是特别高，但是它在正则表达式、XML 文档解释等领域还是得到了广泛使用。

优点

1. 易于改变和扩展文法。由于在解释器模式中使用类来表示语言的文法规则，因此可以通过继承等机制来改变或扩展文法。
2. 每一条文法规则都可以表示为一个类，因此可以方便地实现一个简单的语言。
3. 实现文法较为容易。在抽象语法树中每一个表达式节点类的实现方式都是相似的，这些类的代码编写都不会特别复杂，还可以通过一些工具自动生成节点类代码。
4. 增加新的解释表达式较为方便。如果用户需要增加新的解释表达式只需要对应增加一个新的终结符表达式或非终结符表达式类，原有表达式类代码无须修改，符合开闭原则。

缺点

1. 对于复杂文法难以维护。在解释器模式中，每一条规则至少需要定义一个类，因此如果一个语言包含太多文法规则，类的个数将会急剧增加，导致系统难以管理和维护，此时可以考虑使用语法分析程序等方式来取代解释器模式。
2. 执行效率较低。由于在解释器模式中使用了大量的循环和递归调用，因此在解释较为复杂的句子时其速度很慢，而且代码的调试过程也比较麻烦。

适用场景

1. 可以将一个需要解释执行的语言中的句子表示为一个抽象语法树。
2. 一些重复出现的问题可以用一种简单的语言来进行表达。
3. 一个语言的文法较为简单。
4. 执行效率不是关键问题。

高效的解释器通常不是通过直接解释抽象语法树来实现的，而是需要将它们转换成其他形式，使用解释器模式的执行效率并不高。

标签：解释器,终结符,语言,文法,模式,抽象,设计模式,表达式
From： https://www.cnblogs.com/tuilk/p/16936700.html