零基础设计模式——行为型模式 - 解释器模式

第四部分：行为型模式 - 解释器模式 (Interpreter Pattern)

接下来，我们探讨行为型模式中的解释器模式。这是一个相对不常用但特定场景下非常有用的模式，它为语言的文法定义一个解释器，该解释器使用该表示来解释语言中的句子。

• 核心思想：给定一个语言，定义它的文法的一种表示，并定义一个解释器，这个解释器使用该表示来解释语言中的句子。

解释器模式 (Interpreter Pattern)

“给定一个语言，定义它的文法 (Grammar) 的一种表示，并定义一个解释器 (Interpreter)，这个解释器使用该表示来解释语言中的句子。” (Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language.)

想象一下你要计算一个简单的数学表达式，比如 5 + 2 - 1。

• 语言 (Language)：这里指的是简单的算术表达式语言，包含数字和加减运算符。
• 文法 (Grammar)：定义了这种语言的规则，例如一个表达式可以是一个数字，或者是一个表达式后跟一个运算符再跟另一个表达式。
• 句子 (Sentence)：就是具体的表达式，如 5 + 2 - 1。
• 表示 (Representation)：我们可以用树形结构（抽象语法树 - AST）来表示这个表达式。例如，- 是根节点，左子节点是 +，+ 的左子节点是 5，右子节点是 2，- 的右子节点是 1。
• 解释器 (Interpreter)：一个能够遍历这个树形结构并计算出最终结果（在这个例子中是 6）的组件。

解释器模式通常用于处理简单的、具有明确文法的语言。对于复杂的语言（如成熟的编程语言），通常会使用更专业的工具（如解析器生成器 ANTLR, YACC/Bison）。

1. 目的 (Intent)

解释器模式的主要目的：

1. 定义语言文法的表示：为语言中的每条规则创建一个类。
2. 解释语言中的句子：通过构建一个抽象语法树 (AST) 来表示句子，然后遍历 AST 来执行解释操作。
3. 易于改变和扩展文法：由于每条文法规则都由一个类表示，因此可以通过增加新的类来添加新的规则，或者修改现有类来改变规则。

2. 生活中的例子 (Real-world Analogy)

• 乐谱和演奏：

  • 语言：音乐符号语言（五线谱）。
  • 文法：音符、休止符、节拍、调号等规则。
  • 句子：一段乐谱。
  • 表示：乐谱本身就是一种结构化的表示。
  • 解释器：音乐家或播放器，他们读取乐谱并演奏出音乐。

• 正则表达式：

  • 语言：正则表达式语言。
  • 文法：字符、元字符（., *, +, ?, [], {} 等）及其组合规则。
  • 句子：一个具体的正则表达式，如 [a-zA-Z0-9]+。
  • 表示：正则表达式引擎内部会将其转换为一种内部结构（如NFA/DFA）。
  • 解释器：正则表达式引擎，它根据这个内部结构来匹配文本。

• SQL 查询：

  • 语言：SQL (Structured Query Language)。
  • 文法：SELECT, FROM, WHERE, JOIN 等关键字和表达式规则。
  • 句子：一个具体的SQL查询语句。
  • 表示：数据库系统会将SQL查询解析成查询计划（一种树形结构）。
  • 解释器：数据库的查询执行引擎，它执行查询计划以检索数据。

3. 结构 (Structure)

解释器模式通常包含以下角色：

1. AbstractExpression (抽象表达式)：声明一个抽象的 interpret() 操作，这个接口为文法中所有节点类所共享。这些节点可以是终结符表达式或非终结符表达式。
2. TerminalExpression (终结符表达式)：实现与文法中的终结符有关的 interpret() 方法。一个句子中的每个终结符都需要一个实例。
3. NonterminalExpression (非终结符表达式)：实现与文法中的非终结符有关的 interpret() 方法。对文法中的每一条规则 R ::= R1 R2 … Rn 都需要一个 NonterminalExpression 类。它通常递归地调用其子表达式的 interpret() 方法。
4. Context (上下文/环境)：包含解释器之外的一些全局信息。解释器可能会使用它来存储和访问状态，或者传递给解释方法。
5. Client (客户端)：构建（或被提供）一个代表特定句子的抽象语法树。该 AST 由 NonterminalExpression 和 TerminalExpression 的实例组成。然后客户端调用 interpret() 操作。
   
   工作流程：

