(57)【特許請求の範囲】
【請求項１】
データオブジェクトの入力ストリームを解析するためのデータパーサを生成するための方法であって、
階層で編成された複数のオブジェクトを定義する階層的なデータフォーマットを表す情報を受信するステップであって、前記オブジェクトが、データオブジェクトを表す１又は２以上のスキーマオブジェクト、及び１又は２以上のスキーマオブジェクトにそれぞれが関連する１又は２以上のコンテナオブジェクトを含む、ステップと、
前記データパーサを形成するために前記受信された情報を処理するステップとを含み、前記処理するステップが、
前記階層的なデータフォーマットを表す前記情報に少なくとも部分的に基づいて、前記入力ストリーム内の連続的なデータオブジェクトの間の容認され得る遷移を決定するステップ、
１又は２以上のデータ操作を前記決定された、容認され得る遷移のそれぞれと関連付けるステップ、並びに
（１）前記入力ストリーム内の第１のデータオブジェクトと第２のデータオブジェクトとの間の遷移を認識し、（２）１又は２以上の前に認識された遷移に関連するコンテキストに少なくとも部分的に基づいて前記第２のデータオブジェクト内のデータ値に対して前記認識された遷移に関連するデータ操作を実行するために前記データパーサを実行するようにプロセッサを構成するための仕様を記憶するステップを含む、方法。
【請求項２】
階層的なデータフォーマットを表す情報が、複数のノードのそれぞれが前記階層的なデータフォーマットによって定義された複数のオブジェクトのうちの１つを表すようにして複数のエッジによって相互に接続された前記複数のノードを含む前記階層的なデータフォーマットのツリー表現を含む請求項１に記載の方法。
【請求項３】
１又は２以上の前に認識された遷移に関連するコンテキストが、階層的なデータフォーマットのツリー表現内の位置に対応する請求項２に記載の方法。
【請求項４】
スキーマオブジェクトのうちの少なくとも１つが、前記スキーマオブジェクトによって表される、対応するデータオブジェクトとともに含まれるタグを含む請求項１〜３のいずれかに記載の方法。
【請求項５】
コンテナオブジェクトが、入力ストリーム内に含まれるデータオブジェクトのシーケンス、前記入力ストリーム内に含まれるデータオブジェクトのセット、又は複数の可能なデータオブジェクトの中の前記入力ストリーム内の１つの含まれるデータオブジェクトの選択のうちの少なくとも１つを表す少なくとも１つのコンテナオブジェクトを含む請求項１〜４のいずれかに記載の方法。
【請求項６】
コンテナオブジェクトの少なくとも一部が、入力ストリーム内のデータオブジェクトの一連の複数のコンテナを表すものとして規定される請求項１〜５のいずれかに記載の方法。
【請求項７】
複数のオブジェクトのうちの少なくとも一部のオブジェクトが、階層的なデータフォーマットでオプショナル（optional）として指定される請求項１〜６のいずれかに記載の方法。
【請求項８】
入力ストリーム内の階層的なデータフォーマットのオブジェクトの間の容認され得る遷移を決定するステップが、
前記階層的なデータフォーマットのコンパイルツリー表現を生成するステップであって、前記コンパイルツリー表現が、前記階層的なデータフォーマットによって定義された前記複数のオブジェクトのうちの１つを表す複数のノードの少なくとも一部及びコンパイルに固有のオブジェクトを表す前記複数のノードの少なくとも一部と複数のエッジによって相互に接続された前記複数のノードを含む、ステップを含む請求項１〜７のいずれかに記載の方法。
【請求項９】
コンパイルに固有のオブジェクトを表すノードが、ベクトルコンテナノード、ルートノード、空タグノード、及びファンアウト専用ノードのうちの１又は２以上を含む請求項８に記載の方法。
【請求項１０】
入力ストリーム内の階層的なデータフォーマットのオブジェクトの間の容認され得る遷移を決定するステップが、コンパイルツリー表現のノードの間のすべての容認され得る遷移を決定するために前記コンパイルツリー表現を処理するステップを含む請求項８又は９に記載の方法。
【請求項１１】
コンパイルツリー表現のノードの間のすべての容認され得る遷移を決定するために前記コンパイルツリー表現を処理するステップが、前記コンパイルツリー表現の各ノードに関して、前記ノードへの遷移を有するすべてのノードを決定するステップと、前記ノードが少なくとも１つの遷移を有するすべてのノードを決定するステップとを含む請求項１０に記載の方法。
【請求項１２】
コンパイルツリー表現のノードの間のすべての容認され得る遷移を決定するために前記コンパイルツリー表現を処理するステップが、前記ノードの間の重複する遷移を組み合わせるステップと、前記ノードの間の不完全な遷移を削除するステップを含む請求項１０又は１１に記載の方法。
【請求項１３】
特定されたそれぞれの容認され得る遷移に関する詳細エッジを生成するステップであって、前記詳細エッジが、前記遷移に関連するソースノード、前記遷移に関連するデスティネーションノード、前記遷移に関連するコンテナノード、及び前記遷移に関連するループする動作を含む、ステップをさらに含む請求項１０〜１２のいずれかに記載の方法。
【請求項１４】
１又は２以上のデータ操作を特定された遷移のそれぞれに関連付けるステップが、前記１又は２以上のデータ操作を決定するためにそれぞれの詳細エッジを分析するステップを含む請求項１３に記載の方法。
【請求項１５】
１又は２以上のデータ操作が、コンテナオブジェクトのスコープにプッシュするための操作、コンテナオブジェクトのスコープからポップするための操作、及びデータオブジェクトの値を読み取るための操作を含む請求項１〜１４のいずれかに記載の方法。
【請求項１６】
入力ストリーム内の階層的なデータフォーマットのオブジェクトの間の容認され得る遷移を決定するステップが、前記階層的なデータフォーマットが曖昧な定義を含まないというインジケーション、前記階層的なデータフォーマットが１若しくは２以上の曖昧な定義を確かに含むというインジケーション、又は前記階層的なデータフォーマットに含まれる任意の曖昧な定義の１若しくは２以上の可能な解決策のうちの少なくとも１つを含む出力を生成するステップを含む請求項１〜１５のいずれかに記載の方法。
【請求項１７】
階層的なデータフォーマットを表すデータが、ＡＳＮ．１表記、ＸＭＬ表記、ＳＷＩＦＴ表記、Ｘ１２表記、及びＨＬ７表記のうちの少なくとも１つを用いて規定される請求項１〜１６のいずれかに記載の方法。
【請求項１８】
請求項１〜１７のいずれかに記載の方法に従って生成されたデータパーサ。
【請求項１９】
階層的なデータフォーマットに従ってフォーマットされた入力ストリームを解析するためのデータパーサを生成するためのシステムであって、
階層で編成された複数のオブジェクトを定義する階層的なデータフォーマットを表す情報を受信するように構成された入力デバイス又はポートであって、前記オブジェクトが、データオブジェクトを表す１又は２以上のスキーマオブジェクト、及び１又は２以上のスキーマオブジェクトにそれぞれが関連する１又は２以上のコンテナオブジェクトを含む、入力デバイス又はポートと、
前記データパーサを形成するために前記受信された情報を処理するように構成された少なくとも１つのプロセッサとを含み、前記処理が、
前記階層的なデータフォーマットを表す前記情報に少なくとも部分的に基づいて、前記入力ストリーム内の連続的なデータオブジェクトの間の容認され得る遷移を決定すること、
１又は２以上のデータ操作を前記決定された、容認され得る遷移のそれぞれと関連付けること、並びに
（１）前記入力ストリーム内の第１のデータオブジェクトと第２のデータオブジェクトとの間の遷移を認識し、（２）１又は２以上の前に認識された遷移に関連するコンテキストに少なくとも部分的に基づいて前記第２のデータオブジェクト内のデータ値に対して前記認識された遷移に関連するデータ操作を実行するために前記データパーサを実行するようにプロセッサを構成するための仕様を記憶することを含む、システム。
【請求項２０】
階層的なデータフォーマットに従ってフォーマットされた入力ストリームを解析するためのデータパーサを生成するためのシステムであって、
階層で編成された複数のオブジェクトを定義する階層的なデータフォーマットを表す情報を受信するための手段であって、前記オブジェクトが、データオブジェクトを表す１又は２以上のスキーマオブジェクト、及び１又は２以上のスキーマオブジェクトにそれぞれが関連する１又は２以上のコンテナオブジェクトを含む、手段と、
前記データパーサを形成するために前記受信された情報を処理するための手段とを含み、前記処理が、
前記階層的なデータフォーマットを表す前記情報に少なくとも部分的に基づいて、前記入力ストリーム内の連続的なデータオブジェクトの間の容認され得る遷移を決定すること、
１又は２以上のデータ操作を前記決定された、容認され得る遷移のそれぞれと関連付けること、並びに
（１）前記入力ストリーム内の第１のデータオブジェクトと第２のデータオブジェクトとの間の遷移を認識し、（２）１又は２以上の前に認識された遷移に関連するコンテキストに少なくとも部分的に基づいて前記第２のデータオブジェクト内のデータ値に対して前記認識された遷移に関連するデータ操作を実行するために前記データパーサを実行するようにプロセッサを構成するための仕様を記憶することを含む、システム。
【請求項２１】
データオブジェクトの入力ストリームを解析するためのデータパーサを生成するための、コンピュータ可読媒体に記憶されたソフトウェアであって、コンピューティングシステムに、
階層で編成された複数のオブジェクトを定義する階層的なデータフォーマットを表す情報を受信することであって、前記オブジェクトが、データオブジェクトを表す１又は２以上のスキーマオブジェクト、及び１又は２以上のスキーマオブジェクトにそれぞれが関連する１又は２以上のコンテナオブジェクトを含む、受信することと、
前記データパーサを形成するために前記受信された情報を処理することとを実行させるための命令を含み、前記処理することが、
前記階層的なデータフォーマットを表す前記情報に少なくとも部分的に基づいて、前記入力ストリーム内の連続的なデータオブジェクトの間の容認され得る遷移を決定すること、
１又は２以上のデータ操作を前記決定された、容認され得る遷移のそれぞれと関連付けること、並びに
（１）前記入力ストリーム内の第１のデータオブジェクトと第２のデータオブジェクトとの間の遷移を認識し、（２）１又は２以上の前に認識された遷移に関連するコンテキストに少なくとも部分的に基づいて前記第２のデータオブジェクト内のデータ値に対して前記認識された遷移に関連するデータ操作を実行するために前記データパーサを実行するようにプロセッサを構成するための仕様を記憶することを含む、ソフトウェア。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
２０１３年７月１２日に出願した米国仮出願第６１／８４５，７２２号明細書の優先権を主張する２０１３年１１月２２日に出願した米国特許出願第１４／０８７，１５８号明細書の優先権を主張するものである。
【０００２】
本明細書は、パーサの生成に関する。
【背景技術】
【０００３】
入力を解釈するために入力を分析し、その入力の異なる部分の関係を決定するためのいくつかのシステムのユーザのパーサ。一部のパーサは、プログラマによって手動で記述される。一部のパーサは、パーサジェネレータによって自動的に生成される。例えば、（ｙａｃｃ又はＢｉｓｏｎなどのコンパイラコンパイラとも呼ばれる）一部のパーサジェネレータは、その文法に従って有効と考えられる構文の要素及びそれらの構文の要素の間の関係を記述する生成規則（又は単に「生成（production）」）による文法を入力として受け付ける。パーサジェネレータは、パーサジェネレータに与えられた文法に準ずる入力を解析するための情報を出力として提供する。さまざまな種類のパーサが、さまざまな異なる種類のデータを処理するために使用され得る。例えば、アプリケーションプロトコルパーサは、パケットストリームをパケットストリームのトラフィックの高レベルの表現に変換する。
【発明の概要】
【課題を解決するための手段】
【０００４】
一態様においては、概して、データオブジェクトの入力ストリームを解析するためのデータパーサを生成するための方法が、階層で編成された複数のオブジェクトを定義する階層的なデータフォーマットを表す情報を受信するステップであって、オブジェクトが、データオブジェクトを表す１又は２以上のスキーマオブジェクト、及び１又は２以上のスキーマオブジェクトにそれぞれが関連する１又は２以上のコンテナオブジェクトを含む、ステップと、データパーサを形成するために受信された情報を処理するステップとを含む。処理するステップは、階層的なデータフォーマットを表す情報に少なくとも部分的に基づいて、入力ストリーム内の連続的なデータオブジェクトの間の容認され得る遷移を決定するステップと、１又は２以上のデータ操作を決定された、容認され得る遷移のそれぞれと関連付けるステップと、（１）入力ストリーム内の第１のデータオブジェクトと第２のデータオブジェクトとの間の遷移を認識し、（２）１又は２以上の前に認識された遷移に関連するコンテキストに少なくとも部分的に基づいて第２のデータオブジェクト内のデータ値に対して認識された遷移に関連するデータ操作を実行するためにデータパーサを実行するようにプロセッサを構成するための仕様（例えば、実行可能な命令、又はデータパーサプログラムの任意のその他の仕様）を記憶するステップとを含む。
【０００５】
態様は、以下の特徴のうちの１又は２以上を含み得る。
【０００６】
階層的なデータフォーマットを表す情報は、複数のノードのそれぞれが階層的なデータフォーマットによって定義された複数のオブジェクトのうちの１つを表すようにして複数のエッジによって相互に接続された複数のノードを含む階層的なデータフォーマットのツリー表現を含む。
【０００７】
１又は２以上の前に認識された遷移に関連するコンテキストは、階層的なデータフォーマットのツリー表現内の位置に対応する。
【０００８】
スキーマオブジェクトのうちの少なくとも１つは、スキーマオブジェクトによって表される、対応するデータオブジェクトとともに含まれるタグを含む。
【０００９】
コンテナオブジェクトは、入力ストリーム内に含まれるデータオブジェクトのシーケンス、入力ストリーム内に含まれるデータオブジェクトの組（セット）、又は複数の可能なデータオブジェクトの中の入力ストリーム内の１つの含まれるデータオブジェクトの選択のうちの少なくとも１つを表す少なくとも１つのコンテナオブジェクトを含む。
【００１０】
コンテナオブジェクトの少なくとも一部は、入力ストリーム内のデータオブジェクトの一連の複数のコンテナを表すものとして規定される。
【００１１】
複数のオブジェクトのうちの少なくとも一部のオブジェクトは、階層的なデータフォーマットでオプショナル（optional）として指定される。
【００１２】
入力ストリーム内の階層的なデータフォーマットのオブジェクトの間の容認され得る遷移を決定するステップは、階層的なデータフォーマットのコンパイルツリー（compilation tree）表現を生成するステップであって、コンパイルツリー表現が、階層的なデータフォーマットによって定義された複数のオブジェクトのうちの１つを表す複数のノードの少なくとも一部及びコンパイルに固有のオブジェクトを表す複数のノードの少なくとも一部と、複数のエッジによって相互に接続された複数のノードを含む、ステップを含む。
【００１３】
コンパイルに固有のオブジェクトを表すノードは、ベクトルコンテナノード（vector container node）、ルートノード（root node）、空タグノード（empty tag node）、及びファンアウト専用ノード（fan-out only node）のうちの１又は２以上を含む。
【００１４】
入力ストリーム内の階層的なデータフォーマットのオブジェクトの間の容認され得る遷移を決定するステップは、コンパイルツリー表現のノードの間のすべての容認され得る遷移を決定するためにコンパイルツリー表現を処理するステップを含む。
【００１５】
コンパイルツリー表現のノードの間のすべての容認され得る遷移を決定するためにコンパイルツリー表現を処理するステップは、コンパイルツリー表現の各ノードに関して、ノードへの遷移を有するすべてのノードを決定するステップと、ノードが少なくとも１つの遷移を有するすべてのノードを決定するステップとを含む。
【００１６】
コンパイルツリー表現のノードの間のすべての容認され得る遷移を決定するためにコンパイルツリー表現を処理するステップは、ノードの間の重複する遷移を組み合わせるステップと、ノードの間の不完全な遷移を削除するステップとを含む。
【００１７】
方法は、特定されたそれぞれの容認され得る遷移に関する詳細エッジ（elaborated edge）を生成するステップであって、詳細エッジが、遷移に関連するソースノード、遷移に関連するデスティネーションノード、遷移に関連するコンテナノード、及び遷移に関連するループする動作を含む、ステップをさらに含む。
【００１８】
１又は２以上のデータ操作を特定された遷移のそれぞれに関連付けるステップは、１又は２以上のデータ操作を決定するためにそれぞれの詳細エッジを分析するステップを含む。
【００１９】
１又は２以上のデータ操作は、コンテナオブジェクトのスコープにプッシュするための操作、コンテナオブジェクトのスコープからポップするための操作、及びデータオブジェクトの値を読み取るための操作を含む。
【００２０】
入力ストリーム内の階層的なデータフォーマットのオブジェクトの間の容認され得る遷移を決定するステップは、階層的なデータフォーマットが曖昧な定義を含まないというインジケーション、階層的なデータフォーマットが１若しくは２以上の曖昧な定義を確かに含むというインジケーション、又は階層的なデータフォーマットに含まれる任意の曖昧な定義の１若しくは２以上の可能な解決策のうちの少なくとも１つを含む出力を生成するステップを含む。
【００２１】
階層的なデータフォーマットを表すデータは、ＡＳＮ．１表記、ＸＭＬ表記、ＳＷＩＦＴ表記、Ｘ１２表記、及びＨＬ７表記のうちの少なくとも１つを用いて規定される。
【００２２】
別の態様においては、概して、階層的なデータフォーマットに従ってフォーマットされた入力ストリームを解析するためのデータパーサを生成するためのシステムが、階層で編成された複数のオブジェクトを定義する階層的なデータフォーマットを表す情報を受信するように構成された入力デバイス又はポートであって、オブジェクトが、データオブジェクトを表す１又は２以上のスキーマオブジェクト、及び１又は２以上のスキーマオブジェクトにそれぞれが関連する１又は２以上のコンテナオブジェクトを含む、入力デバイス又はポートと、データパーサを形成するために受信された情報を処理するように構成された少なくとも１つのプロセッサとを含む。処理は、階層的なデータフォーマットを表す情報に少なくとも部分的に基づいて、入力ストリーム内の連続的なデータオブジェクトの間の容認され得る遷移を決定することと、１又は２以上のデータ操作を決定された、容認され得る遷移のそれぞれと関連付けることと、（１）入力ストリーム内の第１のデータオブジェクトと第２のデータオブジェクトとの間の遷移を認識し、（２）１又は２以上の前に認識された遷移に関連するコンテキストに少なくとも部分的に基づいて第２のデータオブジェクト内のデータ値に対して認識された遷移に関連するデータ操作を実行するためにデータパーサを実行するようにプロセッサを構成するための仕様を記憶することとを含む。
【００２３】
別の態様においては、概して、階層的なデータフォーマットに従ってフォーマットされた入力ストリームを解析するためのデータパーサを生成するためのシステムが、階層で編成された複数のオブジェクトを定義する階層的なデータフォーマットを表す情報を受信するための手段であって、オブジェクトが、データオブジェクトを表す１又は２以上のスキーマオブジェクト、及び１又は２以上のスキーマオブジェクトにそれぞれが関連する１又は２以上のコンテナオブジェクトを含む、手段と、データパーサを形成するために受信された情報を処理するための手段とを含む。処理は、階層的なデータフォーマットを表す情報に少なくとも部分的に基づいて、入力ストリーム内の連続的なデータオブジェクトの間の容認され得る遷移を決定することと、１又は２以上のデータ操作を決定された、容認され得る遷移のそれぞれと関連付けることと、（１）入力ストリーム内の第１のデータオブジェクトと第２のデータオブジェクトとの間の遷移を認識し、（２）１又は２以上の前に認識された遷移に関連するコンテキストに少なくとも部分的に基づいて第２のデータオブジェクト内のデータ値に対して認識された遷移に関連するデータ操作を実行するためにデータパーサを実行するようにプロセッサを構成するための仕様を記憶することとを含む。
【００２４】
別の態様においては、概して、データオブジェクトの入力ストリームを解析するためのデータパーサを生成するためのソフトウェアがコンピュータ可読媒体に記憶される。ソフトウェアは、コンピューティングシステムに、階層で編成された複数のオブジェクトを定義する階層的なデータフォーマットを表す情報を受信することであって、オブジェクトが、データオブジェクトを表す１又は２以上のスキーマオブジェクト、及び１又は２以上のスキーマオブジェクトにそれぞれが関連する１又は２以上のコンテナオブジェクトを含む、受信することと、データパーサを形成するために受信された情報を処理することとを実行させる命令を含む。処理することは、階層的なデータフォーマットを表す情報に少なくとも部分的に基づいて、入力ストリーム内の連続的なデータオブジェクトの間の容認され得る遷移を決定することと、１又は２以上のデータ操作を決定された、容認され得る遷移のそれぞれと関連付けることと、（１）入力ストリーム内の第１のデータオブジェクトと第２のデータオブジェクトとの間の遷移を認識し、（２）１又は２以上の前に認識された遷移に関連するコンテキストに少なくとも部分的に基づいて第２のデータオブジェクト内のデータ値に対して認識された遷移に関連するデータ操作を実行するためにデータパーサを実行するようにプロセッサを構成するための仕様を記憶することとを含む。
【００２５】
態様は、以下の利点のうちの１又は２以上を有する可能性がある。
【００２６】
組織は、複数の異なるシステムからのデータを管理する。一部のシステムは、システムにネイティブのフォーマットのデータのデータセットを生成する可能性がある。その他のシステムは、カンマ区切り（ｃｓｖ，comma separated values）、拡張可能マークアップ言語（ＸＭＬ，extensible markup language）、抽象構文記法１（ＡＳＮ．１，Abstract Syntax Notation One）、国際銀行間通信協会（ＳＷＩＦＴ，Society for Worldwide Interbank Financial Telecommunication）、Ｘ１２、又は別の規格などの規格に準拠する非ネイティブフォーマットを用いてデータセットを生成する。概して、データセットが特定の規格を使用することが知られているときでさえも、データセット内のデータオブジェクトは、その特定の規格に準拠する特定のデータフォーマットに従って解析される必要がある。
【００２７】
一部のシステムは、インポートメカニズムを通じてその他のシステムによって提供されたデータセットを受け付ける。インポートメカニズムは、外部データセットを処理のためにシステムにネイティブのフォーマットに変換する。１つのそのようなインポートメカニズムは、特定のデータフォーマット（例えば、スキーマ）に従ってフォーマットされたデータ（例えば、バイナリデータとして又はＡＳＣＩＩテキストなどのキャラクタセットを用いて符号化されたメッセージ又はその他のドキュメント）の入力ストリームを分析し、そのデータの入力ストリームの構成要素の一部を認識するデータパーサであり、そして、そのデータの入力ストリームの構成要素の一部は、ネイティブのデータレコードのフィールドに投入するために使用される。スキーマが、例えば、入力ストリームに現れる可能性があるデータオブジェクトの異なる可能な有効なシーケンスを定義するために使用される可能性がある。入力ストリーム内のデータオブジェクトは、明示的にタグ付けされるか、又は入力ストリーム内の別個のデータオブジェクトとして暗黙的に認識され得る可能性がある。
【００２８】
他の利点の中でもとりわけ、本明細書において説明される手法を用いて生成されるデータパーサは、任意の階層的なデータフォーマットと互換性があるデータ操作を実行するように構成され、開発時間を抑えることができる。これは、概してデータフォーマットの静的な組を考慮して開発され、さらなるデータフォーマットに対応するために再び開発されるか又は改良されなければならず、データが解析されているときにカスタムのデータ操作を実行することができない可能性がある通常のデータパーサからの改善である。
【００２９】
本明細書において説明される手法は、一般化された階層的なタグ値スキーマに従ってフォーマットされたデータを任意のその他のデータフォーマットに変換することができる。
【００３０】
本明細書において説明される手法は、コンテキストのチェックなどの操作が削減されるので、通常の手法からの性能の改善をもたらすことができる。
【００３１】
本明細書において説明される手法は、選択的な「ローカルルーティング（local routing）」とは対照的に「グローバルルーティング（global routing）」を利用し得る。非常に広く、「グローバルルーティング」を利用するデータパーサは、そのデータパーサが実行する各解析操作に関する所与の階層的な入れ子にされたターゲットデータフォーマットのすべてのレベルの要素の間の容認され得る遷移の一部又はすべてを考慮に入れる。「ローカルルーティング」を利用するデータパーサは、そのデータパーサが実行する各解析操作に関する所与の階層的な入れ子にされたターゲットデータフォーマットの単一のレベルの要素の間の容認され得る遷移のみを考慮に入れる。「グローバルルーティング」の使用は、潜在的に、パーサによって必要とされるチェック（例えば、長さのチェック）の量を減らす。特に、階層的な入れ子にされたスキーマの場合、スキーマの各レベルが、ローカルで行われる場合、別個の試験を必要とする可能性がある一方、グローバルに行われる場合、唯１つの検索又は試験によって特定され得る。したがって、一部の例においては、あらゆる解析操作の前又は後の余分なチェックが削除され、例えば、データの完全性を検証するため又は曖昧なルートを扱うために長さのチェックが控え目に実行される。
【００３２】
本発明のその他の特徴及び利点は、以下の説明及び請求項から明らかである。
【図面の簡単な説明】
【００３３】
【図１】データ処理システムの図である。
【図２】例示的なデータフォーマットである。
【図３】例示的なデータフォーマットのツリー表現の図である。
【図４】遷移図である。
【図５Ａ】パーサ生成モジュールの図である。
【図５Ｂ】実行環境の図である。
【図６】例示的なデータフォーマットのスコープツリー（scope tree）表現の図である。
【図７】例示的なデータフォーマットに関する詳細な遷移図である。
【図８】データ操作に関連する遷移のリストである。
【図９】入力ストリームからのデータを解析するパーサの例の図である。
【図１０】図９のデータを解析するときにパーサが従う遷移を強調する遷移図である。
【図１１】データ操作に関連する遷移のリストである。
【発明を実施するための形態】
【００３４】
１  システムの概要
図１は、パーサ生成技術が使用され得る例示的なデータ処理システム１００を示す。システム１００は、ストレージデバイス、又はオンラインデータストリームへの接続などのデータの１又は２以上のソースを含み得るデータソース１０２を含み、それらの１又は２以上のソースのそれぞれは、さまざまな記憶フォーマット（例えば、データベーステーブル、スプレッドシートファイル、フラットテキストファイル、又はメインフレームコンピュータによって使用されるネイティブフォーマット）のいずれかでデータを記憶し得る。実行環境１０４は、パーサ生成モジュール１０６及び実行モジュール１１２を含む。実行環境１０４は、ＵＮＩＸオペレーティングシステムなどの好適なオペレーティングシステムの制御の下で１又は２以上の多目的コンピュータでホストされる可能性がある。例えば、実行環境１０４は、ローカルの（例えば、ＳＭＰコンピュータなどのマルチプロセッサシステム）、又はローカルに分散された（例えば、クラスタ若しくはＭＰＰとして接続された複数のプロセッサ）、又はリモートの若しくはリモートに分散された（例えば、ローカルエリアネットワーク（ＬＡＮ，local area network）及び／若しくは広域ネットワーク（ＷＡＮ，wide-area network）を介して接続された複数のプロセッサ）、又はこれらの任意の組み合わせのいずれかの複数の中央演算処理装置（ＣＰＵ，central processing unit）を用いるコンピュータシステムの構成を含むマルチノード並列コンピューティング環境を含み得る。一部の実施形態において、実行モジュール１１２は、１又は２以上のプロセッサで実行される並列オペレーティングシステムである可能性があるオペレーティングシステムを提供し、パーサ生成モジュール１０６は、そのオペレーティングシステムで実行されるプログラムとして実行される。ユーザ１１５が、表示された出力を見て、ユーザインターフェースで入力を与えることによって実行環境１０４とインタラクションすることもできる。
【００３５】
パーサ生成モジュール１０６は、ターゲットデータフォーマット１０５を表すデータを受信し、ターゲットデータフォーマット１０５は、そのターゲットデータフォーマット１０５に従って（正しく）フォーマットされていると考えられる可能なデータオブジェクトの許容される構造と、入力ストリームに現れる複数のデータオブジェクトの間の許容される順番とを定義する。ターゲットデータフォーマット１０５は、スキーマオブジェクト及びスキーマオブジェクトの間の関係によってどの種類のデータオブジェクトが容認され得るかを定義するためのスキーマを記述する規格に準拠していてもよい。ターゲットデータフォーマット１０５によって定義される構造は、データ値を含むデータオブジェクトを表すスキーマオブジェクト（例えば、データ値が関連するタグに基づいて認識可能であるタグ付けされたデータオブジェクト）と、潜在的に入れ子にされた構造に基づいてスキーマオブジェクト又はその他のコンテナオブジェクトを含み得るコンテナオブジェクト（例えば、タグのシーケンス、タグの組（セット）など）とを含む可能性がある。例えば、ターゲットデータフォーマット１０５がＡＳＮ．１規格のあるバージョンに準拠する場合、スキーマオブジェクトは、データ値に関連するタグ、それに続くデータ値の長さ、それに続くデータ値自体からなるデータオブジェクトを表す。ターゲットデータフォーマット１０５がＸＭＬ規格のあるバージョンに準拠する場合、スキーマオブジェクトは、開始タグ、それに続くデータ値、それに続く終了タグからなるデータオブジェクトを表す。一部の例において、ターゲットデータフォーマット１０５は、階層のノードを表すスキーマオブジェクト及びコンテナオブジェクトによる階層（例えば、ツリー又はその他の形式の階層表現）として表される。
【００３６】
ターゲットデータフォーマット１０５は、データソース１０２から実行環境１０４に届く入力ストリーム（例えば、ターゲットデータフォーマット１０５に従ってフォーマットされた一連のデータオブジェクトを含むデータストリーム）内のデータオブジェクトの期待されるフォーマットを記述する。また、ターゲットデータフォーマット１０５は、階層内のスキーマオブジェクト及びコンテナオブジェクトの間の順番を含む階層の構造に基づいて、入力ストリーム内の連続するデータオブジェクトの間のどの遷移が容認され得るかを暗黙的に決定する。パーサ生成モジュール１０６は、データソース１０２からの入力ストリームを解析することができるパーサを生成するためにターゲットデータフォーマットを処理する。（ＡＳＮ．１などの）一部の規格に準拠するターゲットデータフォーマットに関して、入力ストリームは、さまざまなタイプのコンテナオブジェクトに関して（例えば、シーケンス又は組に関して）含まれるデータオブジェクトの開始（又は終了）を示すタグ（又はその他のマーカ若しくは区切り）を含む可能性もあるが、システム１００はそのようなタグがあってもなくても入力ストリームを処理することができる。概して、実行環境１０４が入力ストリームからのデータを受信するとき、実行環境１０４の実行モジュール１１２は、生成されたパーサを用いて、データソース１０２から受信された入力ストリーム内のデータを解釈し、タグ付けされたデータオブジェクトの間の遷移を識別し、実行環境１０４にネイティブのレコードを投入することを含む、結果１１４を記憶するためのデータ操作を用いてそれらのデータオブジェクト内のデータ値を処理する。一部の例において、レコードは、データストレージシステム１１６に記憶される。データソース１０２及びデータストレージシステム１１６を提供するストレージデバイスは、実行環境１０４のローカルにあり、例えば、実行環境１０４を実行するコンピュータに接続されたストレージ媒体（例えば、ハードドライブ１０８）に記憶され、又は実行環境１０４のリモートにあり、例えば、リモート接続を介して実行環境１０４を実行するコンピュータと通信するリモートシステム（例えば、メインフレーム１００）でホストされる。
【００３７】
また、データストレージシステム１１６は、開発者１２０が解析されているデータ、記憶された結果１１４、及び／又はその他のデータに追加的な処理を適用するために実行モジュール１１２によって実行されるプログラムを開発することができる開発環境１１８にとってアクセス可能である。開発環境１１８は、一部の実施形態において、（構成要素又はデータセットを表す）頂点間の（作業要素（work element）のフローを表す）有向リンクによって接続された頂点を含むデータフローグラフとしてアプリケーションを開発するためのシステムである。例えば、そのような環境は、参照により本明細書に組み込まれる「Managing Parameters for Graph-Based Applications」と題された米国特許出願公開第２００７／００１１６６８号明細書により詳細に説明されている。そのようなグラフに基づく計算を実行するためのシステムは、参照により本明細書に組み込まれる米国特許第５，９６６，０７２号明細書、EXECUTING COMPUTATIONS EXPRESSED AS GRAPHSに説明されている。このシステムによって生成されるデータフローグラフは、プロセス間で情報を移動するため及びプロセスに関する実行の順番を定義するためにグラフの構成要素によって表される個々のプロセスに情報を出し入れするための方法を提供する。このシステムは、プロセス間通信の方法を選択するアルゴリズムを含む（例えば、グラフのリンクに従った通信経路は、ＴＣＰ／ＩＰ若しくはＵＮＩＸドメインソケットを使用するか、又はプロセス間でデータを渡すために共有メモリを使用する）。
【００３８】
図２を参照すると、ターゲットデータフォーマット２０５の単純な例は、それぞれが１又は２以上のスキーマオブジェクト２５２を含むいくつかのコンテナオブジェクト２５０を示す。一部の例において、ターゲットデータフォーマット２０５は、定義されたスキーマに従って容認され得るフォーマット及び入力ストリーム内のデータオブジェクトの間の順番の規定を可能にし、スキーマオブジェクト及びコンテナオブジェクトを規定するための表記を含む、ＸＭＬ又はＡＳＮ．１表記などの規格化された表記を用いて規定される。本明細書において使用されるとき、「スキーマオブジェクト」は、関連するデータオブジェクトのグループを表すために使用される定義されたスキーマを含む。非常に広く、コンテナオブジェクト（単に「コンテナ」とも呼ばれる）の例は、シーケンスコンテナ（sequence container）（つまり、順序付けられた１組のオブジェクトを含む）、組コンテナ（set container）（つまり、１若しくは２以上のオブジェクトが選択され得る１組のオブジェクトを含む）、又は選択コンテナ（choice container）（つまり、唯１つのオブジェクトが選択され得る１組のオブジェクトを含む）を含む。コンテナオブジェクト内のオブジェクトは、スキーマオブジェクト又はその他のコンテナオブジェクトであり、階層を形成する入れ子にされた構造を可能にする。スキーマオブジェクト２５２は、特定の関連するデータ値と、生成されたパーサによって投入されるレコード内のデータ値を表すためにシステム１００が使用するフィールド名とを特定するために入力ストリーム内の対応するデータオブジェクト内に現れるタグ２５３を含む。スキーマオブジェクト２５２は、そのデータ値のタイプを表す関連するデータ型（例えば、図２に示されるように整数の「ｉｎｔ」又は「ｓｔｒｉｎｇ」）を有する。一部のデータフォーマットにおいて、フィールド名は、タグの名前であるか、又は１若しくは２以上のタグに関連付けられる。以下の例の一部において、タグ「Ｔ」及びフィールド名「ｎ」を有するスキーマオブジェクトは、スキーマオブジェクト「Ｔ（ｎ）」と記載される。
【００３９】
以下は、ＡＳＮ．１表記でのターゲットデータフォーマット２０５の例である。
MOD DEFINITIONS IMPLICIT TAGS::=
BEGIN
A ::= SEQUENCE 
{
a1           TagP OPTIONAL,
a2           TagQ,
b            B OPTIONAL,
a6           TagU                
}
B ::= CHOICE 
{
b3           TagR,
c            SET OF C
}
C ::= SET 
{ 
c4           TagS,
c5           TagT
}
TagP ::= [UNIVERSAL 80] INTEGER
TagQ ::= [UNIVERSAL 81] INTEGER
TagR ::= [UNIVERSAL 82] IA5String
TagS ::= [UNIVERSAL 83] INTEGER
TagT ::= [UNIVERSAL 84] INTEGER
TagU ::= [UNIVERSAL 85] INTEGER
END
【００４０】
タグの仕様［ＵＮＩＶＥＲＳＡＬ８１］、［ＵＮＩＶＥＲＳＡＬ８２］などは、データにＡＳＣＩＩ値「Ｐ」、「Ｑ」などと同じタグを持たせる。ＡＳＮ．１に関して、入力ストリームは、下の一部の例において示されるように、シーケンスコンテナ又は組コンテナの始まりをマーキングする（しかし、選択コンテナに関してはマーキングしない）タグも含む。
【００４１】
図２のターゲットデータフォーマット２０５は、第１のスキーマオブジェクトＰ（ａ１）、第２のスキーマオブジェクトＱ（ａ２）、選択コンテナＣＨＯＩＣＥ＿Ｂ、及び第３のスキーマオブジェクトＵ（ａ６）を含むシーケンスコンテナＳＥＱ＿Ａを含む。選択コンテナＣＨＯＩＣＥ＿Ｂは、スキーマオブジェクトＲ（ｂ３）及び組コンテナＳＥＴ＿Ｃを含む。ＳＥＴ＿Ｃ組コンテナは、２つのスキーマオブジェクトＳ（ｃ４）及びＴ（ｃ５）を含む。Ｐ（ａ１）スキーマオブジェクト、ＣＨＯＩＣＥ＿Ｂ選択コンテナ、及びＳＥＴ＿Ｃ組コンテナは、すべて「ｏｐｔｉｏｎａｌ（オプショナル）」として指定されている。ｏｐｔｉｏｎａｌ指定は、指定されたコンテナオブジェクト又はスキーマオブジェクトによって表される（１又は２以上の）データオブジェクトがデータフォーマットによって必要とされず、入力ストリームがそのスキーマオブジェクトに対応するデータオブジェクトを含む若しくは含まないことを意味する。オブジェクトは、ｏｐｔｉｏｎａｌであるものとして、又はターゲットデータフォーマット内に現れる対応するラベルによる何らかのその他のプロパティを有するものとして指定され得る。一部の規格は、ターゲットデータフォーマット内のオブジェクトの明示的な指定を規定し、一部の規格は、ターゲットのデータフォーマット内のオブジェクトの暗黙的な指定を規定する。例えば、一部の規格（例えば、ＥＤＩ／ＥＤＩＦＡＣＴ）は、コンテナ内の第１のスキーマオブジェクトがｏｐｔｉｏｎａｌ指定を有する場合にターゲットデータフォーマットがコンテナ全体をｏｐｔｉｏｎａｌとして指定するポリシーを含む。各コンテナオブジェクトは、コンテナ内のすべてのオブジェクト（すなわち、スキーマオブジェクト及びコンテナオブジェクト）を包含する、本明細書においては「スコープ」と呼ばれるものを定義する。したがって、ＳＥＱ＿Ａのスコープは、Ｐ（ａ１）、Ｑ（ａ２）、ＣＨＯＩＣＥ＿Ｂ、及びＵ（ａ６）を包含する。ＣＨＯＩＣＥ＿Ｂのスコープは、Ｒ（ｂ３）、ＳＥＴ＿Ｃ、Ｓ（ｃ４）、及びＴ（ｃ５）を包含する。ＳＥＴ＿Ｃのスコープは、Ｓ（ｃ４）及びＴ（ｃ５）を包含する。
【００４２】
図３を参照すると、図２のターゲットデータフォーマット２０５が、データフォーマット２０５のコンテナオブジェクト及びスキーマオブジェクトがツリー３０５のノード３１９として示され、コンテナオブジェクト及びスキーマオブジェクトの間の関係がノード３１９を相互に接続するエッジ３２０として示されるツリー３０５として示されている。概して、スキーマオブジェクト及びそれらのスキーマオブジェクトの対応するデータオブジェクトに関連付けられる葉ノード（「データノード」と呼ばれる）が、データ値に対応する関連付けられたタグ及びフィールド名を有する一方、コンテナに関連する内部ノード（「コンテナノード」と呼ばれる）は、値がなく、タグに関連付けられ又は関連付けられない。
【００４３】
動作中、ツリーは、その最上部から下に向かって及びその左側からその右側に向かって読み込まれる。特に、図４の簡単な遷移図４００を参照すると、パーサは図２のデータフォーマット２０５に従ってフォーマットされた入力ストリームを読み込み、ルートφの開始状態から開始する。パーサは、入力ストリームから受信される第１のタグ付けされたデータオブジェクト（例えば、タグ−値ペアと呼ばれるタグとそのタグの対応するデータ値とのペア）がＰ（ａ１）スキーマオブジェクトに関するタグ−値ペアか又は（Ｐ（ａ１）スキーマオブジェクトがｏｐｔｉｏｎａｌとして指定されているので）Ｑ（ａ２）スキーマオブジェクトに関するタグ−値ペアかのどちらかであることを予期する。Ｐ（ａ１）スキーマオブジェクトに関するタグ−値ペアが入力データストリームから受信される場合、入力ストリームから受信される次のタグ−値ペアはＱ（ａ２）スキーマオブジェクトに関するタグ−値ペアでなければならない。
【００４４】
ＣＨＯＩＣＥ＿Ｂコンテナはｏｐｔｉｏｎａｌであるので、入力ストリームから受信される次のタグ−値ペアは、Ｕ（ａ６）、Ｒ（ｂ３）、Ｓ（ｃ４）、又はＴ（ｃ５）スキーマオブジェクトのうちのいずれかに関するタグ−値ペアである。（ＡＳＮ．１などの）一部の規格に関して、Ｓ（ｃ４）又はＴ（ｃ５）スキーマオブジェクトに関するタグ−値ペアの場合、ＳＥＴ＿Ｃの始まりをマーキングするタグも存在する。Ｒ（ｂ３）スキーマオブジェクトに関するタグ−値ペアが受信される場合、入力ストリームから受信される次のタグ−値ペアはＵ（ａ６）スキーマオブジェクトに関するタグ−値ペアでなければならない。Ｔ（ｃ５）スキーマオブジェクトに関するタグ−値ペアが受信される場合、入力ストリームから受信される次のタグ−値ペアはＳ（ｃ４）スキーマオブジェクトに関するタグ−値ペアでなければならない。次に、ＳＥＴ＿Ｃコンテナは（［］演算子によって示される）組コンテナの「ベクトル」として指定されるので、Ｓ（ｃ４）及びＴ（ｃ５）スキーマオブジェクトに関するタグ−値ペアの１又は２以上の組み合わせが入力ストリームから受信される（つまり、ループする動作が容認される）。Ｓ（ｃ４）及びＴ（ｃ５）スキーマオブジェクトのタグ−値ペアの１又は２以上の組み合わせが受信された後、Ｕ（ａ６）スキーマオブジェクトに関するタグ−値ペアが入力ストリームから受信される。Ｕ（ａ６）スキーマオブジェクトに関するタグ−値ペアが受信された後、レコード全体が受信され、レコードが終了される。受信されるすべての後続のタグ−値ペアは、次のレコードの一部である。
【００４５】
２  パーサの生成
図５Ａを参照すると、図１のパーサ生成モジュール１０６の一例が、ターゲットデータフォーマット１０５を入力として受信し、ターゲットデータフォーマット１０５を、データの前処理をほとんど又はまったくせずに、階層的なタグ−値構造を有する任意のターゲットデータフォーマットを確認し、解析することができるコンパイルされたパーサプログラム４１８へと処理するように構成される。そのようにするために、パーサ生成モジュール１０６は、階層的なターゲットデータフォーマットの要素の間の容認され得る遷移の一部又はすべてを特定することを含む、階層的なデータフォーマット内の「グローバルルーティング（global routing）」を決定する。パーサ生成モジュール１０６は、データフォーマットマッピングモジュール４２０、遷移分析モジュール４２４、及びプログラム生成モジュール４３０を含む。
【００４６】
図５Ｂを参照すると、一部の実施形態においては、実行環境１０４において実行されるデータフォーマットプロセッサ５００が、ターゲットデータフォーマット１０５を表す処理されたデータフォーマット情報５０２を形成するためにターゲットデータフォーマット１０５を前処理する。この処理されたデータフォーマット情報５０２は、パーサ生成モジュール１０６に、プログラム４１８が実行モジュール１１２によって実行されるときにデータストリーム５０４を特定の出力レコードフォーマット５０６へと解析するように構成されるパーサプログラム４１８を生成する準備をさせる。したがって、データフォーマット情報５０２は、出力レコードフォーマット５０６の定義も含む。データフォーマット１０５が準拠する規格（例えば、ＡＳＮ．１）の文法を受容し、ターゲットのデータフォーマット１０５から処理されたデータフォーマット情報５０２を生成するためにデータフォーマットプロセッサが使用するフォーマットパーサを出力するコンパイラ-コンパイラ（例えば、ｙａｃｃ又はＢｉｓｏｎ）の使用を含むさまざまな技術のいずれかが、ターゲットデータフォーマット１０５を前処理するようにデータフォーマットプロセッサ５００を構成するために使用され得る。
【００４７】
以下は、（「ｅｘａｍｐｌｅ．ａｓｎ１」と呼ばれるファイルに保存された）上で示されたＡＳＮ．１表記のターゲットデータフォーマット２０５の例から生成されたデータ操作言語（ＤＭＬ，Data Manipulation Language）で規定された処理されたデータフォーマット情報５０２の例である。
constant int ASN1_UNKNOWN = -1;
constant int ASN1_SEQUENCE = 0;
constant int ASN1_SET = 1;
constant int ASN1_CHOICE = 2;
constant unsigned int ASN1_TYPE_NONE = 10;
constant unsigned int ASN1_TYPE_BOOLEAN = 11;
constant unsigned int ASN1_TYPE_INTEGER = 12;
constant unsigned int ASN1_TYPE_ENUMERATED = 13;
constant unsigned int ASN1_TYPE_REAL = 14;
constant unsigned int ASN1_TYPE_OID = 15;
constant unsigned int ASN1_TYPE_ROID = 16;
constant unsigned int ASN1_TYPE_BIT_STRING = 17;
constant unsigned int ASN1_TYPE_OCTET_STRING = 18;
constant unsigned int ASN1_TYPE_NULL = 19;
type asn1_descriptor_t = record
unsigned int[int] tags;
unsigned int[int] elem_tags = NULL;
unsigned int type_encoding = ASN1_TYPE_NONE;
unsigned int lineno = 0;
unsigned int split = 0;
unsigned int extensible_before = 0;
unsigned int extensible_after = 0;
end;
type asn1_type_descriptor_t = record
int rec_type;
int file_id;
asn1_descriptor_t tag_info;
end;
let string(int, charset='x-ab-internal')[int] g_filenames = [vector "../example.asn1"];
//  MOD
type  MOD_TagP = integer(8);
type  MOD_TagQ = integer(8);
type  MOD_TagR = ascii string(integer(4));
type  MOD_TagS = integer(8);
type  MOD_TagT = integer(8);
type  MOD_C =
record
MOD_TagS c4;
MOD_TagT c5;
asn1_type_descriptor_t ASN_type_descriptor() = [record rec_type ASN1_SET file_id 0 tag_info (asn1_descriptor_t) [record tags [vector 68] lineno 22]];
asn1_descriptor_t[int] ASN_field_descriptors() = [vector
(asn1_descriptor_t) [record tags [vector 332] type_encoding ASN1_TYPE_INTEGER lineno 22],
(asn1_descriptor_t) [record tags [vector 336] type_encoding ASN1_TYPE_INTEGER lineno 24] ];
end;
type  MOD_B =
record
int choiceId = -1;
if (choiceId == 0)
MOD_TagR b3;
if (choiceId == 1)
MOD_C [integer(4)] c;
asn1_type_descriptor_t ASN_type_descriptor() = [record rec_type ASN1_CHOICE file_id 0 tag_info (asn1_descriptor_t) [record tags [vector ] lineno 16]];
asn1_descriptor_t[int] ASN_field_descriptors() = [vector
(asn1_descriptor_t) [record tags [vector 328] type_encoding ASN1_TYPE_OCTET_STRING lineno 16],
(asn1_descriptor_t) [record tags [vector 68] lineno 18] ];
end;
type  MOD_TagU = integer(8);
type  MOD_A =
record
MOD_TagP a1 = NULL;
MOD_TagQ a2;
MOD_B b = NULL([record choiceId (int) -1]);
MOD_TagU a6;
asn1_type_descriptor_t ASN_type_descriptor() = [record rec_type ASN1_SEQUENCE file_id 0 tag_info (asn1_descriptor_t) [record tags [vector 64] lineno 7]];
asn1_descriptor_t[int] ASN_field_descriptors() = [vector
(asn1_descriptor_t) [record tags [vector 320] type_encoding ASN1_TYPE_INTEGER lineno 7],
(asn1_descriptor_t) [record tags [vector 324] type_encoding ASN1_TYPE_INTEGER lineno 8],
(asn1_descriptor_t) [record tags [vector ] lineno 9],
(asn1_descriptor_t) [record tags [vector 340] type_encoding ASN1_TYPE_INTEGER lineno 11] ];
end;
type DML_ASN1_decode_t = MOD_A;
【００４８】
一部の実施形態において、パーサ生成モジュール１０６及び実行モジュール１１２は、提供されたデータフォーマットに従ってデータを解析するための共通処理モジュール又はシステムの構成要素である。例えば、単一のデータフローグラフにおいて、データフローグラフ内の単一の構成要素が、処理されたデータフォーマット情報５０２及び入力ストリーム５０４をデータフローグラフへの入力として両方のモジュールの機能を実行する。一部の実施形態においては、実行可能なパーサプログラム４１８を提供する代わりに、パーサ生成モジュール１０６が、下でより詳細に説明されるように、例えば、コンパイルツリー表現に関する詳細エッジの列挙されたリストなどの、解析を実行するために必要とされる遷移及びコンテキスト情報の表現を効率的に記憶するためのデータ構造としてパーサを提供する。
【００４９】
２．１  データフォーマットのマッピング
始めに、データフォーマット１０５は、データフォーマット１０５をパーサ生成モジュール１０６の後続のモジュールによって使用され得る内部の「ターゲット」データフォーマットにマッピングするデータフォーマットマッピングモジュール４２０に提供される。一部の例において、データフォーマット１０５は、規格のフォーマットマップファイル（例えば、ＡＳＮ．１、ＳＷＩＦＴ、又はＸ１２マップファイル）であり、内部のターゲットデータは、データフォーマット１０５のスコープツリー表現を含む。
【００５０】
２．１．１  データフォーマットのマッピングの例
図６を参照すると、図２の例示的なデータフォーマット２０５のスコープツリー表現６００が、データフォーマットに存在する異なるスコープを明示的に表す。スコープツリー表現６００は、コンテナオブジェクトタイプ又はタグ情報を含まない。コンテナタイプ及びタグ情報は、その代わりに、タグ及びコンテナタイプ情報がコンパイルノード（compile node）の属性として記憶されるコンパイルツリー（又はより広く、有向非循環グラフ（ＤＡＧ））に含まれる。コンパイルツリーがトラバースされるとき、属性が、エッジを生成するために使用される。コンパイルツリーは、下でさらに詳細に説明される。
【００５１】
一部の例において、スコープツリー表現６００のスコープ６６０によって包含される各スキーマオブジェクトは、空のプログラムテーブル（図示せず）に関連付けられる。パーサのコンパイルプロセスの後のステップが、スコープ及びスキーマオブジェクトに関連付けられ、１又は２以上の解析コマンドを含む「プログラム」でテーブルを満たし、これは、下でより詳細に説明される。
【００５２】
２．２  遷移の分析
データフォーマットのスコープツリー表現は、データフォーマットマッピングモジュール４２０から、入力ストリームのデータオブジェクト内の構造情報（例えば、タグ）に基づいて入力ストリーム内のデータオブジェクトの間の容認され得る遷移を列挙するためにデータフォーマットのスコープツリー表現を静的に分析する遷移分析モジュール４２４に渡される。この列挙に基づいて、上述のプログラムテーブルが、プログラムを投入される。容認され得る遷移を列挙するために、遷移分析モジュール４２４は、Ｘ１２、ＳＷＩＦＴ、ＨＬ７などの多くのデータ規格が、タグ−値ペアの形式でデータオブジェクトを表す葉としてスキーマオブジェクトを有するツリーとして表され、入力ストリーム内の１つのタグの存在が、入力ストリーム内の別のタグ又はタグの組（及びそれらのタグによって特定される関連するデータ値）の存在を必要とする又は必要としない（図３に示された）事実を利用する。
【００５３】
２．２．１  遷移の分析の例
図７を参照すると、始めに、遷移分析モジュール４２４が、スコープツリー表現のコンパイルツリー表現７００を形成する。上述のように、データフォーマットのコンテナオブジェクト及びスキーマオブジェクトは、ツリーのノード（「コンテナノード」及び「データノード」）として表され、コンテナオブジェクト及びデータオブジェクトの間の関係は、ツリーのノードを接続するエッジとして表される。一部の例においては、データフォーマットがベクトルを含む場合、コンパイルツリー表現７００が、遷移分析モジュール４２４によって内部で使用され、遷移分析プロセスを助ける追加的な「ＶｅｃｔｏｒＣｏｎｔａｉｎｅｒ」ノード７６２を含む。
【００５４】
遷移分析モジュール４２４は、コンパイルツリー７００をひと通り調べ、コンテナオブジェクトを表す各ノードに関して、ノードの「ファンイン」及び「ファンアウト」を計算する。所与のコンテナノードのファンインは、コンテナノードの外の別のノードから直接アクセスされ得るコンテナノードのスコープ内の（コンテナノードとデータノードとの両方を含む）ノードのすべてとして定義される。同様に、所与のコンテナノードのファンアウトは、所与のコンテナノードの外のノードに直接アクセスし得るコンテナノードによって含まれるノードのすべてとして定義される。
【００５５】
概して、組タイプのコンテナに関するファンイン及びファンアウトを計算するとき、組の子は、互いをターゲットとしなければならない。これは、組のすべてのメンバーに対してデカルト積を実行し、その組自体をループとして扱い、すべてのファンアウトノードにファンインノードのすべてをターゲットとさせることによって実現され得る。組がベクトルである場合、組の所与のメンバーがそのメンバー自体のみをターゲットとすることを保証するように注意が払われる。選択タイプのコンテナに関しては、コンテナのメンバーが互いをターゲットとしない。シーケンスタイプのコンテナに関しては、最後の１つを除くそれぞれの子のファンアウトが、次の子のファンインをターゲットとし、次の子がｏｐｔｉｏｎａｌである場合はその１つ後の子をターゲットとする（以下同様）。ノード自体がベクトルである場合、ベクトルノードのファンインを訪問（visit）し、各ファンインノードに関して、ベクトルノードのファンアウトを訪問し、それによってファンアウトからファンインへのエッジを生成することによってループエッジを生成する。
【００５６】
図２に示された例示的なデータフォーマットに関して、ＳＥＱ＿Ａは、Ｐ（ａ１）及びＰ（ａ１）及びＵ（ａ６）が（それぞれ）コンテナオブジェクト内の最初の及び最後のスキーマオブジェクトであり、必須のスキーマオブジェクトであるので、単一のファンインノードＰ（ａ１）及び単一のファンアウトノードＵ（ａ６）を有する。ＣＨＯＩＣＥ＿Ｂは、Ｒ（ｂ３）がｏｐｔｉｏｎａｌのスキーマオブジェクトであり、つまり、Ｑ（ａ２）がＲ（ｂ３）か又はＳＥＴ＿Ｃかのどちらかをターゲットとし得るので、Ｒ（ｂ３）及びＳＥＴ＿Ｃからなるファンインノードのリストを有する。ＣＨＯＩＣＥ＿Ｂのファンアウトノードのリストは、Ｒ（ｂ３）及びＳＥＴ＿Ｃからなる。ＳＥＴ＿Ｃは、Ｓ（ｃ４）及びＴ（ｃ５）からなるファンインノードのリストと、Ｓ（ｃ４）及びＴ（ｃ５）からなるファンアウトノードのリストとを有する。ＶｅｃｔｏｒＣｏｎｔａｉｎｅｒノード７６２は、コンテナのファンアウトがコンテナのファンイン及びシーケンスの次のノードのファンインをターゲットとし得ることを規定する特別なコンパイルに固有のタイプのコンテナオブジェクトを表す。
【００５７】
計算されたコンテナノードのすべてに関するファンイン及びファンアウトによって、エッジ生成プロセスが始まる。エッジ生成プロセスは、最も高いレベルのコンテナがそのコンテナ自体とそのコンテナの子（すなわち、コンテナのスコープ内のすべてのコンテナ及びスキーマオブジェクト）との間のエッジを形成することから始まる。一部の例においては、最も高いレベルのコンテナのノードからコンテナに関連するファンインノードのそれぞれへのエッジが生成される。それから、コンテナの子が、必要に応じて接続される。エッジの生成が完了すると、エッジが、重複するエッジ及び不完全なエッジ（例えば、コンテナ内で生成されたが、外部のコンテナによって不要にされたエッジ）を無効化することを含め、「組み合わされる」。
【００５８】
そして、遷移分析モジュール４２４が、コンパイルツリー表現７００を調べて周って、ツリーのノード（ソースノード及びターゲットノードと呼ばれる）の間の詳細エッジを生成する。詳細エッジは、ループする動作及びエッジに関連付けられる最も上のノードなどルーティング情報を含む、ソースノードからデスティネーションノードへのエッジとして定義される。一部の例において、詳細エッジは、エッジに関するソースノード、エッジに関するターゲットノード、エッジのループする動作、及びエッジに関する最も上のノードを表すデータを含む。ループする動作の可能な値は、Ｎｏ＿Ｌｏｏｐ（つまり、エッジに関してループする動作がない）、Ｅｎｄ＿Ｉｎｓｔａｎｃｅ（つまり、エッジに関してループする動作があり、ベクトルの現在のインスタンスが終了し、新しいインスタンスが始まる）、及びＥｎｄ＿Ｒｅｃｏｒｄ（つまり、エッジに関してループする動作があり、現在のレコードが終了し、新しいレコードが始まる）を含む。エッジに関する最も上のノードは、エッジが生成されるコンテナとして定義される。ループする動作がＥｎｄ＿ＩｎｓｔａｎｃｅであるときにＶｅｃｔｏｒＣｏｎｔａｉｎｅｒ内でエッジが生成される場合、エッジに関する最も上のノードは、ＶｅｃｔｏｒＣｏｎｔａｉｎｅｒノードである。そうではなく、ループする動作がＥｎｄ＿ＲｅｃｏｒｄであるときにＶｅｃｔｏｒＣｏｎｔａｉｎｅｒ内でエッジが生成される場合、エッジに関する最も上のノードは、「最上位ノード」として指定された特別なタイプのノードである。概して、ループする動作が存在する（つまり、ループする動作がＮｏ＿Ｌｏｏｐではない）とき、エッジに関するツリー内の最も上のノードは、ＶｅｃｔｏｒＣｏｎｔａｉｎｅｒノードである。例えば、Ｅｎｄ＿Ｉｎｓｔａｎｃｅのループする動作を有するＶｅｃｔｏｒＣｏｎｔａｉｎｅｒからのＳ（ｃ４）からＴ（ｃ５）へのエッジが生成されるとき、Ｓ（ｃ４）が開始ノードであり、ｃ５がターゲットノードであり、ＶｅｃｔｏｒＣｎｔｒ１がエッジに関する最も上のノードである。
【００５９】
図８を参照すると、図７のコンパイルツリー表現７００に関する詳細エッジの列挙されたリストが示されている。
【００６０】
２．３  曖昧性の解決
データフォーマット１０５へのｏｐｔｉｏｎａｌのスキーマオブジェクト、長さが不定のベクトル、繰り返されるタグ、及び複数のスコープの可能な包含が原因で、入力ストリーム内でのあるデータオブジェクトから別のデータオブジェクトへの遷移を認識する際に曖昧性が存在する可能性がある。これらの曖昧性は、同じソース及びデスティネーションを有する列挙されたリスト（図８）のエッジとして生じ得る。一部の例においては、遷移分析モジュール４２４が、ターゲットデータフォーマット１０５の曖昧性を（自動的にか又はユーザ入力に基づいてかのどちらかで）発見し、解決する。
【００６１】
２．３．１  曖昧性の解決の例
例えば、図２の例示的なデータフォーマットに関して、曖昧性は、ＳＥＴ及びベクトルコンテナの組み合わせが原因で、エッジＴ（ｃ５）−＞Ｓ（ｃ４）の複数のバージョンの間及びエッジＳ（ｃ４）−＞Ｔ（ｃ５）の複数のバージョンの間に存在する。特に、「Ｔ」タグから「Ｓ」タグへの遷移又は「Ｓ」タグから「Ｔ」タグへの遷移が存在するとき、遷移が同じ組内のデータオブジェクトの間にある（つまり、ループしない「内部エッジ」）のか又は１つの組内の最後のデータオブジェクトと後続の組内の最初のデータオブジェクトとの間にある（つまり、ループする「外部エッジ」）のかは、はっきりしない。曖昧性は、ループする構造が原因であるので、同じソース及びデスティネーションを有するエッジの２つのバージョンを複数の可能なターゲットのアクションを有する１つのエッジへと組み合わせることによって自動的に解決され得る。この例においてそのようにするために、ループする動作を含まない内部エッジが、ループする動作を確かに含む外部エッジと組み合わされる。概して、複数のエッジに関するターゲットのアクションは、可能なターゲットのアクションの順序付けられたリストに記憶され、特定のアクションが、リストを順番（例えば、最も近く（内部）から最も遠く（外部）へのエッジのスコープの順番に基づく順番）にトラバースすることに基づいて選択される。選択は、下でより詳細に説明されるように、ユーザ入力に基づくか、又は処理された最後の値の特徴、若しくはデクリメントされたカウント（例えば、２つのアイテムのペアのうちの残された１つのアイテム）、若しくは追跡された長さ（例えば、組の８バイトのうちの読み出されるために残っている４バイト）などのコンテキストを調べることに基づく可能性がある。
【００６２】
一部の例においては、さまざまなタイプの曖昧性の排除のうちのいずれかが使用される。例えば、入力データがＡＳＮ．１の基本符号化規則（ＢＥＲ，basic encoding rules）データとしてフォーマットされる場合、データはタグ−長さ−値の３つ組を含み、真の曖昧性は存在し得ない。この場合、すべての認識される曖昧性が、タグ−長さ−値の３つ組の中の長さ情報に寄って自動的に解決され得る。より広く、曖昧性を無視すること、自動的な曖昧性の排除を実行すること、又はユーザによって支援される曖昧性の排除を実行することなどの選択肢を提供することを含む曖昧性の検出及び解決が、曖昧性の問題に素早く効果的に対処するために使用され得る。
【００６３】
以下は、解析されるべき入力ストリーム内に現れる可能性がある一連のデータオブジェクトの例である。この例は、読みやすくするために、整数がＡＳＮ．１データで実際に符号化されるのと厳密に同様に符号化されないことを除いてＡＳＮ．１データに基づく。データオブジェクトは、任意のＶａｌｕｅが別の入れ子にされたＴＬＶの３つ組みである可能性があるＴ｜Ｌ｜Ｖ形式（Ｔａｇ｜Ｌｅｎｇｔｈ｜Ｖａｌｕｅ）である。
【００６４】
この例において、組及びシーケンスは、それらに関連するタグを常に有する。ＡＳＮ．１のＳＥＴコンテナは、デフォルトでタグ［ＵＮＩＶＥＲＳＡＬ１７］を有し、ＳＥＱＵＥＮＣＥコンテナは、デフォルトでタグ［ＵＮＩＶＥＲＳＡＬ１６］を有する。ＳＥＴ  ＯＦコンテナは、ＳＥＴと同じタグを有する。要素タイプ（この場合ＳＥＴ）に関するタグは、ベクトルの各要素に関するＳＥＴ  ＯＦタグの後に現れる。「葉の値（leaf value）」である（つまり、それら自体はＴＬＶの３つ組みではない）Ｖａｌｕｅに対応する以下の例の中の数は、Ｖａｌｕｅの終わりの「＊」によってマーキングされる。この例のタグは１６、１７、８１、８２、８３、８４、８５だけであり、Ｖａｌｕｅ又はＴａｇではないその他の数のすべてはＬｅｎｇｔｈである。
16|36|81|2|888*|17|24|17|10|83|2|1010*|84|2|2020*|17|10|83|2|444*|84|2|555*|85|2|999*
【００６５】
長さは、曖昧性が存在するとき又はデータの構造的な完全性が検証される必要があるときに調べられるアキュムレータを維持するために使用される（例えば、コンテナノードに関連する期待される長さを有するコンテナノードから外れると、正しい長さ又は量のデータが収集されたことを保証するためにチェックが実行される）。曖昧性がある場合、複数のターゲットのアクションのうちのどれが前のタグから現在のタグへの曖昧なエッジに関して実行されるべきかを決定するためにアキュムレータが調べられる可能性がある。
【００６６】
一部の例において、パーサは、到着するデータの構造的な確認を実行するように構成される。例えば、入力ストリームから受信されるデータが期待されていない順番で到着する場合、パーサは、エラーを発行する。別の例において、入力ストリームから受信されるデータが正常に解析され得ない場合、パーサは、エラーを発行する。
【００６７】
２．４  パーサの生成
ターゲットデータフォーマット１０５に関する詳細エッジのリストが決定されると、リストは、パーサプログラム４１８を生成するプログラム生成モジュール４３０に提供される。詳細エッジのリストは、図６のスコープツリー表現６００のために生成されたテーブルを満たすためのプログラムを構築するのに十分な情報を含む。特に、コンパイルツリー表現７００が単一のルートを有するツリーであるので、パーサの操作（例えば、push( )、pop( )、及びprocess( )コマンド）のシーケンスが、ＶｅｃｔｏｒＣｏｎｔａｉｎｅｒがどのように扱われるかを規定するループする動作を有するエッジに関連するソース、デスティネーション、及び最も上のノードから導出され得る。
【００６８】
プログラムを構築するために、図７のコンパイルツリー表現が再びトラバースされる。コンパイルツリー表現７００の各ノードに関して、ノードに関連するエッジのそれぞれが、エッジに関するプログラムを生成するために処理される。概して、エッジに関するプログラムを生成するために、始めに、プログラム生成モジュール４３０は、エッジに関する制御フローグラフを生成し、制御フローグラフは、生成されたコード（例えば、push( )、pop( )、及びprocess( )コマンド）を含む。それから、プログラム生成モジュール４３０が、制御フローグラフをトラバースしてプログラムを生成する。エッジに関するプログラムが生成されると、プログラムは、スコープツリー表現６００の適切なテーブルに追加される。一部の例において、プログラムは、プログラムに関連するエッジのソースノードに関連するタグを用いてテーブルでキー指定される。
【００６９】
一部の例においては、コンパイルツリー表現７００をトラバースする間に、コンテナが抜け出られるときに累積された長さとの比較が行われ得るようにコンテナが進入されるときにコンテナオブジェクトの期待される長さがコーディングされる。ノードが進入されるときにタグのオーバーヘッド（例えば、バイトで表されたタグの長さ）に注意しながら累積がコーディングされ、コンテナが抜け出られるときにコンテナの期待される長さとの突き合わせが行われる。一部の例においては、パーサが不定の長さを扱うことができるように、ノードが進入されるときにいつもアキュムレータがゼロにされ、長さ変数のインデックスがグローバル変数の配列の知られているインデックスに保存される。
【００７０】
コンテナが抜け出られるとき、累積値が、そのコンテナの親コンテナの累積値に足される。一部の例において、承認されていないタグに関するデフォルトのアクションが、拡張可能なコンテナ内にコーディングされる。組コンテナに関して、組によって必要とされるすべてのフィールドが割り振られることを保証するために、コンテナを抜け出るとチェックが実行される。入力ストリームからの値をその値の適切な形式へと解析するとき、整数値、オブジェクト識別子などが適切に復号され得るようにデータ変換がコーディングされる。
【００７１】
２．４．１  プログラムの生成の例
以下は、コンパイルグラフ表現７００の単一のエッジ（すなわち、エッジの組み合わせ後にＮｏ＿Ｌｏｏｐ遷移も含むＥｎｄ＿Ｉｎｓｔａｎｃｅエッジ、Ｓ（ｃ４）→Ｔ（ｃ５））に関するプログラムの生成の詳細な説明である。
【００７２】
このエッジに関するプログラムを生成するために、始めに制御フローグラフを生成することを含むコード生成が実行される。制御フローグラフは、ステートメント及び単一の条件を含むノードを含む２分木である標準的なコンパイラのデータ構造である。
stmt1,
stmt2,
...,
cond
ここで、ｃｏｎｄは、２つの制御フローグラフのエッジ、真のエッジ及び偽のエッジを有する。ｃｏｎｄに関連するエッジは、制御フローグラフ内のその他のノードに向かう。エッジに関するソースノード、デスティネーションノード、及び最も上のノードを考慮して、Ｓ（ｃ４）とＴ（ｃ５）との間の経路に関する制御フローグラフが、以下のように、始めに２つの有向経路、ＵＰ経路及びＤＯＷＮ経路を有する経路を表現することによって決定され得る。
UP:      c4->SET_C->VectorContainer_1
DOWN:    VectorContainer_1->SET_C->c5
【００７３】
ＵＰ及びＤＯＷＮ経路がトラバースされるとき、エッジに関する制御フローグラフのステートメント及び条件が生成され、制御フローグラフのエッジがそれらのエッジのそれぞれのノードと接続される。特に、エッジのＵＰ経路をトラバースするとき、code_node_exit()と名付けられた仮想関数が、抜け出られる各ノードに関して呼び出される。この場合、code_node_exit( )関数が、Ｓ（ｃ４）ノードに関して１回及びＳＥＴ＿Ｃノードに関して１回の２回呼び出される。これは、通常、制御フローグラフに２つのPOP( )ステートメント（すなわち、コマンド）を追加する。しかし、この場合、曖昧性が存在する。特に、Ｎｏ＿ＬｏｏｐのエッジＳ（ｃ４）−＞Ｔ（ｃ５）が、ループするエッジ（すなわち、Ｅｎｄ＿ｉｎｓｔａｎｃｅのＳ（ｃ４）−＞Ｔ（ｃ５））の中に記憶される。プログラム生成モジュール４３０は、ノードを抜け出ようとしているとき、ループするエッジ内の組み合わされたエッジのリストと照合する。組み合わされたエッジのリストの現在の要素の最上位ノードが抜け出られるノードと同じである場合、解決されなければならない曖昧性が存在する。曖昧性を解決する１つの可能な方法は、解決を実施するための特殊化を許容するためか、又は曖昧性が解決され得ない場合にエラーを発行するためにさえも別の仮想関数resolve_ambiguity( )を呼び出すことである。この例において、resolve_ambiguity( )関数は、ＳＥＴ＿Ｃ内の必須のノードの一部しか割り振られない場合、Ｎｏ＿Ｌｏｏｐ経路を選択する。
【００７４】
一部の例においては、ＳＥＴコンテナが、必須のフィールドの数を規定する変数を自動的にそのＳＥＴコンテナに添付させることが留意される。プログラム生成モジュール４３０がＳＥＴコンテナに入るとき、コンテナに添付された変数が、必須のフィールドの数に設定される。プログラム生成モジュールがそれぞれの必須のフィールドを訪れるとき、ＳＥＴコンテナに添付された変数がデクリメントされる。プログラム生成モジュール４３０がＳＥＴを離れるとき、ＳＥＴコンテナに添付された変数が非ゼロである場合、エラーが発行される。Ｓ（ｃ４）−＞Ｔ（ｃ５）エッジに関しては、曖昧性が原因で、エラーが発行されず、ＳＥＴコンテナが抜け出されない。
【００７５】
したがって、ＵＰ経路（すなわち、ｃ４−＞ＳＥＴ＿Ｃ−＞ＶｅｃｔｏｒＣｏｎｔａｉｎｅｒ＿１）に関して、以下の制御フローグラフのステートメントが生成される。
cf_node 1 {
c4->SET_C: POP
if (SET_C_nr == 0)
goto cf_node_2
else 
goto cf_node_3
}
cf_node_2 {
SET_C->VectorContainer_1: POP
...
}
cf_node_3 {
...
}
【００７６】
ループする動作がＮｏ＿Ｌｏｏｐではないので、ループの一番上において（つまり、ＶｅｃｔｏｒＣｏｎｔａｉｎｅｒ＿１ノードにおいて）、code_loop_top()と名付けられた仮想関数が呼び出される。曖昧性の解決がプログラム生成モジュール４３０がループするエッジを上がり続けることを許容したので、プログラム生成モジュール４３０は、制御フローグラフのｃｆ＿ｎｏｄｅ＿２ノードにステートメントを追加する。この場合、制御フローグラフのｃｆ＿ｎｏｄｅ＿２ノードに以下のステートメントを追加することによってインスタンスが終了され、ＳＥＴ＿Ｃ＿ｎｒ変数がリセットされる。
Vector_Container_1: End_Instance,
SET_C_nr = 2
【００７７】
ＤＯＷＮ経路に関して、code_node_enter()と名付けられた仮想関数が、進入される各ノードに関して呼び出される。この場合、code_node_enter( )は、ＳＥＴ＿Ｃに関して１回、ループするエッジに関するＴ（ｃ５）に関して１回、及びループしないエッジのＴ（ｃ５）に関して１回の３回呼び出される。ループしないエッジに関して、経路は、単純な遷移Ｓ（ｃ４）−＞Ｔ（ｃ５）を含む制御フローグラフのｃｆ＿ｎｏｄｅ＿３ノードを用いて下にトラバースされる。Ｔ（ｃ５）がＳＥＴコンテナ内にあるので、プログラム生成モジュール４３０は、そのＴ（ｃ５）が既に割り振られたかどうかを調べなければならない。ループするエッジに関する割り振りは、Ｅｎｄ＿Ｉｎｓｔａｎｃｅが新しいインスタンスにまだ何も割り振られていないことを保証するので調べられる必要がない。したがって、制御フローグラフのｃｆ＿ｎｏｄｅ＿３ノードは、以下のステートメントを含む。
for cf_node_3:
if (c5 is assigned)
goto cf_node_4
else
error already_assigned
【００７８】
Ｔ（ｃ５）が必須のフィールドであるので、以下のように、ＳＥＴ＿Ｃ＿ｎｒ変数が、制御フローグラフのｃｆ＿ｎｏｄｅ＿４ノードでデクリメントされる。
cf_node_4 {
c4->c5: PUSH c5
SET_C_nr = SET_C_nr - 1
c5: PARSE
}
【００７９】
制御フローグラフのｃｆ＿ｎｏｄｅ＿２ノードは、制御フローグラフのｃｆ＿ｎｏｄｅ＿４ノードと同じステートメントを含む。したがって、最終的な制御グラフは、以下のようになる。
cf
_node 1 {
c4->SET_C: POP
if (SET_C_nr == 0)
goto cf_node_2
else 
goto cf_node_3
}
cf_node_2 {
SET_C->VectorContainer_1: POP
VectorContainer_1:  End_Instance
SET_C_nr = 2
c4->c5: PUSH c5
SET_C_nr = SET_C_nr - 1
c5: PARSE
}
cf_node_3 {
if (c5 is assigned)
goto cf_node_4
else 
error already_assigned
}
cf_node_4 {
c4->c5: PUSH c5
SET_C_nr = SET_C_nr - 1
c5: PARSE
}
【００８０】
エッジのそれぞれに関する制御フローグラフが、エッジに関するバイトコードを組み立てるためにトラバースされる。制御フローグラフのトラバースの結果は、エッジに関するプログラムである。プログラムは、図６のスコープデータ表現６００の適切なテーブルに記憶される。各エッジに関するプログラムが（上記手順に従って）生成されると、パーサプログラム４１８が、プログラム生成モジュール４３０から出力される。
【００８１】
３  データ操作の例
以下の説明は、上述の技術に従ってコンパイルされ、図２のデータフォーマット２０５に従ってフォーマットされたデータを処理するように構成されたパーサを用いて入力データの例示的なストリームを解析する例を説明する。１つのデータオブジェクト（オブジェクト「ａ」）から別のデータオブジェクト（オブジェクト「ｂ」）への遷移が入力ストリーム内で認識された後、パーサは、例えば、「process(b)」コマンドを用いてオブジェクトｂに１又は２以上のデータ操作を適用し得る。
【００８２】
図９〜１１を参照すると、上述のようにパーサ生成モジュール１０６によって生成されたパーサ９２８の例示的な動作が示される。例において、パーサ９２８は、以下の入力ストリームを受信する。
|Q|888|S|1010|T|2020|T|555|S|444|U|999...
【００８３】
図９を参照すると、入力ストリーム９５４が、パーサに入り、レコード７５６へと解析されるところが示されている。さらに図１０を参照すると、パーサが従う遷移図１０５８が、入力ストリーム９５４を処理するためにパーサによって使用される遷移を示す（１）〜（５）の番号が付された太い矢印を含む。特に、入力ストリームから任意のデータを受信する前に、パーサは、そのφ状態にある。それから、パーサは、入力ストリームから後に値８８８が続くタグＱを受信する。入力は、パーサがそのφ状態からそのＱ（ａ２）状態に遷移する第１のパーサの遷移（１）を引き起こす。図１１に示されるように、φからＱ（ａ２）への遷移は、第１のレコードのａ２フィールドに値８８８を読み込むprocess(a)データ操作を含むパーサプログラムに関連付けられる。
【００８４】
それから、パーサは、入力ストリームから後に値１０１０が続くタグＳを受信する。入力は、パーサがそのＱ（ａ２）状態からそのＳ（ｃ４）状態に遷移する第２のパーサの遷移（２）を引き起こす。図１１に示されるように、Ｑ（ａ２）からＳ（ｃ４）への遷移は、push(SCOPE_B)コマンド、push(SCOPE_C)コマンド、及びprocess(c4)コマンドを含むパーサプログラムに関連付けられる。push(SCOPE_B)コマンドは、パーサにＣＨＯＩＣＥ＿Ｂコンテナのスコープへプッシュさせ、push(SCOPE_C)コマンドは、パーサにＳＥＴ＿Ｃコンテナのスコープへプッシュさせ、process(c4)コマンドは、パーサに値１０１０を第１のレコードのｃ４フィールドへ読み込ませる。
【００８５】
それから、パーサは、入力ストリームから後に値２０２０が続くタグＴを受信する。入力は、パーサがそのＳ（ｃ４）状態からそのＴ（ｃ５）状態に遷移する第３のパーサの遷移（３）を引き起こす。図１１に示されるように、Ｓ（ｃ４）からＴ（ｃ５）への遷移は、パーサに値２０２０を第１のレコードのｃ５フィールドに読み込ませるprocess(c5)コマンドを含むパーサプログラムに関連付けられる。パーサが既にＳＣＯＰＥ＿Ｃにあるので、この状況ではpush( )又はpop( )コマンドが必要でないことに留意されたい。
【００８６】
それから、パーサは、入力ストリームから後に値５５５が続く別のタグＴを受信する。Ｔ（ｃ５）がＳＥＴコンテナ（すなわち、ＳＥＴ＿Ｃ）の一部であるスキーマオブジェクトであるので、この場合、タグＴに関する複数の値が容認され得る。ＳＥＴコンテナは、複数の同じオブジェクトを含む１又は２以上のオブジェクトが選択され得るアイテムの順序付けられていない組を含む。入力は、パーサがそのＴ（ｃ５）状態からそのＴ（ｃ５）状態にループして戻るように遷移する第４のパーサの遷移（４）を引き起こす。図１１に示されるように、Ｔ（ｃ５）からＴ（ｃ５）へのループする遷移は、End_Instance( )コマンド（つまり、ＳＥＴ＿Ｃコンテナの第２のインスタンスが受信されていることを示す）と、パーサに値５５５を第１のレコードのｃ５フィールドの第２のインスタンスに読み込ませるprocess(c5)コマンドとを含むプログラムに関連付けられる。
【００８７】
それから、パーサは、入力ストリームから後に値４４４が続く別のタグＳを受信する。再び、Ｓ（ｃ４）スキーマオブジェクトがＳＥＴコンテナ（すなわち、ＳＥＴ＿Ｃ）の一部であるので、タグＳに関する複数の値は、この場合、容認され得る。入力は、パーサがそのＴ（ｃ５）状態からそのＳ（ｃ４）状態に遷移する第５のパーサの遷移（５）を引き起こす。図１１に示されるように、Ｔ（ｃ５）からＳ（ｃ４）への遷移は、パーサに値４４４を第１のレコードのｃ４フィールドの第２のインスタンスに読み込ませるprocess(c4)コマンドを含むパーサプログラムに関連付けられる。
【００８８】
最後に、パーサは、入力ストリームから後に値９９９が続くタグＵを受信する。入力は、パーサがそのＳ（ｃ４）状態からそのＵ（ａ６）状態に遷移する第６のパーサの遷移（６）を引き起こす。図１１に示されるように、Ｓ（ｃ４）からＴ（ｃ５）への遷移は、pop(SCOPE_C)コマンド、pop(SCOPE_B)コマンド、及びprocess(a6)コマンドを含むパーサプログラムに関連付けられる。pop(SCOPE_C)コマンドは、パーサにＳＥＴ＿Ｃコンテナのスコープからポップさせ、pop(SCOPE_B)コマンドは、パーサにＣＨＯＩＣＥ＿Ｂコンテナのスコープからポップさせ、process(a6)は、パーサに値９９９を第１のレコードのａ６フィールドに読み込ませる。この時点で、第１のレコードは、完成しており、パーサは、入力ストリームから受信される後続のデータによって満たされる新しいレコードを生成することができる。
【００８９】
４  代替
一部の例においては、すべての容認され得る遷移を含むコンパイルされたパーサを生成するのではなく、パーサによって必要とされる遷移が、要求に応じてコンパイルされる可能性がある（つまり、遷移は、必要とされるまでパーサにコンパイルされない）。そのようにすることは、メッセージの規格が大きいが、通常、実際のメッセージが規格の小さな部分しか実装しないという点で入力ストリームからのメッセージが概してまばらであるという事実を利用する。
【００９０】
上述の技術は、好適なソフトウェアを実行するコンピューティングシステムを用いて実装され得る。例えば、ソフトウェアは、それぞれが少なくとも１つのプロセッサ、（揮発性及び／又は不揮発性メモリ及び／又はストレージ要素を含む）少なくとも１つのデータストレージシステム、（少なくとも１つの入力デバイス又はポートを用いて入力を受け取るため、及び少なくとも１つの出力デバイス又はポートを用いて出力を与えるための）少なくとも１つのユーザインターフェースを含む（分散、クライアント／サーバ、又はグリッドなどのさまざまなアーキテクチャである可能性がある）１又は２以上のプログラミングされた又はプログラミング可能なコンピュータシステムで実行される１又は２以上のコンピュータプログラムの手順を含み得る。ソフトウェアは、例えば、データフローグラフの設計、構成、及び実行に関連するサービスを提供するより大きなプログラムの１又は２以上のモジュールを含む可能性がある。プログラムのモジュール（例えば、データフローグラフの要素）は、データリポジトリに記憶されたデータモデルに準拠するデータ構造又はその他の編成されたデータとして実装され得る。
【００９１】
上で提示された手法はデータフローグラフを用いて実装されるものとして説明されているが、手法は、任意の好適なプログラミング言語を用いて実行され得ることが留意される。つまり、手法は、データフローグラフ環境での使用に限定されない。
【００９２】
一部の例において、上述のコンパイルツリーは、特別な状況及び規格の例外を扱うために追加的なタイプのノードを含む。一部の例において、コンパイルツリーは、４つの異なるタイプの特別なノード、すなわち、ルートノード、ベクトルコンテナノード、空タグノード、及びファンアウト専用ノードを含む。（上で述べられた）ルートノードは、コンパイルツリーの開始の状態を表す。（やはり上で述べられた）ベクトルコンテナノードは、コンパイルツリー内のループの処理のために使用される。空タグノードは、承認されていないタグを表すために使用される。空タグノードは、例えば、拡張マーカの概念があり、承認されていないタグが無視されるＡＳＮ．１規格に関連して使用され得る。ファンアウト専用ノードは、タグに関連付けられるが、その子のすべて（すなわち、メンバー）がｏｐｔｉｏｎａｌであるコンテナを表すために使用される。つまり、コンテナは、いかなるデータ操作も実行せずに進入され、それから抜け出され得る。ファンアウト専用ノードは、例えば、必須であるが、完全にｏｐｔｉｏｎａｌな中身を有するコンテナを含むＡＳＮ．１規格に関連して使用され得る。ファンアウト専用ノードは、コンテナのファンアウトが直接、ターゲットにされ得るようにコンテナ内のノードとして挿入される。
【００９３】
一部の例において、ＡＳＮ．１規格の拡張マーカは、特別な処理を必要とする。以下の２つのシーケンスを考える。
TopSeq ::= SEQUENCE {
seq BottomSeq,
...
} 
BottomSeq ::= SEQUENCE {
str1 [0] IA5String,
str2 [1] IA5String OPTIONAL,
}
【００９４】
ＢｏｔｔｏｍＳｅｑのｓｔｒ１からｓｔｒ２への遷移は、タグ［１］がＴｏｐＳｅｑで無視されるタグである可能性があるので、ＴｏｐＳｅｑの拡張マーカ（すなわち、「．．．」）が原因で曖昧である。この状況を扱うために、曖昧性の解決中に、ｓｔｒ１からｓｔｒ２への遷移は、その遷移がＴｏｐＳｅｑの拡張マーカ（すなわち、「．．．」）もターゲットにするように強制的に曖昧にされる。
【００９５】
ソフトウェアは、ＣＤ−ＲＯＭ又は（例えば、多目的若しくは専用のコンピューティングシステム若しくはデバイスによって読み取り可能な）その他のコンピュータ可読媒体などの有形の非一時的媒体で提供されるか、或いはそのソフトウェアが実行されるコンピューティングシステムの有形の非一時的媒体にネットワークの通信媒体を介して配信される（例えば、伝播信号で符号化される）可能性がある。処理の一部又はすべては、専用のコンピュータで、又はコプロセッサ若しくはフィールドプログラマブルゲートアレイ（ＦＰＧＡ，field-programmable gate array）若しくは専用の特定用途向け集積回路（ＡＳＩＣ，application-specific integrated circuit）などの専用のハードウェアを用いて実行される可能性がある。処理は、ソフトウェアによって指定された計算の異なる部分が異なる計算要素によって実行される分散された方法で実装される可能性がある。それぞれのそのようなコンピュータプログラムは、本明細書において説明された処理を実行するためにストレージデバイスの媒体がコンピュータによって読み取られるときにコンピュータを構成し、動作させるために、多目的又は専用のプログラミング可能なコンピュータによってアクセス可能なストレージデバイスのコンピュータ可読記憶媒体（例えば、ソリッドステートメモリ若しくは媒体、又は磁気式若しくは光学式媒体）に記憶されるか又はダウンロードされることが好ましい。本発明のシステムは、コンピュータプログラムで構成された有形の非一時的媒体として実装されると考えられる可能性もあり、そのように構成された媒体は、本明細書において説明された処理ステップのうちの１又は２以上を実行するために特定の予め定義された方法でコンピュータを動作させる。
【００９６】
本発明のいくつかの実施形態が、説明された。しかしながら、上述の説明は、添付の請求項の範囲によって画定される本発明の範囲を例示するように意図されており、限定するように意図されていないことを理解されたい。したがって、その他の実施形態も、以下の請求項の範囲内にある。例えば、本発明の範囲を逸脱することなくさまざまな修正がなされ得る。さらに、上述のステップの一部は、順番に依存しない可能性があり、したがって、説明された順番とは異なる順番で実行され得る。
【図１】
0006377739.tif 000002
【図２】
0006377739.tif 000003
【図３】
0006377739.tif 000004
【図４】
0006377739.tif 000005
【図５Ａ】
0006377739.tif 000006
【図５Ｂ】
0006377739.tif 000007
【図６】
0006377739.tif 000008
【図７】
0006377739.tif 000009
【図８】
0006377739.tif 000010
【図９】
0006377739.tif 000011
【図１０】
0006377739.tif 000012
【図１１】
0006377739.tif 000013