単純でありふれた構文解析タスクの大部分では、自動パーサー生成プログラムのような複雑なものは不要です。たとえば、CSV (Comma-Separated-Value) ファイルの各断片をばらばらにするというような分かりやすいプログラミングの場合、必要なのはファイルの構造の理解と、おそらくはJavaStringTokenizer の使用法の理解です。それらを除けば、CSVでは、構文解析の理論そのものの知識もほとんど必要ありませんし、タスクに自動ツールを適用する必要もありません。

しかし、言語、および言語を記述する文法が複雑になると、言語に含まれる妥当な式の数が急速に増加します。構文解析する必要のあるコードを手作業で扱って、任意の式を構成要素の断片にする (構文解析を非常に簡潔に定義するなら、大体このとおりです) のはだんだん難しくなります。自動化されたパーサー生成プログラムは、この困難を軽減してくれます。読者が独自の目的で生成したパーサーを、他のプログラマーが使用することもできるかもしれません。

BNFから始める

複雑な言語の文法を記述するには、BNF (バッカス正規形式) 表記法か、その近親にあたるEBNF (拡張BNF) を使用するのが一般的です。自動ツールは、これらの記述 (これら2つのバリエーションを指してBNF という総称を用います)、またはこれによく似た記述を使用して、構文解析コードを生成してくれます。この記事では、そのようなパーサー生成ツールの1つであるJavaCCを説明します。JavaCCの基本的な点を簡潔に説明し、最後はいくらか時間を取って、その補助ツールの1つであるJJTreeについて説明します。途中、あまり理論の説明でわき道にそれないようにします。この記事では、正式な構文解析理論の知識があまりなくても構文解析は可能、という筆者の信念を実証したいと思います。

なぜJavaCCなのでしょうか。2つの理由があります。まず、筆者はXQueryに強い関心があります。JavaCCは、W3CのXML Queryワーキング・グループにより、XQuery文法 (およびこのワーキング・グループとXSLグループとが共有しているXPath文法) のさまざまなバージョンの作成とテストに使用されています。また、筆者はXQEngineに照会構文解析コードを提供するためにもJavaCCを使用しています。XQEngineは、筆者独自のオープン・ソースのXQuery実装です (参考文献を参照)。

大切なことを言い落としましたが、価格もまったく適正なものです。JavaCCはオープン・ソースではありませんが、100%無料です。(JavaCCの入手法については、参考文献を参照してください。)

上に戻る

構文解析の基礎

実際のXQuery文法に取りかかる前に、もっと簡単なBNFから始めましょう。これは、整数にしか作用しない、2つの算術演算子だけから構成される言語を記述するものです。この言語をSimpleLang と呼ぶことにします。

simpleLang     ::=   integerLiteral ( ( "+" | "-" ) integerLiteral )?
integerLiteral ::=   [ 0-9 ]+

この文法の規則それぞれを生成規則と言います。その中の左側の語 (生成規則の名前) は、文法中の他の生成規則によって記述されます。一番上の生成規則simpleLang は、この言語の妥当な (または適法な) 式を構成するのが整数リテラルであると述べています。オプションで、その後に正符号 (+) または負符号 (-) を置き、その後に別の整数リテラルを続けることができます。この文法によれば、単一の整数 "42" は妥当であり、式 "42 + 1" も妥当です。2番目の生成規則は、整数リテラルがどのようなものかを、regex風の方法で、より具体的に記述しています。つまり、整数リテラルとは、1つ以上の数字から成る、連続するシーケンスです。

文法は、simpleLang とintegerLiteral という2つの生成規則の間に存在する、抽象的な関係を記述します。また、3つのトークン (正符号、負符号、整数) の構成も具体的に詳述します。パーサーは、入力ストリームをスキャンするときに、これらのトークンに遭遇するものと期待します。驚くべきことではありませんが、このタスクを受け持つパーサーの部分のことを、スキャナーまたはトークナイザー（トークン分割プログラム）と言います。simpleLang は、この言語の中の非終端 シンボル、つまり他の生成規則を参照するシンボルの一例です。一方、integerLiteral の規則は終端 シンボル、つまり、もうこれ以上他の生成規則に分解できないシンボルを記述しています。

