Design Pattern: Interpreter 模式

对于一个具有层次节点关系的问题来说，如果您要剖析每一个节点，您可以使用Interpreter模式，直译器模式有些类似演算法中的个别击破方式，对每一个父节点我们剖析出其子节点组合，然而交给子节点剖析物件继续剖析，直到剖析至终端节点为止。

举个例子来说明好了，先说明的是，这个例子是改写自 Design Patterns于Java语言之实习应用 第23章的范例，我将之更简化了，以让大家将焦点能集中在如何使用Interpreter模式，以及如何实用。

假设您要实作一个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 command> | <primitive command>
<repeat command> ::= REPEAT <number> <command list>
<primitive command> ::= PRINT <string>
???????????????????????? | BREAK | SPACE | LINEBREAK

?

程式文法制定需要对程式进行语句分析与定义，在这边并不讨论这个课题，在程式中，command节点由primitive或repeat两个节点任意组合，一个command list节点则是零个以上的command节点组合而成，其中repeat还可以组合command list节点，这是组合模式的应用，可以在程式中组合巢状回圈。

在直译程式时，以读到PROGRAM作为开始节点，接下来我们剖析程式为command list 节点，并将它们丢给专门剖析command list的物件继续剖析，这个物件将之分析，看是不是有repeat command或primitive command节点，如果有就再往下交由专属物件进行剖析，如此层层剥开，并由专属物件负责剖析工作。

Interpreter模式的基本观念就如上所示，先来看看如何以程式实现剖析的过程，下面这个程式会剖析您的程式，并将程式加上对应的括号来将同一个区块组合起来，以表示它完成剖析之后的结果：

INode.java

public interface INode {     public void parse(Context context); } 

?

ProgramNode.java

// <program> ::= PROGRAM <command list> public class ProgramNode implements INode {     private INode commandListNode;     public void parse(Context context) {         context.skipToken("PROGRAM");         commandListNode = new CommandListNode();         commandListNode.parse(context);     }     public String toString() {         return "[PROGRAM " + commandListNode + "]";     } }  

?

CommandListNode.java

import java.util.Vector; // <command list> ::= <command>* END public class CommandListNode implements INode {     private Vector list = new Vector();    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 {                 INode commandNode = new CommandNode();                 commandNode.parse(context);                 list.add(commandNode);             }         }     }    public String toString() {         return "" + list;     } }  

?

CommandNode.java

// <command> ::= <repeat command> | <primitive command> public class CommandNode implements INode {     private INode node;    public void parse(Context context) {         if (context.currentToken().equals("REPEAT")) {             node = new RepeatCommandNode();             node.parse(context);         } else {             node = new PrimitiveCommandNode();             node.parse(context);         }     }    public String toString() {         return node.toString();     } }  

?

RepeatCommandNode.java

public class RepeatCommandNode implements INode {     private int number;     private INode commandListNode;     public void parse(Context context) {         context.skipToken("REPEAT");         number = context.currentNumber();         context.nextToken();         commandListNode = new CommandListNode();         commandListNode.parse(context);     }    public String toString() {        return "[REPEAT " + number + " "                   + commandListNode + "]";     } }

?

PrimitiveCommandNode.java

// <primitive command> ::= PRINT <string> //                           | SPACE | BREAK | LINEBREAK public class PrimitiveCommandNode implements INode {    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();             name += text;             context.nextToken();         }     }    public String toString() {         return name;     } }  

?

Context.java

import java.util.*; public class Context {     private StringTokenizer tokenizer;     private String currentToken;     public Context(String text) {         tokenizer = new StringTokenizer(text);         nextToken();     }     public String nextToken() {         if (tokenizer.hasMoreTokens()) {             currentToken = tokenizer.nextToken();         } else {             currentToken = null;         }         return currentToken;     }     public String currentToken() {         return currentToken;     }     public void skipToken(String token) {         if (!token.equals(currentToken)) {             System.err.println("Warning: " + token +                           " is expected, but " +                           currentToken + " is found.");         }         nextToken();     }     public int currentNumber() {         int number = 0;         try {             number = Integer.parseInt(currentToken);         } catch (NumberFormatException e) {             System.err.println("Warning: " + e);         }         return number;     } }  

?

Main.java

import java.util.*; import java.io.*;public class Main {     public static void main(String[] args) {         try {             BufferedReader reader = new                   BufferedReader(new FileReader(args[0]));             String text;             while ((text = reader.readLine()) != null) {                 System.out.println("text = \"" +                                        text + "\"");                 INode node = new ProgramNode();                 node.parse(new Context(text));                 System.out.println("node = " + node);             }         }         catch (ArrayIndexOutOfBoundsException e) {             System.err.println(                   "Usage: java Main yourprogram.txt");         }         catch (Exception e) {             e.printStackTrace();         }     } } 

假设您的程式是这样写的：

program.txt

PROGRAM PRINT xxx ENDPROGRAM REPEAT 4 PRINT xxx END END PROGRAM REPEAT 4 PRINT xxx PRINT "yyy" END END

则执行Intrepreter程式之后会是：

