Interpreter 模式

對於一個具有層次節點關係的問題來說，如果您要剖析每一個節點，可以使用Interpreter模式，直譯器模式有些類似演算法中的個別擊破方式，對每個父節點剖析出其子節點組合，然而交給子節點剖析物件繼續剖析，直到剖析至終端節點為止。

假設您要實作一個直譯器，可以直譯您文字檔中的程式，並依您自訂的程式文法來執行程式，幾個簡單的程式如下：

PROGRAM
    PRINT dog SPACE
    PRINT is SPACE
    PRINT an SPACE
    PRINT animai
END

您的這式程個會印出"dog is an animal"的文字，再來一個例子是：

PROGRAM
    REPEAT 2
        LINEBREAK
        PRINT dog
        BREAK
    END
END

這個程式要印出：

------------------------------
dog
------------------------------
dog

您也可以任意的組合程式，例如：

PROGRAM
    PRINT begin
    BREAK
    REPEAT 3
        REPEAT 2
            PRINT dog SPACE
            PRINT is SPACE
            PRINT a SPACE
            PRINT animal
            BREAK
        END
    END
END

這個程式中的幾個關鍵字是PROGRAM、PRINT、SPACE、BREAK、LINEBREAK、REPEAT、END， PROGRAM是表示程式開始，以END作結，PRINT可以印出一個無空白的字串，SPACE印出一個空白，BREAK是換行，而 LINEBREAK是畫一個直線並換行，REPEAT是迴圈指令，可以指定迴圈次數，以END作結。

觀察程式，可以制定出以下的文法，如下：

<program> ::= PROGRAM <command list>
<command list> ::= <command>* END
<command> ::= <repeat> | <primitive>
<repeat> ::= REPEAT <number> <command list>
<primitive> ::= PRINT <string> | BREAK | SPACE | LINEBREAK

程式文法制定需要對程式進行語句分析與定義，在這邊並不討論這個課題，在程式中，command節點由primitive或repeat兩個節點任意組合，一個command list節點則是零個以上的command節點組合而成，其中repeat還可以組合command list節點，這是 Composite 模式的應用，可以在程式中組合巢狀迴圈。

在直譯程式時，以讀到PROGRAM作為開始節點，接下來剖析程式為command list 節點，並將它們丟給專門剖析command list的物件繼續剖析，這個物件將之分析，看是不是有repeat或primitive節點，如果有就再往下交由專屬物件進行剖析，如此層層剝開，並由專屬物件負責剖析工作。

以下是個示範程式：

import java.util.*;
import java.io.*;

interface Node { 
    void parse(Context context); 
    void execute();
}

// <program> ::= PROGRAM <command list> 
class Program implements Node { 
    private Node commandList; 
    public void parse(Context context) { 
        context.skipToken("PROGRAM"); 
        commandList = new CommandList(); 
        commandList.parse(context); 
    } 
    public void execute() {
        commandList.execute();
    }
}  

// <command list> ::= <command>* END 
class CommandList implements Node { 
    private List<Node> commands = new ArrayList<Node>();
    public void parse(Context context) { 
        while (true) { 
            if(context.currentToken() == null) { 
                System.err.println("Missing 'END'"); 
                break; 
            } 
            else if(context.currentToken().equals("END")) {
                context.skipToken("END"); 
                break; 
            } 
            else { 
                Node command = new Command(); 
                command.parse(context); 
                commands.add(command); 
            } 
        } 
    }
    public void execute() {
        for(Node command : commands) {
            command.execute();
        }
    }
}  

// <command> ::= <repeat> | <primitive> 
class Command implements Node { 
    private Node node;
    public void parse(Context context) { 
        if(context.currentToken().equals("REPEAT")) { 
            node = new Repeat(); 
            node.parse(context); 
        } else { 
            node = new Primitive(); 
            node.parse(context); 
        } 
    }
    public void execute() {
        node.execute();
    }
}

// <primitive> ::= PRINT <string> | SPACE | BREAK | LINEBREAK
class Primitive implements Node {
    private String name;
    private String text;
    public void parse(Context context) {
        name = context.currentToken();
        context.skipToken(name);
        if (!(name.equals("PRINT") ||
              name.equals("BREAK") ||
              name.equals("LINEBREAK") ||
              name.equals("SPACE"))) {
            System.err.println("Undefined Command");
        }
        if (name.equals("PRINT")) {
            text = context.currentToken();
            context.nextToken();
        }
    } 
    public void execute() {
        if(name.equals("PRINT"))
            System.out.print(text);
        else if(name.equals("SPACE"))
            System.out.print(" ");
        else if(name.equals("BREAK"))
            System.out.println();
        else if(name.equals("LINEBREAK"))
            System.out.println("\n------------------------------");
    }
}