スキャン中にパーサーが上記の3つのトークン以外 のものを何か見つけると、スキャン中の式は妥当でないと見なされます。パーサーの主な仕事の1つは、渡されたあらゆる式の妥当性を判断して、その結果を知らせることです。他の仕事は、いったん式が妥当と判断されたなら、入力ストリームを構成要素の断片に分割して、これを有用な方法で引き渡すことです。

上に戻る

BNFからJavaCCへ

JavaCCを使用してこの文法を実装する方法を調べてみましょう。JavaCCは、.jjファイルというものと連動します。このファイルには、BNFと非常に良く似た表記法で、文法の記述が書き込まれます。したがって、一般に、一方の表記法からもう一方の表記法へ変換するのは大変容易です。(この表記法には独自の構文があり、JavaCCで表現できるようになっています。)

JavaCCの .jjファイルの文法と標準のBNFの主な相違点は、JavaCCバージョンの場合、文法にアクションを組み込めるということです。こうしたアクションは、文法のその部分が正常にトラバースされると実行されます。アクションはJavaステートメントであり、パーサー生成プロセスの一環として生成される、パーサー用のJavaソース・コードの一部となります。

(リスト1 には、Javaprintln() ステートメント以外には、この言語で実際に式を評価しなければならない組み込みJavaコードが含まれていないことに注意してください。この点については、JJTreeとその構文解析ツリー表現を調べた後で、詳細に説明します。)

                
PARSER_BEGIN( Parser_1 )
package examples.example_1;
public class Parser_1 {}
PARSER_END( Parser_1 )
void simpleLang() : {}             { integerLiteral() ( ( "+" | "-" ) integerLiteral() )? <EOF> }
void integerLiteral() : {Token t;} { t=<INT> { System.out.println("integer = "+t.image); }}
SKIP 	: { " " | "\t" | "\n" | "\r" }
TOKEN	: { < INT : ( ["0" - "9"] )+ > }

このファイルに関し、次の点に注意してください。

• PARSER_BEGIN ディレクティブとPARSER_END ディレクティブは、生成されるJavaパーサーの名前 (Parser_1.java) を指定するとともに、このクラスにJavaステートメントを挿入するための場所を提供します。この場合、ファイルの最上部にJavaのpackage ステートメントが置かれています。package ステートメントは、生成プロセスの一環として作成されるJavaヘルパー・ファイルの最上部にも置かれます (JavaCCのコンパイル・プロセスを参照)。この場所は、生成規則の中のJavaステートメントが参照するインスタンス変数を宣言するのにも適していますが、この例ではその方法を採用しません。好みに応じて、この位置にJavaのmain() プロシージャーを挿入し、このプロシージャーを使用して、生成対象のパーサーを起動してテストするためのスタンドアロンのアプリケーションを作成することさえできます。
• JavaCCの構文は、見た目が手続き型で、生成規則もメソッド呼び出しによく似ています。これは偶然ではありません。JavaCCがこのスクリプトをコンパイルするときに作成されるJavaのソースには、これらの生成規則と同じ名前のメソッドが含まれています。実行時に、これらのメソッドは、.jjスクリプトで呼び出された順番に従って実行されます。これがどのように機能するかは、パーサー・コードを歩き回るで示します。(ここで使用する「コンパイル」という用語も偶然ではありません。パーサー生成プログラムは一般に、「コンパイラー・コンパイラー」とも呼ばれます。)
• 中括弧 ({ と }) は、生成規則の本体を表すとともに、組み込まれるあらゆるJavaアクションをエスケープします。integerLiteral 規則のSystem.out.println() ステートメントを囲んでいる中括弧に注意してください。このアクションは、メソッドParser_1.integerLiteral() の一部として作成されます。このアクションは、パーサーが整数に遭遇するたびに実行されます。
• ファイルの末尾のSKIP ステートメントは、トークン同士の間に空白 (ブランク、タブ、復帰、改行) がはさまる場合があることと、それが無視されることを述べています。
• TOKEN ステートメントには、整数トークンがどのようなものであるかを記述する、regex風の式が入ります。先行する生成規則の中でこれらのトークンを参照する場合、不等号括弧で囲まれます。
• 2番目の生成規則 (integerLiteral() に関するもの) は、タイプToken (JavaCCの組み込みクラス) のローカル変数t を宣言します。入力ストリームの中で整数に遭遇すると、この規則が起動 し、この整数の値 (テキストとしての値) がインスタンス変数t.image に割り当てられます。一方のToken フィールドt.kind は、enumであり、この特定のトークンが整数にほかならず、パーサーが認識する別の種類のトークンではないことを示す値が割り当てられます。最終的に、パーサーの中に生成されるJavaのSystem.out.println() コードは、構文解析時にこのトークンの中身を突き止めることができます。その際には、t.image を使用して、このトークンのテキスト値にアクセスして、これを出力します。

