Java 8 で字句解析を作る(その2)

はじめに

自作のJavaコンソールプログラムで使用する為の、簡易字句解析器を作りました。
前回の記事で、トークンクラスを作成しましたので、今回は字句解析器本体になります。
字句解析なら各種ライブラリを使う方が手間がかからないのですが、外部サイトからのダウンロードが禁止されている職場で使用する為、Java8 の機能のみを使ってイチから作成しています。

2018/10/22 ソース修正しました。
2018/10/24 コンストラクタで、解析対象文字列のコピーを保存するよう修正しました。

作成にあたり、単純な字句解析をJavaで実装するを参考にしています。

注意点

今回は、ソースとその解説が長くなるので、前回の記事をご覧下さい。

字句解析クラス

LexicalAnalyzer.java

package console;

public class LexicalAnalyzer {
    public static LexicalAnalyzer create(String target) {
        if ( target == null  || target.trim().isEmpty() ) { target = ""; }
        return new LexicalAnalyzer(target);
    }

    public java.util.List<Token> analyze() {
        char c;
        while ( (c = next()) != '\0' ) {
            if ( isSymbol_1(c) ) {
                tokens_.add( Token.create(c) );
                continue;
            }
            if ( isQuote(c) ) {
                quotedText(c);
                continue;
            }
            text(c);
        }
        return new java.util.ArrayList<>(tokens_);
    }

    // query methods ================================================================================
    public boolean isEmpty() { return tokens_.size() == 0;}

    public boolean isValid() {
        return !isEmpty()  &&  tokens_.stream().noneMatch( e -> e.kind() == Token.Kinds.Unknown );
    }

    // internal methods ======================================================================
    /** 次のクォート文字までを一塊のトークンとして切出し. */
    private void quotedText(char quote) {
        tokens_.add( Token.create(quote));  // create token of begin quote

        java.lang.StringBuilder builder = new java.lang.StringBuilder();
        char c;
        while ( (c = nextAll()) != '\0'  &&  c != quote) { builder.append(c); }
        if ( builder.length() != 0 ) {
            tokens_.add( Token.create(builder.toString()) );  // append string
        }

        tokens_.add( Token.create(c) );  // append token of end quote
    }

    /** セパレータ、空白文字までを一塊のトークンとして切出し. */
    private void text(char first) {
        java.lang.StringBuilder builder = new java.lang.StringBuilder();
        builder.append(first);

        char c;
        while ( (c = nextAll()) != '\0'  &&  !isSeparator(c)  &&  !isWhitespace(c) ) { 
            builder.append(c);
        }
        tokens_.add( Token.create(builder.toString()) );

        // append separator token, if not end of text
        if ( isEnd() ) { return; }

        tokens_.add( isWhitespace(c) ? Token.create(' ') : Token.create(c) );
    }

    private char next() {
        skipSpace();
        return nextAll();
    }

    private char nextAll() {
        char c = aChar();
        ++pos_;
        return c;
    }

    private char aChar() { return isEnd() ? '\0' : target_.charAt(pos_); }

    private void skipSpace() {
        while ( !isEnd()  &&  Character.isWhitespace(aChar()) ) { pos_++; }
    }

    private boolean isEnd()                 { return length_ <= pos_; }
    private boolean isSeparator(char c)     { return exists(separators_, c);    }
    private boolean isQuote(char c)         { return exists(quotes_, c);        }
    private boolean isSymbol_1(char c)      { return exists(symbol1_, c);       }
    private boolean isWhitespace(char c)    { return Character.isWhitespace(c); }

    private boolean exists(char[] arr, char c) {
        return java.util.Arrays.binarySearch(arr, c) >= 0;
    }

    private LexicalAnalyzer(String target) {
        target_ = target;
        length_ = target.length();
    }

    // internal fields ======================================================================
    private static final char[] separators_ = { ':', ',', '=', '(', ')', '{', '}' };
    static { Arrays.sort(separators_); }

    private static final char[] quotes_ = { '"', '\'' };
    static { Arrays.sort(quotes_); }

    private static final char[] symbol1_ = {'(', ')', '{', '}', ':', ',', '=', '&' };
    static { Arrays.sort(symbol1_); }

    final String target_;       // analyze target string
    final int    length_;       // length of target string
    int          pos_ = 0;      // "next" analyzing position

    java.util.List<Token> tokens_ = new java.util.ArrayList<>();  // result
}

解説

ファクトリメソッド

本来は、引数である解析対象の文字列は必須にしたい所ですが、それを呼び出し元に強制する手段はありませんので、空文字列を対象文字列にセットします。
これで、呼び出し元は null チェックや、例外処理の手間から開放されます。ついでにコンストラクタでの引数チェックなども不要になります。

