デザインパターンInterpreterについて勉強した
Interpreterパターンとは
インタプリタとは通訳のことです。
インタプリタといえばプログラム言語の一種、もしくはスクリプト言語として知っている人も多いのではないでしょうか。
Interpreterパターンはまさにそのスクリプト言語を作ろうというものです。
パターンの目的としてはアプリの動作を変更するのにコンパイルを必要としない、極限まで柔軟化したプログラムの一つとすることです。
作り方によればプログラミングの知識がないような人でもちょっと調べれば欲しい機能を実装できるようになります。
エクセルの関数なんかもそんな感じですね。
今回例として、入力した文字列を数式と読み取って計算してくれるスクリプトを作ってみましょう。
ただし、本格的に作るとそれこそ同人誌から技術書１冊分くらいの情報量になってしまうので、Interpreterの基本的な考え方がわかる程度として足し算、引き算のみを実装するようにします。
と言っても２つの数字を足し引きするだけでは流石に味気ないので、1+2-3+4のように足し算引き算であればいくらでも繋げられるようにはしたいと思います。
構文設計
まずはスクリプトの構文仕様を決めます。
BNF（バッカス・ナウア記法）
<integer> ::= "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"|<integer><integer> <operator> ::= "+"|"-" <number> ::= <integer>|<operator><number> <operation> ::= <operation><operator><operation>)|<number>
正規表現のようなものです。
「::=」は代入のような意味で考えればいいでしょう。
「＜integer＞は"0"~"9"のどれかです」のような意味になります。
一つずつみていきます。
＜integer＞ ::= "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"|＜integer＞＜integer＞
＜integer＞はJava言語でも整数クラスという意味ですね。
右辺には"0"~"9"が並んでおり、それぞれの間に|が挟まっています。これは0~9の文字どれかがあれば＜integer＞として扱うとなります。
最後に＜integer＞＜integer＞があります。こちらは＜integer＞が2つ並んでいますが、これは＜integer＞が２つ並んでいるものも１つの＜integer＞として扱うという意味になります。＜integer＞が2つで１つの＜integer＞になるので、それらを合わせた（全部で４つ,またそれ以上並んだ）＜integer＞も１つとして扱うという意味にもなります。再起的な表現ですね。
ここでは説明のためあえて書きましたが、数値の定義まで書くのはめんどくさいということで「数値」や「文字列」のルールは書かない場合もあるようです。
<operator> ::= "+"|"-"
今度は＜operator＞です。
＜integer＞と比べるとシンプルですね。"+"もしくは"-"のどちらかという意味です。
<number> ::= <integer>|<operator><number>
＜number＞は数値という意味です。
＜integer＞とはどう違うのでしょうか。
定義をよく読んでみると＜integer＞には数字の前に"-"がついた０より小さい数については説明されていません。ただの数列のみです。
＜number＞は数列の前にマイナスがついた０より小さい数字、もしくはマイナスのつかない０以上の数字について説明されています。
＜integer＞の方にマイナスのついた数列を定義するのは難しいです。＜integer＞の連続で再帰しているので、例えば12-34という文字列も＜integer＞として説明できてしまうためです。
<operation> ::= <operation><operator><operation>)|<number>
最後に＜operation＞です。数式を表しています。
まず＜operation＞は＜number＞単体でもそれとして扱うことができます。つまり、「１」も「１２３４」も＜operation＞です。
＜opeator＞は「+」もしくは「-」でしたね。ということは＜operation＞＜operator＞＜operation＞の部分は「1+1234」にマッチします。
よくみるとここでも再帰がありますね。ということは「1+1234」＜operator＞＜operation＞と考えられるので、「1+1234」の後にさらに「-56」を付け足すこともできます。このように無限に式を伸ばすことが可能です。
コード例
それではコードを見ていきましょう。
Lexerクラス
public class Lexer { private String integer_regex = "\\d+"; private String operator_regex = "\\+|-"; public Token[] toTokens(String code) throws ParserException{ if(code==null) return new Token[0]; code = code.trim(); Pattern pattern = Pattern.compile(String.format("(\s*%s)|(\s*%s)", integer_regex,operator_regex)); Matcher matcher = pattern.matcher(code); ArrayList<Token> tokens = new ArrayList<Token>(); int index = 0; while(index<code.length()) { if(!matcher.find(index)) { throw new ParserException("字句解析に失敗しました"); } tokens.add(createToken(matcher)); index = matcher.end(); } return tokens.toArray(new Token[0]); } public Token createToken(Matcher matcher) { Token token = null; if(matcher.group(1)!=null) { token = new Token(TokenType.NUMBER,matcher.group(1).trim()); } if(matcher.group(2)!=null) { token = new Token(TokenType.OPERATOR,matcher.group(2).trim()); } //System.out.println(token); return token; } }
字句解析をするクラスです。
例えば「1+234-56」をプログラムが解釈するとき、「１」「＋」「２３４」「ー」「５６」に分ける必要があります。これら単体を字句と呼び、文字列を字句に分解、解析することを字句解析と言います。
integer_regexとoperator_regexという２つのフィールドがあります。
中身は正規表現です。
integer_regexは＜integer＞に、operator_regexは＜operator＞にそれぞれ対応しているのがわかるでしょうか。
toTokensメソッドは字句解析をするときに最初に呼び出されるメソッドです。
throwsがついていますね。構文的におかしな文字列が渡された時は例外を出して解析を中止するようにします。
pattern変数は各字句のパターンを設定しています。
tokens変数は解析できた軸を補完するためのリストです。
index変数は、現在どこまで解析ができたかを保持するためのものです。
whileループです。
indexがコードの文字数よりも多くなったら全コードを解析できたということでループを終了します。
if文の!matcher.findはマッチする文字列がなかった場合の処理です。
まだ解析できていないコードが残っているのにマッチしない場合、これは本来コードに含まれるべきではない文字が含まれていることが考えられるため、例外を出します。
その後createTokenメソッドにマッチ結果を丸投げします。
ここまでくればコードの先頭の字句は正常に読み取れているはずです。
createtokenメソッドを見てみます。
matcher.group(1)!=nullに注目します。
group(1)とは正規表現でマッチした部分の１つ目を読み出すメソッドです。
パターンを見直してみましょう。
String.format("(\s*%s)|(\s*%s)", integer_regex,operator_regex)
パターンは"(\s*%s)|(\s*%s)",となっています。
group(0)だと全体にマッチします。つまりinterger_regexにマッチした場合でもoperator_regexがマッチした場合でも何かしらの文字列が返されます。
group(1)では1つ目の括弧の中身が返されます。つまりこのパターンの場合はinteger_regexにマッチした場合のみ文字列が返され、operator_regexにマッチした場合はnullが返ります。
group(2)だとその逆で、opearator_regexにマッチした場合に文字列が返り、integer_regexにマッチした場合はnullが変えることになります。
それを踏まえてif文をみてみるとif(matcher.group(1)!=null) {はinteger_regexがnullではない、つまりinteger_regexにマッチしているということになります。
マッチするものが見つかったらTokenクラスのインスタンスを作って返します。
TokenType
public enum TokenType { OPERATOR, NUMBER, }
字句の種類です。
operatorつまり演算子とnumberつまり数字の２種類です。
Tokenクラス
public class Token { private TokenType type ; private String name; public Token(TokenType type,String name) { this.type = type; this.name = name; } public TokenType getType() { return type; } public String getName() { return name; } @Override public String toString() { return type + "\t" + name; } }
字句１つを表すクラスです。
自身のタイプと名前（"+"や"-"、"123"など）を保持するだけのものです。
ParserExceptionクラス
public class ParserException extends Exception { public ParserException(String message) { super(message); } }
構文解析できなかった場合の例外クラスです。
ここまでできたら一度実行してみましょう。
createTokenメソッドの最後にSystem.out.println(token);の一文を追加すると解析状況がわかります。
今度は構文解析と実行のコードを書いていきます。
Nodeクラス
public abstract class Node { public abstract int execute(); }
Nodeは数値、計算式などを表す抽象クラスです。
実際の処理はサブクラスに実装します。
NumberNodeクラス
public class NumberNode extends Node { private int number ; public NumberNode(int number) { this.number = number; } @Override public int execute() { return number; } }
＜number＞を担当するクラスです。
numberフィールドで数値を保持します。
executeメソッドは計算の実行をしますが、このクラスはただの数値なので処理もただ保持している数値を返すだけになっています。
OperationNodeクラス
public class OperationNode extends Node { private Node left ; private Token operator ; private Node right ; public OperationNode(Node left,Token operator,Node right) { this.left = left; this.operator = operator; this.right = right; } @Override public int execute() { if(operator.getName().equals("+")) { return left.execute()+right.execute(); }else { return left.execute()-right.execute(); } } }
＜opearation＞を担当し、計算式を表すクラスです。
フィールドを見てみると３つあります。
leftは計算式の左を担当するNodeです。これが＜number＞なのか＜operation＞なのかはこの時点ではわかりません。コンストラクタに渡されたNodeによって変わります。
operatorは演算子で、「＋」もしくは「ー」になります。
rightは計算式の右を担当するNodeです。leftと同様に何が入るかはわかりません。
executeメソッドはoperatorが「＋」か「ー」かによって処理が足し算か引き算に変わります。
NumberNodeよりは難しいですがまだなんてことはありません。
Parserクラス
public class Parser { private int index ; private Token[] tokens ; public Node toNode(Token[] tokens) throws ParserException{ index = 0; this.tokens = tokens; return toOperationNode(); } public Node toOperationNode() throws ParserException{ Token token = currentToken(); if(token==null) return null; Node node = toNumberNode(); while((token=currentToken())!=null) { if(token.getType()!=TokenType.OPERATOR) { throw new ParserException("計算式は+/-のみ有効 : "+token); } nextToken(); node = new OperationNode(node,token,toNumberNode()); } return node; } public Node toNumberNode() throws ParserException{ int i = 1; Token token ; while((token=currentToken())!=null) { if(token.getType()==TokenType.OPERATOR) { if(token.getName().equals("-")) { i *= -1; } nextToken(); }else { break; } } if(token==null) throw new ParserException("数値を入力してください"); nextToken(); return new NumberNode(Integer.parseInt(token.getName())*i); } public boolean hasCurrent() { return index<tokens.length; } public Token currentToken() { if(!hasCurrent()) { return null; } return tokens[index]; } public Token nextToken() { index++; return currentToken(); } }
構文解析をするクラスです。
indexフィールドはトークン列のどこまで解析が済んでいるかを保持します。
tokensフィールドは解析対象のトークン列を保持します。
コンストラクタでは渡された値をフィールドに保持し、toOperationNodeメソッドを呼んで解析を開始します。
toOperationNodeメソッドはOperationNodeを生成するメソッドです。
currentTokenは現在参照しているトークンを返すメソッドで、この戻り値がnullであるということはそもそもコードがないということです。
まずは式の左の数値を解析します。
whileでは続いて演算子がある場合の解析をしています。
演算子を保持し、演算子があるということはさらに続いて数値があるはずなので、あると決めてtoNumberNodeを呼びます。もし数値がなければtoNumberNodeから例外が返ってきます。
所々で無駄にnextTokenを呼び出していますね。現在どのトークンを参照しているか、次に呼び出すメソッドはどこが参照されていることを前提として設計されているかを意識しないと、トークンの読み飛ばしや２重に読んでしまうなどが起こってしまうので、注意が必要です。
toNumberNodeメソッドを見てみましょう。
whileループがありますが、これは「＋」「ー」が並んでいる間はループし続けます。
「ー」が出てくるたびに数値の符号を反転するためです。
符号が出てこなければループを脱します。
脱しても数字が出てこなければ例外です。
hasCurrentメソッドは現在参照しているトークンが存在するかを返します。
存在しない、falseが変えるということはトークン列の最後に達したということになります。
currentTokenメソッドは現在参照しているトークンを返します。
存在しなければnullを返します。
nextTokenメソッドは参照するトークンを次へ進めて、次のトークンを返します。
存在しなければnullを返します。
public class Main { public Main() { Scanner scanner = new Scanner(System.in); while(true) { try { System.out.println("計算式を入力してください"); String code = scanner.nextLine(); if(code.equals("exit")) break; Lexer lexer = new Lexer(); Token[] tokens = lexer.toTokens(code); Parser parser = new Parser(); Node node = parser.toNode(tokens); if(node==null) continue; int response = node.execute(); System.out.println(">>"+response); } catch (ParserException e) { System.out.println(e.getMessage()); } System.out.println(); } scanner.close(); } public static void main(String[] args) { new Main(); } }
今回もScannerでコンソール入力をするようにしました。
ループ条件は常にtrueです。
式を入力して、「exit」だったらループを抜けて終了します。
入力された式をLexerに渡し、字句解析されたトークン列を取得します。
さらにトークン列をParserに渡し、構文解析されたノードを取得します。
ここでもし式が入力されていなければnullが返ってきているので、nullチェックをしておきます。
ノードのexecuteを呼び出すことで式の計算を開始します。
実行
計算式を入力してください 1+1 >>2 計算式を入力してください 100+1 >>101 計算式を入力してください 10-5 >>5 計算式を入力してください 5--1 >>6 計算式を入力してください 5-----2 >>3
特徴
ユーザーがコードを書くことで処理が変化できるような、非常に柔軟なアプリを作ることができます。
本格的なスクリプト言語を作ることもあれば、アプリの補助機能として簡単なものを実装することもあります。
まとめ
今回は足し算と引き算しかしないスクリプトを作りました。
ちょっとごちゃっとした感じになりましたが、これは簡単な方です。
というのも、実際の計算では算数レベルでも掛け算や割り算が出てきます。掛け算割り算は足し算引き算に比べて優先順位が高いものです。さらに括弧のついた式を考えるとさらに複雑になります。
この優先順位を避けるために足し算引き算のみにしましたが、掛け算割り算を実装した途端に難易度がぐんと上がったような記憶があります。
エディタ系や自動化系のアプリを作るときには結構欲しくなる機能なので、覚えておいて損はないと思います。