?$ java Main program.txt
?text = "PROGRAM PRINT xxx END"
?node = [PROGRAM [PRINTxxx]]

?text = "PROGRAM REPEAT 4 PRINT xxx END END"
?node = [PROGRAM [[REPEAT 4 [PRINTxxx]]]]

?text = "PROGRAM REPEAT 4 PRINT xxx PRINT "yyy" END END"
?node = [PROGRAM [[REPEAT 4 [PRINTxxx, PRINT"yyy"]]]]

?

TerminalExpression就像我们的primitive command，再剖析下去已经没有子节点了，而NonterminalExpression就像是repeat command，注意到其中也使用了组合模式，就如之前所说的，组合模式让可以递回的组合句子为更复杂的语句。

您已经会剖析句子了，接下来要如何让这个直译器真正工作，虽然程式中使用toString()来表示每一个节点的剖析结果，但事实上，这个程式也已经说明了如何让剖析的结果真正运作了，既然已经记录好剖析之后的语句顺序了，只要由上而下追踪剖析结果，就一定可以执行到 primitive command，且顺序符合自订的程式原始码的需求，这只要将toString()改为execute()，并作一些转发与重复执行的修改就可以了，直接来看程式会比较容易理解：

?

CommandListNode.java

import java.util.*;    // <command list> ::= <command>* ENDpublic class CommandListNode implements INode {    private Vector list = new Vector();    private INode commandNode;    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 {                commandNode = new CommandNode();                commandNode.parse(context);                list.add(commandNode);            }        }    }    public void execute() {        Iterator it = list.iterator();        while (it.hasNext()) {            ((CommandNode)it.next()).execute();        }    }    public String toString() {        return "" + list;   }} 

?

CommandNode.java

// <command> ::= <repeat command> | <primitive command>public class CommandNode implements INode {    private INode node;    public void parse(Context context) {        if (context.currentToken().equals("REPEAT")) {            node = new RepeatCommandNode();            node.parse(context);        } else {            node = new PrimitiveCommandNode();            node.parse(context);        }    }    public void execute() {        node.execute();    }    public String toString() {        return node.toString();    }} 

?

PrimitiveCommandNode.java

// <primitive command> ::= PRINT <string> //                           | SPACE | BREAK | LINEBREAKpublic class PrimitiveCommandNode implements INode {    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------------------------------");    }    public String toString() {        return name;    }} 

?

RepeatCommandNode.java

public class RepeatCommandNode implements INode {    private int number;    private INode commandListNode;    public void parse(Context context) {        context.skipToken("REPEAT");        number = context.currentNumber();        context.nextToken();        commandListNode = new CommandListNode();        commandListNode.parse(context);    }    public void execute() {        for(int i = 0; i < number; i++)            commandListNode.execute();    }    public String toString() {        return "[REPEAT " + number + " " +                              commandListNode + "]";    }} 

?

Context.java

import java.util.*;public class Context {    private StringTokenizer tokenizer;    private String currentToken;    public Context(String text) {        tokenizer = new StringTokenizer(text);        nextToken();    }    public String nextToken() {        if (tokenizer.hasMoreTokens()) {            currentToken = tokenizer.nextToken();        } else {            currentToken = null;        }        return currentToken;    }    public String currentToken() {        return currentToken;    }    public void skipToken(String token) {        if (!token.equals(currentToken)) {            System.err.println("Warning: " + token +                            " is expected, but " +                            currentToken + " is found.");        }        nextToken();    }    public int currentNumber() {        int number = 0;        try {            number = Integer.parseInt(currentToken);        } catch (NumberFormatException e) {            System.err.println("Warning: " + e);        }        return number;    }} 

?

Main.java

import java.util.*;import java.io.*;public class Main {    public static void main(String[] args) {        try {            BufferedReader reader = new BufferedReader(                               new FileReader(args[0]));            String text;            while ((text = reader.readLine()) != null) {                System.out.println("text = \"" + text                                       + "\"");                INode node = new ProgramNode();                node.parse(new Context(text));                node.execute();            }        }        catch (ArrayIndexOutOfBoundsException e) {            System.err.println(                 "Useage: java Main yourprogram.txt");        }        catch (Exception e) {            e.printStackTrace();        }    }}

假设您的直译程式稿是这么撰写的：

program.txt

PROGRAM REPEAT 4 LINEBREAK PRINT justin SPACE PRINT momor LINEBREAK END END

则程式执行的结果就是：

? $ java Main program.txt
?text = "PROGRAM REPEAT 4 LINEBREAK PRINT justin SPACE
???????? PRINT momor LINEBREAK END END"
?------------------------------
?justin momor
?------------------------------

?------------------------------
?justin momor
?------------------------------

?------------------------------
?justin momor
?------------------------------

?------------------------------
?justin momor
?------------------------------?

Design Patterns于Java语言之实习应用 第23章的范例中，可以让您依指令稿直译，画出任何的图案，让范例结合了工厂（Factory）模式、外观（Facade）模式等等，在这边建议您看看那个范例，看看不同的设计模式之间如何组合且相互合作。

?