• 客户端首先将需要解释的句子（字符串形式）解析成一个抽象语法树 (AST)。树的叶子节点是终结符表达式，内部节点是非终结符表达式。
• 然后，客户端调用 AST 根节点的 interpret() 方法。
• interpret() 方法在非终结符节点中通常会递归调用其子节点的 interpret() 方法，直到达到终结符节点。
• 终结符节点的 interpret() 方法执行与该终结符相关的基本操作。
• 解释的结果从叶子节点向上汇聚，最终由根节点返回整个句子的解释结果。
• 上下文对象 (Context) 可以在整个解释过程中传递，用于存储中间状态或全局信息。

4. 适用场景 (When to Use)

• 当有一个语言需要解释执行，并且你可将该语言中的句子表示为一个抽象语法树时。
• 当文法相对简单且稳定时。对于复杂的文法，维护解释器模式的类层次结构可能会变得非常复杂和困难。
• 当效率不是关键问题时。解释器模式通常会导致执行效率较低，因为解释过程涉及多次方法调用和可能的递归。
• 当你想对语言进行扩展或修改时，可以通过添加新的表达式类来实现。
• 用于实现一些领域特定语言 (DSL - Domain Specific Language) 的简单解析器。

5. 优缺点 (Pros and Cons)

优点：

1. 易于改变和扩展文法：由于文法规则被表示为独立的类，因此可以通过增加新的表达式类来轻松地添加或修改文法规则，符合开闭原则。
2. 易于实现语言：对于简单的文法，实现解释器相对直接。
3. 文法清晰：类的层次结构清晰地反映了语言的文法结构。

缺点：

1. 复杂文法难于维护：对于包含大量文法规则的语言，解释器模式会导致产生大量的类，使得系统难以管理和维护。
2. 性能问题：解释器模式通常执行效率较低，因为解释过程涉及多次方法调用，特别是对于递归下降的解释器。
3. 不适用于所有场景：只适用于文法比较简单且固定的情况。对于复杂的语言解析，通常会使用更专业的工具（如词法分析器生成器和语法分析器生成器）。

6. 实现方式 (Implementations)

让我们实现一个简单的解释器，用于计算只包含加法和减法的算术表达式，例如 10 + 5 - 3。我们假设表达式是后缀表达式（逆波兰表示法 RPN）以简化解析，例如 10 5 + 3 -。
或者，为了更直观，我们处理中缀表达式，但手动构建AST。

假设我们要解释的语言是简单的布尔表达式，如 true and (false or true)。

上下文 (Context - 可选，这里我们直接传递值)

对于这个简单的布尔表达式，上下文可以用来存储变量的值（如果表达式中有变量）。这里我们假设只有 true 和 false 常量。

抽象表达式 (BooleanExpression - AbstractExpression)

// boolean_expression.go (AbstractExpression)
package interpreter

// BooleanExpression 抽象表达式接口
type BooleanExpression interface {
	Interpret(variables map[string]bool) bool
	// String() string // For pretty printing the expression tree (optional)
}

// BooleanExpression.java (AbstractExpression interface)
package com.example.interpreter;

import java.util.Map;

public interface BooleanExpression {
    boolean interpret(Map<String, Boolean> context);
    // String toString(); // For pretty printing
}

终结符表达式 (Constant, Variable - TerminalExpression)

// constant_expression.go
package interpreter

// Constant 代表一个布尔常量 (true/false)
type Constant struct {
	value bool
}

func NewConstant(value bool) *Constant {
	return &Constant{value: value}
}

func (c *Constant) Interpret(variables map[string]bool) bool {
	return c.value
}

// variable_expression.go (如果需要变量)
package interpreter

// VariableExpression 代表一个变量
type VariableExpression struct {
	name string
}

func NewVariableExpression(name string) *VariableExpression {
	return &VariableExpression{name: name}
}

