解釋器模式

<image>

在電腦編程中，解釋器模式（interpreter pattern），是一種設計模式，它規定了如何求值一個語言中的句子。基本想法是使專門電腦語言的每個符號（終結符與非終結符）都有一個類。這個語言中句子的語法樹是合成模式的一個實例，它被用來為客戶求值（解釋）這個句子。

## 結構

<image>

在上面的UML類圖中：

- 客戶`Client`類提及公共的`AbstractExpression`接口來解釋一個表達式`interpret(context)`。
- 終結表達式`TerminalExpression`類沒有子表達式並且直接解釋一個表達式。
- 非終結表達式`NonTerminalExpression`類維護一個子表達式的容器（`expressions`）並且將解釋請求轉發給這些`expressions`。

對象圖展示了運行時交互：

- 客戶`Client`對象發送解釋請求到抽象語法樹。這個請求被沿著樹結構轉發到（辦理於）所有對象。
- 非終結表達式`NonTerminalExpression`對象（`ntExpr1,ntExpr2`）將請求轉發到它們的子表達式。
- 終結表達式`TerminalExpression`對象（`tExpr1,tExpr2,&hellip;`）直接的進行解釋。

## 示例

### C++

下面的例子是基於《設計模式》書中先於C++98的樣例代碼的C++23實現：

```c++
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& context) const {
        return context.lookup(this);
    }

    [[nodiscard]]
    virtual UniquePtr<VariableExpression> replace(const String& name, BooleanExpression& exp) {
        if (this->name == 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 VariableExpression&) = 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& context) const {
        return operand1->evaluate(context) && operand2->evaluate(context);
    }

    [[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;  
}
```

程序輸出為：

```output
0
1
```

### Python

下面是Python的例子：

```python
from abc import ABC, abstractmethod

class Context():
    def __init__(self):
        self.var_dict = {}
    def lookup(self, var):
        return (self.var_dict[var.name]
            if var.name in self.var_dict else None)
    def assign(self, var, value):
        self.var_dict[var.name] = value

class BooleanExp(ABC):
    @abstractmethod
    def evaluate(self): pass
    @abstractmethod
    def replace(self): pass
    @abstractmethod
    def copy(self): pass

class VariableExp(BooleanExp):
    def __init__(self, context, name, value=None):
        self.context = context
        self.name = name
        if value is not None:
            self.context.assign(self, value)
    def __str__(self):
        return f"({self.name})"
    def evaluate(self):
        return self.context.lookup(self)
    def replace(self, var, exp):
        return (exp.copy() if self.name == var.name
            else self.copy())
    def copy(self):
        return type(self)(self.context, self.name)

class AndExp(BooleanExp):
    def __init__(self, opd1, opd2):
        self.opd1 = opd1
        self.opd2 = opd2   
    def __str__(self):
        return f"({self.opd1} and {self.opd2})"
    def evaluate(self):
        opd1 = self.opd1.evaluate()
        opd2 = self.opd2.evaluate()
        return opd1 and opd2 
    def replace(self, var, exp):
        opd1 = self.opd1.replace(var, exp)
        opd2 = self.opd2.replace(var, exp)
        return type(self)(opd1, opd2)
    def copy(self):
        opd1 = self.opd1.copy()
        opd2 = self.opd2.copy()
        return type(self)(opd1, opd2)

def demo():
    context = Context()
    x = VariableExp(context, "X", False)
    y = VariableExp(context, "Y", True)
    exp = AndExp(x, y)
    print(exp)
    print(exp.evaluate())
    context.assign(x, True)
    z = VariableExp(context, "Z")
    context.assign(z, exp.evaluate())
    print(context.lookup(z))
    exp1 = exp.replace(x, z)
    print(exp1)
    print(exp1.evaluate())
    context.assign(z, False)
    print(exp1.evaluate())
```

其輸出：

```pycon
>>> demo()
((X) and (Y))
False
True
((Z) and (Y))
True
False
```

## 外部連結

- Interpreter implementation in Ruby
- Interpreter implementation in C++
- SourceMaking tutorial
- Interpreter pattern description from the Portland Pattern Repository