class Repeat implements Node {
    private int number;
    private Node commandList;
    public void parse(Context context) {
        context.skipToken("REPEAT");
        number = context.currentNumber();
        context.nextToken();
        commandList = new CommandList();
        commandList.parse(context);
    }
    public void execute() {
        for(int i = 0; i < number; i++) {
            commandList.execute();
        }
    }
}

class Context {
    private Iterator<String> tokens;
    private String currentToken;

    Context(String filename) throws IOException {
        List<String> tokenList = new ArrayList<String>();
        BufferedReader reader = new BufferedReader(
                                     new FileReader(filename));
        String input = null;
        while((input = reader.readLine()) != null) {
            for(String token : input.trim().split("\s+")) {
                tokenList.add(token);
            }
        }
        reader.close();
        tokens = tokenList.iterator();
        nextToken();
    }

    String nextToken() {
        currentToken = null;
        if (tokens.hasNext()) {
            currentToken = tokens.next();
        } 
        return currentToken;
    }

    String currentToken() {
        return currentToken;
    }

    void skipToken(String token) {
        if (!token.equals(currentToken)) {
            System.err.println("Warning: " + token + 
                           " is expected, but " + 
                           currentToken + " is found.");
        }
        nextToken();
    }

    int currentNumber() {
        return Integer.parseInt(currentToken);
    }
} 

public class Main {
    public static void main(String[] args) throws Exception {
        Node node = new Program();
        node.parse(new Context(args[0]));
        node.execute();
    }
}

程式首先剖析完所有節點，再對節點執行任務，來看一下Intrepreter模式的 UML 類別結構圖：

TerminalExpression就像我們的primitive，再剖析下去已經沒有子節點了，而NonterminalExpression就像是 repeat，其中也使用了 Composite 模式，可以遞迴地組合句子為更複雜的語句。

以下是使用Python來實作範例：

import sys
import re

# <program> ::= PROGRAM <command list> 
class Program:
    def parse(self, context):
        context.skipToken("PROGRAM")
        self.commandList = CommandList() 
        self.commandList.parse(context)

    def execute(self):
        self.commandList.execute()

# <command list> ::= <command>* END 
class CommandList:
    def parse(self, context):
        self.commands = []
        while True:
            if not context.currentToken():
                print("Missing 'END'")
                break
            elif context.currentToken() == "END":
                context.skipToken("END")
                break
            else:
                command = Command()
                command.parse(context) 
                self.commands.append(command) 

    def execute(self):
        for command in self.commands:
            command.execute()

# <command> ::= <repeat> | <primitive> 
class Command:
    def parse(self, context):
        if context.currentToken() == "REPEAT":
            self.node = Repeat()
            self.node.parse(context)
        else:
            self.node = Primitive()
            self.node.parse(context)

    def execute(self):
        self.node.execute()

# <primitive> ::= PRINT <string> | SPACE | BREAK | LINEBREAK
class Primitive:
    def parse(self, context):
        self.name = context.currentToken()
        context.skipToken(self.name)
        if (self.name != "PRINT" and
            self.name != "BREAK" and
            self.name != "LINEBREAK" and
            self.name != "SPACE"):
            print("Undefined Command")
        
        if self.name == "PRINT":
            self.text = context.currentToken()
            context.nextToken()
    
    def execute(self):
        if self.name == "PRINT":
            print(self.text, end="")
        elif self.name == "SPACE":
            print(end=" ")
        elif self.name == "BREAK":
            print()
        elif self.name == "LINEBREAK":
            print("\n------------------------------")

class Repeat:
    def parse(self, context):
        context.skipToken("REPEAT")
        self.number = context.currentNumber()
        context.nextToken()
        self.commandList = CommandList()
        self.commandList.parse(context)
    
    def execute(self):
        for i in range(self.number):
            self.commandList.execute()

class Context:
    def __init__(self, filename):
        tokenList = []
        for line in open(filename):
            for token in re.split("\s+", line.strip()):
                tokenList.append(token)
        self.tokens = iter(tokenList)
        self.nextToken()
    
    def nextToken(self):
        self.current = None
        try:
            self.current = next(self.tokens)
        except StopIteration: 
            pass
        return self.current
       
    def currentToken(self):
        return self.current
    
    def skipToken(self, token):
        if token != self.current:
            print("Warning: " + token + 
                  " is expected, but " + 
                  self.currentToken + " is found.");
        self.nextToken()

    def currentNumber(self):
        return int(self.current)

node = Program()
node.parse(Context(sys.argv[1]))
node.execute()

Toy Lang 是使用 JavaScript 來實作的一個進階範例，有興趣可以參考看看。