func (ve *VariableExpression) Interpret(variables map[string]bool) bool {
	val, ok := variables[ve.name]
	if !ok {
		// Handle error: variable not found, or return a default
		return false
	}
	return val
}

// Constant.java (TerminalExpression)
package com.example.interpreter;

import java.util.Map;

public class Constant implements BooleanExpression {
    private boolean value;

    public Constant(boolean value) {
        this.value = value;
    }

    @Override
    public boolean interpret(Map<String, Boolean> context) {
        return value;
    }
}

// VariableExpression.java (TerminalExpression - if needed)
package com.example.interpreter;

import java.util.Map;

public class VariableExpression implements BooleanExpression {
    private String name;

    public VariableExpression(String name) {
        this.name = name;
    }

    @Override
    public boolean interpret(Map<String, Boolean> context) {
        Boolean value = context.get(name);
        if (value == null) {
            // Handle error or return default
            // throw new IllegalArgumentException("Variable not found in context: " + name);
            return false; // Defaulting to false if not found
        }
        return value;
    }
}

非终结符表达式 (AndExpression, OrExpression, NotExpression - NonterminalExpression)

// and_expression.go
package interpreter

// AndExpression 代表逻辑与操作
type AndExpression struct {
	left, right BooleanExpression
}

func NewAndExpression(left, right BooleanExpression) *AndExpression {
	return &AndExpression{left: left, right: right}
}

func (ae *AndExpression) Interpret(variables map[string]bool) bool {
	return ae.left.Interpret(variables) && ae.right.Interpret(variables)
}

// or_expression.go
package interpreter

// OrExpression 代表逻辑或操作
type OrExpression struct {
	left, right BooleanExpression
}

func NewOrExpression(left, right BooleanExpression) *OrExpression {
	return &OrExpression{left: left, right: right}
}

func (oe *OrExpression) Interpret(variables map[string]bool) bool {
	return oe.left.Interpret(variables) || oe.right.Interpret(variables)
}

// not_expression.go (一元操作符)
package interpreter

// NotExpression 代表逻辑非操作
type NotExpression struct {
	expression BooleanExpression
}

func NewNotExpression(expression BooleanExpression) *NotExpression {
	return &NotExpression{expression: expression}
}

func (ne *NotExpression) Interpret(variables map[string]bool) bool {
	return !ne.expression.Interpret(variables)
}

// AndExpression.java (NonterminalExpression)
package com.example.interpreter;

import java.util.Map;

public class AndExpression implements BooleanExpression {
    private BooleanExpression left;
    private BooleanExpression right;

    public AndExpression(BooleanExpression left, BooleanExpression right) {
        this.left = left;
        this.right = right;
    }

    @Override
    public boolean interpret(Map<String, Boolean> context) {
        return left.interpret(context) && right.interpret(context);
    }
}

// OrExpression.java (NonterminalExpression)
package com.example.interpreter;

import java.util.Map;

public class OrExpression implements BooleanExpression {
    private BooleanExpression left;
    private BooleanExpression right;

    public OrExpression(BooleanExpression left, BooleanExpression right) {
        this.left = left;
        this.right = right;
    }

    @Override
    public boolean interpret(Map<String, Boolean> context) {
        return left.interpret(context) || right.interpret(context);
    }
}

// NotExpression.java (NonterminalExpression - Unary)
package com.example.interpreter;

import java.util.Map;

public class NotExpression implements BooleanExpression {
    private BooleanExpression expression;

    public NotExpression(BooleanExpression expression) {
        this.expression = expression;
    }

    @Override
    public boolean interpret(Map<String, Boolean> context) {
        return !expression.interpret(context);
    }
}

客户端使用

客户端负责构建抽象语法树 (AST)。对于一个真实的解释器，这部分通常由一个解析器 (Parser) 完成，该解析器根据文法规则将输入的字符串转换为 AST。这里我们手动构建 AST。

表达式: (A and B) or (C and (not A))
假设 A=true, B=false, C=true