上に戻る

パーサー・コードを歩き回る

ここまでで作成されたパーサーの中身を簡単に調べてみましょう。特定の .jj文法によって生成されるメソッドと、実行時にそれらのメソッドが実行される順序についていくらか知っておくと便利です。以下の2つの理由があります。

• ときどき (初めての場合は特に)、パーサーの返す結果が、.jjファイルに指示されているはずの内容と食い違うように思えることがあります。実行時に、作成されたパーサー・コードをステップごとに実行し、実際に何が行われているのかを調べ、それに応じて文法ファイルを調整することができます。筆者自身、いまだにこれを頻繁に行っています。
• 生成規則/メソッドの実行順序を知っているなら、特定の結果を得るためにJavaアクションをどこに組み込んだらよいのかが、よりよく分かります。この点については、第2回でJJTreeと構文解析ツリー表現について説明するときに、再度詳しく取り上げます。

作成したパーサーの詳細をあまりに深く掘り下げることはこの記事の範囲を超えたことですが、リスト2 に、メソッドParser_1.integerLiteral() のために生成されたコードを示します。これを見るなら、最終的なコードがどのようなものかがある程度分かるでしょう。特に、メソッドの最後のステートメントである、System.out.println( "integer = "+t.image) に注目してください。このステートメントは、.jjスクリプトに組み込まれたJavaアクションそのものが埋め込まれたものです。

                
  static final public void integerLiteral() throws ParseException {
                            Token t;
    t = jj_consume_token(INT);
    System.out.println( "integer = "+t.image);
  }

ここで、このパーサーが行うことについて、抽象的なレベルで1ステップずつ説明をします。

1. 最上部のメソッドsimpleLang() がintegerLiteral() を呼び出します。
2. integerLiteral() は、入力ストリームの中で最初に整数と遭遇するものと期待します。整数に遭遇しないと、式は妥当でなくなります。これを検査するため、このメソッドはトークン分割プログラム (Tokenizer.java) を呼び出し、入力ストリーム内の次のトークンを返します。トークン分割プログラムはストリームを進んで行き、一度に1つずつ文字を調査します。これは、整数かファイル終わりに遭遇するまで続きます。整数に遭遇した場合、値は<INT> トークンにパッケージされ、ファイル終わりに遭遇した場合は<EOF> になります。そして、トークンはintegerLiteral() に返されて、さらに処理されることになります。どちらのトークンにも遭遇しなかった場合、トークン分割プログラムは字句エラーを返します。
3. トークン分割プログラムによって返されたトークンが整数トークンまたは<EOF> でなかった場合、integerLiteral() はParseException をスローし、構文解析は完了します。
4. 整数トークンであった場合、式は依然として妥当である見込みがあります。integerLiteral() は、次のトークンを返すために、トークン分割プログラムを再度呼び出します。<EOF> が返された場合、式全体は単一の整数で構成され、妥当です。パーサーは呼び出し側アプリケーションに制御を戻します。
5. トークン分割プログラムが正符号または負符号のどちらかのトークンを返した場合、式は依然として妥当であり、integerLiteral() はトークン分割プログラムを最後にもう一度だけ呼び出し、もう1つの整数を探します。整数が見つかれば、式は妥当であり、パーサーは完了します。次のトークンが整数でなかった場合、パーサーは例外をスローします。

パーサーに障害が起こった場合は、ParseException かTokenMgrError のどちらかがスローされることに注意してください。どちらも、式が妥当でなかったことを示します。

ここでキー・ポイントとなるのは、これらの2つの生成規則に組み込まれたJavaアクションはいずれも、アクションが組み込まれた生成規則の箇所がパーサーによって正常にトラバースされた場合にだけ実行されるということです。このパーサーに式 "42 + 1" が渡されると、コンソールにステートメントinteger = 42 とinteger = 1 が出力されます。妥当でない式 "42 + abc" に対してパーサーが実行されると、メッセージinteger = 42 が出された後、キャッチ・ブロック・メッセージa Token Manager error! が出力されます。後者の場合、パーサーはsimpleLang の最初のintegerLiteral() という項目についてだけトラバースに成功し、2番目の項目については成功しませんでした。

