今日書くこと

今日は昨日から続いている、「JavaでBasicライクな言語のインタプリタを実装する」の第2回目の記事です。昨日の記事は

namazu-tech.hatenablog.com

こちらになります。

今日は構文解析の部分を解説＆実装していこうと思います。

構文解析

構文解析とは？

構文解析とは、字句の並びから、プログラム言語の文法(Syntax)と照らし合わせAST（抽象構文木)を作ることです。よくあるシンタックスエラー（かっこの対がおかしいとか、for文の使い方が間違ってる）などはこの段階で判明するわけですね。

具体的には

a = 5
DO UNTIL a < 1
PRINT "HELLO"
a = a -1
LOOP
END

このようなプログラムを読み込んで、

f:id:kituneko-510:20171227140051p:plain

のような構文木を構築することです。

Do untilのブロック内に関数実行と代入文があり、代入文はaにa-1の結果を入れる。と言うような意味が発生するようになります。

字句解析の時点では、それぞれどんな字句かだけだったのが、字句の並びと文法規則からそれぞれ意味を持つようになります。

文法

ボスが文法を示してくれるのでそれを参考にしましょう。

https://service.cloud.teu.ac.jp/lecture/CSF/ktago/lecture_prog/syntax.txt

BNF記法で書いてあるやつですね。　これとにらめっこしながら作ります。

構文解析部分攻略方

ファースト集合とかフォロー集合とか、終端記号とか非終端記号とかの単語をちゃんと理解しましょう。 kmd先生の講義を取ればちゃんと教えてくれる上に、構文解析表とかも書けるようになります。

ボスもなんだかんだそれっぽいことを教えてくれるけどね。　

この部分は基本的にひたすら実装なので流れをつかんで時間があるときにやってください。式の部分は明日解説しますが、そこだけちょっと面倒。　

実装

実装方針

非終端要素についてクラスを１つ１つ作ります。それぞれのクラスはNodeクラスを継承するようにします。

Nodeクラスは抽象クラスとしparse()の関数実装を強制します。

Nodeクラスを継承した非終端要素のクラスでisMatch()とparse()を実装します。

isMatchは、与えられた字句が、その非終端要素のファースト集合に含まれるかどうかを判定し、含まれるならば自身をインスタンス化して返します。また、今回の文法はLL2である（２個先まで読まないとどの文法規則を適用すればいいか確定しない cf 代入文(NAME => EQ)と関数呼び出し(NAME => LP))のでそういう重複がありえる非終端要素の場合は確定させるまで読んで返します。

parseは、字句を読み進め、自分の下の要素を構築したりします。

コードで示した方が早そうなので書いていきます。

すべての実装は、

github.com

にあります。　syntax_nodeパッケージが今回の非終端要素のクラス群が入っているところです。

それでは。

Node.java

大本のクラスです。すべての非終端要素のクラスはこれを継承させます。

/**
 * 全構文要素の親クラス.
 * 構文木の非終端要素
 */
public abstract class Node {
    /**
    * Nodeのタイプ.
    */
    public final NodeType type;
    
    /**
    * 実行環境.
    * 変数テーブル. 関数テーブル. 字句解析器等.
    */
    public final Environment env;
    
    public Node(NodeType type, Environment env) {
        this.type = type;
        this.env = env;
    }
    
    public NodeType getType() {
        return type;
    }
    
    /**
    * 文法解析メソッド
    * @return 構文にマッチしないならfalse
    */
    public abstract boolean parse();
    
    // toStringの実装を強制
    public abstract String toString();
    
    /**
    * 次のLexicalUnitを見る Utilメソッド
    */
    protected LexicalUnit peekLexicalUnit() {
        LexicalUnit unit = env.getInput().get();
        env.getInput().unget(unit);
        return unit;
    }
    
    /**
    * 次の字句タイプを見て期待した字句と一致していればその字句を読み飛ばすUtilメソッド
    * NLとかLOOPとかのチェックしないといけないけど無視する字句に使う
    *
    * もし次に現れた字句が期待した物と一致しないのであればfalseを返す
    *
    * @param expectType 複数指定した場合は指定した順番でチェックしつつ読み飛ばす
    * @return 期待した字句と一致しない場合false
    */
    protected boolean skipExpectNode(LexicalType... expectType) {
        for (LexicalType expect : expectType) {
            if (peekLexicalUnit().getType() == expect) {
                env.getInput().get();
                continue;
            }
            return false;
        }
        return true;
    }
}

