iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 19
0

今天要介紹的是 Intepreter,它是一種 Behavior Pattern。這個 Pattern 的目的是要用來解釋已經被定義的文法,將一段敘述轉換成表示法。那麼我們就來了解一下這個特別的 Design Pattern 吧!

Interpreter 產生的動機

當一個特定的問題發生的頻率夠高,那麼就應該值得定義一個簡單語言來表示它,而當定義了這樣的語言後,就可以使用 Interpreter Pattern 來解決轉譯句子的問題。

舉例來說:搜尋特定符合特定模式的字串,這是一個很通用常見的問題,而 Regular Expression 就是一個用來指定字串模式的標準的語言。而要怎麼將一個這樣的語言轉換成程式語言可使用的表示,就可以透過套用 Interpreter Pattern,將文字敘述轉換成抽象語法樹(Abstract Syntax Tree),就可為程式語言使用。

Interpreter 結構與組成

  • AbstractExpression:定義一個在抽象語法樹(Abstract Syntax Tree)中所有節點都有共同的抽象化Interpret操作。
  • TerminalExpression
    1. 實現文法中與終結符號相關的轉譯操作。
    2. 在一個句子中,終結符號是必須的。
  • NonterminalExpression:文法中的每一個規則都代表了一個非終結表達式。
  • Context:包含 Interpreter 以外的全域訊息。
  • Client
    1. 建立抽象語法樹(Abstract Syntax Tree)者,抽象語法數的組成便是 TerminalExpressionNonterminalExpression 的實體。
    2. 調用 interpret 操作者。

Interpreter 可以應用的情境

當有一個語言需要被解譯的時候可以使用 Interpreter Pattern,而且你可以用抽象語法樹(Abstract Syntax Tree)來表示一個語言的聲明。Interpreter Pattern 特別適合於:

  1. 文法簡單的語言
  2. 效率不是重要考量時

實作看看吧!

我們就使用簡單的加法表示式來做練習,而範例將用 Swift 來撰寫!不過因為 Swift 裡面並沒有 Abstract Class 的概念,我們可以用 Protocol 來實現 Interpreter。

class IntegerContext {
    private var data = [Character: Int]()
    
    func lookup(name: Character) -> Int {
        return data[name]!
    }
    
    func assign(expression: IntegerVariableExpression, value: Int) {
        data[expression.name] = value
    }
}

protocol IntegerExpression {

    func evaluate(_ context: IntegerContext) -> Int
    func replace(character name: Character, integerExpression: IntegerExpression) -> IntegerExpression
    func copied() -> IntegerExpression
    
}

class IntegerVariableExpression: IntegerExpression {
    
    let name: Character

    init(name: Character) {
        self.name = name
    }
    

    func evaluate(_ context: IntegerContext) -> Int {
        return context.lookup(name: self.name)
    }

    func replace(character name: Character, integerExpression: IntegerExpression) -> IntegerExpression {
        if name == self.name {
            return integerExpression.copied()
        } else {
            return IntegerVariableExpression(name: self.name)
        }
    }

    func copied() -> IntegerExpression {
        return IntegerVariableExpression(name: self.name)
    }
}

class PlusExpression: IntegerExpression {
    private var operand1: IntegerExpression
    private var operand2: IntegerExpression

    init(op1: IntegerExpression, op2: IntegerExpression) {
        self.operand1 = op1
        self.operand2 = op2
    }

    func evaluate(_ context: IntegerContext) -> Int {
        return self.operand1.evaluate(context) + self.operand2.evaluate(context)
    }

    func replace(character: Character, integerExpression: IntegerExpression) -> IntegerExpression {
        return PlusExpression(op1: operand1.replace(character: character, integerExpression: integerExpression),
                             op2: operand2.replace(character: character, integerExpression: integerExpression))
    }

    func copied() -> IntegerExpression {
        return PlusExpression(op1: self.operand1, op2: self.operand2)
    }
}

let context = IntegerContext()

let a = IntegerVariableExpression(name: "a")
let b = IntegerVariableExpression(name: "b")
let c = IntegerVariableExpression(name: "c")

let expression = PlusExpression(op1: a, op2: PlusExpression(op1: b, op2: c))

context.assign(expression: a, value: 4)
context.assign(expression: b, value: 1)
context.assign(expression: c, value: 2)


print(expression.evaluate(context))

let newExpression = expression.replace(character: "c", integerExpression: a)

print(newExpression.evaluate(context))

Output

7
9

Interpreter 優點與缺點

  • 優點
    1. 可以容易地改變或拓展文法:因為在 Interpreter 中,是使用 Class 來表示文法規則,所以可以使用繼承來改變或拓展文法—存在的每一個 Expression 都可以逐步地被修改,新的 Expression 可以被定義成已存在的 Expression 的變異。
    2. 也可以容易的實作一個簡單的語言:因為每一個文法規則都被定義成抽象語法樹中每個節點的 Class,它們除了容易撰寫外,也很容易可以自動被 Compiler 或 Parser Generator 產生。
    3. 增加新的解譯表示法較為簡便。
  • 缺點
    1. 對於複雜的文法難以維護:在 Interpreter Pattern 中,每一個規則都要定義一個 Class,因此如果一個語言的文法定義了太多規則時,那麼 Class 的數量就會增加,導致系統難以維護。
    2. 執行效率比較低:因為在 Interpreter 中使用大量的循環和遞迴呼叫,因此在解釋複雜文法的句子速度會很慢。

Reference

  1. Design Patterns - Elements of Reusabel Object-Oriented Software by Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides(Gang of four)
  2. https://openhome.cc/Gossip/DesignPattern/InterpreterPattern.htm
  3. https://xyz.cinc.biz/2013/08/interpreter-pattern.html
  4. https://blog.csdn.net/fanyun_01/article/details/51862242
  5. https://github.com/ochococo/Design-Patterns-In-Swift/blob/master/source/behavioral/interpreter.swift

作者:Charles


上一篇
[Design Pattern] Command 命令模式
下一篇
[Design Pattern] Mediator 中介者模式
系列文
什麼?又是/不只是 Design Patterns!?32

尚未有邦友留言

立即登入留言