天天看点
返回

设计模式（Java）—Interpreter模式

在Interpreter模式中，程序要解决的问题会被用非常简单的“迷你语言”表述出来，即用“迷你语言”编写的“迷你程序”把具体问题表述出来。迷你程序是无法单独工作的，我们还需要用Java语言编写一个负责“翻译”的程序。翻译程序会理解迷你语言，并解释和运行迷你程序。这段翻译程序也称为解释器。这样，当需要解决的问题发生变化时，不需要修改Java语言程序，只需要修改迷你语言程序即可应对。

使用Java语言编程时，需要修改代码，但是，在使用Interpreter模式后，我们就无需修改Java程序，只需修改迷你语言编写的迷你程序即可。

设计模式（Java）—Interpreter模式

迷你语言

此次迷你语言的用途是控制无线玩具车。虽说是玩具车，其实能做的事情不过以下3种。

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

  • 重复（repeat）

    以上就是可以向玩具车发送的命令，go是前进1米后停止的命令；right是原地向右转的命令，left是原地向左转的命令。在实际操作时，是不能完全没有偏差地原地转弯的，为了使问题简单化，我们这里并不会改变玩具车的位置，而是像将其放在旋转桌子上一样，让他转个方向。

    以上命令组合起来就是可以控制无线玩具车的迷你语言了。

控制无线玩具车的迷你语言

设计模式（Java）—Interpreter模式

迷你语言程序示例

下面我们来看一段用迷你语言编写的迷你程序。下面这条语句可以控制无线玩具车前进（之后停止）。

program go end

为了便于大家看出语句的开头和结尾，我们在语句前后分别加上了program和end关键字。这个迷你程序的运行结果如下。

program go end的运行结果

设计模式（Java）—Interpreter模式

接下来是一段让无限玩具车先前进一米，接着让它右转两次再返回的程序。

program go right right go end

再接下来的这段程序是让无线玩具车按照正方形路径行进，其运行结果如下所示。

program go right go right go right go right end…（A）

program go right go right go right go right end的运行结果

设计模式（Java）—Interpreter模式

(A)程序的最后（即end之前）之所以加上了right，是因为当无线玩具车回到起点后，我们希望它的方向与出发时相同，在（A）程序中，重复出现了4次go right。这样，我们可以使用repeat…end语句来实现下面的（B）程序（为了能够编写出这段程序，我们需要定义迷你语言的语法），其运行结果如图所示。

设计模式（Java）—Interpreter模式

program repeat 4 go right end end …(B)

在（B）程序的最后出现了两个end，其中第一个（左边）end表示repeat的结束，第二个（右边）end表示program的结束，也就是说，程序的结构如下：

设计模式（Java）—Interpreter模式

再如：

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

现在玩具车会按照如下图所示的锯齿形状路线前进。

设计模式（Java）—Interpreter模式

这段程序可分解如下形式：

设计模式（Java）—Interpreter模式

内侧的循环语句是go right go left,它是一条让无线玩具车“前进后右转，前进后左转”的命令。该命令会重复3次。这样，玩具车就会向右沿着锯齿形路线行进，接着，退至外侧循环看，玩具车会连续4次“沿着锯齿形路线进行一次后，右转一次”。这样，最终行进路线就变成了一个锯齿样的菱形。

迷你语言的语法

设计模式（Java）—Interpreter模式

上图展示了迷你语言的语法。这里使用的描述方法是BNF的一个变种，BNF经常被用于描述算法。

<program>::=program <command list>

首先我们定义了程序<program>，即“所谓<program>，是指program关键字后面跟着的命令列表<command list>”，“::=”的左边表示定义的名字，右边表示定义的内容。

<command list> ::=<command>* end

接着，我们定义了命令列表<command list>，即“所谓<command list>,是指重复0次以上<command>后，接着一个end关键字”，“*”表示前面的内容循环0次以上。

<command> ::=<repeat command> | <primitive command>