ポイントとしては、Nodeクラスにある程度のUtilメソッドを含めておくと楽です。　例えばpeekLecicalUnitは単に次の字句を見ることができます。 skipExpcetNodeは字句をチェックしつつ読み流すときに使います。　この処理はなんども後で出てくるので一括してここで定義しておくといいです。

ProgramNode.java

Nodeを継承した、構文木のトップ要素のProgramNodeは以下のように書けます

/**
 * <program>  ::=
 *              <stmt_list>
 *
 */
public class ProgramNode extends Node {
    
    // StmtListNode
    private Node child;
    
    public ProgramNode(NodeType type, Environment env) {
        super(type, env);
    }
    
    static FirstCollection fc = new FirstCollection(
            StmtListNode.fc,
            BlockNode.fc
            );
    
    public static Node isMatch(Environment env, LexicalUnit first) {
        // LexicalUnit first が　First集合に含まれる字句か判断する.
        if (fc.contains(first)) {
            return new ProgramNode(NodeType.PROGRAM, env);
        }
        
        return null;
    }
    
    @Override
    public boolean parse() {
        NextNodeList nextNodeList = new NextNodeList(StmtListNode.class);
        Node chiled = nextNodeList.nextNode(env, peekLexicalUnit());
        if (chiled != null) {
            this.child = chiled;
            return chiled.parse();
        }
        return false;
    }
    
    @Override
    public String toString() {
        return child.toString();
    }
    
}

isMatchではProgramノードのファースト集合に含まれるかを判定させます。ここでProgramノードのファースト集合はStmtListNodeのファースト集合とBlockNodeのファースト集合の和集合であるということに気づくとコードがきれいになります。

この和集合を扱うために以下のようなことをします。

/**
 * First集合のコレクション.
 *
 */
public class FirstCollection {
    List<LexicalType> firstListUnit;
    
    public FirstCollection(LexicalType... firstTypes) {
        this.firstListUnit = Arrays.asList(firstTypes);
    }
    
    public FirstCollection(FirstCollection... firstCollections) {
        this.firstListUnit = new ArrayList<>();
        for (FirstCollection firstCollection : firstCollections) {
            firstListUnit.addAll(firstCollection.firstListUnit);
        }
    }
    
    public boolean contains(LexicalUnit unit) {
        LexicalType type = unit.getType();
        return firstListUnit.contains(type);
    }
}

このようなFirst集合を合わせたりして扱うことができるクラスを用意しておき、上位のfirst集合は直接字句を書かず、子のファースト集合の和集合として定義するときれいです。

   static FirstCollection fc = new FirstCollection(
            StmtListNode.fc,
            BlockNode.fc
            );

こんな感じでね。

parse()は子のisMatch(stmtlistのisMatch)を呼び、自身のフィールドに子のインスタンスを保持するようにします。こうして、ProgramがフィールドにStmtListのインスタンスを持ち、StmtListがフィールドにAssignStmtやLoopBlockのインスタンスを持ち。。。と順々につなげていくことでリンクするように、構文木が表現できます。

またコードをさくっと終わらせるために、一々isMatchを呼び出して確定させる等の処理は面倒（子に持ちうるのが複数の非終端要素の場合があり得て、何個もisMatchを呼ばなきゃいけない）なので、

/**
 * 子になりうるNodeのリスト.
 *
 * first集合の字句を投げて、子のnodeのインスタンスが得られるUtilクラス
 *
 * 必須要件.
 * 登録されたNodeにはisMatchが静的メソッドとして実装されている
 */
public class NextNodeList extends ArrayList<Class<? extends Node>> {
    
    public NextNodeList(Class<? extends Node>... nextNodes) {
        addAll(Arrays.asList(nextNodes));
    }
    