// main.go (示例用法)
/*
package main

import (
	"./interpreter"
	"fmt"
)

func main() {
	// 上下文，包含变量的值
	variables := make(map[string]bool)
	variables["A"] = true
	variables["B"] = false
	variables["C"] = true

	// 构建表达式: (A and B) or (C and (not A))
	// A = Variable("A")
	// B = Variable("B")
	// C = Variable("C")

	varA := interpreter.NewVariableExpression("A")
	varB := interpreter.NewVariableExpression("B")
	varC := interpreter.NewVariableExpression("C")

	// notA = not A
	notA := interpreter.NewNotExpression(varA)

	// term1 = A and B
	term1 := interpreter.NewAndExpression(varA, varB)

	// term2Inner = C and (not A)
	term2Inner := interpreter.NewAndExpression(varC, notA)

	// expression = term1 or term2Inner
	expression := interpreter.NewOrExpression(term1, term2Inner)

	// 解释表达式
	result := expression.Interpret(variables)

	// (true and false) or (true and (not true))
	// (false) or (true and false)
	// false or false
	// result should be false
	fmt.Printf("Expression (A and B) or (C and (not A)) with A=%t, B=%t, C=%t evaluates to: %t\n",
		variables["A"], variables["B"], variables["C"], result)

	// 另一个例子: true or (false and true)
	constTrue := interpreter.NewConstant(true)
	constFalse := interpreter.NewConstant(false)

	// false and true
	andExpr := interpreter.NewAndExpression(constFalse, constTrue)
	// true or (false and true)
	orExpr := interpreter.NewOrExpression(constTrue, andExpr)

	resultSimple := orExpr.Interpret(nil) // nil context as no variables
	// true or (false)
	// result should be true
	fmt.Printf("Expression true or (false and true) evaluates to: %t\n", resultSimple)
}
*/

// Main.java (示例用法)
/*
package com.example;

import com.example.interpreter.*;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        // 上下文，包含变量的值
        Map<String, Boolean> context = new HashMap<>();
        context.put("A", true);
        context.put("B", false);
        context.put("C", true);

        // 构建表达式: (A and B) or (C and (not A))
        // A = Variable("A")
        // B = Variable("B")
        // C = Variable("C")
        BooleanExpression varA = new VariableExpression("A");
        BooleanExpression varB = new VariableExpression("B");
        BooleanExpression varC = new VariableExpression("C");

        // notA = not A
        BooleanExpression notA = new NotExpression(varA);

        // term1 = A and B
        BooleanExpression term1 = new AndExpression(varA, varB);

        // term2Inner = C and (not A)
        BooleanExpression term2Inner = new AndExpression(varC, notA);

        // expression = term1 or term2Inner
        BooleanExpression expression = new OrExpression(term1, term2Inner);

        // 解释表达式
        boolean result = expression.interpret(context);

        // (true and false) or (true and (not true))
        // (false) or (true and false)
        // false or false
        // result should be false
        System.out.printf("Expression (A and B) or (C and (not A)) with A=%b, B=%b, C=%b evaluates to: %b\n",
                context.get("A"), context.get("B"), context.get("C"), result);

        // 另一个例子: true or (false and true)
        BooleanExpression constTrue = new Constant(true);
        BooleanExpression constFalse = new Constant(false);

        // false and true
        BooleanExpression andExpr = new AndExpression(constFalse, constTrue);
        // true or (false and true)
        BooleanExpression orExpr = new OrExpression(constTrue, andExpr);

        boolean resultSimple = orExpr.interpret(new HashMap<>()); // Empty context as no variables
        // true or (false)
        // result should be true
        System.out.printf("Expression true or (false and true) evaluates to: %b\n", resultSimple);
    }
}
*/

7. 总结

解释器模式为定义和解释简单语言提供了一种结构化的方法。它通过将语言的每条文法规则映射到一个类，并使用这些类的实例构建抽象语法树来表示句子。然后，通过调用树根的 interpret 方法来执行解释。虽然它对于简单语言非常有效且易于扩展，但对于复杂文法，其维护成本和性能可能会成为问题。在这些情况下，更专业的解析工具可能是更好的选择。然而，理解解释器模式有助于掌握如何处理和执行基于规则的系统和简单的领域特定语言。