现在，我们来定义<command>，即“所谓<command>，是指<repeat command>或<primitive command>”。

<repeat command>::= repeat <number><command list>

接下来，我们定义循环命令，即“所谓<repeat command>，是指repeat关键字后面跟着循环次数<number>”和要循环的命令列表<command list>。其中<command list>在之前已经定义过了，而在定义命令列表的时候使用了<command>，在定义<command>的时候又使用了<command>，而在定义<repeat command>的时候又使用了<command list>，像这样，在定义某个东西时，他自身又出现在了定义的内容中，我们称这种定义为递归定义。

<primitive command>::= go | right | left

这是基本命令<primitive command>的定义，即“所谓<primitive command>是指go或者right或者left”。

终结符表达式与非终结符表达式

前面讲到的想<primitive command>这样的不会进一步展开的表达式被成为“终结符表达式”。与之相对的是，像<command>和<repeat command>这样的需要被进一步展开的表达式被成为“非终结符表达式”。

示例程序

示例程序实现了一个迷你程序的语法解析器。

在之前学习迷你程序的相关内容时，我们分别学习了迷你程序的各个语法部分。像这样将迷你程序当作普通字符分解，然后看看各个部分分别是什么结构的过程，就是语法解析。

例如有迷你程序

program repeat 4 go right end end

将这段迷你程序推导成为下图那样的结构（语法树）的处理，就是语法解析。

设计模式（Java）—Interpreter模式

示例程序的类图

设计模式（Java）—Interpreter模式

Node类

该类是语法树中各个部分中最顶层的节点。

package Interpreter;

//解释器的语法树总结点类，该类为抽象类，其中声明另外抽象方法parse，参数传递为语法分析的文本上下文对象
public abstract class Node {
	//当标记解析出错时抛出异常，打印异常信息
	public abstract void parse(Context context) throws ParseException;

}

ProgramNode类

package Interpreter;

//Program节点类， <program> ::= program <command list>
public class ProgramNode extends Node {
	//定义命令列表变量
	private Node commandListNode;
	public void parse(Context context) throws ParseException {
		//跳过program标记
		context.skipToken("program");
		//创建commandList实例
		commandListNode = new CommandeListNode();
		//将上文内容传递给commandList实例解析
		commandListNode.parse(context);
	};
	//重写toString方法
	public String toString(){
		return "[program"+commandListNode+"]";
	}

}

CommandList类

package Interpreter;

import java.util.ArrayList;
//CommandeListNode类  <command list> ::= <command>* end
//重复0次以上command 然后以end结束
public class CommandeListNode extends Node {
	//保存command实例
	private ArrayList list = new ArrayList<>();
	public void parse(Context context) throws ParseException {
		while(true){
			//当前标记为空，抛出异常，缺少end关键字
			if(context.currentToken()==null){
				throw new ParseException("Missing end");
			}else if(context.currentToken().equals("end")){
				//当前标记为end，则解析完毕，跳过end标记，break出循环，结束解析工作
				context.skipToken("end");
				break;
			}else {
				//否则，创建command实例，将context交由command实例解析
				Node commandNode = new CommandNode();
				commandNode.parse(context);
				//将command实例添加至列表中
				list.add(commandNode);
			}
		}
	}
	public String toString(){
		return list.toString();
	}

}

CommandNode类

package Interpreter;

public class CommandNode extends Node {
	//保存RepeatCommandNode或PrimitiveCommandNode实例
	private Node node;
	public void parse(Context context) throws ParseException {
		//如果当前标记是repeat，则创建RepeatCommandNode实例，交由其解析
		if(context.currentToken().equals("repeat")){
			node = new RepeatCommandNode();
			node.parse(context);
		}else {
			//否则交由PrimitiveCommandNode实例解析
			node = new PrimitiveCommandNode();
			node.parse(context);
		}
	}
	public String toString(){
		return node.toString();
	}

}

RepeatCommandNode类

package Interpreter;