    /**
    * 次の一致するノードを探し出す.
    */
    public Node nextNode(Environment env, LexicalUnit unit) {
        Iterator<Class<? extends Node>> i = iterator();
        while (i.hasNext()) {
            Method isMatch;
            try {
                isMatch = i.next().getMethod("isMatch", Environment.class, LexicalUnit.class);
                Object res = isMatch.invoke(null, env, unit);
                
                if (res != null) {
                    return (Node) res;
                }
                
            } catch (NoSuchMethodException | SecurityException | IllegalAccessException | IllegalArgumentException
                    | InvocationTargetException ex) {
                // programming error
                ex.printStackTrace();
            }
        }
        return null;
    }
}

こんなちょっとごにょってるクラスを作ってしまい、

NextNodeList nextNodeList = new NextNodeList(StmtListNode.class);
Node chiled = nextNodeList.nextNode(env, peekLexicalUnit());

こんな感じで一気に処理すればisMatchをNextNodeListに登録したクラス全部に試行して、確定した子ノードのインスタンスを返してくれるnextNodeメソッドが使えるようになります。

リフレクションしたのは反則感があるけど。

StmtListを作ったら、似たような感じでどんどん構文を下に向かって作っていきます。（ExprNode以外はノリでいけます）

StmtListNode.java

/**
 * <stmt_list>　::=
 *         <stmt>
 *         | <stmt_list> <NL> <stmt>
 *         | <block>
 *         | <block> <stmt_list>
 *
 */
public class StmtListNode extends Node {
    private List<Node> childNodes = new ArrayList<>();
    
    public StmtListNode(NodeType type, Environment env) {
        super(type, env);
    }
    
    static FirstCollection fc = new FirstCollection(
            StmtNode.fc,
            BlockNode.fc
            );
    
    public static Node isMatch(Environment env, LexicalUnit first) {
        if (fc.contains(first)) {
            return new StmtListNode(NodeType.STMT_LIST, env);
        }
        return null;
    }
    
    @Override
    public boolean parse() {
        while (true) {
            // NLを読み飛ばす
            if (peekLexicalUnit().getType() == LexicalType.NL) {
                env.getInput().get();
                continue;
            }
            
            NextNodeList nextNodeList = new NextNodeList(StmtNode.class, BlockNode.class);
            Node chiled = nextNodeList.nextNode(env, peekLexicalUnit());
            if (chiled != null) {
                if (!chiled.parse()) {
                    return false;
                }
                // Stmtの後にはNLが存在する
                if (chiled instanceof StmtNode) {
                    env.getInput().get();
                }
                childNodes.add(chiled);
                continue;
            }
            return true;
        }
    }
    
    @Override
    public String toString() {
        return childNodes
                .stream()
                .map(Node::toString)
                .collect(Collectors.joining(";"));
    }
}

StmtListも同じように、ファースト集合はStmtNodeとBlockNodeのファースト集合の和集合になるので、ProgramNodeと同じように定義します。 parseもStmtListの下はStmtNodeかBlockNodeなので、どちらか調べてさらにそれぞれparseしていきます。子のparseに成功したら、自身のフィールドで子ノードとして保持しておきます。

LoopBlockNode.java

だんだん下のほうの非終端要素になると、終端要素をチェックしたり色々が始まります。 LOOPとかはその最たる例。　DO や　UNTILとかがちゃんと正しい順番で入ってるかチェックしないとだめ

/**
 * <block> ::=
 *         | <WHILE> <cond> <NL> <stmt_list> <WEND> <NL>
 *         | <DO> <WHILE> <cond> <NL> <stmt_list> <LOOP> <NL>
 *         | <DO> <UNTIL> <cond> <NL> <stmt_list> <LOOP> <NL>
 *         | <DO> <NL> <stmt_list> <LOOP> <WHILE> <cond> <NL>
 *         | <DO> <NL> <stmt_list> <LOOP> <UNTIL> <cond> <NL>
 */
public class LoopBlockNode extends Node {
    
    /**
    * Do While 文　つまり１度は走る文かどうか
    */
    private boolean isDo;
    
    /**
    * While文ならtrue Until文ならfalse
    */
    private boolean isWhile;
    
    /**
    * ループ実行条件ノード
    */
    private CondNode condNode;
    
    /**
    * ループブロック本体
    */
    private StmtListNode stmtListNode;
    
    public LoopBlockNode(NodeType type, Environment env) {
        super(type, env);
    }
    