<修正> 文字列セット時に、引数のコピーをセットします。コピーしないと、外部で対象文字列を変更できてしまいます。

    public static LexicalAnalyzer create(String target) {
        if ( target == null  || target.trim().isEmpty() ) { target = ""; }
        return new LexicalAnalyzer(target);
    }

    private LexicalAnalyzer(String target) {
        target_ = new String(target);
        length_ = target.length();
    }

    final String target_;       // analyze target string
    final int    length_;       // length of target string

サポートメソッド

字句解析器ということで、対象の文字列を1文字ずつ取り出して、処理を行います。
その為の基礎となる機能が、以下のメソッド群になります。

• <追加> nextAll() は、新しい文字を読み込み、読み込み位置(pos_)を１つ進めます。next()との違いは、空白文字も含めて全ての文字を返すことです。これは、後述の text()、quotedText() で使用します。
• <変更> next() は、空白文字を読み飛ばして、有効な文字に到達したら、それを返します。
• aChar() は、読込み位置の文字を返します。対象文字列がもうこれ以上なければヌル文字('\0')を返します。
• skipSpace() は、構文的に意味の無い空白文字を読み飛ばします。(読込み位置を進めます)
• isEnd() は、対象文字列の終わりに達した時に true を返します。
• <変更> isSeparator() は、引数が演算記号や、空白文字、括弧の場合に true を返します。これは、識別子のような記号で区切られる文字列の終了位置の判定に使用されます。
  修正前は、直接charリテラルと比較していましたが、配列 separators_ に登録された文字を、Arrays.binarySearch() を使用して検索し、見つかれば true を返します。Arrays.binarySearch() の要件として、検索対対象の配列がソート済みであることを要求されますので、静的初期化子(配列初期化直後の static{ ... })でソートを行っています。
  尚、前回の Tokenクラスで設定した記号種類に比べ、区切りとなる記号が少ないのは、自分で使用する上位プログラムの要件に合わせています。(大カッコなどの使用を想定していません)
• <追加> isQuote() は、クォート文字の場合に、trueを返します。
  判定方法は、isSeparator() と同様、対象の文字を静的配列 separators_ に登録しています。
• <追加> isSymbol_1() は、1文字でトークンを形成する記号(静的配列 symbol1_ に含まれる文字)ならば true を返します。
• <追加> isWhitespace() は、本来不要ですが、処理本体の中に、インスタンスメソッドと Java API が混在するのが微妙ですので、追加しました。
• <追加> isExists() は、配列検索処理の実装部分です。(Arrays.binarySearch() を何箇所も使用するのは冗長に思えたので)
• <追加> 静的配列は、それぞれ上述した isSeparator()、isQuote()、isSymbol_1() での検索対象です。いくつか不足していた文字を追加してます。

    private char next() {
        skipSpace();
        return nextAll();
    }

    private char nextAll() {
        char c = aChar();
        ++pos_;
        return c;
    }

    private char aChar() { return isEnd() ? '\0' : target_.charAt(pos_); }

    private void skipSpace() {
        while ( !isEnd()  &&  Character.isWhitespace(aChar()) ) { pos_++; }
    }

    private boolean isEnd() { return length_ <= pos_; }
    private boolean isSeparator(char c)     { return exists(separators_, c);    }
    private boolean isQuote(char c)         { return exists(quotes_, c);        }
    private boolean isSymbol_1(char c)      { return exists(symbol1_, c);       }
    private boolean isWhitespace(char c)    { return Character.isWhitespace(c); }

    private boolean exists(char[] arr, char c) {
        return java.util.Arrays.binarySearch(arr, c) >= 0;
    }

    private static final char[] separators_ = { ',', '=', '(', ')', '{', '}', ':' };
    static { Arrays.sort(separators_); }

    private static final char[] quotes_ = { '"', '\'' };
    static { Arrays.sort(quotes_); }

    private static final char[] symbol1_ = { '(', ')', '{', '}', ':', ',', '=', '&' };
    static { Arrays.sort(symbol1_); }


    int          pos_ = 0;      // "next" analyzing position

解析処理

字句解析を行い、その結果を前回作成した Token オブジェクトのリストとして返します。
返値は内部に保持しているトークンリスト tokens_ のコピーです。標準のリストですので、呼び出し元で要素の追加/削除が可能な上、それがオブジェクトが保持している tokens_ に影響してしまう(正確には同じオブジェクトを参照している)為です。
analyze() を二度目以降に呼び出した場合、既に作成済みのトークンリストのコピーを返します。再解析は行いません。

