目次


JavaCC、構文解析ツリー、およびXQueryの文法: 第2回

JJTreeによるカスタム構文解析ツリーの生成と利用

Comments

JavaCCパーサー生成プログラムには、1つの大きな欠点があります。つまり、BNF (バッカス正規形式) をエンコードした .jj文法スクリプトにクライアント・サイドのJavaコードのかなりの部分を埋め込む必要があるため、開発サイクルで通常のJava IDEのメリットを生かせなくなってしまうということです。

そこで登場するのが、JavaCCの姉妹ツールともいうべきJJTreeです。このJJTreeから生成されるパーサーの主な機能は、埋め込まれているJavaアクションを実行することではなく、解析対象の式の独立した構文解析ツリー表現を生成することです。1つのツリーができ上がれば、ツリーを生成した構文解析コードとは関係なく実行時にツリーをたどれるので、構文解析セッションの状態情報を取り込むのが容易になります。また、構文解析ツリーを使えば、デバッグも簡単になり、開発時間も短縮できます。なお、JJTreeは、JavaCCの配布ファイルに組み込まれています(参考文献を参照)。

ここで、1つだけ用語の説明をしておきましょう。構文解析ツリー抽象構文ツリー (abstract syntax tree: AST) は、基本的に同じ文法構造を指しています。この記事では、構文解析ツリーという表現を使っていますが、言葉にうるさい人であれば、ASTのほうが正確な言い方だということになるかもしれません。

JJTreeを使用するには、次の2つの作業が必要です。

  1. JJTreeの入力として使用する .jjtスクリプトの作成
  2. 実行時に生成される構文解析ツリーをたどって評価するためのクライアント・サイド・コードの記述

この記事では、その両方の作業について説明します。ありとあらゆることを取り上げるわけではありませんが、入門編としては十分でしょう。

JJTreeの基本

JJTreeはプリプロセッサーです。特定のBNFのためのパーサーを生成するプロセスはシンプルで、次の2つのステップからなっています。

  1. いわゆる .jjtファイルに対してJJTreeを実行する (結果として、.jjという中間ファイルが生成されます)
  2. そのファイルをJavaCCでコンパイルする (このプロセスについては、第1回の記事で取り上げました)

.jj形式については、第1回の記事で取り上げたとおりですが、.jjtファイルの構造も .jj形式をわずかに拡張したものにすぎないので、心配するには及びません。主な違いは、ノード・コンストラクターという新しい文法構造が追加されるという点です。この構造によって、構文解析時に、どこで、どんな条件に基づいて構文解析ツリーの各ノードを生成するのかを指定できます。要するに、この構造の指定によって、パーサーによって生成される構文解析ツリーの形状と内容が決まるということです。

リスト1は、シンプルなJavaCC .jjスクリプトであり、第1回の記事で取り上げたものとよく似ています。ここでは、簡単にするために生成規則の部分だけを示します。

リスト1. simpleLang のJavaCC文法
void simpleLang() 	: {} 	{ addExpr() <EOF> }
void addExpr()		: {}	{ integerLiteral() ( "+" integerLiteral() )? } 
void integerLiteral()	: {}	{ <INT> }
SKIP  : { " " | "\t" | "\n" | "\r" }
TOKEN : { < INT : ( ["0" - "9"] )+ > }

この文法によれば、この言語の有効な式は次のいずれかになります。

  1. 1つの整数リテラル
  2. 整数リテラルの後にプラス記号を付けてさらに整数リテラルを指定したもの

これに対応するJJTree .jjtスクリプトは、次のようになります (この場合も少し省略しています)。