public class RepeatCommandNode extends Node {
	private Node commandListNode;
	private int number;
	public void parse(Context context) throws ParseException {
		//跳过repeat标记
		context.skipToken("repeat");
		//repeat标记后面一定是数字
		number = context.currentNumber();
		context.nextToken();
		//repeat标记后面又可以还是命令列表，所以继续调用CommandeListNode实例解析
		commandListNode = new CommandeListNode();
		commandListNode.parse(context);
		
	}
	public String toString(){
		return "[repeat "+number+" "+commandListNode+"]";
	}
}

PrimitiveCommandNode类

package Interpreter;

public class PrimitiveCommandNode extends Node {
	//保存当前标记即动作名称
	private String name;
	public void parse(Context context) throws ParseException {
		//获取当前标记
		name = context.currentToken();
		//跳至下一标记
		context.nextToken();
		//判断，若果标记不是go、right、left其中一个的话，抛出异常
		if(!name.equals("go")&&!name.equals("right")&&!name.equals("left")){
			throw new ParseException(name+ "is undefined");
		}
	}
	public String toString(){
		return name;
	}

}

Context类

package Interpreter;
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;
		try {
			number = Integer.parseInt(currentToken);
		} catch (NumberFormatException e) {
			// TODO: handle exception
			throw new ParseException("warning:"+e);
		}
		return number;
	}
}

ParseException类

package Interpreter;

public class ParseException extends Exception {
	public ParseException(String msg) {
		// TODO Auto-generated constructor stub
		super(msg);
	}
}

Main类

package Interpreter;

import java.io.BufferedReader;
import java.io.FileReader;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		try {
			//从文本中逐行读取内容，对每行内容进行解析
			BufferedReader bufferedReader = new BufferedReader(new FileReader("program.txt"));
			String text;
			while((text=bufferedReader.readLine())!=null){
				System.out.println("text = \""+text+"\"");
				//先创建ProgramNode实例，并对该行进行递归解析
				Node node = new ProgramNode();
				node.parse(new Context(text));
				System.out.println("node = "+node);
			}
			//关闭buffer指针
			bufferedReader.close();
		} catch (Exception e) {
			// TODO: handle exception
			e.printStackTrace();
		}

	}

}

运行结果：

设计模式（Java）—Interpreter模式

练习

增加以下功能：

  • 示例程序中只进行了语法分析，修改程序，让示例程序还可以“运行”迷你程序语言。
  • 使用GUI显示基本命令的“运行”结果。
  • 使用Facade模式使解释器更易于使用。
  • 编写一个生成基本命令的类。
  • 将解释器的相关代码单独整理至一个包中。

language包

设计模式（Java）—Interpreter模式

turtle包

设计模式（Java）—Interpreter模式

测试类

设计模式（Java）—Interpreter模式
设计模式（Java）—Interpreter模式

InterpreterFacade类

package language;

public class InterpreterFacade implements Executor {
    private ExecutorFactory factory;
    private Context context;
    private Node programNode;
    public InterpreterFacade(ExecutorFactory factory) {
        this.factory = factory;
    }
    public boolean parse(String text) {
        boolean ok = true;
        this.context = new Context(text);
        this.context.setExecutorFactory(factory);
        this.programNode = new ProgramNode();
        try {
            programNode.parse(context);
            System.out.println(programNode.toString());
        } catch (ParseException e) {
            e.printStackTrace();
            ok = false;
        }
        return ok;
    }
    public void execute() throws ExecuteException {
        try {
            programNode.execute();
        } catch (ExecuteException e) {
            e.printStackTrace();
        }
    }
}

ExecutorFactory接口

package language;

public interface ExecutorFactory {
    public abstract Executor createExecutor(String name);
}

Context类

package language;

import java.util.*;

public class Context implements ExecutorFactory {
    private ExecutorFactory factory;
    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;
    }
    public void setExecutorFactory(ExecutorFactory factory) {
        this.factory = factory;
    }
    public Executor createExecutor(String name) {
        return factory.createExecutor(name);
    }
}

Node类

