5 優先順位付けの括弧に対応する

はじめに

以前の記事でインタプリタにprintlnを追加しました。
その過程でLexerへ(と)を解析する機能を加えました。
加えたついでに括弧による演算の優先順位付けにも対応しましょう。

優先順位付けの括弧対応でやりたいこと

説明の必要もないと思いますが、例えば下のようなプログラムがあったら、計算結果aの値が35になることを目指します。

a = (3 + 4) * 5

実装の仕方

実装は構文解析(Parser)へ行います。
構文解析のどこへ実装するかを考えるのに、現状の構文解析の仕方を観察して考えます。

観察対象として下の括弧のない式を取り上げます。
括弧のない式を構文解析するとき、1トークンの順番とどのメソッドで処理されるかに注目します。

a = 1 + 2

1トークンはトークンの並びで3番目にあり、Parserのlead()メソッドで処理されます。

続いて対応したい括弧のある下の式を、括弧のない式と比べながら考えます。
括弧のある式の3番目のトークンは(です。

a = (3 + 4)

先の観察から、1トークンと同じ位置に(トークンがあるので、
(トークンはlead()メソッドに中であらわれることが予測できます。
そして、(トークンのあとの３ + ４は普通の式になっているので、
expression()メソッドで解析できます。
そして、最後に閉じ括弧)があることを確認すれば、構文解析できそうです。

Javaで実装してみる

実装にうつります。

Parser.java

Parser.javaの実装です。
<-- Addの箇所へ優先順位付け括弧対応の処理を追加しました。
まずはlead()メソッドの中で(トークンがあらわれたことを確認します。
Token expr = expression(0)で括弧内の式の解析結果を一旦保持しておきます。
そのあとconsume(")")で閉じ括弧があることを確認します。
戻り値は保持しておいた解析結果です。
対応らしい対応は以上です。

Parser.java

    private Token lead(Token token) throws Exception {
        if (factorKinds.contains(token.kind)) {
            return token;
        } else if(token.kind.equals("paren") && token.value.equals("(")) {  // <-- Add
            Token expr = expression(0);
            consume(")");
            return expr;
        } else {
            throw new Exception("The token cannot place there.");
        }
    }

Interpreter.java

Interpreter.javaの実装です。
優先順位付け括弧の対応が反映されるか、
String text = "a = (3 + 4) * 5";を括弧のある式へ変えました。
標準出力に35がでるはずです。

Interpreter.java

    public static void main(String[] args) throws Exception {
        String text = "a = (3 + 4) * 5";    // <-- Update
        text += "println(a)";
        List<Token> tokens = new Lexer().init(text).tokenize();
        List<Token> blk = new Parser().init(tokens).block();
        new Interpreter().init(blk).run();
        // --> 35
    }

実装は以上です。
ありががとうございました。

おわりに

ソースの全文はこちらで公開しています。

Calc
https://github.com/quwahara/Calc/tree/article-5-parenthesis/Calc/src/main/java

続きの記事があります。

単項演算に対応する
http://qiita.com/quwahara/items/4069d47b511e4d11f44b