void simpleLang() : {} { integerLiteral() ( ("+" | "-") integerLiteral() )? <EOF> }

言い換えれば、2番目のintegerLiteral() メソッドは、予想された整数トークンが見つからなかったために実行されませんでした。

上に戻る

JavaCCのコンパイル・プロセス

.jjファイルに対してJavaCCを実行すると、複数のJavaソース・ファイルが生成されます。1つは、主要な構文解析コードParser_1.javaです。構文解析する式があるとき、このファイルをアプリケーションから呼び出します。JavaCCは、パーサーによって使用される他の6つの補助ファイルも作成します。合計すると、JavaCCは以下の7つのJavaファイルを生成します。最初の3つは、特定の文法に固有のものです。残りの4つは汎用ヘルパーであり、文法がどのようなものであれ、必ず生成されます。

• Parser_1.java
• Parser_1Constants.java
• Parser_1TokenManager.java
• ParseException.java
• SimpleCharStream.java
• Token.java
• TokenMgrError.java

JavaCCが上記の7つのJavaソースを生成したら、これらのソースをコンパイルして、Javaアプリケーションにリンクすることができます。それから、アプリケーション・コードから新しいパーサーを呼び出し、評価すべき式をこれに渡すことができます。以下に示すサンプル・アプリケーションは、パーサーのインスタンスを生成し、このパーサーに対して、アプリケーション上にハードコーディングされた式を渡します。

                
package examples.example_1;
import examples.example_1.Parser_1;
import examples.example_1.ParseException;
import java.io.StringReader;
public class Example_1
{
    static String expression = "1 + 42";
    public static void main( String[] args )
    //--------------------------------------
    {
        new Example_1().parse( expression );
    }
    void parse( String expression )
    //-----------------------------
    {
        Parser_1 parser = new Parser_1( new StringReader( expression ));
        try {
            parser.simpleLang();
        }
        catch( ParseException pe )  {
            System.out.println( "not a valid expression" ); }
        catch( TokenMgrError e ) {
            System.out.println( "a Token Manager error!" );
        }
    }
}

ここで注目に値することは何でしょうか。

1. Parser_1 内の構文解析コードを起動するには、このクラスのメソッドsimpleLang() を起動します。一般に .jjファイル内の生成規則の順序に意味はありませんが、この場合だけは例外です。つまり、文法の中の一番上の生成規則が、パーサーを起動するために使用されます。
2. 構文解析コードに渡す式を文法に従って正しく解析できない場合、ParseException かLexicalError のどちらかがスローされます。
3. 式が妥当なら、正常にトラバースされた文法部分に組み込まれている、あらゆるJavaアクションが実行されます。これは、パーサー・コードを歩き回るの最後で説明したとおりです。

上に戻る

結論

この記事の第2回では、この続きの部分を扱います。まず類似のサンプル・コードを取り上げてから、JavaCCの関連ツールJJTreeを使用して、.jjスクリプトに組み込んだアクションを実行する代わりに、実行時に構文解析の構文解析ツリー表現を作成するパーサーを作成する方法を学びます。この方法にたくさんの利点があることが分かるでしょう。

参考文献

• BNFについてさらにお調べになりたいですか。Wikipedia.org をお調べください。
  
  
• 無料の (とは言えオープン・ソースではない)JavaCCとJJTreeの配布ファイルをお調べください。
  
  
• XML Queryホーム・ページで、W3CのXQueryとXPathの仕様書をさらにお調べください。
  
  
• XQEngine は、筆者による、Javaベースでオープン・ソースのXQueryエンジンの実装です。
  
  
• この記事で扱ったテクノロジーの詳細を、developerWorksのXML とJava technology の各ゾーンでお調べください。
  
  
• XMLおよびその関連テクノロジーのIBM Certified Developer になる方法をお調べください。
  
  

著者について

この記事を評価する

コメント

上に戻る

目次

• BNFから始める
• 構文解析の基礎
• BNFからJavaCCへ
• パーサー・コードを歩き回る
• JavaCCのコンパイル・プロセス
• 結論
• 参考文献
• 著者について
• コメント