package language;

public abstract class Node implements Executor {
    public abstract void parse(Context context) throws ParseException;
}

Executor接口

package language;

public interface Executor {
    public abstract void execute() throws ExecuteException;
}

ProgramNodel类

package language;

// <program> ::= program <command list>
public class ProgramNode extends Node {
    private Node commandListNode;
    public void parse(Context context) throws ParseException {
        context.skipToken("program");
        commandListNode = new CommandListNode();
        commandListNode.parse(context);
    }
    public void execute() throws ExecuteException {
        commandListNode.execute();
    }
    public String toString() {
        return "[program " + commandListNode + "]";
    }
}

CommandNode类

package language;

// <command> ::= <repeat command> | <primitive command>
public class CommandNode extends Node {
    private Node node;
    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);
        }
    }
    public void execute() throws ExecuteException {
        node.execute();
    }
    public String toString() {
        return node.toString();
    }
}

RepeatCommandNode类

package language;

// <repeat command> ::= repeat <number> <command list>
public class RepeatCommandNode extends Node {
    private int number;
    private Node commandListNode;
    public void parse(Context context) throws ParseException {
        context.skipToken("repeat");
        number = context.currentNumber();
        context.nextToken();
        commandListNode = new CommandListNode();
        commandListNode.parse(context);
    }
    public void execute() throws ExecuteException {
        for (int i = 0; i < number; i++) {
            commandListNode.execute();
        }
    }
    public String toString() {
        return "[repeat " + number + " " + commandListNode + "]";
    }
}

CommandListNode类

package language;

import java.util.*;

// <command list> ::= <command>* end
public class CommandListNode extends Node {
    private ArrayList list = new ArrayList();
    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);
            }
        }
    }
    public void execute() throws ExecuteException {
        Iterator it = list.iterator();
        while (it.hasNext()) {
            ((CommandNode)it.next()).execute();
        }
    }
    public String toString() {
        return list.toString();
    }
}

PrimitiveCommandNode类

package language;

// <primitive command> ::= go | right | left
public class PrimitiveCommandNode extends Node {
    private String name;
    private Executor executor;
    public void parse(Context context) throws ParseException {
        name = context.currentToken();
        context.skipToken(name);
        executor = context.createExecutor(name);
    }
    public void execute() throws ExecuteException {
        if (executor == null) {
            throw new ExecuteException(name + ": is not defined");
        } else {
            executor.execute();
        }
    }
    public String toString() {
        return name;
    }
}

ExecuteException类

package language;

public class ExecuteException extends Exception {
    public ExecuteException(String msg) {
        super(msg);
    }
}

ParseException类

package language;

public class ParseException extends Exception {
    public ParseException(String msg) {
        super(msg);
    }
}

TurtleCanvas类

package turtle;

import language.Executor;
import language.ExecutorFactory;
import language.ExecuteException;
import java.awt.*;

