mohuneko’s blog

かんばる駆け出しエンジニアのブログです

【Java】Interpreter パターン【デザインパターン】

駆け出しエンジニアがデザインパターンをもくもく勉強します

 こんな本で勉強しています🌟

目次

Interpreterパターンについて

Interpreterパターンとは

  • Interpreterパターンは、何らかの形式で書かれたファイルの中身を、「通訳」の役目を果たすプログラムで解析・表現するパターンです
  • プログラムが解決しようとしている問題を簡単なミニ言語で表現し、ミニ言語で書かれたミニプログラムで表現します
    • ミニムログラム単体では動かないので、Java言語で通訳する(interpreter) 役目が必要です
    • 通訳は、ミニ言語を理解し、ミニプログラムを解釈、実行します
  • 問題が変更した際には、ミニプログラムを書き換える事で対処します
  • こうする事で、Java言語で書かれたコードの修正が不要になります

ミニ言語の文法

  • 今回の実装例では、ラジコンで車を動かす言語を考えます
  • プログラムの開始と終了がわかるように、programとendで挟みます
  • ミニ言語の文法ではBNF記法(Backus-Naur Form)の変形バージョンを使います
<program> ::= program <command list>
<command list> ::= <command>* end
<command> ::= <repeat command> | <primitive command>
<repeat command> ::= repeat <number> <command list>
<primitive command> ::= go | right | left
名前 役割
<program> トークンprogram の後にコマンドの列<command list>が続いたもの
<command list> <command>が0個以上繰り返したあとトークン end が続いたもの
<command> 繰り返しコマンド<repeat command> または基本コマンド <primitive command>のいずれか
<repeat command> トークン repeat のあとに繰り返し回数<number>が続き,さらにコマンドの列<command list>が続いたもの
<primitive command> go または right または left
  • <primitive command>のようにこれ以上展開されない表現を、"terminal expression" と言います

サンプルプログラム

  • Interpreterパターンを使って、テキストファイルに書かれた、先ほどのミニ言語の構文を解析する例を取り上げます
  • 各クラスの役割は以下のようになっています
名前 役割
Node(AbstractException) 構文木の「ノード」となるクラス
ProgramNode(NonterminalExpression) <program>に対応するクラス
CommandListNode(NonterminalExpression) <command list>に対応するクラス
CommandNode(NonterminalExpression) <command>に対応するクラス
RepeatCommandNode(NonterminalExpression) <repeat command>に対応するクラス
PrimitiveCommandNode(TerminalExpression) <primitive command>に対応するクラス
Context 構文解析のための前後関係を表すクラス
ParseException 構文解析中の例外クラス

f:id:mohuNeko:20210103125322p:plain

Nodeクラス

  • 構文木の各部分を構成する最上位のクラスです
  • parseメソッドは構文解析という処理を行うためのメソッドです
public abstract class Node {
    public abstract void parse(Context context) throws ParseException;
}

ProgramNodeクラス

  • Node型のCommandListNodeフィールドに、自分の後に続く<command list>に対応するノードを保持します
  • <command list>に対応したCommandListNodeのインスタンスを生成し、そのインスタンスのparseメソッドを呼びます
// <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 String toString() {
        return "[program " + commandListNode + "]";
    }
}

CommandListNodeクラス

  • 0回以上繰り返す<command>を保持するためにArrayList型のフィールドlistを持っています
    • この中に<command>に対応したCommandNodeクラスのインスタンスを格納します
  • parseメソッドで、現在注目しているトークン(context.currentToken)がnullなら、ミニプログラムを最後まで読んだことになります
    • 最後のトークンがendなら、endを飛ばしてwhileループを抜けます
    • endでは無かったら、CommandNodeのインスタンスを作ってparseし、CommandListNodeのlistフィールドにaddします
import java.util.ArrayList;

// <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 String toString() {
        return list.toString();
    }
}

CommandNodeクラス

  • nodeフィールドに、<repeat command>に対応するRepeatCommandNodeクラスのインスタンス<primitive command>に対応するPrimitiveCommandNodeクラスのインスタンスを格納します
// <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 String toString() {
        return node.toString();
    }
}

RepeatCommandNodeクラス

  • RepeatCommandNodeクラスは<repeat command>に対応します
  • 各クラスで以下のように再帰的にparseメソッドを呼び出します
    • RepeatCommandNodeのparseメソッドの中で
    • CommandListNodeのparseメソッドの中で
    • CommandNodeのparseメソッドの中で
    • RepeatCommandNodeのparseメソッドの中で
      • (略)
  • 最終的に、"terminal expression" が来ると、RepeatCommandNodeではなく、PrimitiveCommandNodeを作ります
  • PrimitiveCommandNodeのparseメソッドの中では、他のparseメソッドを呼びません
// <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 String toString() {
        return "[repeat " + number + " " + commandListNode + "]";
    }
}

PrimitiveCommandNodeクラス

  • 他のparseメソッドを呼びません
// <primitive command> ::= go | right | left
public class PrimitiveCommandNode extends Node {
    private String name;
    public void parse(Context context) throws ParseException {
        name = context.currentToken();
        context.skipToken(name);
        if (!name.equals("go") && !name.equals("right") && !name.equals("left")) {
            throw new ParseException(name + " is undefined");
        }
    }
    public String toString() {
        return name;
    }
}

Contextクラス

  • java.util.StringTokenizer tokenizerを使い、区切り文字で、与えられた文字列をトークンに分割します
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) 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 クラス

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

Mainクラスで動作確認

  • program.txtのファイルを読み、一行ずつミニプログラムを構文解析し、その結果を文字列で表示します
import java.util.*;
import java.io.*;

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);
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
  • program.txt
program end
program go end
program go right go right go right go right end
program repeat 4 go right end end
program repeat 4 repeat 3 go right go left end right end end
  • 実行結果
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]]]]

Interpreterパターンのメリット

  • Interpreterパターンを利用すると、規則の追加や変更が容易になります
    • Interpreterパターンの特徴の1つは、"1つの規則を1つのクラスで表す" 事です
    • つまり、新しい規則を追加・修正する場合は AbstractException(Node)クラスのサブクラスを追加・修正するだけで良くなります

今日のポイント

  • Interpreterパターンは、何らかの形式で書かれたファイルの中身を、「通訳」の役目を果たすプログラムで解析・表現するパターンです
  • プログラムが解決しようとしている問題を簡単なミニ言語で表現し、ミニ言語で書かれたミニプログラムで表現します
  • 問題が変更した際には、ミニプログラムを書き換える事で対処する事で、Java言語で書かれたコードの修正が不要になります
  • Interpreterパターンを利用して、"1つの規則を1つのクラスで表す" 事で、新しい規則を追加・修正する場合は AbstractException(Node)クラスのサブクラスを追加・修正するだけで良くなります

 本日もお疲れ様です😊