日毎に寒さが加わり、心細くなってまいりましたがRhinoコードリーディング 0x04回目です。

今回はParserクラスを中心とした、ソースコード解析について学んだことの覚え書きのような話をします。

前回もお話ししましたが、Parserクラスはソースコードを解析して抽象構文木を作成するクラスです。

例えば"1+2"をparseした場合、以下のような抽象構文木が作成されます。

- AstRoot(root要素)
  - ExpressionStatement(式文)
    - InfixExpression(二項演算式) @type = ADD(+)
      - NumberLiteral(数値リテラル) @number = 1.0 # Left
      - NumberLiteral(数値リテラル) @number = 2.0 # Right

これはコンパイラやインタプリタでは一般的な処理ですが、

以前より、yaccやJavaCCなどの構文解析器作成ツールを使用した解析が主流です。

しかしRhinoでは、それらを一切使わなず手書きで構文解析器を作成しています。

構文解析には「再帰下降法」と呼ばれる解析手法を使います。

再帰下降法とはトークンに対応した表を作らず、

「トークンAの後にトークンBがきたらこんな処理」と直接関数を作っていく解析方法で、

自動生成が難しい反面、構文規則通りに書けばいいので手書のパーサーを作る際によく使われます。

このあたりは口で説明するより、実際に処理をみたほうが速いと思うので前回と同様、疑似コードをのせてみます。

public class Parser 
{
    public AstRoot parse(String sourceString, String sourceURI)
    {
        this.ts = new TokenStream(this, sourceString);
        AstRoot root = new AstRoot();
        currentScope = currentScriptOrFn = root;
        for (;;) {
            int token = ts.getToken(); // 現在のトークンを取得
            if (token <= Token.EOF) {
                break;
            }
            AstNode n;
            if (token == Token.FUNCTION) {
                // 関数の解析
                n = function(); 
            } else {
                // 文の解析
                n = statement(); 
            }
            root.addChildToBack(n);
            n.setParent(root);
        }
    
        return root;
    }

    private FunctionNode function()
    {
        // 現在のトークンを取得
        int token = ts.getToken(); 

        Name name = null;
        if (token == Token.NAME) {
            // 関数名の取得
            name = createNameNode(true, Token.NAME);
        } else {
            // 無名関数 λ...
        }
        FunctionNode fnNode = new FunctionNode(name);
        // 引数の解析
        parseFunctionParams(fnNode); 
        // bodyの解析
        fnNode.setBody(parseFunctionBody()); 

        return fnNode;
    }

    private AstNode statement() {
        int token = ts.getToken();
        switch (token) {
          case Token.IF: // if文
              return ifStatement();

          case Token.SWITCH: // switch文
              return switchStatement();

          case Token.WHILE: // while文
              return whileLoop();

          case Token.FOR:  // for文
              return forLoop();

          case Token.FUNCTION: // 関数
              return function(); 

          // ...略

          default: // それ意外の文(式文)
              return new ExpressionStatement(expr(), !insideFunction());
        }
    }

    // その他各構文の解析
}

解説の為にかなりの部分の処理を省略しましたが、大体の流れは実際のコードでも同様です。

前回のエントリーで「構文解析の前にはソースコードからトークンを解析する「字句解析」の処理を行なう必要がある」と書きましたが、

その責務を受けもっているのがTokenStreamクラスです。

TokenStreamクラスのgetTokenメソッドを呼ぶと、ソースコードから字句の解析を行ない、

現在カーソルが指し示すトークンを一つ取得した後にカーソルを一つ進めます。

getTokenメソッドが呼ばれる度に、字句解析の処理を行なうため、

字句解析と構文解析は処理フェーズとして明確に分けられていません。

また、コンパイラによっては「意味解析」と呼ばれるフェーズが存在します。

これは「プログラムの構成要素どうしが、意味的に正しいつながりをもっているかどうかを検査する」フェーズですが、

Rhinoではこれをやっていないというのが、現在での見解です。

Rhinoでも、構文解析時にはシンボルテーブルの作成を、

同じく中間コードの作成時には関数テーブルの作成を行なっているのですが、

その際に意味的な妥当性の検査を行なっていない為です。（意味的におかしいコードは実行時例外になったりする）

さて、このあたりで構文解析の話は一旦終了です。

最後に学習のメモ代りに使用したマインドマップを載せて置きます。

何か他の方の学習の肥やしになれば幸いですが、

内容の正誤は保証できませんのであくまで参考程度に留めておいてください。