public class TurtleCanvas extends Canvas implements ExecutorFactory {
    final static int UNIT_LENGTH = 30;  // 前进时的长度单位
    final static int DIRECTION_UP = 0; // 上方
    final static int DIRECTION_RIGHT = 3; // 右方
    final static int DIRECTION_DOWN = 6; // 下方
    final static int DIRECTION_LEFT = 9; // 左方
    final static int RELATIVE_DIRECTION_RIGHT = 3; // 右转
    final static int RELATIVE_DIRECTION_LEFT = -3; // 左转
    final static int RADIUS = 3; // 半径
    private int direction = 0;
    private Point position;
    private Executor executor;
    public TurtleCanvas(int width, int height) {
        setSize(width, height);
        initialize();
    }
    public void setExecutor(Executor executor) {
        this.executor = executor;
    }
    void setRelativeDirection(int relativeDirection) {
        setDirection(direction + relativeDirection);
    }
    void setDirection(int direction) {
        if (direction < 0) {
            direction = 12 - (-direction) % 12;
        } else {
            direction = direction % 12;
        }
        this.direction = direction % 12;
    }
    void go(int length) {
        int newx = position.x;
        int newy = position.y;
        switch (direction) {
        case DIRECTION_UP:
            newy -= length;
            break;
        case DIRECTION_RIGHT:
            newx += length;
            break;
        case DIRECTION_DOWN:
            newy += length;
            break;
        case DIRECTION_LEFT:
            newx -= length;
            break;
        default:
            break;
        }
        Graphics g = getGraphics();
        if (g != null) {
            g.drawLine(position.x, position.y, newx, newy);
            g.fillOval(newx - RADIUS, newy - RADIUS, RADIUS * 2 + 1, RADIUS * 2 + 1);
        }
        position.x = newx;
        position.y = newy;
    }
    public Executor createExecutor(String name) {
        if (name.equals("go")) {
            return new GoExecutor(this);
        } else if (name.equals("right")) {
            return new DirectionExecutor(this, RELATIVE_DIRECTION_RIGHT);
        } else if (name.equals("left")) {
            return new DirectionExecutor(this, RELATIVE_DIRECTION_LEFT);
        } else {
            return null;
        }
    }
    public void initialize() {
        Dimension size = getSize();
        position = new Point(size.width / 2, size.height / 2);
        direction = 0;
        setForeground(Color.red);
        setBackground(Color.white);
        Graphics g = getGraphics();
        if (g != null) {
            g.clearRect(0, 0, size.width, size.height);
        }
    }
    public void paint(Graphics g) {         
        initialize();                       
        if (executor != null) {             
            try {                           
                executor.execute();         
            } catch (ExecuteException e) {  
            }                               
        }                                   
    }                                       
}

abstract class TurtleExecutor implements Executor {
    protected TurtleCanvas canvas;
    public TurtleExecutor(TurtleCanvas canvas) {
        this.canvas = canvas;
    }
    public abstract void execute();
}

class GoExecutor extends TurtleExecutor {
    public GoExecutor(TurtleCanvas canvas) {
        super(canvas);
    }
    public void execute() {
        canvas.go(TurtleCanvas.UNIT_LENGTH);
    }
}

class DirectionExecutor extends TurtleExecutor {
    private int relativeDirection;
    public DirectionExecutor(TurtleCanvas canvas, int relativeDirection) {
        super(canvas);
        this.relativeDirection = relativeDirection;
    }
    public void execute() {
        canvas.setRelativeDirection(relativeDirection);
    }
}

Main类

import language.InterpreterFacade;
import turtle.TurtleCanvas;

import java.util.*;
import java.io.*;
import java.awt.*;
import java.awt.event.*;

public class Main extends Frame implements ActionListener {
    private TurtleCanvas canvas = new TurtleCanvas(400, 400);
    private InterpreterFacade facade = new InterpreterFacade(canvas);
    private TextField programTextField = new TextField("program repeat 3 go right go left end end");

    // 构造函数
    public Main(String title) {
        super(title);

        canvas.setExecutor(facade);

        setLayout(new BorderLayout());

        programTextField.addActionListener(this);

        this.addWindowListener(new WindowAdapter() {
            public void windowClosing(WindowEvent e) {
                System.exit(0);
            }
        });

        add(programTextField, BorderLayout.NORTH);
        add(canvas, BorderLayout.CENTER);
        pack();
        parseAndExecute();
        show();
    }

    // 供ActionListener用
    public void actionPerformed(ActionEvent e) {
        if (e.getSource() == programTextField) {
            parseAndExecute();
        }
    }

    private void parseAndExecute() {
        String programText = programTextField.getText();
        System.out.println("programText = " + programText);
        facade.parse(programText);
        canvas.repaint();
    }

    public static void main(String[] args) {
        new Main("Interpreter Pattern Sample");
    }
}
java 解释器模式 Interpreter模式 语法解析 迷你语言 语法树
上一篇: /bin/bash^M: bad interpreter 错误解决方式
下一篇: execl error: Permission denied 错误解决

继续阅读