【图解设计模式】Interpreter模式

Posted on | In

要解决的问题会被用非常简单的“迷你语言”表述出来，用Java语言编写一个负责“翻译”的程序。这样，当需要解决的问题发生变化时，不需要修改Java语言程序，只需要修改迷你语言程序即可应对。

mvHAAO.png

迷你语言

迷你语言的用途是控制无线玩具车。

  • 前进1米（go）
  • 右转（right）
  • 左转（left）
  • 重复（repeat）

示例

program repeat 4 repeat 3 go right go left end right end end

mxwTRH.png

语法

1
2
3
4
5
<program> ::= program <command list>
<command list> ::= <command>* end
<command> ::= <repeat command> | <primitive command>
<repeat command> ::= repeat <number> <command list>
<primitive command> ::= go | left | right

示例

一个迷你程序的语法解析器。例如有如下迷你程序。

program repeat 4 go right end end

将这段迷你程序推导成为如下那样的语法树。

mxBZnI.png

类图

mxBl9g.png

Node类

1
2
3
public abstract class Node {
    public abstract void parse(Context context) throws ParseException;
}

ProgramNode类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// <program> ::= program <command list>
public class ProgramNode extends Node {
    private Node commandListNode;

    @Override
    public void parse(Context context) throws ParseException {
        context.skipToken("program");
        commandListNode = new CommandListNode();
        commandListNode.parse(context);
    }

    @Override
    public String toString() {
        return "[program " + commandListNode + "]";
    }
}

CommandListNode类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.ArrayList;

// <command list> ::= <command>* end
public class CommandListNode extends Node {
    private ArrayList list = new ArrayList();

    @Override
    public void parse(Context context) throws ParseException {
        while (true) {
            if (context.currentToken() == null)
                throw new ParseException("Missing 'end'");
            else if (context.currentToken().equals("end")) {
                context.skipToken("end");
                break;
            }
            else {
                Node commandNode = new CommandNode();
                commandNode.parse(context);
                list.add(commandNode);
            }
        }
    }

    @Override
    public String toString() {
        return list.toString();
    }
}

CommandNode类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// <command> ::= <repeat command> | <primitive command>
public class CommandNode extends Node {
    private Node node;

    @Override
    public void parse(Context context) throws ParseException {
        if (context.currentToken().equals("repeat")) {
            node = new RepeatCommandNode();
            node.parse(context);
        }
        else {
            node = new PrimitiveCommandNode();
            node.parse(context);
        }
    }

    @Override
    public String toString() {
        return node.toString();
    }
}

RepeatCommandNode类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// <repeat command> ::= repeat <number> <command list>
public class RepeatCommandNode extends Node {
    private int number;
    private Node commandListNode;

    @Override
    public void parse(Context context) throws ParseException {
        context.skipToken("repeat");
        number = context.currentNumber();
        context.nextToken();
        commandListNode = new CommandListNode();
        commandListNode.parse(context);
    }

    @Override
    public String toString() {
        return "[repeat " + number + " " + commandListNode + "]";
    }
}

PrimitiveCommandNode类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// <primitive command> ::= go | left | right
public class PrimitiveCommandNode extends Node {
    private String name;

    @Override
    public void parse(Context context) throws ParseException {
        name = context.currentToken();
        context.skipToken(name);

        if (!name.equals("go") && !name.equals("left") && !name.equals("right"))
            throw new ParseException(name + " is undefined");
    }

    @Override
    public String toString() {
        return name;
    }
}

Context类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.StringTokenizer;

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) throws ParseException {
        if (!token.equals(currentToken))
            throw new ParseException("Warning: " + token + " is expected, but " + currentToken + " is found.");

        nextToken();
    }

    public int currentNumber() throws ParseException {
        int number = 0;

        try {
            number = Integer.parseInt(currentToken);
        } catch (NumberFormatException e) {
            throw new ParseException("Warning: " + e);
        }

        return number;
    }
}

ParseException类

1
2
3
4
5
6
public class ParseException extends Exception {
    
    public ParseException(String msg) {
        super(msg);
    }
}

Main类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.io.BufferedReader;
import java.io.FileReader;

public class Main {

    public static void main(String[] args) {
        try {
            BufferedReader reader = new BufferedReader(new FileReader("program.txt"));
            String text;

            while ((text = reader.readLine()) != null){
                System.out.println("text = \"" + text + "\"");
                Node node = new ProgramNode();
                node.parse(new Context(text));
                System.out.println("node = \"" + node + "\"");
            }

            reader.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

运行结果

1
2
3
4
5
6
7
8
9
10
text = "program end"
node = "[program []]"
text = "program go end"
node = "[program [go]]"
text = "program go right go right go right go right end"
node = "[program [go, right, go, right, go, right, go, right]]"
text = "program repeat 4 go right end end"
node = "[program [[repeat 4 [go, right]]]]"
text = "program repeat 4 repeat 3 go right go left end right end end"
node = "[program [[repeat 4 [[repeat 3 [go, right, go, left]], right]]]]"

登场角色

AbstractExpression（抽象表达式）

AbstractExpression角色定义了语法树节点的共同接口（API）。在示例程序中，由Node类扮演此角色。

TerminalExpression（终结符表达式）

TerminalExpression角色对应BNF中的终结符表达式。在示例程序中，由PrimitiveCommandNode类扮演此角色。

NonterminalExpression（非终结符表达式）

NonterminalExpression角色对应BNF中的非终结符表达式。在示例程序中，由ProgramNode类、CommandNode类、RepeatCommandNode类和CommandListNode类扮演此角色。

Context（文脉、上下文）

Context角色为解释器进行语法解析提供了必要的信息。在示例程序中，由Context类扮演此角色。

Client（请求者）

为了推导语法树，Client角色会调用TerminalExpression角色和NonterminalExpression角色。在示例程序中，由Main类扮演此角色。

类图

mxvicD.png