リスト2. リスト1のJavaCC文法に相当するJJTree文法
SimpleNode simpleLang() : #Root       {}  { addExpr() <EOF> { return jjtThis; }}
void addExpr()          :             {}  { integerLiteral() ( "+" integerLiteral() #Add(2) )? } 
void integerLiteral()   : #IntLiteral {}  { <INT> } 
SKIP  : { " " | "\t" | "\n" | "\r" }
TOKEN : { < INT : ( ["0" - "9"] )+ > }

このスクリプトでは、新しい文法構造がいくらか追加されています。これから主な特徴に触れていきますが、詳細はあとから取り上げることにします。

JJTree文法の特徴

最初に注目したいのは、JavaCCの冒頭にあるsimpleLang() 生成規則のプロシージャー構文にSimpleNode という戻り型が指定されているという点です。さらに、return jjtThis (JJTreeのちょっとした特徴) というJavaアクションも埋め込まれているので、アプリケーション・コードからパーサーのsimpleLang() メソッドを呼び出すと、構文解析ツリーのルートが戻され、そこからツリーをたどれるようになります。

JavaCCの場合、パーサーの呼び出しは、次のようになります。

    SimpleParser parser = new SimpleParser(new StringReader( expression ));
    parser.simpleLang();

それが、JJTreeでは次のようになります。

    SimpleParser parser = new SimpleParser(new StringReader( expression ));
    SimpleNode rootNode = parser.simpleLang();

ただし、ここで生成するルート・ノードは、単なるSimpleNode 型ではありません。実際には、リスト2#Root ディレクティブによって指定されているとおり、Root 型になります(もっとも、上記の呼び出しコードではその点を利用していません)。Root は、SimpleNode の下位ノードです。実際のところ、JJTreeから作成されるパーサーによって生成されるノードはすべてSimpleNode の下位ノードになります。これから、SimpleNode の組み込みメソッドをいくつか見ていきましょう。

まず、addExpr() 生成規則の#Add(2) 構造は、その上にある#Root ディレクティブといくつかの点で異なっています。

  • この構造は、パラメーター化されています。このツリー・ビルダーは、ツリー生成時にノード・スタックを利用します。ノード・コンストラクターにパラメーターを指定しない場合は、構文解析ツリーの最上位にノードが生成されるというのがデフォルトの動作です。つまり、同じ「ノード・スコープ」で生成されるすべてのノードをノード・スタックの外に出し、そのノード自体がそれらのノードの親になるというわけです。2 という引数は、新しい親 (この場合はAdd ノード) が2つの子ノードを持つようになるという意味です。この場合は、2つのIntLiteral サブノードを持つようになります (この点については、次の項目を参照)。JJTreeの資料には、このプロセスが詳しく説明されています。また、良質のデバッガーで実行時に構文解析ツリーをたどってみることも、JJTreeのツリー生成のしくみを理解するのに役立ちます。
  • もう1つの重要な点として、位置の問題があります。#Root ディレクティブが生成規則の本体の外にある場合は、この生成規則がトラバースされるたびにRoot ノードが生成されることになります(もっとも、この場合は1回しか生成されません)。しかし、#Add(2) ディレクティブを「0または1」というオプションの条件の内側に入れると、構文解析時にそのディレクティブを含んだオプション文節がトラバースされる場合にのみ、つまり、この生成規則が実際の加算演算である場合にのみ、Add ノードが生成されることになります。Add ノードが生成されると、integerLiteral() が2回トラバースされ、それぞれの呼び出しでツリーに1つずつIntLiteral ノードが生成されます。そのIntLiteral ノードはいずれもAdd ノードの子になります。しかし、その式が1つの整数である場合は、生成される1つのIntLiteral ノードがRoot の直接の子になります。

古いことわざをもじれば、こういう場合は、百万の言葉よりも1つの図のほうが雄弁です。上記の文法から生成される2種類の構文解析ツリーを図にすれば、次のようになります。

図1: 1つの整数式の場合の構文解析ツリー
1つの整数式の場合の構文解析ツリー
図2: 加算演算の場合の構文解析ツリー
加算演算の場合の構文解析ツリー

これから、SimpleNode のクラス階層をさらに詳しく見ていきましょう。

構文解析ツリーの操作

.jjtスクリプトの中に宣言した各ノードに基づいて、パーサーは、JJTreeのSimpleNode クラスのサブクラスを生成します。このSimpleNode は、Node というJavaインターフェースを実装したクラスです。これらのクラスのソース・ファイルはいずれも、各JJTreeスクリプトによって自動的に生成されます。また、そのときには、カスタム .jjファイルも一緒に生成されます。リスト1 に示したのは、今回のカスタム .jjファイルのサンプルです。今回のサンプルでは、JJTreeによってさらにユーザー独自のクラス(RootAddIntLiteral)のソース・ファイルや、ここでは取り上げないいくつかのヘルパー・クラスのソース・ファイルも生成されます。

SimpleNode のすべてのサブクラスは、便利な動作を継承します。その典型的な例が、SimpleNodedump() メソッドです。この記事の冒頭で、構文解析ツリーを使うと、デバッグが簡単になり、開発時間も短縮されるということを書きましたが、このメソッドは、その点を示す好例でもあります。次に示す3行のコードは、パーサーのインスタンスを作成し、そのインスタンスを呼び出し、戻される構文解析ツリーを取得し、ツリーのシンプルなテキスト表現をコンソールに書き出すクライアント・サイド・コードです。

    SimpleParser parser = new SimpleParser(new StringReader( expression ));
    SimpleNode rootNode = parser.simpleLang();
    rootNode.dump();

図2のツリーのデバッグ出力は、次のようになります。

    Root
        Add
            IntLiteral
            IntLiteral

ナビゲーション用の機能

SimpleNode に用意されているもう1つの便利なメソッドは、jjtGetChild(int) です。クライアント・サイドで構文解析ツリーを下のほうにたどっていくときにAdd ノードを検出したら、そのノードの子であるIntLiteral を取得し、その整数値を抽出し、加算を実行することになります(それがこの処理のそもそもの目的です)。たとえば、次に示すコードのaddNode が、そのAdd 型のノードを表す変数であるとすれば、そのaddNode の2つの子にアクセスできるというわけです(なお、lhsrhs はそれぞれ、左側 (left-hand side) と右側 (right-hand side) を表す略語です)。

     SimpleNode lhs = addNode.jjtGetChild( 0 );
     SimpleNode rhs = addNode.jjtGetChild( 1 );

ところが、これまでに取り上げた情報や機能をすべて活用しても、この構文解析ツリーで表されている演算の結果を計算できるわけではありません。今回のスクリプトには、1つの重要な点が抜けています。つまり、トークン分割プログラムが入力ストリーム内の整数値を検出したときに、その整数値をツリー内に保存するための記述が抜けているため、ツリー内の2つのIntLiteral ノードが、本来表しているはずの整数値を実際には含んでいない状態になっています。したがって、integerLiteral() 生成規則を修正して、整数値を保存するようにしなければなりません。さらに、SimpleNode にシンプルなアクセサー・メソッドをいくつか追加する必要もあります。

状態の保存と復元

検出されたトークンの値を正しいノードに格納するために、SimpleNode に次のような修正コードを追加します。

public class SimpleNode extends Node
    {
        String m_text;
        public void   setText( String text ) { m_text = text; }
        public String getText()              { return m_text; }
        ...
    }

さらに、JJTreeスクリプトで、次の生成規則を見つけます。

void integerLiteral() : #IntLiteral {} <INT> }

その生成規則を次のように修正します。

void integerLiteral() : #IntLiteral { Token t; } { t=<INT> { jjtThis.setText( t.image );} }

この生成規則は、t.image から検出した整数の生テキスト値を取得し、その文字列をsetText() セッターによって現在のノードに格納します。それに対応するgetText() ゲッターの使い方を示したのが、リスト5eval() クライアント・サイド・コードです。

構文解析時にm_text の値を格納したノードについて、その値を出力するようにSimpleNode.dump() を修正するのは簡単です。そのためのコードは、読者の練習のためにここでは取り上げないことにします。いずれにしても、その出力が得られれば、デバッグ用の構文解析ツリーのようすを視覚的にはっきりとつかむことができます。たとえば、「42 + 1」を構文解析した場合は、少し手を加えたdump() ルーチンによって、次のような便利な出力を生成できます。

    Root     Add         IntLiteral[42]         IntLiteral[1]

まとめ: XQuery用のBNFコード

最後にまとめとして、実社会で通用する実用的な文法コードを見てみましょう。ここでは、XQuery用の小さなBNFコードを取り上げます。XQueryとは、XML用の照会言語としてW3Cが定めた仕様です(参考文献を参照)。この部分の説明は、基本的にXPathにも当てはまります。この2つの仕様には、共通の文法が多く含まれているからです。さらに、演算子の優先順位の問題にも簡単に触れながら、このツリーをたどるコードを本格的な再帰的ルーチンに汎用化してみたいと思います。このルーチンを使えば、非常に複雑な構文解析ツリーでも十分に処理できます。

ここで取り上げるXQuery文法の一部をリスト3 に示します。このBNFコードは、2002年11月15日のワーキング・ドラフトからの抜粋です。

リスト3: XQuery文法の一部
[21]  Query              ::= QueryProlog QueryBody
	...
[23]  QueryBody          ::= ExprSequence?
[24]  ExprSequence       ::= Expr ( "," Expr )*
[25]  Expr               ::= OrExpr
	...
[35]  RangeExpr          ::= AdditiveExpr ( "to" AdditiveExpr )*
[36]  AdditiveExpr       ::= MultiplicativeExpr (("+" | "-") MultiplicativeExpr )*
[37]  MultiplicativeExpr ::= UnionExpr (("*" | "div" | "idiv" | "mod") UnaryExpr )*
      ...

ここで作成するのは、生成規則の [36] と [37] にある+-*div の各演算子を処理できる程度のJJTree文法スクリプトにすぎません。この場合も、説明を簡単にするために、この文法で扱うデータ型が整数だけであるという前提を設けています。もちろん、このサンプル文法はあまりにも小さすぎるので、豊富な式やデータ型を実際にサポートしているXQueryにたいへん失礼な感じがするのは否めませんが、それでも、JavaCCとJJTreeを活用する手始めとしてはこれで十分でしょう。今後さらに大がかりで複雑な文法に対応したパーサーを作成するにしても、これが幸先のよいスタートになるのは間違いありません。

リスト4 に示すのが、その .jjtスクリプトです。まず、ファイルの冒頭にあるoptions{} ブロックに注目してください。用意されているスイッチはほかにもたくさんありますが、そのブロックの中のオプションでは、特にこの場合のツリー生成を「マルチ」モードに指定しています。このモードでは、ノード・コンストラクターを使って、生成するノードのタイプを明示的に指定することになります。ほかにも、ここでは取り上げませんが、生成規則によってSimpleNode ノードだけを構文解析ツリーに書き出す(つまり、サブクラスは書き出さない) というオプションもあります。このオプションは、ノードのクラスを増やしたくない場合に便利です。

さらに、元のXQuery BNFでは、複数の演算子が1つの生成規則の中にまとめられているのに対し、リスト4 のJJTreeスクリプトでは、各演算子がそれぞれの生成規則に分けられているという点にも注目してください。このほうが、クライアント・サイドのコードが読みやすくなります。実際にそれをまとめるには、先ほどの整数値の説明にあったように、検出した演算子の値を格納していけばよいわけです。

リスト4: リスト3のXQuery文法に対応したJJTreeスクリプト
options {
   MULTI=true;
   NODE_DEFAULT_VOID=true;
   NODE_PREFIX=";
}

PARSER_BEGIN( XQueryParser )
package examples.example_2;
public class XQueryParser{}
PARSER_END( XQueryParser )

SimpleNode query()     #Root      : {} { additiveExpr() <EOF> { return jjtThis; }}
void additiveExpr()               : {} { subtractiveExpr() 
                                       ( "+" subtractiveExpr() #Add(2) )* }
void subtractiveExpr()            : {} { multiplicativeExpr() 
                                       ( "-" multiplicativeExpr() #Subtract(2) )* }
void multiplicativeExpr()         : {} { divExpr() ( "*" divExpr() #Mult(2) )* }
void divExpr()                    : {} { integerLiteral() 
                                       ( "div" integerLiteral() #Div(2) )* }
void integerLiteral() #IntLiteral :    { Token t; }  
                                       { t=<INT> { jjtThis.setText(t.image); }}

SKIP  : { " " | "\t" | "\n" | "\r" }
TOKEN : { < INT : ( ["0" - "9"] )+ > }

この .jjtファイルには、新しい機能がいくつか盛り込まれています。まず、この文法の演算生成規則が「反復的」になっています。つまり、オプションの第2条件として、リスト2 では? (0または1) というオカレンス標識が指定されているのに対し、ここでは* (0以上) というオカレンス標識が指定されているわけです。したがって、このスクリプトから生成されるパーサーは、「1 + 2 * 3 div 4 + 5」というような非常に長い式でも解析できます。

優先順位の実装

この文法では、「演算子の優先順位」も処理できます。たとえば、乗算と加算がある場合は、乗算のほうを優先するといった順序を指定できるわけです。その場合、「1 + 2 * 3」という式であれば、「( 1 + 2 ) * 3」ではなく「1 + ( 2 * 3 )」と評価することになります。

優先順位は、カスケード・スタイルによって実装します。つまり、各生成規則が、直後に上位の生成規則を呼び出すようにするわけです。このようなスタイルと、ノード・コンストラクターの位置や形式によって、構文解析ツリーが正しく生成され、結果としてツリーをたどる処理も正確に実行されるようになります。この場合も、言葉で説明を聞くより、図を見たほうがわかりやすいかもしれません。

図3 は、この文法によって生成される構文解析ツリーです。このツリーをたどれば、「1 + 2 * 3」を「1 + ( 2 * 3 )」として正しく評価できます。Mult 演算子のほうが、Plus 演算子よりも条件を密に結合している点に注目してください。つまり、これが正しい優先順位です。

図3. 正しい形のツリー
正しい形のツリ

一方、図4 は、この文法から生成されない架空のツリーであり、このツリーをたどると、式が「(1 + 2) * 3」と (間違って) 評価されます。

図4. 間違った形のツリー
間違った形のツリー

クライアント・サイドで構文解析ツリーをたどる

冒頭で述べたように、このパーサーを呼び出し、そのパーサーから生成される構文解析ツリーをたどるためのクライアント・サイド・コードを最後に示します。このコードでは、シンプルながらも強力な再帰的関数eval() を使って、ツリーで検出する各ノードに正しい処理を実行していきます。リスト5 では、JJTreeの内部処理の詳しい説明をコメントとして記しておきます。

リスト5. 簡単に汎用化できるeval() ルーチン
    // 'query' を評価した演算結果を戻す
    public int parse( String query )
    //------------------------------
    {
        SimpleNode root = null;
          // パーサーのインスタンスを生成する
           XQueryParser parser = new XQueryParser( new StringReader( query ));
        try
        {
            // 最上位の生成規則によってパーサーを呼び出し、// 構文解析ツリーを取得する
                root = parser.query();
            root.dump(");
        }
        catch( ParseException pe ) {
            System.out.println( "parse(): an invalid expression!" ); }
        catch( TokenMgrError e )  { System.out.println( "a Token Manager error!" );  }
        // 最上位のルート・ノードは単なるプレースホルダーなので、無視してよい
          return eval( (SimpleNode) root.jjtGetChild(0) );
    }
    int eval( SimpleNode node )
    //-------------------------
    {
        // 各ノードには、ノードのタイプを示すidフィールドがある。
        // これらをonにする。instanceofを使ってもかまわないが、効率が落ちる
           // JJTINTLITERALなどのenum値は、インターフェース・ファイル
           // SimpleParserTreeConstantsに基づく。このファイルは、SimpleParserを実装したもの。
           // このインターフェース・ファイルは、JJTreeから生成される
           // Javaの補助ソースの1つ。JavaCCからはさらにいくつかのファイルが生成される。
           int id = node.id;
        // 最終的に処理が終われば、最後にスタックを解放する
           if ( node.id == JJTINTLITERAL )
            return Integer.parseInt( node.getText() );
        SimpleNode lhs =  (SimpleNode) node.jjtGetChild(0);
        SimpleNode rhs =  (SimpleNode) node.jjtGetChild(1);
        switch( id )
        {
            case JJTADD :       return eval( lhs ) + eval( rhs );
            case JJTSUBTRACT :  return eval( lhs ) - eval( rhs );
            case JJTMULT :      return eval( lhs ) * eval( rhs );
            case JJTDIV :       return eval( lhs ) / eval( rhs );
            default :
                throw new java.lang.IllegalArgumentException(
                                  "eval(): invalid operator!" );
        }
    }

結論

実際のXQuery文法でサポートされている多くの機能を処理する本格的なeval() 関数を見たいという方は、筆者のオープン・ソースのXQuery実装であるXQEngineを遠慮なくダウンロードしてください(参考文献を参照)。TreeWalker.eval() ルーチンは、XQueryの30以上のノード・タイプに対応しています。もちろん、.jjtスクリプトもあります。


ダウンロード可能なリソース


関連トピック

  • この記事の第1回では、文法、パーサー、BNFについて説明し、JavaCCを紹介しています。また、BNFによる文法記述に基づいて、JavaCCを使ってカスタム・パーサーを作成するためのサンプル・コードもあります。
  • 無料の (とは言えオープン・ソースではない)JavaCCとJJTreeの配布ファイルをお調べください。
  • XML Queryホーム・ページで、W3CのXQueryとXPathの仕様書をさらにお調べください。
  • XQEngine は、筆者による、Javaベースでオープン・ソースのXQueryエンジンの実装です。
  • BNFについてさらにお調べになりたいですか。Wikipedia.org をお調べください。
  • この記事で扱ったテクノロジーの詳細を、developerWorksのXMLJava technology の各ゾーンでお調べください。
  • XMLおよびその関連テクノロジーのIBM Certified Developer になる方法をお調べください。

コメント

コメントを登録するにはサインインあるいは登録してください。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=XML
ArticleID=239862
ArticleTitle=JavaCC、構文解析ツリー、およびXQueryの文法: 第2回
publish-date=12012002