• <修正> next() で、解析対象の1文字を取得します。文字列の終わりに達していた場合、ヌル文字が返されますので、それをループの終了条件(正確には継続条件ですね...)にします。
  next() 内部で空白文字を読み飛ばすように変更しました。
• <修正> 読取った文字が、引用符を除く一文字トークンに該当する(isSymbol_1() が true を返した)場合、一文字トークンを作成してリストに追加します。
• <修正> 読取った文字が、引用符の場合は、quotedText(char) に処理を渡します。引数として、読み取った引用符を渡します。
• 上記のいずれにも該当しない場合は、text(char) に処理を渡します。最初の文字をtext()内部で文字列トークンとして登録してもらう為、引数で渡します。
• <修正> ループを抜けたら、トークンリストのコピーを呼び出し元に返します。
  もし、ファクトリメソッドに不正な引数を渡していた場合は、解析対象文字列が空文字列になっている為、ループは実行されず、空リストが返されます。

next() の実装変更(空白文字スキップ)と、判定メソッドの追加により、以前の switch文による制御に比較し、すっきりしました。ついでに、判定の意図がメソッド名に表れているので、コメントも不要になりました。(なりましたよね？)

    public java.util.List<Token> analyze() {
        char c;
        while ( (c = next()) != '\0' ) {
            if ( isSymbol_1(c) ) {
                tokens_.add( Token.create(c) );
                continue;
            }
            if ( isQuote(c) ) {
                quotedText(c);
                continue;
            }
            text(c);
        }
        return new java.util.ArrayList<>(tokens_);
    }

    java.util.List<Token> tokens_ = new java.util.ArrayList<>();  // result

引用符付き文字列処理

引用符で囲まれた文字列を空白文字も含めて、1つのトークンにします。
引用符と最初の文字の間、最後の文字と引用符の間の空白文字は除去されますが、それを除く文字列の間の空白文字は、改行文字やタブ文字も含め、そのまま保持します。

• まずはメソッドの入り口で、引用符をトークンリストに登録します。
• <修正> 次にループを使用し、文字列の終わりか、引数で渡された引用符と同じ引用符が現れるまで、StringBuilder に文字を追加して行きます。ここでは、空白文字をスキップして欲しくないので、空白文字を含めて取得できる、nextAll() を使用しています。
• ループ終了時後、StringBuilder に1文字でも追加されていれば、文字列トークンとして登録します。("")という具合に、引用符の中身が無ければ、文字列トークンは追加されません。
• 最後にループを抜けた時に取得していた、引用符をリストに登録します。

    /** 次のクォート文字までを一塊のトークンとして切出し. */
    private void quotedText(char quote) {
        tokens_.add( Token.create(quote));  // create token of begin quote

        java.lang.StringBuilder builder = new java.lang.StringBuilder();
        char c;
        while ( (c = nextAll()) != '\0'  &&  c != quote) { builder.append(c); }

        if ( builder.length() != 0 ) {
            tokens_.add( Token.create(builder.toString()) );  // append string
        }

        tokens_.add( Token.create(c) );  // append token of end quote
    }

文字列(識別子)処理

引用符に囲まれていない文字列トークンを切り出します。

• まずは、文字列の一文字目を引数として受け取っているので、それを StringBuilder に追加します。
• <修正> 文字列の終わり、区切り文字、空白文字のいずれかになるまで文字を読み取り、StringBuilder に追加します。
  空白文字をスキップすると、スペースによるトークンの終わりが検出不能になる為、文字取得を nextAll() に変更しました。
• ループが終了したら、文字列トークンとしてリストに登録します。
• もし対象文字列の終わりに達していた場合は、この時点で終了します。この場合、c = '\0' となる為、そのまま登録すると、不明トークンが追加されてしまう為、下の登録処理を抑止する必要があります。
• 最後に、ループ終了条件として前に読み込まれた区切り文字をトークンとして登録します。空白文字は複数存在しますが、全てスペース1文字のトークンとして登録します。

    /** セパレータ、空白文字までを一塊のトークンとして切出し. */
    private void text(char first) {
        java.lang.StringBuilder builder = new java.lang.StringBuilder();
        builder.append(first);

        char c;
        while ( (c = nextAll()) != '\0'  &&  !isSeparator(c)  &&  !Character.isWhitespace(c) ) {
            builder.append(c);
        }
        tokens_.add( Token.create(builder.toString()) );

        if ( isEnd() ) { return; }

        tokens_.add( isWhitespace(c) ? Token.create(' ') : Token.create(c) );
    }