    static FirstCollection fc = new FirstCollection(
            LexicalType.WHILE,
            LexicalType.DO
            );
    
    public static Node isMatch(Environment env, LexicalUnit first) {
        if (fc.contains(first)) {
            return new LoopBlockNode(NodeType.LOOP_BLOCK, env);
        }
        return null;
    }
    
    @Override
    public boolean parse() {
        LexicalUnit first = env.getInput().get();
        // DO
        if (first.getType() == LexicalType.DO) {
            return doParse();
        }
        // WHILE
        if (first.getType() == LexicalType.WHILE) {
            return whileParse();
        }
        return false;
    }
    
    /**
    * Do文を解析
    * @return
    */
    private boolean doParse() {
        isDo = true;
        
        LexicalUnit next = env.getInput().get();
        switch (next.getType()) {
        case WHILE:
        case UNTIL:
            // do - (while or until) - cond -nl -stmtlist - loop - nl
            untilOrWhileHandl(next);
            if (!condHandl()) {
                return false;
            }
            if (!skipExpectNode(LexicalType.NL)) {
                return false;
            }
            if (!stmtListHandl()) {
                return false;
            }
            if (!skipExpectNode(LexicalType.LOOP, LexicalType.NL)) {
                return false;
            }
            return true;
        case NL:
            // do - nl - stmtlist - loop - (while or until) - cond -nl
            if (!stmtListHandl()) {
                return false;
            }
            if (!skipExpectNode(LexicalType.LOOP)) {
                return false;
            }
            if (!untilOrWhileHandl(env.getInput().get())) {
                return false;
            }
            if (!condHandl()) {
                return false;
            }
            if (!skipExpectNode(LexicalType.NL)) {
                return false;
            }
            return true;
     default:
            return false;
        }
        
    }
    
    /**
    * While文を解析
    * @return
    */
    private boolean whileParse() {
        isDo = false;
        isWhile = true;
        
        // while -> cond -> nl -> stmtlist -> loop -> nl
        if (!condHandl()) {
            return false;
        }
        if (!skipExpectNode(LexicalType.NL)) {
            return false;
        }
        if (!stmtListHandl()) {
            return false;
        }
        if (!skipExpectNode(LexicalType.LOOP, LexicalType.NL)) {
            return false;
        }
        return true;
    }
    
    /**
    * Loopブロックの条件式部分を解析
    * @return SyntaxErrorならfalse
    */
    private boolean condHandl() {
        condNode = (CondNode) CondNode.isMatch(env, peekLexicalUnit());
        if (condNode == null || !condNode.parse()) {
            return false;
        }
        return true;
    }
    
    /**
    * LoopブロックのStmtList部分を解析
    * @return SyntaxErrorならfalse
    */
    private boolean stmtListHandl() {
        stmtListNode = (StmtListNode) StmtListNode.isMatch(env, peekLexicalUnit());
        if (stmtListNode == null || !stmtListNode.parse()) {
            return false;
        }
        return true;
    }
    
    /**
    * Until文なのかWhile文なのか調べてインスタンス変数に情報格納
    * @param unit Until or Whileの　LexicalUnit
    */
    private boolean untilOrWhileHandl(LexicalUnit unit) {
        switch (unit.getType()) {
        case WHILE:
            isWhile = true;
            return true;
            
        case UNTIL:
            isWhile = false;
            return true;
        }
        
        return false;
    }
    
    @Override
    public String toString() {
        return "LOOP[" + condNode + "[" + stmtListNode + "]]";
    }
}

こんな感じでいけます。　そろそろ長くなって辛くなってきた。 LOOPのチェックとかがちゃんとできればあとは流れでほかのNodeも作れるでしょ。

さいご

ファースト集合とか、構文解析表とか知ってれば、あとは構文木をどんな感じに構成すればいいか（フィールドに子を持たせる）を思いつけばコードにできますね。

ここはひたすら実装が必要なのでだるいところ。　BNF記法流し込んだら構文木自動構築みたいなことしないかぎり実装はそんな面倒じゃない。

明日は構文木を組み上げるうえで一番面倒くさい式の解析の部分を書こうと思います。

ぬまのどろ

namazuのゆるい日記。　ゆるり更新。

JavaでBasicライク言語のインタプリタ実装 #2 構文解析編-1