状態取得

LexicalAnalyzer の状態取得メソッドです。

• isEmpty() は、解析結果のトークンリストが空の場合に true を返します。analyze() 実行前は、トークンリストは空ですので、この場合も true を返します。
• isValid() は、解析結果に不正なトークンが無いかチェックします。不正(返り値 = false) となる条件は以下の3パターンです。
  • Token.kind() == Kinds.Unknownとなるトークンがリストの中に一つでも含まれている。
  • 解析対象文字列が空文字列。
  • 解析実行前(状態が不明な為)

    public boolean isEmpty() { return tokens_.size() == 0;}

    public boolean isValid() {
        return !isEmpty()  &&  tokens_.stream().noneMatch( e -> e.kind() == Token.Kinds.Unknown );
    }

テスト

最後に長くなりますが、テスト用の main() メソッドと処理結果を挙げておきます。JUnitなんて知らない
処理結果の行数を減らす為、区切りトークンは非表示にしています。

    public static void main(String[] args) {
        String s;
        java.util.List<Token> tokens;
        LexicalAnalyzer lex;

        System.out.println("test 1 -----------------------------------------------------------------------------------");
        LexicalAnalyzer.create(null).analyze().stream().filter( e -> e.kind() != Token.Kinds.Separator )
                                                       .forEach( e -> System.out.println(e) );
        System.out.printf("isEmpty()  after analyze  : %s\r\n", lex.isEmpty());

        System.out.println("\r\ntest 2 -------------------------------------------------------------------------------");
        s = "s";
        lex = LexicalAnalyzer.create(s);
        System.out.printf("isEmpty() before analyze() : %s\r\n", lex.isEmpty());
        lex.analyze().stream().filter( e -> e.kind() != Token.Kinds.Separator )
                              .forEach( e -> System.out.println(e) );
        System.out.printf("isEmpty() after analyze()  : %s\r\n", lex.isEmpty());

        System.out.println("test 3 -----------------------------------------------------------------------------------");
        s = "   [some] -c  \" text  document  \", \r\n (sequence1, \"seq 2\r\n  quoted\",seq3 seq4 'seq 5  ')\"ss";
        lex = LexicalAnalyzer.create(s);
        System.out.printf("isValid() before analyze() : %s\r\n", lex.isValid());
        lex.analyze().stream().filter( e -> e.kind() != Token.Kinds.Separator )
                              .forEach( e -> System.out.println(e) );
        System.out.printf("isValid() after  analyze() : %s\r\n", lex.isValid());
    }

実行結果

test 1 ...引数に null を渡したケース

ファクトリメソッドの中で、空文字列をセットして、エラー無く動くように仕込んである為、analyze() と、その後続の stream() まで実行しても問題なし。何も表示されないだけ。
"isEmpty() ..." は、isEmpty() メソッドのテスト結果。

test 2 ...1文字だけ解析

解析結果の確認というよりも、analyze()実行前後の isEmpty() の仕様確認。

test 3 ...それらしい文字列の解析

"seq 2..." は引用符の中に改行が含まれているので、処理結果にも改行が含まれている。
最後の isValid() が false になっているのは、引用符文字列として解析を始めたが、対の引用符が無く、文字列終了となった為。きちんと閉じれば true になる。

test 1 -------------------------------------------------------------------------------
isEmpty()  after analyze  : true

test 2 -------------------------------------------------------------------------------
isEmpty() before analyze() : true
[String          : "s"]
isEmpty() after analyze()  : false

test 3 -------------------------------------------------------------------------------
isValid() before analyze() : false
[String          : "[some]"]
[String          : "-c"]
[DoubleQuote     : """]
[String          : "text  document"]
[DoubleQuote     : """]
[LeftParenthesis : "("]
[String          : "sequence1"]
[DoubleQuote     : """]
[String          : "seq 2
  quoted"]
[DoubleQuote     : """]
[String          : "seq3"]
[String          : "seq4"]
[SingleQuote     : "'"]
[String          : "seq 5"]
[SingleQuote     : "'"]
[RightParenthesis: ")"]
[DoubleQuote     : """]
[String          : "ss"]
[Unknown         : "**Unknown**"]
isValid() after  analyze() : false

まとめ

かなり長くなってしまいましたが、以上で字句解析器の作成は終了となります。

ここまでやって構文解析は？ と言われそうですが、利用する側の構文が決まっていないので、書けません。
想定される文法は、ある程度決めてありますが、その為の仕込みが追いついていないので、いつ書くことになるかは未定です。(先にコンソールクラスを完成させねばならない...)