モジュラフォレストオートマトン
モジュラフォレストオートマトン（ＭＦＡ）は、半順序正規ツリーパターンについての統一された記載を提供する。ＭＦＡはまた、これらのパターンの決定化、サブタイプ化、交わり、および相補のための簡素な方法を提供する。ＭＦＡは、高性能のパターン分析およびマッチングをサポートする。モジュラフォレストオートマトンと併せて、モジュラフォレストトランスデューサにより、コンパイラが、セマンティックアクションを任意の状態遷移におくことが可能にされ、一方でラベル付き有向グラフの効率的な変換がサポートされる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、モジュラフォレストオートマトンに関する。
【背景技術】
【０００２】
プログラミング言語では、値のクラス間を区別するパターンを使用することが可能である。例えば、以下の疑似コードの２行では、整数のリストの合計を計算する関数が定義される。
Ｓｕｍ（ｎｉｌ）＝０
Ｓｕｍ（ｃｏｎｓ［ｈｅａｄ，ｔａｉｌ］）＝ｈｅａｄ＋Ｓｕｍ（ｔａｉｌ）
【０００３】
この例のパターンは２つの役割を有する。すなわち、第１に、入力事例を区別すること、第２に、パターン変数および型推論の使用を介して簡潔な値の脱構築を可能にすることである。
【０００４】
パターンは、構造型に密接に関連する。本明細書において記載する正規ツリーパターンは、変数束縛を含むことができる正規ツリー型である。セマンティックアクションと連結されたツリーパターンをツリー変換規則と呼ぶ。
【０００５】
ＸＭＬスキーマ言語等の構造型システムでは、値のカテゴリを定義する。プログラミング言語では、構造型システムを使用してプログラムの安全特性を静的にチェックすることがよくある。ＳＱＬデータベースではまた、主として構造に焦点を合わせた型システムを使用する。結合の結果得られるテーブルは、例えば、無名の構造型を持つものとして記載されるタプルを含む。データベース管理システムは、様々なプログラムがシステムに記憶されるデータを解釈することが可能であることを要求する。構造型システムは、データベース管理システムがこの要求を満たすようにサポートする。
【０００６】
分散システムではまた、構造型に対する要求を引き起こす。レイテンシのため、分散プログラムコンポーネント間で交換されるメッセージは、オブジェクト間で交換されるメソッド引数より大きくかつ複雑であることが多い。
【０００７】
データベースに記憶され分散コンポーネント間で交換される値は、複雑性においては、プログラム表現により操作される単純な値とチューリングマシンの複雑性との中間にある。本明細書において記載するが、正規ツリーパターンを使用して構造の複雑性のこれらの中間レベルが定義される。
【０００８】
順序正規ツリーパターンおよび非順序正規ツリーパターンの両方を表現しかつ分析することは、有用かつ有益な能力であろう。分析が有益に向上されるであろうドメインの例には、モデル検査および半順序ツリーパターンを使用する権限付与ロジックが含まれる。ＸＭＬスキーマ等の特定の既存の言語では、順序正規ツリーを部分的に使用することができるが、現在のところサブタイプ化するための手段がない。さらに、そのような言語では、現在既知の方法の下で効果的な実現をサポートするためにセマンティックな制約が課せられる。
【０００９】
欲張りな正規表現のマッチングおよびプログラミング言語ＸＳｔａｔｉｃについて研究がなされ、正規の順序ツリー型をオブジェクト指向の言語にどのように組み込むかが模索されてきた。ＸＤｕｃｅのように、ＸＳｔａｔｉｃでは、シーケンスに対して一定の表現を使用する。そのような研究により正規の順序ツリー型がオブジェクトにマップされ、フラット化を使用して、正規言語の包含物の自然意味論をサポートする。最後にｔｒｘが、スキームの文脈で正規順序ツリー型を模索する。
【発明の概要】
【課題を解決するための手段】
【００１０】
プッシュダウンフォレストオートマトン（ＰＦＡ）についても研究が達成された。しかし、ＰＦＡでは、非順序のネスト（マルチ集合）に対処するサブタイプ化のアルゴリズムまたは機構を提供しない。
【００１１】
本発明の実施形態は、モジュラフォレストオートマトン（ＭＦＡ）に関する。本明細書において記載するモジュラフォレストオートマトンを使用して、正規ツリーパターンを記述および分析することが可能であり、また、ラベル付き有向グラフの変換を簡潔に表現することができるモジュラフォレストトランスデューサ（ＭＦＴ）を作成することが可能である。グラフ変換は、ロジック、処理モデル、およびプログラミング言語の実装における基本の要素である。モジュラフォレストオートマトンの実装を使用して、高性能な、強力にタイプ化されたグラフ変換をサポートすることができる。
【００１２】
モジュラフォレストオートマトンは、半順序の、有限の、ランク付けされないツリーのコレクションを定義、再組織化、および変換するための機構である。ＭＦＡは、ＭＦＡ階層の分析および合成をサポートする。ＭＦＡでは、順序ツリーパターンおよび非順序ツリーパターンを統一して処理する。
【００１３】
本明細書において記載する実施形態には、正規ツリーパターンを分析するための方法、システム、およびコンピュータプログラム製品が含まれる。特定の実施形態では、シーケンスおよび集合の両方を記述するモジュール（マシン（machine））として決定または書き換えされることが可能なデータが、受け取られる。和集合は、受け取られたデータから決定されるモジュールから作成することができる。決定されたモジュールおよびモジュールの和集合は、ラベル付き受容状態を備えることができる。ラベル付き受容状態から、サブタイプ関係がモジュールに対して決定される。
【００１４】
本明細書において記載する他の実施異形態にはまた、正規ツリーパターンの変換を表現するための方法、システム、およびコンピュータプログラム製品が含まれる。正規ツリーパターンが受け取られ、特定のインスタンスデータが受け取られる。トランスデューサが、受け取られた正規ツリーパターンからコンパイルされる。トランスデューサの遷移が、所望の変換に対応する命令で拡張される。拡張されたトランスデューサの遷移およびインスタンスデータから、正規ツリーパターンのエレメントとインスタンスデータのエレメントとの間の対応が決定される。
【００１５】
この要約は、以下の「発明を実施するための形態」でさらに述べる概念を選択して簡略化した形式で紹介するために提供するものである。この要約は、請求の主題の重要な特徴または主要な特徴を確認することを意図しておらず、請求の主題の範囲を決定する際の助けとして使用されることも意図していない。
【００１６】
本発明の追加の特徴および利点は、以下に続く記載において説明され、一部は記載により明らかにされ、または、本発明の実践により習得されるであろう。本発明の特徴および利点は、特に添付の請求項において指摘される機器および組み合わせを用いて、実現および取得することができる。本発明のこれらおよびその他の特徴は、以下の記載および添付の請求項からさらに完全に明らかにされ、または、以下に説明されるような本発明の実践により習得されるであろう。
【図面の簡単な説明】
【００１７】
本発明の上記に列挙した利点および特徴ならびに他の利点および特徴を取得することが可能な方法で記載するために、上記で簡単に記載された本発明のより詳しい説明が、添付の図面に例示される本発明の特定の実施形態を参照して描写される。これらの図面は、本発明の単なる典型的な実施形態を示し、かつ、従ってその範囲を制限するとみなされないことを理解した上で、本発明は、添付の図面を使用して追加の特異性および詳細と共に記載および説明されるであろう。
【図１】本発明の原理の実施形態を動作させることができるコンピュータ環境を例示する図である。
【図２】パターンのネストされたコンテンツに対する置換モジュラフォレストオートマトンを例示する図である。
【図３】特定のパターンＥｘｐｒの決定された翻訳を例示する図である。
【図４】パターンＰｏｎｄのネストされたコンテンツに対する最適化されたモジュラフォレストオートマトンを例示する図である。
【図５】サブタイプ分析で決定された種々のサブタイプの図式表現を例示する図である。
【図６】パターンＧＴＥのネストされたコンテンツに対する非決定性モジュラフォレストオートマトンを例示する図である。
【図７】パターンＧＴＥのネストされたコンテンツに対して決定されたモジュラフォレストオートマトンを例示する図である。
【図８】本発明の特定の実施形態に従って、正規ツリーパターンを分析するための方法のフローチャートを例示する図である。
【図９】本発明の特定の実施形態に従って、正規ツリーパターンの変換を表現するための方法のフローチャートを例示する図である。
【発明を実施するための形態】
【００１８】
本明細書において記載する実施形態は、正規ツリーパターンを分析するための方法、システムおよびコンピュータプログラム製品に関する。本明細書において記載する追加の実施形態は、正規ツリーパターンの（単数または複数の）変換を表現するための方法、システムおよびコンピュータプログラム製品に関する。本発明の実施形態は、以下で詳細に検討するように、種々のコンピュータハードウェアを含む専用または汎用のコンピュータを備えることができる。
【００１９】
図１は、本明細書において記載する実施形態が実践される例示のコンピュータ環境１００を説明する。コンピュータ環境１００には、１つまたは複数のコンピュータプロセッサ１１０が含まれる。コンピュータ環境１００にはまた、１つまたは複数のコンピュータメモリのインスタンス１２０が含まれる。コンピュータメモリ１２０は、適切であることが既知である任意のコンピュータ可読メモリとすることができ、ＲＡＭ、ＳＲＡＭ、およびフラッシュメモリを含む（がこれに限定されない）。コンピュータメモリはまた、ハードディスク、ソリッドステートディスクドライブ、ＣＤＲＯＭ、ＤＶＤ、等の永続記憶装置１３０とすることができる。コンピュータメモリ１２０および記憶装置１３０は、任意の特定の実施形態において適切であるように、ＲＯＭまたはＣＤまたはＤＶＤ等の読取り専用メモリとすることができ、または、ＲＡＭ、フラッシュメモリおよび一般的なディスクドライブ等の読取り可能かつ書込み可能メモリとすることができる。
【００２０】
コンピュータ環境１００にはまた、入力／出力１４０が含まれる。入力／出力１４０は、磁気ディスクに記憶されるデータ、ネットワークを介してアクセス可能なデータ、またはその他、等の任意の適切なフォーマットまたは媒体を備えることができる。コンピュータ環境１００にはまた、データが送受信される外部永続記憶装置１５０が含まれる。記憶装置１３０と同様に、外部永続記憶装置１５０は、磁気ディスク、テープ、ＣＤ−Ｒ／Ｗ、またはその他、等の任意の適切な形式をとることができる。
【００２１】
本発明の範囲内にある実施形態にはまた、コンピュータ実行可能命令またはそれに記憶されるデータ構造を搬送するまたは有するためのコンピュータ可読媒体が含まれる。そのようなコンピュータ可読媒体は、汎用または専用のコンピュータによりアクセス可能な任意の利用可能な媒体とすることができる。制限ではなく例として、そのようなコンピュータ可読媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭもしくは他の光ディスク記憶装置、磁気ディスク記憶装置もしくは他の磁気記憶デバイス、または、汎用または専用のコンピュータによりアクセス可能なコンピュータ実行可能命令またはデータ構造の形式の所望のプログラムコード手段を、搬送または記憶するために使用可能な任意の他の媒体、等の記憶媒体を備えることができる。ネットワークまたは別の通信接続（有線、無線、または有線と無線の組み合わせ）を介して、コンピュータに情報が転送または提供されると、コンピュータはその接続をコンピュータ可読媒体として適正に見なす。そのようなネットワークまたは通信接続を、本明細書において、通信媒体と称する。従って、任意のそのような接続を、適正にコンピュータ可読媒体と呼ぶ。記憶媒体および通信媒体の両方を含む上記の組み合わせもまた、コンピュータ可読媒体の範囲に含めることができる。
【００２２】
コンピュータ実行可能命令は、例えば、汎用コンピュータ、専用コンピュータ、または専用の処理デバイスに、特定の機能または機能のグループを実行させる、命令およびデータを備える。そのようなコンピュータ実行可能命令は、コンピュータメモリ１２０内、永続記憶装置１３０内、任意の入力もしくは出力の媒体もしくはデバイス１４０上、または外部記憶装置１５０上、に記憶することができる。コンピュータ実行可能命令を、任意の適切な通信媒体を介して適切なコンピュータ環境に転送することもできる。
【００２３】
主題が、構造的特徴および／または方法論的な動作に特有の言語で記載されたが、添付の請求項に定義される主題が必ずしも記載された特有の特徴または動作に限定されないことは理解されるべきである。むしろ、前述の特有の特徴および動作は、請求項を実装する例示の形式として開示される。
【００２４】
本明細書において記載する実施形態は、正規ツリーパターンを分析するための方法、システム、およびコンピュータプログラム製品に関する。本明細書において記載する追加の実施形態は、正規ツリーパターンの変換を表現するための方法、システムおよびコンピュータプログラム製品に関する。本発明の実施形態は、以下で詳細に検討するように、種々のコンピュータハードウェアを含む専用または汎用のコンピュータを備えることができる。
【００２５】
例えば、図８は、正規ツリーパターンを分析するための方法を例示する。方法は、１シーケンスおよび１集合の内の少なくとも１つを備える正規ツリーパターンを備えるデータを受け取るステップ８１０を含む。ツリーパターンが１シーケンスを備える場合、８２０で、そのシーケンスに対応するマシンが決定される。決定されたマシンは、「モジュール」とも呼ばれる。１シーケンスは、その名前が暗に示すように、特定の順番を有するエレメントの１集合である。
【００２６】
８３０で、ツリーパターンが１集合を備える場合、その１集合に対応するマシンが決定される。特定の順番を有する１シーケンスとは対照的に、１集合は、特に順番が指定されないエレメントのコレクションとすることができる。
【００２７】
８４０で、決定されたマシンの和集合が作成される。８５０で、決定されたマシン（モジュール）の和集合から、ラベル付き受容状態の１集合が決定される。最後に、８６０で、ラベル付き受容状態からサブタイプ関係が決定される。
【００２８】
本明細書においてさらに詳細に記載するように、サブタイプ関係は、等価、サブタイプ、スーパータイプ、互いに素、および交わり、の内の１つとすることができる。２つのモジュールＭ1およびＭ2が、同一の受容状態を有す場合、これらは等価である。Ｍ1がＭ2の全ての受容状態を含み、その逆が無い場合、Ｍ1はＭ2のスーパータイプであり、Ｍ2はＭ1のサブタイプである。Ｍ1とＭ2が共通した受容状態を持たない場合、Ｍ1とＭ2は互いに素である。Ｍ1とＭ2がいくつかの受容状態を共有するが、Ｍ1、Ｍ2のそれぞれが他とは共有されない受容状態を有する場合、これらは交わっている。サブタイプ関係は、以下でより詳細に図５と併せて検討する。
【００２９】
実施形態はまた、ラベル付きネストへの少なくとも１つの遷移を備えるルートレベルマシン（モジュール）を決定するステップを含む。ラベル付きネストは、本明細書においてより詳細に記載するように、Ｌａｂｅｌ［・・］またはＬａｂｅｌ｛・・｝の形式を有することができる。モジュールは、ラベル付きネストに対応して作成される。ラベル付きネストからの復帰（リターン）に対応する継続状態は、スタック上に置くことができる。継続状態をスタック上に置いた後、ラベル付きネストに対応するアクションが実行される。受容状態がラベル付きネストに達すると、継続状態がスタックからポップされ、処理はルートレベルマシンに向かって再開される。
【００３０】
明細書において記載する実施形態を採用すると、受け取られたデータは、プログラミング言語で構造型を定義するデータに対応する。そのようなデータは、本明細書において記載する技術により分析されて、構造型が等価であるか、または、本明細書に記載されるような他のサブタイプ関係のいずれかを有するか、を判定することができる。
【００３１】
本明細書において記載する実施形態を採用すると、受け取られたデータは、データベースのスキーマおよび／またはスキーマ定義を備えるデータに対応する。そのようなデータは、本明細書において記載する技術により分析されて、スキーマとスキーマ定義が等価であるか、または、他のサブタイプ関係のいずれかを有するか、を判定することができる。
【００３２】
本明細書において記載する実施形態を採用すると、受け取られたデータは、ＸＭＬスキーマに対応する。そのようなデータは、本明細書において記載する技術により分析されて、ＸＭＬスキーマが等価であるか、または、他のサブタイプ関係のいずれかを有するか、を判定することができる。
【００３３】
本明細書において記載する実施形態を採用して、判定されたサブタイプ関係に対応する構造的関係および論理的関係を決定することができ、また、プログラミング言語、データベース、オブジェクト等におけるデータ構造に対する最適化、効率、およびデータ翻訳の目的に適用することができる。
【００３４】
本明細書において記載する実施形態はまた、正規ツリーパターンの変換を表現するための方法を含む。図９は、正規ツリーパターンの変換を表現するための方法９００を例示する。方法は、正規ツリーパターンに対応する第１のデータを受け取るステップ９１０を含む。方法はまた、実際のインスタンスに対応する第２のデータを受け取るステップ９２０を含む。
【００３５】
例えば、正規ツリーパターンを備えるデータは、ＸＭＬスキーマを備えることができ、データベーススキーマを備えることができ、プログラミング言語またはオブジェクト定義のための構造型を備えることができる。実際のインスタンスに対応するデータは、データベース内のデータを備えることができ、シリアルデータ入力ストリームを備えることができ、または、オブジェクト指向のオブジェクト内で具現化されるデータまたはプログラミング言語内に定義される構造型を備えることができる。
【００３６】
方法９００は、正規ツリーパターンをトランスデューサにコンパイルするステップ９３０を含む。ツリーパターンのコンパイルについては、本記載の後の章でより詳細に記載する。コンパイルされると、９４０で、トランスデューサの遷移が所望の変換に対応する命令で拡張される。遷移が命令で拡張された後、９５０で、拡張された遷移から、および、実際のインスタンスに対応するデータから、インスタンスのエレメントと正規ツリーパターンのエレメントとの間の対応が決定される。
【００３７】
例えば、Ｒｏｏｔ［Ａ＋，Ｂ*，Ｃ？］等のパターン、および、実際のインスタンスデータ（環境内に与えられた）［ａａａ，ｂｂｂ，−］がある。この例から、方法９００では、特定の束縛Ａ＝‘ａａａ’、Ｂ＝‘ｂｂｂ’、およびＣ＝‘−’を決定することができる。さらに、例えば、ａｃｔｉｏｎ：Ｒｏｏｔ［Ａ，Ｂ，Ｃ］→Ｒｏｏｔ［Ａ，Ｃ］、等のアクションが実行される。束縛が決定されると、例示のアクションは、「Ｂを削除する」アクションであると考えることができる。
【００３８】
方法９００を、変数束縛の環境に採用することができる。そのような変数束縛は、プログラミング言語、データベーススキーマ、ＸＭＬスキーマ等における構造型と、タイプまたはスキーマ内に定義される変数に対応する実際の値と、の間の対応を決定することができる。
【００３９】
方法９００の命令はまた、条件のマッチングを備えることができ、また、セマンティックアクションを備えることができる。方法９００のインスタンスデータは、ＸＭＬスキーマインスタンスを備えることができ、特定のデータベーススキーマに従ってデータベース内に含まれるデータのインスタンスを備えることができ、または、プログラミング言語内に定義される構造型に従って定義または記憶されるデータを備えることができる。
【００４０】
方法９００はまた、クエリ表現をコンパイルするステップと、正規ツリーパターンおよび実際のインスタンスデータに対応するクエリ表現の結果を判定するステップと、を備えることができる。例えば、そのようなクエリは、ＳＱＬ等のデータベースクエリとすることができ、また、データアクセス等の権限付与クエリとすることができる。
【００４１】
なお、本明細書において記載する全ての方法および技術は、コンピュータ環境内で実行する方法、本明細書において記載する方法および技術を実行するためのコンピュータ実行可能コードを備えるコンピュータプログラム製品、および、本明細書において記載する方法および技術を実行するためのコンピュータプロセッサおよびコンピュータ実行可能コードを備えるコンピュータシステム、を備えることができる（がこれに限定されない）種々の実施形態において実現することができる。
【００４２】
本明細書において記載する実施形態の方法および技術についての、より詳細かつ綿密な検討が続く。
【００４３】
正規ツリーパターン
リスト１には、正規ツリーパターンに使用することができる構文を記載する。リスト１の文法では、項Ａｃｔｉｏｎはセマンティックアクションの言語を参照する引数である。項Ｎａｍｅ、Ｖａｒｉａｂｌｅ、およびＬａｂｅｌは、１つのアルファベットで呼ばれる記号の集合をそれぞれ提供する引数である。本明細書において記載するように、変数、パターン名、およびラベルの記号は、別々のアルファベットでできているものとする。これらの記号に加えて、パターンは、非パターン型、またはリテラル値を含む基の記号を参照することができる。
Ｄｅｆｉｎｉｔｉｏｎ→ Ｎａｍｅ‘＝’Ｐａｔｔｅｒｎ
Ｐａｔｔｅｒｎ → Ｕｎｉｏｎ
｜ ΛＶａｒｉａｂｌｅ．Ｐａｔｔｅｒｎ
｜ ε
Ｕｎｉｏｎ → Ｒｕｌｅ（‘｜’ＲｕＩｅ）＊
Ｒｕｌｅ → ＴｒｅｅＡｃｔｉｏｎ？
Ｔｒｅｅ → Ｌａｂｅｌ［Ｆｏｒｅｓｔ？］
｜ Ｌａｂｅｌ｛Ｆｏｒｅｓｔ？｝
｜ ＢｉｎｄｉｎｇＴｒｅｅ
｜ ＴｒｅｅＲｅｐｅｔｉｔｉｏｎ
｜ Ｔｒｅｅ∧Ｔｒｅｅ
｜ ¬Ｔｒｅｅ
｜ （Ｔｒｅｅ）
｜ ａｎｙ
｜ Ｒｅｆｅｒｅｎｃｅ
Ｆｏｒｅｓｔ → ＴｒｅｅＦｏｒｅｓｔ，Ｔｒｅｅ
Ｒｅｐｅｔｉｔｉｏｎ→ ＊｜＋｜？
｜ ［Ｍｉｎ．．．Ｍａｘ］
Ｒｅｆｅｒｅｎｃｅ → ＳｙｍｂｏｌＴｙｐｅＰａｒａｍ？
ＴｙｐｅＰａｒａｍ → （Ｕｎｉｏｎ）
Ｂｉｎｄｉｎｇ → Ｖａｒｉａｂｌｅ：
リスト１．正規ツリーパターン構文
【００４４】
正規ツリーパターンの定義では、ネスト演算子（以下で説明する）の文脈内での再帰的なパターン参照を可能にするだけである。正規ツリー文法に対するそのような制約を採用して、正規ツリーの文法が文脈自由文字列文法の最大限の力を引き出すことが無いようにする。
【００４５】
Ｒｅｐｅｔｉｔｉｏｎ（繰り返し）の構造「＊｜＋｜？」は、この構造が修飾するＴｒｅｅに対して許可される最小発生回数および最大発生回数を表す。最大発生回数は、無限とすることができる。演算子「＊」「＋」および「？」は、それぞれ［０．．∞］、［ｌ．．∞］および［０．．１］と解釈される。換言すると、「Ａ*」は０個以上のＡ（すなわち、［０．．∞］）、「Ｂ＋」は１つまたは複数個のＢ（すなわち、［ｌ．．∞］）、「Ｃ？」は、０個または１個のＣ（すなわち，［０．．１］）、を意味する。この構造は、ランク付けされないツリーノードを特定するパターンをサポートする。ランク付けされないツリーノードは、任意の数の子を持つことができる。
【００４６】
任意のワイルドカードは任意の値をマッチングする。¬演算子は、ツリーパターンを補間する。∧演算子は、１対のツリーパターンの共通集合を表す。｜演算子は、１対のツリーパターンの和集合を表す。最後に、λＰ．ｂ演算子は、ボディｂおよびパターン引数Ｐを持つポリモーフィック（多型）パターンを表す。
【００４７】
ネスト演算子Ｌ［Ｆｏｒｅｓｔ？］は、ラベルＬの順序付きのランク付けされないツリーノードを定義する。そのような順序付きの項目はまた、シーケンスとも呼ばれる。ネスト演算子Ｌ｛Ｆｏｒｅｓｔ？｝は、ラベルＬの非順序付きのランク付けされないツリーノードを定義する。非順序付きの項目は、集合（またはマルチ集合）とも呼ばれる。我々は、用語マルチ集合パターンを使用して、Ｌ｛ｃ｝の形式のパターンを参照するが、これはｃが０個以上のツリーノードのマルチ集合をマッチングするからである。我々は、用語半順序ツリーパターンを使用して、順序サブツリーおよび非順序サブツリーの両方を特定することができるツリーパターンを参照する。
【００４８】
半順序ツリーパターンにより、厳密な順序ツリーパターンまたは非順序ツリーパターンを使用して表現することが冗長または不可能な考えを、プログラマが正確に表現することを可能にする。例えば、リスト２で定義される変換規則を含む処理モデル検査アプリケーションを以下に記載する。
ｐａｒ｛ｓｅｎｄｅｒ：ｃｈｏｉｃｅ｛ｓｅｑ［ｓｅｎｄ［ｘ：ａｎｙ］，ＣＳ：ａｎｙ］，ａｎｙ*｝，
ｒｅｃｅｉｖｅｒ：ｃｈｏｉｃｅ｛ｓｅｑ［ｒｅｃｖ［ｘ：ａｎｙ］，ＣＲ：ａｎｙ］，ａｎｙ*｝，
ｐｒｏｃｓ：ａｎｙ*｝
＝＝＞
ｐａｒ｛ＣＳ，ＣＲ，ｐｒｏｃｓ
リスト２ 処理相互作用規則
ラベルｐａｒのマルチ集合パターンは、並行して実行される処理のコレクションをモデル化する。ｃｈｏｉｃｅでラベル付けされる各ノードは、選択肢の集合の中から選択することにより継続される処理をモデル化する。Ｓｅｑでラベル付けされる各ノードは、処理のシーケンスを示す。最後に、ｓｅｎｄ［ｘ］およびｒｅｃｅｉｖｅ［ｘ］は、タイプｘのメッセージを送信および受信することに対応する。
【００４９】
規則は、対になった処理（パターンにおける変数の送信側と受信側に結び付けられる）の間の相互作用をモデル化する。送信側の処理では、タイプｘのメッセージを送信し、受信側の処理では、このメッセージを受信する。相互作用の後、並行処理のコレクションには、送信側（ＣＳ）の継続、受信側（ＣＲ）の継続、およびこの相互作用に加わらない処理のコレクション（ｐｒｏｃｓ）、が含まれる。
【００５０】
並行処理の集合内には、相互作用のパターンとマッチすると、複数の対の潜在的に相互作用する処理、および、従って複数の可能性のある成果が存在する場合がある。以下に記載するＭＦＡの機構を使用して、１つまたは複数のこれらの成果を生成することができる。
【００５１】
マルチ集合パターンは、簡潔さ以上のものを提供する。これらはまた、実装および特定の実施形態において、入力コレクションの本質的には非順序の表現が使用されることを可能にする。探索ツリーまたはハッシュテーブル等の非順序の表現を直接使用することで、変換エンジンに入力コレクションに対して別のインデックスを形成させないようにすることができる。
【００５２】
例えば、アクセス要求が権限付与のポリシーを満たすことを、要求をアサーションのデータベースおよび規則の集合に対してマッチングすることによりチェックする、以下に記載する権限付与ロジックの実装が、評価される。権限付与のポリシーのアプリケーションは、アサーションデータベースの非順序の表現に対して直接働くマルチ集合パターンを使用することができる。
【００５３】
マルチ集合パターンおよびポリモーフィズム（多態性）が、正規ツリーの文法から削除されると、正規ツリー型システムは、理解されるように、ＸＭＬツリー変換の関数型プログラミング言語と同様のところにたどり着く。そのようなシステムを採用して、ネストされた正規の表現上のサブタイプ関係を決定するためのアルゴリズムを生成することができる。そのようなアルゴリズムでは、トップダウンのアプローチを使用して、パターンの表現を比較する。アルゴリズムは、正規ツリー表現に関する以前の理論的研究から発展し、それを拡大させる。このプロジェクトでは、最初はボトムアップツリーオートマトンの決定化を使用して包含物を決定したが、これは拡大可能なアプローチではないことが分かった、と報告されている。ボトムアップツリーオートマトンの決定化アルゴリズムは、サブセットの構成を適用する際に左の文脈を考慮に入れない。これは、指数関数的な爆発が、文脈に注意することよりもはるかに一般的なものになる原因となる。どのようにモジュラフォレストオートマトンが左の文脈を使用してそのような落とし穴を回避し、一方で決定化およびサブタイプ化に直接アプローチする簡略性を維持するのか、を以下に示す。
【００５４】
別の実施形態では、上述のシステムを、ポリモーフィズム、関数型、およびレコードで拡大させる。レコードは、一意性制約をラベル全体に要求する。以下に記載するＭＦＡの実装では、パターン変数全体への等式制約に加えて、一意性制約をサポートする。
【００５５】
理解されるように、アンビエント計算演算子ｎ［］、は、正規ツリーパターンの演算子Ｌａｂｅｌ｛Ｆｏｒｅｓｔ？｝に強力に対応する。アンビエント計算の並行合成演算子を、１対のツリーをその根で連結されるツリー合成演算子として解釈できることが実証される。アンビエント論理を、ツリー構造を記述しクエリするための基本として使用できることが提案される。アンビエント論理は、処理に関して推論するための一時的な空間論理である。リスト１の正規ツリーの文法とは異なり、アンビエント論理は非順序のネストのみを考慮する。アンビエント論理では、サブタイプ関係の決定は、含意を決定することと同意義である。これは、この理論の変形に対しても当てはまる。
【００５６】
ＸＭＬスキーマ言語
成功裏にインポートされ、かつ、Ｗ３ＣＸＭＬスキーマ言語のインスタンスに対するサブタイプ関係を決定する、モジュラフォレストオートマトン（ＭＦＡ）の実装が、本明細書において記載される。ＸＳＤ複合型は、構造式に対して名称を割り当てる。ＸＳＤにおける構造式は、コンテントモデルと呼ばれる。コンテントモデルは、要素宣言、属性一覧と呼ばれる非順序ネストパターン、および、パーティクルコンポジタを含む。ａｌｌ、ｃｈｏｉｃｅ、およびｓｅｑｕｅｎｃｅの３つのコンポジタがある。正規ツリー文法の和集合および連結のコンストラクタは、選択およびシーケンスのコンポジタにそれぞれ対応する。
【００５７】
ａｌｌコンポジタは、本明細書において記載する非順序のネスト演算子に対応する。ＸＳＤは、ａｌｌコンポジタの使用について何らかの制約を与える。例えば、ＸＳＤではａｌｌコンポジタ内の項目は多様性が限定されることを要求する。
【００５８】
ＸＭＬの要素の宣言は、要素ｑｎａｍｅの役割を担う演算子名Ｌａｂｅｌを用い、正規ツリーの文法の順序ツリー構造Ｌａｂｅｌ［Ｆｏｒｅｓｔ？］と同一構造である。しかし、ＸＭＬスキーマ言語は、２つのコンテントパーティクルａおよびｂの任意の和集合に対して、単一の先行読み取りの一意のパーティクル属性の実行、すわなち、トークンを１つだけ読むこと、をパーサが可能でなければならないことと、インスタンスがｃｈｏｉｃｅの枝ａまたはｂに対応するかどうかをパーサが識別可能でなければならないこととを要求する。
【００５９】
モジュラフォレストオートマトン
半順序正規ツリーパターンについては上記に記載した。
モジュラフォレストオートマトン（ＭＦＡ）は、シーケンスおよび集合の順序正規ツリーパターンおよび非順序正規ツリーパターンを統一して処理する機構を提供する。そのような順序正規ツリーパターンおよび非順序正規ツリーパターンは、シーケンスおよび集合と呼ばれることがある。各ＭＦＡは、ＭＦＡ階層の分析および合成をサポートする規約を実装する。規約により、ＭＦＡは、本明細書において検討したように、決定化の間に左の文脈を活用することができる。ＭＦＡにおける左の文脈の使用により、ボトムアップツリーオートマトンの決定化のための特定の以前の方法に見られた、可能性のある状態の爆発が回避できる。
【００６０】
モジュラフォレストオートマトン（ＭＦＡ）は、可視プッシュダウンオートマトン（ＶＰＡ）である。可視プッシュダウンオートマトンは、当業者には既知であるようなプッシュダウンオートマトンの１クラスである。ＭＦＡに対して、プッシュダウンオートマトンは１タプルとして定義される。
【００６１】
Ｍ＝（Ｋ，Σ，Γ，Δ，ｓ，Ｆ）、ここで
Ｋは状態の有限集合、
Σは、アルファベット（入力記号）、
Γは、アルファベット（スタック記号）、
ｓ∈Ｋは、初期状態、
Ｆ⊆Ｋは、最終状態の集合、
【００６２】
Δは、遷移関係であり、（Ｋ×Σ*×Γ*）×（Ｋ×Γ*）の有限のサブセットである。
遷移関係は、３種類のもの（カレント状態、入力記号、ポップされるスタック記号）を対（新しい状態、プッシュされるスタック記号）にマップする。
【００６３】
分析をサポートするには、ＭＦＡでは、可視プッシュダウン言語（ＶＰＬ）のスタック使用の制約を採用する。このクラスの言語は、その遷移関係をリスト３の３つのプッシュダウン遷移カテゴリの１つに従うように制約するプッシュダウンオートマトンを使用して定義される。
Ｌｏｃａｌ（ｑ0，ａ∈Σ1，ε）→（ｑ1，ε）
Ｃａｌｌ（ｃａｌｌＳｉｔｅ，ａ∈ΣC，ε）−＞（ｃａｌｌＴａｒｇｅｔ，ｃａｌｌＳｉｔｅ）
Ｒｅｔｕｒｎ（ｒｅｔｕｒｎＳｉｔｅ，ａ∈Σr，ｃａｌｌＳｉｔｅ）→（ｃｏｎｔｉｎｕａｔｉｏｎ，ε）
リスト３ ＭＦＡ遷移カテゴリ
これらのカテゴリは、Σを、ｃａｌｌ（コール）、ｒｅｔｕｒｎ（リターン）、およびｌｏｃａｌ（ローカル）、の遷移を生じさせることが可能な記号にそれぞれ対応する３つの互いに素な集合、ΣC、Σr、Σ1、に分割する。ローカル遷移は、正規有限オートマトンにおける遷移と同一である。ＭＦＡであるＭ0における状態ｑ0からのコール遷移は、記号ａを読み込み、ｃａｌｌＳｉｔｅをスタックにセーブし、状態ｃａｌｌＴａｒｇｅｔに制御を渡す。リターン遷移は、スタックからｃａｌｌＳｉｔｅをポップさせ、カレント状態をｃｏｎｔｉｎｕａｔｉｏｎ（継続）させる。
【００６４】
上述のスタック規則により、ＶＰＬを、プッシュダウンオートマトンの、クリーネスターとリネームする和集合および連接の閉包性に加えて、共通集合および補集合の下で閉じたままにすることができる。一般的な非決定性文脈自由言語とは異なり、非決定性ＶＰＬのクラスは、決定性ＶＰＬのクラスと等価である。
【００６５】
各ＭＦＡのＭは、コール対象の状態の集合Ｔを有する。Ｍの開始状態は、コール遷移で終了するパスによりｓから到達可能な任意の状態のように、Ｔ内にある。Ｍは、モジュールと呼ばれる状態の互いに素な集合の階層として見ることができる。Ｍは、各状態ｔ∈Ｔに対して１つのモジュールを持つ。コール対象の状態をｔとすると、対応するモジュールＭｏｄｕｌｅ（Ｔ）は、ローカル遷移のみを使用してｔから到達可能な状態の集合である。
【００６６】
１つのモジュールはただ１つのコール対象の状態ｔを含むことが要求される。コール対象の状態ｔは、モジュールのエントリポイントと呼ばれる。従って、ＭＦＡは、別のコール対象の状態からローカル遷移により到達可能な対象の状態を有するコール遷移を含むことができない。ＭＦＡの開始状態を含むモジュールは、ＭＦＡのトップレベルモジュールと呼ばれる。スタック規則を維持するために、ＭＦＡでは、モジュール間ε遷移を許可しない。
【００６７】
有限の追加の記帳をＭＦＡに使用して、ＶＰＡのコール／リターン戦略を、非順序ネストパターンに適用して、順序ネストパターンおよび非順序ネストパターンの両方に適用可能な単一のサブタイプ化方法を得る。
【００６８】
各ＭＦＡの状態は、０個以上のパターンの同値類が状態により受容されることを示すビットベクトルでラベル付けされる。このラベルはタグと呼ばれる。各ＭＦＡには、マッピングＴａｇ：Ｋ→Ｂ（ここで、Ｂはｋビットの文字列）が含まれる。所与のモジュールＭに対して、ｋは一定であり、ｋはモジュールＭのタグ長と呼ばれる。Ｆにおける各最終状態ｆに対して、Ｔａｇ（ｆ）は少なくとも１つの非ゼロビットを含まなければならない。
【００６９】
タグの目的は、呼び出しから復帰した時に、呼び出しているＭＦＡをどのように継続させるかを導くことである。ＭＦＡにおいて、リターン遷移は、固定した対象の状態を持たない。その代わり、ＭＦＡの状態ｓからのリターン遷移は、コール状態をスタックからポップさせ、スタックＴａｇ（ｓ）にプッシュし、カレント状態をコール状態に変更する。そして、コール状態は、タグをスタックからポップさせ、かつ、制御を継続状態に渡す、継続遷移を実行する。
【００７０】
ＭＦＡ機構に継続遷移を追加することは、ＭＦＡの基本のプロパティを変更することではない。なぜなら、継続遷移を持つＭＦＡの継続遷移を除去することができるからである。継続遷移を持つＭＦＡの継続遷移を除去することは、以下のように行う。まず、Ｍｏｄｕｌｅ（ｔ）における状態の、コール対象の状態ｔを有する各コールサイトｃに対するコピーを作る。このコピーは対象モジュールと呼ばれる。次に、対象モジュールにおける各リターン遷移（ｒ；α∈Σr，ｃ）→（ｃ，ｔａｇ）に対して、対応する継続遷移（ｃ，ε，ｔａｇ）→（ｃｏｎｔｉｎｕａｔｉｏｎ；ε）をコールモジュールにおいて求め、両方の遷移を削除する。最後に、リターン遷移（ｒ；α∈Σr；ｃ）→（ｃｏｎｔｉｎｕａｔｉｏｎ；ε）を対象モジュールに追加する。上述したように継続遷移の削除が可能であるため、ＭＦＡが継続遷移を持つことが推測される。
【００７１】
また、ＭＦＡが、フォレストの入力スタックと呼ばれるスタック対するアクセスを有する、と推測することができる。ＭＦＡの実行は、入力スタックが元の入力フォレストを含むＭＦＡの開始状態で始まる。ＭＦＡには、カレントツリーの概念が含まれる。カレントツリーは、入力スタックのトップにあるフォレスト内の何かのツリーである。これらの構想を使用して、ＭＦＡの特定の実装にマップすることができる。コールは、カレントツリーの子を入力スタックにプッシュする。リターンは子をスタックからポップさせる。
【００７２】
モジュールＭのローカル遷移のみを考慮すると、Ｍは、フォレストのコンテンツを認識する正規文字列オートマトンである。理解されるように、これを使用してプッシュダウンフォレストオートマトン（ＰＦＡ）のクラスを定義することができる。プッシュダウンフォレストオートマトンは、フォレスト状態ＱFおよびツリー状態ＱTという２つの状態の集合を持つ。プッシュダウンフォレストオートマトンは、フォレスト状態の互いに素な集合に連結するＥｎｔｒｙ（入場）遷移およびＥｘｉｔ（退場）遷移を持つ。プッシュダウンフォレストオートマトンはまた、退場遷移からの情報を組み込み、かつ、制御をツリー状態からフォレスト状態に渡す、遷移関係Ｃｏｍｂを有する。
【００７３】
タグがＭＦＡから削除されると、ＰＦＡはＭＦＡと同一構造となる。所与のＰＦＡであるＰを、等価のＭＦＡであるＭPに以下のように変換することができる。Ｐの各フォレスト状態に対して、Ｍpにおける状態を作成する。Ｐにおける各ツリー状態に対して、Ｍpにおける状態を作成する。Ｐの入場遷移、退場遷移、その組み合わせの遷移、およびローカル遷移を直接ＭPにコピーする。これらは、コール遷移、リターン遷移、継続遷移、ローカル遷移にそれぞれ対応する。各コール状態ｃをフォレスト状態とツリー状態ｔとに分割すること、かつ、初期状態がｔである継続遷移となるべき継続遷移を適合させることにより、タグの無いＭＦＡを、等価のＰＦＡに変換することができる。
【００７４】
プリプロセッサＰｒｅｐ（ｓ）を、任意のＭＦＡの状態ｓと関連付けることができる。Ｐｒｅｐ（ｓ）は、有効なＭＦＡに対してまたは⊥に対して設定されなければならない。所与のモジュール内では、全ての状態が同じプリプロセッサ値を共有しなければならない。状態が⊥以外のプリプロセッサを有するモジュールは、プリプロセシングモジュールと呼ばれる。入力フォレストをｉとすると、プリプロセシングモジュールは、ｉの各エレメントに対してそのエレメントを処理する前にプリプロセッサを呼び出す。プリプロセッサを使用して、入力の同値類間を区別する。プリプロセッサを再帰的に呼び出すことはできない。特に、プリプロセシングモジュールｐｒｅｐの状態には、Ｐｒｅｐ（ｔ）＝ｐｒｅｐであるような対象状態ｔを有する遷移を含むパスを初期化できるものはない。プリプロセッサを使用して、マルチ集合パターンをマッチンング可能なＭＦＡを構成することができる。
【００７５】
プリプロセシングモジュールを追加することは、ＭＦＡの基本のプロパティを変更することではない。プリプロセシングモジュールは、その各入力ｉをΨ［ｉ］（ここでΨは予約ラベル）に変換することにより動作するものと考えることができる。そして、プリプロセッシングのステップは、Ψでラベル付けされるネストに対してコール遷移として符号化することができる。
【００７６】
また、セマンティックアクションＡｃｔｉｏｎ（ｔｒ）を、任意のローカルＭＦＡ遷移ｔｒに追加することができる。このようにして拡張される遷移は、アクション遷移と呼ばれる。１つまたは複数のアクション遷移を持つＭＦＡは、モジュラフォレストトランスデューサ（ＭＦＴ）と呼ばれる。セマンティックアクションの順序付けは、ＭＦＴ決定化の間、保持される。
【００７７】
ＭＦＡへのツリーパターンの翻訳
半順序正規ツリーパターンは、ＭＦＡに変換することができる。共通集合および補集合の方法には、決定化ステップが含まれるため、非決定性ＭＦＡ（ＮＭＦＡ）の決定化のための方法の詳細を最初に提供する。
【００７８】
ツリーパターンからＮＭＦＡを形成するための構築プロシージャは、他の既知の構築プロシージャとは異なる。第１に、ツリーパターンには、ネスト演算子が含まれる。第２に、ツリーパターンは、アクションおよび変数束縛を含むことができる。特定の実装におけるパターンコンパイラは、変数束縛をアクションに翻訳することができる。従って、変数束縛は特には扱わない。
【００７９】
ＭＦＡへの入力は、ツリー値の適格なフォレストとすることができる。適格な入力フォレストは、フォレスト終了の記号「］」で終了する。翻訳プロシージャは、あらゆる生成されたＭＦＡ状態ｓに対して、にリターン遷移を追加する］。
【００８０】
２つのＮＭＦＡの和集合Ｍ2＝Ｍ0∪Ｍ1は、タグおよびプリプロセッサに調整を加えることにより拡張される既知の標準的な方法を使用して計算される。構築においては、Ｍ0が長さｋ0のタグを持ち、Ｍ1が長さｋ1のタグを持つことを前提とする。Ｍ2は、長さｋ0＋ｋ1のタグを持つこととなる。Ｍ2の状態ｓがＭ0の最終状態を有する時、ｋ1個のゼロでできた文字列がそのタグに加えられる。そうでなければ、ｓがＭ1の最終状態である時、そのタグは左にｋ0個分シフトされ、ゼロが書き込まれる。
【００８１】
プリプロセシングモジュールの組み合わせをサポートするには、和集合の構築を以下のように修正する。Ｍ2＝Ｍ0∪Ｍ1を計算する時、Ｍ0のトップレベルモジュールがプリプロセッサｐｒｅｐ0≠⊥を持ち、かつ、トップレベルモジュールＭ1がプリプロセッサｐｒｅｐ1≠⊥を持つ場合、Ｍ2のトップレベルモジュールの各状態にプリプロセッサｐｒｅｐ０∪ｐｒｅｐ1を割り当てる。
【００８２】
プリプロセシングモジュールと正規モジュールを組み合わせるには、プリプロセッサを、正規モジュールに対して合成する。ｐｒｅｐ0≠⊥かつｐｒｅｐ1＝⊥であると仮定する。Ｍlに対するプリプロセッサは、Ｍ1のローカル遷移のための遷移記号を認識するＭＦＡの集合の和集合に対して第１の設定ｐｒｅｐ1により合成される。次に、Ｍ1の遷移関係内の各コール遷移（ｃ，Ｌ，ε）→（ｃａｌｌＴａｒｇｅｔ，ｃ）に対して、ｐｒｅｐ1＝ｐｒｅｐ1∪Ｎを設定する（ここでＮは、開始状態がｃａｌｌＴａｒｇｅｔであるモジュールにより識別される子を持つＬでラベル付けされるツリーを認識するＭＦＡである）。
【００８３】
ネスト
ネスト演算子は、順序または非順序のどちらであっても翻訳される。ラベルＬおよびコンテンツｃのネスト演算子を仮定すると、まず、ｃに対してＭｃというＮＭＦＡを作成し、開始状態をｓｃとする。次に、ＭｎｅｓｔというＮＭＦＡを作成し、開始状態ｓ、最終状態ｆ、および、遷移が（ｓ，Ｌ，ε）→（ｓｃ，ｓ）（Ｍｃをコール）および（ｓ，ε，ｔａｇｃ）→（ｆ，ε）（コールから継続）とする。最後に、Ｍｃの状態をＭｎｅｓｔに組み込み、Ｍｃの各最終状態ｆｃをタグｔａｇｃに割り当て、ｆｃを、リターン遷移（ｆｃ，］，ｓ）→（ｓ；ｔａｇｃ）を持つ非最終状態に変更する。この構築において、Ｍｃの状態がＭｎｅｓｔのモジュールになる。
【００８４】
連接演算子を使用して、順序ネストのコンテンツを翻訳することができる。１対のＮＭＦＡをＭ0およびＭ1とすると、この方法では、Ｍ2に対して新しい開始状態を作成し、Ｍ0の各最終状態からＭ1の開始状態へのε遷移を作成することによりｓからＭ0の開始状態へのε遷移を作成し、最後にＭ2の最終状態としてＭ1の最終状態を採用することにより、Ｍ2＝Ｍ0，Ｍ1を構築する。
【００８５】
マルチ集合のネストされたコンテンツ
以下の戦略を使用して、非順序ネストのコンテンツを認識するＭＦＡを生成することができる。
【００８６】
一般に、マルチ集合パターンは、以下の形式を持つものと見なすことができる。
【００８７】
【数１】
【００８８】
この表記では、入力コレクションをマッチングするマルチ集合ネスト演算子の内容に対して、各パターンエレメントＰiが少なくともｌi個の入力エレメントとマッチしなければならず、また、多くともｈi個の入力エレメントとマッチすることができる、ということが指定される。
【００８９】
マルチ集合パターンは、最初に変換されて任意の発生の制約が取り除かれる。上述のように指定されるマルチ集合パターンをＰとすると、パターンコンパイラは、以下のようにＰを等価なマルチ集合パターンＰ’に変換することができる。
Ｐ内の各エレメントパターン
【００９０】
【数２】
【００９１】
に対して、
ａ）Ｐ’にｐiのｌ1個のコピーを追加する。
これらのコピーをＰ’の要求されるパターンエレメントとする。
ｂ）ｈiが有限ならば、ｐ１＊をＰ’に追加する。
追加されたパターンをＰ’の非束縛パターンエレメントとする。
そうでなければ、ｐi？のｈi−ｌi個のコピーをＰ’に追加する。
これらのコピーをＰ’の選択的パターンエレメントとする。
リスト４ 変換マルチ集合パターン
パターンコンパイラは次に、パターンエレメント∪iｐiの和集合をマッチングするエレメントＭＦＡと呼ばれるプリプロセシングＭＦＡを構築する。第３に、パターンコンパイラは、置換ＭＦＡを構築する。置換ＭＦＡは、その入力上にプリプロセッサとしてエレメントＭＦＡを呼び出す。各呼び出しにおいて、エレメントＭＦＡは、どのｐiがカレント入力とマッチするかを示すタグを戻す。置換ＭＦＡは、要求されるパターンまたは選択的パターンとマッチする入力に遭遇すると、状態を変更する。状態変更は、要求されるパターンまたは選択的パターンをカウントする。置換ＭＦＡは、非束縛パターンに遭遇すると、カレント状態にループバックする。
【００９２】
置換ＭＦＡが、カウントオートマトンの形式であることは認識されるであろう。置換ＭＦＡは、そのプリプロセッサステップでの使用における他のカウントオートマトンとは異なる。図２は、置換ＭＦＡが入力をどのようにカウントするかを例示する。図２に例示されるＭＦＡ２００は、以下のパターンのネストされたコンテンツをマッチングする。
Ｐｏｎｄ＝Ｐｏｎｄ｛ｗａｔｅｒ，ｆｒｏｇ＋，ｃａｎｏｅ*，ｂｒｉｄｇｅ？｝
【００９３】
Ｒｅｐｅｔｉｔｉｏｎ（繰り返し）、Ｒｅｆｅｒｅｎｃｅ（参照）、Ｔｙｐｅ Ｐａｒａｍｅｔｅｒ（型引数）
リスト１の繰り返し構造を翻訳するには、パターンコンパイラでは、周知の技術を使用する。この構造を拡張して、繰り返されるパターンをマッチングして入力項目を蓄積する変数束縛を実装することができる。
【００９４】
記号参照を翻訳するには、パターンコンパイラが、記号のいくつかのクラス間を区別しなければならない。基本型すなわちリテラル記号ｓｙｍは、ｓｙｍに対する単一のローカル遷移として翻訳される。型引数ｐａｒａｍへの参照は、ｐａｒａｍに対する形式的遷移として翻訳される。形式的遷移は実行することができない。コンパイラは、形式的遷移を含むパラメータ化されたモジュールを生成することができるが、実行可能なモジュールを作成するためには、モジュールの形式的遷移に対して実際のパターンを与えることにより、パラメータ化されたモジュールをインスタンス化しなければならない。インスタンス化の間、コンパイラは、各形式的遷移の代わりに、対応する実際のパターンの翻訳を用いる。
【００９５】
パターンコンパイラは、パターンＰへの参照を、Ｐを参照した文脈に、Ｐを翻訳して変換することで代用して、翻訳する。知られているように、正規ツリーの文法は、ｎｅｘｔ演算子の文脈の外への再帰的な参照を許可しない。パターンコンパイラは、このプロパティと、ネストがコールとしてコンパイルされるという不変条件と、を組み合わせて、全てのインライン展開が、ネスト演算子またはパターン参照を含まないパターン等の基本事例に到達することを確実にすることができる。
【００９６】
例えば、図３は、以下の再帰的パターンに対する翻訳を例示する。
Ｅｘｐｒ＝ｃ｜ｐｌｕｓ［Ｅｘｐｒ，Ｅｘｐｒ］
図３では、各ノードがそのタグでラベル付けされる。図３には２つのモジュールが含まれ、それぞれ、３００および３１０で示され、Ｅｘｐｒ３００およびＰｌｕｓＮｅｓｔ３１０と名付けられる。Ｅｘｐｒ３００は、和集合をマッチングするためタグ長２を持つ。ＰｌｕｓＮｅｓｔ３１０はタグ長１を持つ。モジュールＥｘｐｒ３００は、ＭＦＡの開始状態を含み、ｃをマッチングすることにより、または、ＰｌｕｓＮｅｓｔ３１０を呼び出して、ＰｌｕｓＮｅｓｔからタグ１が復帰した時に、１０がタグ付けされた最終状態に継続することにより、Ｅｘｐｒパターンをマッチングする。ＰｌｕｓＮｅｓｔ３１０は、パターンＥｘｐｒの２つのインラインインスタンスを連接させることにより、パターンフラグメント［Ｅｘｐｒ，Ｅｘｐｒ］をマッチングする。Ｅｘｐｒのこれらのインライン展開は、ＰｌｕｓＮｅｓｔへの再帰的呼び出しを生み出す。非最終状態へつながるリターン遷移またはパスは示さない。
【００９７】
【００９８】
リスト６は、ＭＦＡを決定化するための構造を提供する。決定化を簡素化するために、コール遷移
（ｃ，Ｌａｂｅｌ，ε）→（ｃａｌｌＴａｒｇｅｔ，ｃ）
と、その関連する継続遷移
（ｃ，ε，ｔａｇ）→（ｃｏｎｔ，ε）
と、をネスト遷移と呼ばれるモジュール内遷移
（ｃ，（Ｌａｂｅｌ，ｃａｌｌＴａｒｇｅｔ，ｔａｇ），ε）→（ｃｏｎｔ，ε）
として組み合わせて表す。
この表現により、決定化メソッドでは遷移を均一に処理できるが、これはローカル遷移およびネスト遷移の両方がモジュール内遷移であるからである。リスト６の決定化メソッドにおける使用のために、関数Ｌａｂｅｌｓ（ｓ）が導入され、これにより、ｓから生じるネスト遷移において使用されるラベルの集合が生み出される。
【００９９】
トップレベルモジュールをＭとすると、決定化メソッドでは、以下の２つのステップを、ＮＦＡの決定化のためのクラスメソッドに追加する。第１に、ステップ２．ｃでは、ＣｏｍｂｉｎｅＮｅｓｔｓメソッドを使用して、状態ｔからのネスト遷移のコール対象を組み合わせる。第２に、ステップ４では、決定されたＭＦＡの最終状態Ｆ’の集合における各最終状態に対するタグを更新する。所与の最終状態ｆ’に対して、ステップ４では、ｆ’の要素であるＮＭＦＡの状態のタグ全体に亘って、ｆ’に対するタグをビットワイズ論理和に設定する。
【０１００】
決定化メソッドでは、サブルーチンとしてε閉包演算子Ｅ（ｓ）を使用する。状態をｓとすると、Ｅ（ｓ）は、ε遷移のみを含むパスによりｓから到達可能な状態の集合である。明確にするために、リスト６では、ワイルドカード遷移の扱いに関する詳細は省略する。状態ｔから生じるワイルドカード遷移を実装するために、ワイルドカード遷移に対するｍｏｖｅｓｅｔを、ｔから生じる各非ワイルドカード遷移のｍｏｖｅｓｅｔと組み合わせる。
【０１０１】
サブタイプ化
決定化の間、追加の記帳に労力を使ってタグを追跡するため、追加の記帳の利点が、１対のＭＦＡであるＭ0およびＭ1の比較において得られる。ＭＦＡを比較するためのプロシージャをリスト７に与える。
０．１対のＭＦＡをＭ0およびＭ1とし、Ｍ0およびＭ1により認識される値の集合間の包含関係を決定する。
１．Ｍ0またはＭ1の各状態ｑに対して、
Ｔａｇ（ｑ）≠０ならば、Ｔａｇ（ｑ）＝１を設定；
そうでなければ、Ｔａｇ（ｑ）＝０を設定；
２．Ｍ2＝Ｍ0∪Ｍ1を設定する。
（例えば、和集合の構造では、Ｍ0の最終状態にタグ０１を割り当て、Ｍ1の最終状態にタグ１０を割り当てる）
３．Ｄｅｔｅｒｍｉｎｉｚｅ（Ｍ２）の最終状態にある異なるタグの集合にＣを設定する。
表１のＣの値を調べることによりＭ０とＭ１との関係を求める。
リスト７ ＭＦＡ比較アルゴリズム
【０１０２】
重要な目的は、決定化プロシージャが、最終状態にあるタグを介して、Ｍ0およびＭ1が同時にアクセスされるのか、および、Ｍ0またはＭ1または両方がお互いに無関係にアクセスされるのか、について追跡することである。表１ｘｘｘｘを使用して、比較の結果に対して、Ｍ0およびＭ1の決定化された和集合における最終状態に存在するタグ値の集合Ｃをマップすることができる。図５は、表１に列挙される可能性のあるサブタイプ関係の図式的な例示である。
【０１０３】
【表１】
【０１０４】
図５は、等価５００関係、サブタイプ５１０関係、スーパータイプ５２０関係、互いに素５３０関係、および交わり５４０関係、のそれぞれを示す。
補集合、共通集合、差
追加の利点が、上述したタグの記帳から得られる。タグを使用して、ＭＦＡの補集合、共通集合、および差のためのプロシージャを実装することができる。共通集合Ｍ0∧Ｍ1を構成するために、共通集合構造はまず、決定化された和集合Ｉ＝Ｄｅｔｅｒｍｉｎｉｚｅ（Ｍ0∪Ｍ1）を計算し、次に、タグ１１を持つ最終状態が到達可能できない各状態ｔをＩから除去する。
【０１０５】
この計算の結果、ＭＦＡである、状態を持たないＩが得られた場合は、単一の非アクセス開始状態がＩに加えられ、Ｉは入力にアクセスしないＭＦＡとなる。
【０１０６】
同様の構造を使用して、Ｍ0−Ｍ1を計算することができる。そのようにするには、上記の交わりの構造においてタグ１１の代わりにタグ０１を用いる。Ｍ1−Ｍ0を計算するために、構造内にタグ１０を使用する。
【０１０７】
¬Ｍ、すなわちＭの補集合、を構築するには、補集合構造はまず、Ｍ’＝Ｄｅｔｅｒｍｉｎｉｚｅ（Ｍ）を計算する。次に、Ｍ’の各最終状態ｆに対して、構造は、ｆのタグを０に設定し、ｆを非最終とする。元のＭ’の各非最終状態ｎｆに対して、構造は、ｎｆのタグを１に設定し、ｎｆを最終とする。タグが調節されたＭ’は¬Ｍを受容する。
【０１０８】
この構造の重要な態様は、呼び出されたモジュールにより戻されたゼロのタグに対する遷移が最終状態につながるということである。ゼロのタグに対して暗黙的遷移を使用することにより空間を確保するＭＦＡの実装では、これらの遷移を補集合に対する明示的遷移に変換する方法を持たなければならない。
セマンティックアクションの順序付け
特定の本発明の実施形態の利点により、パターンコンパイラが、セマンティックアクションを任意のＮＭＦＡの遷移に置くことが可能にされる。この柔軟性をサポートするために、決定化の間、セマンティックアクションの順序を保持するための方法が必要とされる。ＮＭＦＡであるＭの全てのパス［ｔｒ1，ｔｒ2，．．．，ｔｒn］に対して、ｉ＜ｊの時に限りＡｃｔｉｏｎ（ｔｒi）はＡｃｔｉｏｎ（ｔｒj）の前に実行される、というプロパティを保持することは有益である。このプロパティを保持するために、ＭのパスがＤｅｔｅｒｍｉｎｉｚｅ（Ｍ）の遷移と関連付けられる。
【０１０９】
これを達成するために、決定性ＭＦＡの基本パス
Ｍ’＝Ｄｅｔｅｒｍｉｎｉｚｅ（Ｍ）
が、ローカル遷移またはネスト遷移のシーケンス［ｔｒ1，ｔｒ2，．．．，ｔｒn］として定義され、各遷移ｔｒi＝（ｑi，ｓｙｍ，ε）→（ｑi+1，ε）に対して、ｑi+1が入力遷移を１つだけ持つ、ｉ＝０、またはｉ＋１＝ｎ、のいずれかであるとする。この定義の目的のため、Ｍ’の開始状態は、暗黙的入力遷移を持つと考える。
【０１１０】
Ｍ’の基本パスは、複数の入力遷移を持つ状態で開始および終了することができる。しかし、基本パス中の任意の中間状態は、厳密に１つの遷移のみを持たなければならない。このプロパティから導かれる結果は、基本パスの最終遷移ｔｒnが一意的にこの基本パスを識別するということである。
【０１１１】
この結果は、各基本パスｂｐの最終遷移ｔｒnに、ｂｐに対応するＮＭＦＡのパスの集合ｎｐから順番に集められるセマンティックアクションのシーケンスの集合Ａを割り当てることにより、使用される。ＭＦＴは、ｂｐの遷移ｔｒnを実行する時に、Ａの各要素をも実行する。
【０１１２】
Ｍ’の所与の基本パスｂｐに対して、Ｍからの対応するパスｎｐの集合が、以下の方法で求められる。まず、ｂｐ内の各遷移ｔｒiに対して、ｔｒiに対応するＮＭＦＡの遷移を求める。ＮＭＦＡの遷移
ｎｔｒ＝（ｒ1，ｓｙｍ，ε）→（ｒ2，ε）
は、ｒ1∈ｑiかつｒ2∈ｑi+1である限り、ｔｒiに対応する。
【０１１３】
ｔｒiに対応する各ＮＭＦＡの遷移に対して、ＮＭＦＡのパスは、ｎｐａｔｈi＝ｐａｔｈa，ｎｔｒ，ｐａｔｈb（ここで、ｐａｔｈaは以下のプロパティを持つ）であるように構築される。第１に、ｐａｔｈaは全て、最初の状態と最後の状態がｑi内にあるε遷移から成る。第２に、ｐａｔｈaの第１の状態は、ｑi内に先行するものを持たない。最後に、ｐａｔｈaの最終的な状態は、遷移ｎｔｒの最初の状態である。同様に、ｐａｔｈbは全て、最初の状態と最後の状態がｑi+1内にあるε遷移から成り、ｐａｔｈbは、ｎｔｒの最後の状態で始まる。
【０１１４】
順に、ＮＭＦＡのパスは、ｂｐ内の何らかの遷移に対応する全てのサブパスを一続きにすることにより、基本パスｂｐに従って構築される。ｂｐの各遷移が、対応するＮＭＦＡの遷移を１つしか持たない場合、これらのサブパスは、単一のＮＭＦＡパスを形成するであろう。しかし、ｂｐのいくつかの遷移が、対応するＮＭＦＡの遷移を複数持つ場合、ｎｐａｔｈaの最終的な状態がｎｐａｔｈbの第１の状態となるＮＭＦＡのサブパスの対（ｎｐａｔｈa、ｎｐａｔｈb）を連結することにより、サブパスを組み合わせることができる。所与のＮＭＦＡのサブパスが、複数のそのような対に関与することができ、そのため、所与の基本パスに対応するいくつかのＮＭＦＡのパスは、共通のプレフィックスを共有することができる。
【０１１５】
図６および７は、パターン
ＧＴＥ＝ＧＴＥ［ａｎｙ，０］｜ＧＴＥ［０，Ｓ［ａｎｙ］］
のネストされたコンテンツに対する構造化されたＮＭＦＡ６００と、その決定された等価物７００との間の対応をそれぞれ示す。これらの図におけるＭＦＡには、表２で記載したように、シフトアクションおよび受容アクションが含まれる。図６では、記号ｅを使用してε遷移を表す。図７は、ＮＭＦＡのパスのそれぞれからのアクションシーケンス７００が、どのように集められ、かつ、決定されたＭＦＡの基本パスを終了させる遷移にどのように割り当てられたか、を例示する。これらの遷移はまた、それらに割り当てられたＮＭＦＡのパスでラベル付けされる。
【０１１６】
図７はまた、ワイルドカードａｎｙに対する翻訳の視点を与える。ＧＴＥに対して決定されたＭＦＡでは、ｏｔｈｅｒｗｉｓｅでラベル付けされる遷移を使用して、ワイルドカードを翻訳する。この翻訳はデフォルト翻訳と呼ばれ、他の翻訳が適用されない場合に実行される。状態ｓから開始されるワイルドカード遷移の対象状態ｔが、ｓからのデフォルト翻訳のｍｏｖｅｓｅｔに追加される。加えて、ｔが、ｓからの任意の非ワイルドカード遷移のｍｏｖｅｓｅｔに追加される。
【０１１７】
最後に、図７は、セマンティックアクションの順序付けを簡素化するリターン遷移を表すための技術を例示する。リターン遷移は、フォレスト終了（］）に対するローカル遷移として見ることができる。これらのローカル遷移は、セマンティックアクションのプレースホルダとなることができる。本明細書において記載するパターンコンパイラは、この技術を使用する。
【０１１８】
置換ＭＦＡの最適化
異なる入力順序を明らかにするため、置換ＭＦＡは、多数の遷移を持つことができる。置換ＭＦＡにおける遷移の数を減らすためには、パターンコンパイラは、タグオーダと呼ばれる半順序を、エレメントＭＦＡに対応するタグに割り当てることができる。コンパイラは次に、置換ＭＦＡから適切でないパスを削除することができ、ランタイムシステムが次の２つの戦略の内の１つを使用して入力フォレストをマッチングすることを予測する。第１の戦略として、ランタイムシステムは、入力コレクション全体にインデックスを使用して、要求されるパターンエレメントとマッチするであろう項目を抽出することができる。第２の戦略として、ランタイムシステムは、エレメントＭＦＡを使用して、入力フォレストを前処理することができ、そして、その結果をエレメントＭＦＡのタグオーダに従ってソートすることができる。
【０１１９】
第１の戦略は、パターンエレメントの１つがワイルドカードａｎｙ＊である場合に良く機能する。このシナリオにおいて、ランタイムシステムは、インデックスを使用してタグオーダで、要求されるパターンエレメントを「チェリーピック（良いものだけを選択）」し、残りの入力フォレストの項目をワイルドカードパターンエレメントに割り当てることができる。
【０１２０】
第２の戦略では、減少したメモリの使用と、ソートのために潜在的に増加するマッチングの時間とを交換する。置換ＭＦＡは、ラベル付き有向グラフの変換に使用すると、典型的には、入力フォレストのかなりの部分を変数に対して束縛することができる。さらに、マルチ集合パターンのユーザにおいては、マッチング操作から変数束縛の複数の集合が明らかにされることを期待することができる。これらのシナリオにおいて、ランタイムシステムは、入力フォレストのコピーを保持しなければならず、従ってソートをサポートすることになる。
【０１２１】
パターンエレメントの集合をＰとすると、対応するプリプロセッサＭＦＡのタグの全順序は、以下のように導き出すことができる。まず、パターンエレメントを順序付ける。Ｐにおける１対のパターンエレメントを（ｐi，ｐj）とすると、ｐiが要求されかつｐjが要求されない場合、または、ｐiが選択肢でありかつｐjが非束縛である場合、または、ｐiがｐjより高い優先度を持つ場合に、ｐi＜ｐjを定義する。優先度が割り当てられていない場合、優先度を辞書順に割り当て、パターンエレメント間に全順序をつける。
【０１２２】
決定化の際、プリプロセッサＭＦＡは、１つまたは複数のパターンエレメントの集合の受容を示すタグを持つ。そのような１対のタグを（ｔi、ｔj）とすると、ｍｉｎ（ｔi）＜ｍｉｎ（ｔj）ならば、ｔi＜ｔjである。ｔiおよびｔjが同じ最小エレメントを持つ場合、｜ｔi｜＞｜ｔj｜ならばｔi＜ｔjである。この最後の規則は、置換 ＭＦＡにより、いくつかのパターンエレメントとマッチする最初の入力が考慮されることを確実にする。図４は、Ｐｏｎｄパターン
Ｐｏｎｄ＝Ｐｏｎｄ｛ｗａｔｅｒ，ｆｒｏｇ＋，ｃａｎｏｅ*，ｂｒｉｄｇｅ？｝
に対するＭＦＡ４００ついてのタグオーダの最適化の効果を例示する。
【０１２３】
ＭＦＡの実装
ＭＦＡおよびＭＦＴの特定の実装において、トランスデューサと呼ばれるこれらのオートマトンのインスタンスを実装するランタイムシステムがある。別の実施形態において、パターンコンパイラは、正規ツリーパターンをトランスデューサに変換し、変数束縛と、条件のマッチングと、セマンティックアクションと、を実装する命令でトランスデューサの遷移を拡張する。特定の実施形態は、少なくとも４つの応用に適用することができる。すなわち、主張に基づく権限付与サービス、プロトコルモデル検査アプリケーション、ＸＭＬスキーマインスタンスをインポート、サブタイプ化、マッチングするためのシステム、およびクエリ表現のためのコンパイラ、である。
【０１２４】
特定の実施形態の実際の評価として、１秒当たり２４０万から８９０万ノードのレートでラベル付き有向グラフをマッチングするトランスデューサランタイムが得られた。さらに、このトランスデューサランタイムは、１秒当たり６０万から２１０万ノードのレートでラベル付き有向グラフを変換することができた。
ランタイム
【０１２５】
各変換規則
ｒｕｌｅ＝ｐａｔｔｅｒｎ，ａｃｔｉｏｎ
に対して、パターンコンパイラは、フレームテンプレートを作成する。フレームテンプレートは、規則で束縛される各変数のためのスロットを特定し、さらに、追加のスロットを特定してアクションを適用した結果を保持する。ランタイム時、トランスデューサ機構は、各規則ｒに対してフレームコレクションのスタックを割り当てることができる。各規則ｒに対するフレームコレクションは、ｆに対するフレームテンプレートにより記載される配置を持つ０個以上のフレームを含む。フレームコレクションは、複数のフレームを含むことができるが、それは、マルチ集合パターンが、その入力を複数の方法でマッチングすることができ、変数束縛の複数の集合を生み出すからである。フレームコレクションをスタックさせて、再帰を操作することができる。
トランスデューサの命令
【０１２６】
【表２】
【０１２７】
トランスデューサの状態遷移は、トランスデューサの命令のシーケンスであるアクションブロックを参照することができる。トランスデューサの命令の組には、表２に与えられる命令が含まれる。表２において、ｒでラベル付けされるオペランドは、文法規則を参照する。ｒ．ｘでラベル付けされるオペランドは、ｒの規則コレクションスタックの最上部にある規則フレーム内の変数ｘのスロットを参照する。ｉでラベル付けされるオペランドは、命令を参照する。ｔでラベル付けされるオペランドは、受容された規則の集合を示すタグを参照する。ｂでラベル付けされるオペランドは、アクションブロックの集合を参照する。
【０１２８】
明示的なオペランドに加えて、命令には、シフト型およびシフト規則を含むこともできる。シフト型は、変換エンジンがフォレスト内で次の項目にどのように移動すべきかを示す。シフト型がＳＨＩＦＴ ＮＥＳＴである場合、変換エンジンは、次のツリーノードに移る前にカレントツリーノードの後継ノードを書き換える。シフト規則は、（ネストパターンがマッチングしたものの中で）どの規則を書き換えるべきかを示す。
【０１２９】
表２の最初の４つの命令は、フレーム更新命令と呼ばれ、なぜなら、ある規則ｒについて、ｒのコレクションスタック上の各フレームに対して、変数ｒ．ｘのスロットを更新する。
【０１３０】
Ｅｘｅｃ命令は、ｒのコレクションスタックからトップのコレクションをポップさせる。ポップされたコレクションの各フレームに対して、Ｅｘｅｃ命令は、ｒに関連する書き換えアクションを実行する。それぞれの結果に対して、Ｅｘｅｃ命令は、ある変数ｔａｒｇｅｔ．ｘを更新するフレーム更新命令ｉを実行する。再帰の場合、ｔａｒｇｅｔはｒと同じ規則となる。
【０１３１】
Ｐｕｓｈ命令は、新しい規則コレクションをｒに対する規則コレクションスタックにプッシュする。Ｐａｒ命令は、アクションブロックの集合を並行して実行する。集合内の各アクションブロックに対して、Ｐａｒ命令は、カレント入力ノードを用いて開始される。集合内の各アクションブロックは、入力ポインタを同量進ませなければならない。変換エンジンは、並行するブロックの各要素を必ずしも実行するわけではない。各並行するブロックの要素は、規則識別子で示すことができる。トランスデューサは、トランスデューサが現在書き換えている規則用の識別子で示される、並行するブロックの要素のみを実行する。
【０１３２】
Ｓｈｉｆｔ命令は、トランスデューサを次の入力項目に進ませる。パターンコンパイラは、カレントパターン位置に関連する変数束縛が無い場合に、この命令を生成する。パターン位置が変数束縛を持つ場合は、コンパイラはその代わりに、シフト情報をフレーム更新命令の一部として与える。
【０１３３】
応用
特定の権限付与のポリシーエンジン（Ｔｈｏｒと呼ばれる）では、データアクセス要求の主張に基づく権限付与をサポートする権限付与ロジックを使用する。Ｔｈｏｒは、主張の大きなデータベースを備え、例えば、ａ／ｄｎｓ＝？ｘ−＞ｂ／ｄｎｓ＝？ｘ（これは、ａが、プロパティｄｎｓは変数ｘに対して束縛される値を持つ、と主張する場合、ｂが同じ主張を行う、ということを表す）という主張のような論理で表される。主張ａ／ｄｎｓ＝”ＬｏｃａｌＨｏｓｔ”は、ａが、プロパティｄｎｓに値”ＬｏｃａｌＨｏｓｔ”が割り当てられる、と主張することを示す。全てのそのような主張は、主張データベースにおいて非順序表として表され、主構とプロパティによりインデックスが付けられる。
【０１３４】
権限付与のポリシーエンジンは、構造的規約を使用してその主張データベースを非順序フォレストとして表す。主張を処理するためにまず、主張を、形式ｐｒｏｖｅ［ｃｏｎｔｅｘｔ｛ｄａｔａｂａｓｅ｝，ｇｏａｌ］のツリーに変換する。次に、エンジンは、規則の集合を使用して、定点に到達するまで主張を繰り返し変換する。エンジンが主張を証明することができる場合、主張は、証明においてステップを識別する証明木に変換される。
【０１３５】
パターンコンパイラは、エンジンの規則をトランスデューサに翻訳することができる。探索プロシージャは、このトランスデューサを呼び出して、各変換ステップを実行する。規則は、構成的論理の順次計算を実装し、デリゲーション演算子の分散規則で拡張される。この論理における典型的な規則は、以下のものである。
【０１３６】
ＩｍｐｌｉｅｓＣｏｎｄｉｔｉｏｎＭｅｔ＝
ｐｒｏｖｅ［
ｃｏｎｔｅｘｔ｛ｔｙｐｅｄＴｅｒｍ［ｐｒｏｏｆｌ：ａｎｄｙ，ａ：ａｎｙ］，
ｔｙｐｅｄＴｅｒｍ［ｐｒｏｏｆ２：ａｎｙ，ｉｍｐｌｉｅｓ［ａ：ａｎｙ，ｂ：ａｎｙ］］，
ｒｅｓｔ：ａｎｙ*｝，
ｇｏａｌ：ａｎｙ］
＝＝＞
ｐｒｏｖｅ［
ｃｏｎｔｅｘｔ｛ｒｅｓｔ，
ｔｙｐｅｄＴｅｒｍ［ｐｒｏｏｆｌ：ａｎｙ，ａ：ａｎｙ］，
ｔｙｐｅｄＴｅｒｍ［ａｐｐｌｙ［ｐｒｏｏｆ２：ａｎｙ，ｐｒｏｏｆｌ：ａｎｙ］，ｂ：ａｎｙ］｝，
ｇｏａｌ：ａｎｙ］；
【０１３７】
エンジンは、本明細書において上記に記載したインデックス付けおよびタグオーダソートを使用して、かなりのスループット（ある例では、１秒当たり２３，０００個の主張と計測された）を達成する。これにより、主張処理が、権限付与サービス全体の速度を制限する工程となってしまうことを防ぐという、可能性のある利点がもたらされる。
【０１３８】
別の応用は、処理モデルチェッカである。そのようなモデルチェッカは、シンプルな反転ビットプロトコルからＴＣＰ（通信制御プロトコル）のモデルにまで及ぶプロトコルに適用することができる。モデルチェッカは、デッドロックフリー型プロトコルを検査することができる。モデルチェッカは、多くの結果を産出する、リスト２の相互作用パターン等のパターンを使用する。そのような場合、トランスデューサは、数フレームに相当する変数束縛を、書き換えの度にバッファすることができる。
【０１３９】
別の実施形態は、ＸＭＬスキーマをインポート、認可、およびサブタイプ化する応用に適用される。この実施形態は、ＸＭＬスキーマを半順序ツリーパターンにインポートする。そのような応用では、バッチモードおよび相互作用モードの両方において機能する。相互作用モードにおいて、この応用を、パターンをコンピュータアプリケーションに組み込むためのオーサリングシステムの一部として採用することができる。
【０１４０】
さらに別の実施形態は、クエリ表現のためのコンパイラコンポーネントに適用された。そのようなコンポーネントは、ＳＱＬなどのようなデータベースのクエリアプリケーションのフロントエンドとして使用することができる。このコンポーネントは、規則の集合を使用して、クエリ表現Ｑを包括的な代数に翻訳し、代数的表現を定点に変換する第２の規則の集合を使用することによりＱを最適化する。
【０１４１】
本明細書において記載する実施形態の最適化も可能である。例えば、パターンコンパイラは、束縛された変数間の依存性を認識し、それらの依存性を使用してマッチングを駆動することができる。コンパイラは、上記に示す意味合いでこの最適化をパターンに対して使用することができる。入力フォレストから、パターンエレメント
ｔｙｐｅｄＴｅｒｍ［ｐｒｏｏｆ２：ａｎｙ，ｉｍｐｌｉｅｓ［ａ：ａｎｙ，ｂ：ａｎｙ］］
とマッチする入力項目を抽出することにより、生成されたトランスデューサは、パターンエレメント
ｔｙｐｅｄＴｅｒｍ［ｐｒｏｏｆ１：ａｎｄｙ，ａ：ａｎｙ］
に対する可能性のあるマッチングを制約することができる。
【０１４２】
モジュラフォレストオートマトンは、半順序正規ツリーパターンについての統一された記載を提供する。ＭＦＡはまた、これらのパターンの決定化、サブタイプ化、交わり、および相補のための簡素なアルゴリズムを提供する。実際には、モジュラフォレストオートマトンは、高性能のパターン分析およびマッチングをサポートする。モジュラフォレストトランスデューサにより、コンパイラが、セマンティックアクションを任意の状態遷移におくことが可能にされ、一方でラベル付き有向グラフの効率的な変換がサポートされる。
【０１４３】
本発明は、その精神または主要な特徴から逸脱することなく他の特定の形式において具現化することができる。記載される実施形態は、あらゆる点において単に例示としてみなされ、制限するものとしてみなされない。従って、本発明の範囲は、前述の記載によるのではなく、添付の請求項により示される。請求項と等価の意味および範囲に入る全ての変更は、請求項の範囲に包含される。
【技術分野】
【０００１】
本発明は、モジュラフォレストオートマトンに関する。
【背景技術】
【０００２】
プログラミング言語では、値のクラス間を区別するパターンを使用することが可能である。例えば、以下の疑似コードの２行では、整数のリストの合計を計算する関数が定義される。
Ｓｕｍ（ｎｉｌ）＝０
Ｓｕｍ（ｃｏｎｓ［ｈｅａｄ，ｔａｉｌ］）＝ｈｅａｄ＋Ｓｕｍ（ｔａｉｌ）
【０００３】
この例のパターンは２つの役割を有する。すなわち、第１に、入力事例を区別すること、第２に、パターン変数および型推論の使用を介して簡潔な値の脱構築を可能にすることである。
【０００４】
パターンは、構造型に密接に関連する。本明細書において記載する正規ツリーパターンは、変数束縛を含むことができる正規ツリー型である。セマンティックアクションと連結されたツリーパターンをツリー変換規則と呼ぶ。
【０００５】
ＸＭＬスキーマ言語等の構造型システムでは、値のカテゴリを定義する。プログラミング言語では、構造型システムを使用してプログラムの安全特性を静的にチェックすることがよくある。ＳＱＬデータベースではまた、主として構造に焦点を合わせた型システムを使用する。結合の結果得られるテーブルは、例えば、無名の構造型を持つものとして記載されるタプルを含む。データベース管理システムは、様々なプログラムがシステムに記憶されるデータを解釈することが可能であることを要求する。構造型システムは、データベース管理システムがこの要求を満たすようにサポートする。
【０００６】
分散システムではまた、構造型に対する要求を引き起こす。レイテンシのため、分散プログラムコンポーネント間で交換されるメッセージは、オブジェクト間で交換されるメソッド引数より大きくかつ複雑であることが多い。
【０００７】
データベースに記憶され分散コンポーネント間で交換される値は、複雑性においては、プログラム表現により操作される単純な値とチューリングマシンの複雑性との中間にある。本明細書において記載するが、正規ツリーパターンを使用して構造の複雑性のこれらの中間レベルが定義される。
【０００８】
順序正規ツリーパターンおよび非順序正規ツリーパターンの両方を表現しかつ分析することは、有用かつ有益な能力であろう。分析が有益に向上されるであろうドメインの例には、モデル検査および半順序ツリーパターンを使用する権限付与ロジックが含まれる。ＸＭＬスキーマ等の特定の既存の言語では、順序正規ツリーを部分的に使用することができるが、現在のところサブタイプ化するための手段がない。さらに、そのような言語では、現在既知の方法の下で効果的な実現をサポートするためにセマンティックな制約が課せられる。
【０００９】
欲張りな正規表現のマッチングおよびプログラミング言語ＸＳｔａｔｉｃについて研究がなされ、正規の順序ツリー型をオブジェクト指向の言語にどのように組み込むかが模索されてきた。ＸＤｕｃｅのように、ＸＳｔａｔｉｃでは、シーケンスに対して一定の表現を使用する。そのような研究により正規の順序ツリー型がオブジェクトにマップされ、フラット化を使用して、正規言語の包含物の自然意味論をサポートする。最後にｔｒｘが、スキームの文脈で正規順序ツリー型を模索する。
【発明の概要】
【課題を解決するための手段】
【００１０】
プッシュダウンフォレストオートマトン（ＰＦＡ）についても研究が達成された。しかし、ＰＦＡでは、非順序のネスト（マルチ集合）に対処するサブタイプ化のアルゴリズムまたは機構を提供しない。
【００１１】
本発明の実施形態は、モジュラフォレストオートマトン（ＭＦＡ）に関する。本明細書において記載するモジュラフォレストオートマトンを使用して、正規ツリーパターンを記述および分析することが可能であり、また、ラベル付き有向グラフの変換を簡潔に表現することができるモジュラフォレストトランスデューサ（ＭＦＴ）を作成することが可能である。グラフ変換は、ロジック、処理モデル、およびプログラミング言語の実装における基本の要素である。モジュラフォレストオートマトンの実装を使用して、高性能な、強力にタイプ化されたグラフ変換をサポートすることができる。
【００１２】
モジュラフォレストオートマトンは、半順序の、有限の、ランク付けされないツリーのコレクションを定義、再組織化、および変換するための機構である。ＭＦＡは、ＭＦＡ階層の分析および合成をサポートする。ＭＦＡでは、順序ツリーパターンおよび非順序ツリーパターンを統一して処理する。
【００１３】
本明細書において記載する実施形態には、正規ツリーパターンを分析するための方法、システム、およびコンピュータプログラム製品が含まれる。特定の実施形態では、シーケンスおよび集合の両方を記述するモジュール（マシン（machine））として決定または書き換えされることが可能なデータが、受け取られる。和集合は、受け取られたデータから決定されるモジュールから作成することができる。決定されたモジュールおよびモジュールの和集合は、ラベル付き受容状態を備えることができる。ラベル付き受容状態から、サブタイプ関係がモジュールに対して決定される。
【００１４】
本明細書において記載する他の実施異形態にはまた、正規ツリーパターンの変換を表現するための方法、システム、およびコンピュータプログラム製品が含まれる。正規ツリーパターンが受け取られ、特定のインスタンスデータが受け取られる。トランスデューサが、受け取られた正規ツリーパターンからコンパイルされる。トランスデューサの遷移が、所望の変換に対応する命令で拡張される。拡張されたトランスデューサの遷移およびインスタンスデータから、正規ツリーパターンのエレメントとインスタンスデータのエレメントとの間の対応が決定される。
【００１５】
この要約は、以下の「発明を実施するための形態」でさらに述べる概念を選択して簡略化した形式で紹介するために提供するものである。この要約は、請求の主題の重要な特徴または主要な特徴を確認することを意図しておらず、請求の主題の範囲を決定する際の助けとして使用されることも意図していない。
【００１６】
本発明の追加の特徴および利点は、以下に続く記載において説明され、一部は記載により明らかにされ、または、本発明の実践により習得されるであろう。本発明の特徴および利点は、特に添付の請求項において指摘される機器および組み合わせを用いて、実現および取得することができる。本発明のこれらおよびその他の特徴は、以下の記載および添付の請求項からさらに完全に明らかにされ、または、以下に説明されるような本発明の実践により習得されるであろう。
【図面の簡単な説明】
【００１７】
本発明の上記に列挙した利点および特徴ならびに他の利点および特徴を取得することが可能な方法で記載するために、上記で簡単に記載された本発明のより詳しい説明が、添付の図面に例示される本発明の特定の実施形態を参照して描写される。これらの図面は、本発明の単なる典型的な実施形態を示し、かつ、従ってその範囲を制限するとみなされないことを理解した上で、本発明は、添付の図面を使用して追加の特異性および詳細と共に記載および説明されるであろう。
【図１】本発明の原理の実施形態を動作させることができるコンピュータ環境を例示する図である。
【図２】パターンのネストされたコンテンツに対する置換モジュラフォレストオートマトンを例示する図である。
【図３】特定のパターンＥｘｐｒの決定された翻訳を例示する図である。
【図４】パターンＰｏｎｄのネストされたコンテンツに対する最適化されたモジュラフォレストオートマトンを例示する図である。
【図５】サブタイプ分析で決定された種々のサブタイプの図式表現を例示する図である。
【図６】パターンＧＴＥのネストされたコンテンツに対する非決定性モジュラフォレストオートマトンを例示する図である。
【図７】パターンＧＴＥのネストされたコンテンツに対して決定されたモジュラフォレストオートマトンを例示する図である。
【図８】本発明の特定の実施形態に従って、正規ツリーパターンを分析するための方法のフローチャートを例示する図である。
【図９】本発明の特定の実施形態に従って、正規ツリーパターンの変換を表現するための方法のフローチャートを例示する図である。
【発明を実施するための形態】
【００１８】
本明細書において記載する実施形態は、正規ツリーパターンを分析するための方法、システムおよびコンピュータプログラム製品に関する。本明細書において記載する追加の実施形態は、正規ツリーパターンの（単数または複数の）変換を表現するための方法、システムおよびコンピュータプログラム製品に関する。本発明の実施形態は、以下で詳細に検討するように、種々のコンピュータハードウェアを含む専用または汎用のコンピュータを備えることができる。
【００１９】
図１は、本明細書において記載する実施形態が実践される例示のコンピュータ環境１００を説明する。コンピュータ環境１００には、１つまたは複数のコンピュータプロセッサ１１０が含まれる。コンピュータ環境１００にはまた、１つまたは複数のコンピュータメモリのインスタンス１２０が含まれる。コンピュータメモリ１２０は、適切であることが既知である任意のコンピュータ可読メモリとすることができ、ＲＡＭ、ＳＲＡＭ、およびフラッシュメモリを含む（がこれに限定されない）。コンピュータメモリはまた、ハードディスク、ソリッドステートディスクドライブ、ＣＤＲＯＭ、ＤＶＤ、等の永続記憶装置１３０とすることができる。コンピュータメモリ１２０および記憶装置１３０は、任意の特定の実施形態において適切であるように、ＲＯＭまたはＣＤまたはＤＶＤ等の読取り専用メモリとすることができ、または、ＲＡＭ、フラッシュメモリおよび一般的なディスクドライブ等の読取り可能かつ書込み可能メモリとすることができる。
【００２０】
コンピュータ環境１００にはまた、入力／出力１４０が含まれる。入力／出力１４０は、磁気ディスクに記憶されるデータ、ネットワークを介してアクセス可能なデータ、またはその他、等の任意の適切なフォーマットまたは媒体を備えることができる。コンピュータ環境１００にはまた、データが送受信される外部永続記憶装置１５０が含まれる。記憶装置１３０と同様に、外部永続記憶装置１５０は、磁気ディスク、テープ、ＣＤ−Ｒ／Ｗ、またはその他、等の任意の適切な形式をとることができる。
【００２１】
本発明の範囲内にある実施形態にはまた、コンピュータ実行可能命令またはそれに記憶されるデータ構造を搬送するまたは有するためのコンピュータ可読媒体が含まれる。そのようなコンピュータ可読媒体は、汎用または専用のコンピュータによりアクセス可能な任意の利用可能な媒体とすることができる。制限ではなく例として、そのようなコンピュータ可読媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭもしくは他の光ディスク記憶装置、磁気ディスク記憶装置もしくは他の磁気記憶デバイス、または、汎用または専用のコンピュータによりアクセス可能なコンピュータ実行可能命令またはデータ構造の形式の所望のプログラムコード手段を、搬送または記憶するために使用可能な任意の他の媒体、等の記憶媒体を備えることができる。ネットワークまたは別の通信接続（有線、無線、または有線と無線の組み合わせ）を介して、コンピュータに情報が転送または提供されると、コンピュータはその接続をコンピュータ可読媒体として適正に見なす。そのようなネットワークまたは通信接続を、本明細書において、通信媒体と称する。従って、任意のそのような接続を、適正にコンピュータ可読媒体と呼ぶ。記憶媒体および通信媒体の両方を含む上記の組み合わせもまた、コンピュータ可読媒体の範囲に含めることができる。
【００２２】
コンピュータ実行可能命令は、例えば、汎用コンピュータ、専用コンピュータ、または専用の処理デバイスに、特定の機能または機能のグループを実行させる、命令およびデータを備える。そのようなコンピュータ実行可能命令は、コンピュータメモリ１２０内、永続記憶装置１３０内、任意の入力もしくは出力の媒体もしくはデバイス１４０上、または外部記憶装置１５０上、に記憶することができる。コンピュータ実行可能命令を、任意の適切な通信媒体を介して適切なコンピュータ環境に転送することもできる。
【００２３】
主題が、構造的特徴および／または方法論的な動作に特有の言語で記載されたが、添付の請求項に定義される主題が必ずしも記載された特有の特徴または動作に限定されないことは理解されるべきである。むしろ、前述の特有の特徴および動作は、請求項を実装する例示の形式として開示される。
【００２４】
本明細書において記載する実施形態は、正規ツリーパターンを分析するための方法、システム、およびコンピュータプログラム製品に関する。本明細書において記載する追加の実施形態は、正規ツリーパターンの変換を表現するための方法、システムおよびコンピュータプログラム製品に関する。本発明の実施形態は、以下で詳細に検討するように、種々のコンピュータハードウェアを含む専用または汎用のコンピュータを備えることができる。
【００２５】
例えば、図８は、正規ツリーパターンを分析するための方法を例示する。方法は、１シーケンスおよび１集合の内の少なくとも１つを備える正規ツリーパターンを備えるデータを受け取るステップ８１０を含む。ツリーパターンが１シーケンスを備える場合、８２０で、そのシーケンスに対応するマシンが決定される。決定されたマシンは、「モジュール」とも呼ばれる。１シーケンスは、その名前が暗に示すように、特定の順番を有するエレメントの１集合である。
【００２６】
８３０で、ツリーパターンが１集合を備える場合、その１集合に対応するマシンが決定される。特定の順番を有する１シーケンスとは対照的に、１集合は、特に順番が指定されないエレメントのコレクションとすることができる。
【００２７】
８４０で、決定されたマシンの和集合が作成される。８５０で、決定されたマシン（モジュール）の和集合から、ラベル付き受容状態の１集合が決定される。最後に、８６０で、ラベル付き受容状態からサブタイプ関係が決定される。
【００２８】
本明細書においてさらに詳細に記載するように、サブタイプ関係は、等価、サブタイプ、スーパータイプ、互いに素、および交わり、の内の１つとすることができる。２つのモジュールＭ1およびＭ2が、同一の受容状態を有す場合、これらは等価である。Ｍ1がＭ2の全ての受容状態を含み、その逆が無い場合、Ｍ1はＭ2のスーパータイプであり、Ｍ2はＭ1のサブタイプである。Ｍ1とＭ2が共通した受容状態を持たない場合、Ｍ1とＭ2は互いに素である。Ｍ1とＭ2がいくつかの受容状態を共有するが、Ｍ1、Ｍ2のそれぞれが他とは共有されない受容状態を有する場合、これらは交わっている。サブタイプ関係は、以下でより詳細に図５と併せて検討する。
【００２９】
実施形態はまた、ラベル付きネストへの少なくとも１つの遷移を備えるルートレベルマシン（モジュール）を決定するステップを含む。ラベル付きネストは、本明細書においてより詳細に記載するように、Ｌａｂｅｌ［・・］またはＬａｂｅｌ｛・・｝の形式を有することができる。モジュールは、ラベル付きネストに対応して作成される。ラベル付きネストからの復帰（リターン）に対応する継続状態は、スタック上に置くことができる。継続状態をスタック上に置いた後、ラベル付きネストに対応するアクションが実行される。受容状態がラベル付きネストに達すると、継続状態がスタックからポップされ、処理はルートレベルマシンに向かって再開される。
【００３０】
明細書において記載する実施形態を採用すると、受け取られたデータは、プログラミング言語で構造型を定義するデータに対応する。そのようなデータは、本明細書において記載する技術により分析されて、構造型が等価であるか、または、本明細書に記載されるような他のサブタイプ関係のいずれかを有するか、を判定することができる。
【００３１】
本明細書において記載する実施形態を採用すると、受け取られたデータは、データベースのスキーマおよび／またはスキーマ定義を備えるデータに対応する。そのようなデータは、本明細書において記載する技術により分析されて、スキーマとスキーマ定義が等価であるか、または、他のサブタイプ関係のいずれかを有するか、を判定することができる。
【００３２】
本明細書において記載する実施形態を採用すると、受け取られたデータは、ＸＭＬスキーマに対応する。そのようなデータは、本明細書において記載する技術により分析されて、ＸＭＬスキーマが等価であるか、または、他のサブタイプ関係のいずれかを有するか、を判定することができる。
【００３３】
本明細書において記載する実施形態を採用して、判定されたサブタイプ関係に対応する構造的関係および論理的関係を決定することができ、また、プログラミング言語、データベース、オブジェクト等におけるデータ構造に対する最適化、効率、およびデータ翻訳の目的に適用することができる。
【００３４】
本明細書において記載する実施形態はまた、正規ツリーパターンの変換を表現するための方法を含む。図９は、正規ツリーパターンの変換を表現するための方法９００を例示する。方法は、正規ツリーパターンに対応する第１のデータを受け取るステップ９１０を含む。方法はまた、実際のインスタンスに対応する第２のデータを受け取るステップ９２０を含む。
【００３５】
例えば、正規ツリーパターンを備えるデータは、ＸＭＬスキーマを備えることができ、データベーススキーマを備えることができ、プログラミング言語またはオブジェクト定義のための構造型を備えることができる。実際のインスタンスに対応するデータは、データベース内のデータを備えることができ、シリアルデータ入力ストリームを備えることができ、または、オブジェクト指向のオブジェクト内で具現化されるデータまたはプログラミング言語内に定義される構造型を備えることができる。
【００３６】
方法９００は、正規ツリーパターンをトランスデューサにコンパイルするステップ９３０を含む。ツリーパターンのコンパイルについては、本記載の後の章でより詳細に記載する。コンパイルされると、９４０で、トランスデューサの遷移が所望の変換に対応する命令で拡張される。遷移が命令で拡張された後、９５０で、拡張された遷移から、および、実際のインスタンスに対応するデータから、インスタンスのエレメントと正規ツリーパターンのエレメントとの間の対応が決定される。
【００３７】
例えば、Ｒｏｏｔ［Ａ＋，Ｂ*，Ｃ？］等のパターン、および、実際のインスタンスデータ（環境内に与えられた）［ａａａ，ｂｂｂ，−］がある。この例から、方法９００では、特定の束縛Ａ＝‘ａａａ’、Ｂ＝‘ｂｂｂ’、およびＣ＝‘−’を決定することができる。さらに、例えば、ａｃｔｉｏｎ：Ｒｏｏｔ［Ａ，Ｂ，Ｃ］→Ｒｏｏｔ［Ａ，Ｃ］、等のアクションが実行される。束縛が決定されると、例示のアクションは、「Ｂを削除する」アクションであると考えることができる。
【００３８】
方法９００を、変数束縛の環境に採用することができる。そのような変数束縛は、プログラミング言語、データベーススキーマ、ＸＭＬスキーマ等における構造型と、タイプまたはスキーマ内に定義される変数に対応する実際の値と、の間の対応を決定することができる。
【００３９】
方法９００の命令はまた、条件のマッチングを備えることができ、また、セマンティックアクションを備えることができる。方法９００のインスタンスデータは、ＸＭＬスキーマインスタンスを備えることができ、特定のデータベーススキーマに従ってデータベース内に含まれるデータのインスタンスを備えることができ、または、プログラミング言語内に定義される構造型に従って定義または記憶されるデータを備えることができる。
【００４０】
方法９００はまた、クエリ表現をコンパイルするステップと、正規ツリーパターンおよび実際のインスタンスデータに対応するクエリ表現の結果を判定するステップと、を備えることができる。例えば、そのようなクエリは、ＳＱＬ等のデータベースクエリとすることができ、また、データアクセス等の権限付与クエリとすることができる。
【００４１】
なお、本明細書において記載する全ての方法および技術は、コンピュータ環境内で実行する方法、本明細書において記載する方法および技術を実行するためのコンピュータ実行可能コードを備えるコンピュータプログラム製品、および、本明細書において記載する方法および技術を実行するためのコンピュータプロセッサおよびコンピュータ実行可能コードを備えるコンピュータシステム、を備えることができる（がこれに限定されない）種々の実施形態において実現することができる。
【００４２】
本明細書において記載する実施形態の方法および技術についての、より詳細かつ綿密な検討が続く。
【００４３】
正規ツリーパターン
リスト１には、正規ツリーパターンに使用することができる構文を記載する。リスト１の文法では、項Ａｃｔｉｏｎはセマンティックアクションの言語を参照する引数である。項Ｎａｍｅ、Ｖａｒｉａｂｌｅ、およびＬａｂｅｌは、１つのアルファベットで呼ばれる記号の集合をそれぞれ提供する引数である。本明細書において記載するように、変数、パターン名、およびラベルの記号は、別々のアルファベットでできているものとする。これらの記号に加えて、パターンは、非パターン型、またはリテラル値を含む基の記号を参照することができる。
Ｄｅｆｉｎｉｔｉｏｎ→ Ｎａｍｅ‘＝’Ｐａｔｔｅｒｎ
Ｐａｔｔｅｒｎ → Ｕｎｉｏｎ
｜ ΛＶａｒｉａｂｌｅ．Ｐａｔｔｅｒｎ
｜ ε
Ｕｎｉｏｎ → Ｒｕｌｅ（‘｜’ＲｕＩｅ）＊
Ｒｕｌｅ → ＴｒｅｅＡｃｔｉｏｎ？
Ｔｒｅｅ → Ｌａｂｅｌ［Ｆｏｒｅｓｔ？］
｜ Ｌａｂｅｌ｛Ｆｏｒｅｓｔ？｝
｜ ＢｉｎｄｉｎｇＴｒｅｅ
｜ ＴｒｅｅＲｅｐｅｔｉｔｉｏｎ
｜ Ｔｒｅｅ∧Ｔｒｅｅ
｜ ¬Ｔｒｅｅ
｜ （Ｔｒｅｅ）
｜ ａｎｙ
｜ Ｒｅｆｅｒｅｎｃｅ
Ｆｏｒｅｓｔ → ＴｒｅｅＦｏｒｅｓｔ，Ｔｒｅｅ
Ｒｅｐｅｔｉｔｉｏｎ→ ＊｜＋｜？
｜ ［Ｍｉｎ．．．Ｍａｘ］
Ｒｅｆｅｒｅｎｃｅ → ＳｙｍｂｏｌＴｙｐｅＰａｒａｍ？
ＴｙｐｅＰａｒａｍ → （Ｕｎｉｏｎ）
Ｂｉｎｄｉｎｇ → Ｖａｒｉａｂｌｅ：
リスト１．正規ツリーパターン構文
【００４４】
正規ツリーパターンの定義では、ネスト演算子（以下で説明する）の文脈内での再帰的なパターン参照を可能にするだけである。正規ツリー文法に対するそのような制約を採用して、正規ツリーの文法が文脈自由文字列文法の最大限の力を引き出すことが無いようにする。
【００４５】
Ｒｅｐｅｔｉｔｉｏｎ（繰り返し）の構造「＊｜＋｜？」は、この構造が修飾するＴｒｅｅに対して許可される最小発生回数および最大発生回数を表す。最大発生回数は、無限とすることができる。演算子「＊」「＋」および「？」は、それぞれ［０．．∞］、［ｌ．．∞］および［０．．１］と解釈される。換言すると、「Ａ*」は０個以上のＡ（すなわち、［０．．∞］）、「Ｂ＋」は１つまたは複数個のＢ（すなわち、［ｌ．．∞］）、「Ｃ？」は、０個または１個のＣ（すなわち，［０．．１］）、を意味する。この構造は、ランク付けされないツリーノードを特定するパターンをサポートする。ランク付けされないツリーノードは、任意の数の子を持つことができる。
【００４６】
任意のワイルドカードは任意の値をマッチングする。¬演算子は、ツリーパターンを補間する。∧演算子は、１対のツリーパターンの共通集合を表す。｜演算子は、１対のツリーパターンの和集合を表す。最後に、λＰ．ｂ演算子は、ボディｂおよびパターン引数Ｐを持つポリモーフィック（多型）パターンを表す。
【００４７】
ネスト演算子Ｌ［Ｆｏｒｅｓｔ？］は、ラベルＬの順序付きのランク付けされないツリーノードを定義する。そのような順序付きの項目はまた、シーケンスとも呼ばれる。ネスト演算子Ｌ｛Ｆｏｒｅｓｔ？｝は、ラベルＬの非順序付きのランク付けされないツリーノードを定義する。非順序付きの項目は、集合（またはマルチ集合）とも呼ばれる。我々は、用語マルチ集合パターンを使用して、Ｌ｛ｃ｝の形式のパターンを参照するが、これはｃが０個以上のツリーノードのマルチ集合をマッチングするからである。我々は、用語半順序ツリーパターンを使用して、順序サブツリーおよび非順序サブツリーの両方を特定することができるツリーパターンを参照する。
【００４８】
半順序ツリーパターンにより、厳密な順序ツリーパターンまたは非順序ツリーパターンを使用して表現することが冗長または不可能な考えを、プログラマが正確に表現することを可能にする。例えば、リスト２で定義される変換規則を含む処理モデル検査アプリケーションを以下に記載する。
ｐａｒ｛ｓｅｎｄｅｒ：ｃｈｏｉｃｅ｛ｓｅｑ［ｓｅｎｄ［ｘ：ａｎｙ］，ＣＳ：ａｎｙ］，ａｎｙ*｝，
ｒｅｃｅｉｖｅｒ：ｃｈｏｉｃｅ｛ｓｅｑ［ｒｅｃｖ［ｘ：ａｎｙ］，ＣＲ：ａｎｙ］，ａｎｙ*｝，
ｐｒｏｃｓ：ａｎｙ*｝
＝＝＞
ｐａｒ｛ＣＳ，ＣＲ，ｐｒｏｃｓ
リスト２ 処理相互作用規則
ラベルｐａｒのマルチ集合パターンは、並行して実行される処理のコレクションをモデル化する。ｃｈｏｉｃｅでラベル付けされる各ノードは、選択肢の集合の中から選択することにより継続される処理をモデル化する。Ｓｅｑでラベル付けされる各ノードは、処理のシーケンスを示す。最後に、ｓｅｎｄ［ｘ］およびｒｅｃｅｉｖｅ［ｘ］は、タイプｘのメッセージを送信および受信することに対応する。
【００４９】
規則は、対になった処理（パターンにおける変数の送信側と受信側に結び付けられる）の間の相互作用をモデル化する。送信側の処理では、タイプｘのメッセージを送信し、受信側の処理では、このメッセージを受信する。相互作用の後、並行処理のコレクションには、送信側（ＣＳ）の継続、受信側（ＣＲ）の継続、およびこの相互作用に加わらない処理のコレクション（ｐｒｏｃｓ）、が含まれる。
【００５０】
並行処理の集合内には、相互作用のパターンとマッチすると、複数の対の潜在的に相互作用する処理、および、従って複数の可能性のある成果が存在する場合がある。以下に記載するＭＦＡの機構を使用して、１つまたは複数のこれらの成果を生成することができる。
【００５１】
マルチ集合パターンは、簡潔さ以上のものを提供する。これらはまた、実装および特定の実施形態において、入力コレクションの本質的には非順序の表現が使用されることを可能にする。探索ツリーまたはハッシュテーブル等の非順序の表現を直接使用することで、変換エンジンに入力コレクションに対して別のインデックスを形成させないようにすることができる。
【００５２】
例えば、アクセス要求が権限付与のポリシーを満たすことを、要求をアサーションのデータベースおよび規則の集合に対してマッチングすることによりチェックする、以下に記載する権限付与ロジックの実装が、評価される。権限付与のポリシーのアプリケーションは、アサーションデータベースの非順序の表現に対して直接働くマルチ集合パターンを使用することができる。
【００５３】
マルチ集合パターンおよびポリモーフィズム（多態性）が、正規ツリーの文法から削除されると、正規ツリー型システムは、理解されるように、ＸＭＬツリー変換の関数型プログラミング言語と同様のところにたどり着く。そのようなシステムを採用して、ネストされた正規の表現上のサブタイプ関係を決定するためのアルゴリズムを生成することができる。そのようなアルゴリズムでは、トップダウンのアプローチを使用して、パターンの表現を比較する。アルゴリズムは、正規ツリー表現に関する以前の理論的研究から発展し、それを拡大させる。このプロジェクトでは、最初はボトムアップツリーオートマトンの決定化を使用して包含物を決定したが、これは拡大可能なアプローチではないことが分かった、と報告されている。ボトムアップツリーオートマトンの決定化アルゴリズムは、サブセットの構成を適用する際に左の文脈を考慮に入れない。これは、指数関数的な爆発が、文脈に注意することよりもはるかに一般的なものになる原因となる。どのようにモジュラフォレストオートマトンが左の文脈を使用してそのような落とし穴を回避し、一方で決定化およびサブタイプ化に直接アプローチする簡略性を維持するのか、を以下に示す。
【００５４】
別の実施形態では、上述のシステムを、ポリモーフィズム、関数型、およびレコードで拡大させる。レコードは、一意性制約をラベル全体に要求する。以下に記載するＭＦＡの実装では、パターン変数全体への等式制約に加えて、一意性制約をサポートする。
【００５５】
理解されるように、アンビエント計算演算子ｎ［］、は、正規ツリーパターンの演算子Ｌａｂｅｌ｛Ｆｏｒｅｓｔ？｝に強力に対応する。アンビエント計算の並行合成演算子を、１対のツリーをその根で連結されるツリー合成演算子として解釈できることが実証される。アンビエント論理を、ツリー構造を記述しクエリするための基本として使用できることが提案される。アンビエント論理は、処理に関して推論するための一時的な空間論理である。リスト１の正規ツリーの文法とは異なり、アンビエント論理は非順序のネストのみを考慮する。アンビエント論理では、サブタイプ関係の決定は、含意を決定することと同意義である。これは、この理論の変形に対しても当てはまる。
【００５６】
ＸＭＬスキーマ言語
成功裏にインポートされ、かつ、Ｗ３ＣＸＭＬスキーマ言語のインスタンスに対するサブタイプ関係を決定する、モジュラフォレストオートマトン（ＭＦＡ）の実装が、本明細書において記載される。ＸＳＤ複合型は、構造式に対して名称を割り当てる。ＸＳＤにおける構造式は、コンテントモデルと呼ばれる。コンテントモデルは、要素宣言、属性一覧と呼ばれる非順序ネストパターン、および、パーティクルコンポジタを含む。ａｌｌ、ｃｈｏｉｃｅ、およびｓｅｑｕｅｎｃｅの３つのコンポジタがある。正規ツリー文法の和集合および連結のコンストラクタは、選択およびシーケンスのコンポジタにそれぞれ対応する。
【００５７】
ａｌｌコンポジタは、本明細書において記載する非順序のネスト演算子に対応する。ＸＳＤは、ａｌｌコンポジタの使用について何らかの制約を与える。例えば、ＸＳＤではａｌｌコンポジタ内の項目は多様性が限定されることを要求する。
【００５８】
ＸＭＬの要素の宣言は、要素ｑｎａｍｅの役割を担う演算子名Ｌａｂｅｌを用い、正規ツリーの文法の順序ツリー構造Ｌａｂｅｌ［Ｆｏｒｅｓｔ？］と同一構造である。しかし、ＸＭＬスキーマ言語は、２つのコンテントパーティクルａおよびｂの任意の和集合に対して、単一の先行読み取りの一意のパーティクル属性の実行、すわなち、トークンを１つだけ読むこと、をパーサが可能でなければならないことと、インスタンスがｃｈｏｉｃｅの枝ａまたはｂに対応するかどうかをパーサが識別可能でなければならないこととを要求する。
【００５９】
モジュラフォレストオートマトン
半順序正規ツリーパターンについては上記に記載した。
モジュラフォレストオートマトン（ＭＦＡ）は、シーケンスおよび集合の順序正規ツリーパターンおよび非順序正規ツリーパターンを統一して処理する機構を提供する。そのような順序正規ツリーパターンおよび非順序正規ツリーパターンは、シーケンスおよび集合と呼ばれることがある。各ＭＦＡは、ＭＦＡ階層の分析および合成をサポートする規約を実装する。規約により、ＭＦＡは、本明細書において検討したように、決定化の間に左の文脈を活用することができる。ＭＦＡにおける左の文脈の使用により、ボトムアップツリーオートマトンの決定化のための特定の以前の方法に見られた、可能性のある状態の爆発が回避できる。
【００６０】
モジュラフォレストオートマトン（ＭＦＡ）は、可視プッシュダウンオートマトン（ＶＰＡ）である。可視プッシュダウンオートマトンは、当業者には既知であるようなプッシュダウンオートマトンの１クラスである。ＭＦＡに対して、プッシュダウンオートマトンは１タプルとして定義される。
【００６１】
Ｍ＝（Ｋ，Σ，Γ，Δ，ｓ，Ｆ）、ここで
Ｋは状態の有限集合、
Σは、アルファベット（入力記号）、
Γは、アルファベット（スタック記号）、
ｓ∈Ｋは、初期状態、
Ｆ⊆Ｋは、最終状態の集合、
【００６２】
Δは、遷移関係であり、（Ｋ×Σ*×Γ*）×（Ｋ×Γ*）の有限のサブセットである。
遷移関係は、３種類のもの（カレント状態、入力記号、ポップされるスタック記号）を対（新しい状態、プッシュされるスタック記号）にマップする。
【００６３】
分析をサポートするには、ＭＦＡでは、可視プッシュダウン言語（ＶＰＬ）のスタック使用の制約を採用する。このクラスの言語は、その遷移関係をリスト３の３つのプッシュダウン遷移カテゴリの１つに従うように制約するプッシュダウンオートマトンを使用して定義される。
Ｌｏｃａｌ（ｑ0，ａ∈Σ1，ε）→（ｑ1，ε）
Ｃａｌｌ（ｃａｌｌＳｉｔｅ，ａ∈ΣC，ε）−＞（ｃａｌｌＴａｒｇｅｔ，ｃａｌｌＳｉｔｅ）
Ｒｅｔｕｒｎ（ｒｅｔｕｒｎＳｉｔｅ，ａ∈Σr，ｃａｌｌＳｉｔｅ）→（ｃｏｎｔｉｎｕａｔｉｏｎ，ε）
リスト３ ＭＦＡ遷移カテゴリ
これらのカテゴリは、Σを、ｃａｌｌ（コール）、ｒｅｔｕｒｎ（リターン）、およびｌｏｃａｌ（ローカル）、の遷移を生じさせることが可能な記号にそれぞれ対応する３つの互いに素な集合、ΣC、Σr、Σ1、に分割する。ローカル遷移は、正規有限オートマトンにおける遷移と同一である。ＭＦＡであるＭ0における状態ｑ0からのコール遷移は、記号ａを読み込み、ｃａｌｌＳｉｔｅをスタックにセーブし、状態ｃａｌｌＴａｒｇｅｔに制御を渡す。リターン遷移は、スタックからｃａｌｌＳｉｔｅをポップさせ、カレント状態をｃｏｎｔｉｎｕａｔｉｏｎ（継続）させる。
【００６４】
上述のスタック規則により、ＶＰＬを、プッシュダウンオートマトンの、クリーネスターとリネームする和集合および連接の閉包性に加えて、共通集合および補集合の下で閉じたままにすることができる。一般的な非決定性文脈自由言語とは異なり、非決定性ＶＰＬのクラスは、決定性ＶＰＬのクラスと等価である。
【００６５】
各ＭＦＡのＭは、コール対象の状態の集合Ｔを有する。Ｍの開始状態は、コール遷移で終了するパスによりｓから到達可能な任意の状態のように、Ｔ内にある。Ｍは、モジュールと呼ばれる状態の互いに素な集合の階層として見ることができる。Ｍは、各状態ｔ∈Ｔに対して１つのモジュールを持つ。コール対象の状態をｔとすると、対応するモジュールＭｏｄｕｌｅ（Ｔ）は、ローカル遷移のみを使用してｔから到達可能な状態の集合である。
【００６６】
１つのモジュールはただ１つのコール対象の状態ｔを含むことが要求される。コール対象の状態ｔは、モジュールのエントリポイントと呼ばれる。従って、ＭＦＡは、別のコール対象の状態からローカル遷移により到達可能な対象の状態を有するコール遷移を含むことができない。ＭＦＡの開始状態を含むモジュールは、ＭＦＡのトップレベルモジュールと呼ばれる。スタック規則を維持するために、ＭＦＡでは、モジュール間ε遷移を許可しない。
【００６７】
有限の追加の記帳をＭＦＡに使用して、ＶＰＡのコール／リターン戦略を、非順序ネストパターンに適用して、順序ネストパターンおよび非順序ネストパターンの両方に適用可能な単一のサブタイプ化方法を得る。
【００６８】
各ＭＦＡの状態は、０個以上のパターンの同値類が状態により受容されることを示すビットベクトルでラベル付けされる。このラベルはタグと呼ばれる。各ＭＦＡには、マッピングＴａｇ：Ｋ→Ｂ（ここで、Ｂはｋビットの文字列）が含まれる。所与のモジュールＭに対して、ｋは一定であり、ｋはモジュールＭのタグ長と呼ばれる。Ｆにおける各最終状態ｆに対して、Ｔａｇ（ｆ）は少なくとも１つの非ゼロビットを含まなければならない。
【００６９】
タグの目的は、呼び出しから復帰した時に、呼び出しているＭＦＡをどのように継続させるかを導くことである。ＭＦＡにおいて、リターン遷移は、固定した対象の状態を持たない。その代わり、ＭＦＡの状態ｓからのリターン遷移は、コール状態をスタックからポップさせ、スタックＴａｇ（ｓ）にプッシュし、カレント状態をコール状態に変更する。そして、コール状態は、タグをスタックからポップさせ、かつ、制御を継続状態に渡す、継続遷移を実行する。
【００７０】
ＭＦＡ機構に継続遷移を追加することは、ＭＦＡの基本のプロパティを変更することではない。なぜなら、継続遷移を持つＭＦＡの継続遷移を除去することができるからである。継続遷移を持つＭＦＡの継続遷移を除去することは、以下のように行う。まず、Ｍｏｄｕｌｅ（ｔ）における状態の、コール対象の状態ｔを有する各コールサイトｃに対するコピーを作る。このコピーは対象モジュールと呼ばれる。次に、対象モジュールにおける各リターン遷移（ｒ；α∈Σr，ｃ）→（ｃ，ｔａｇ）に対して、対応する継続遷移（ｃ，ε，ｔａｇ）→（ｃｏｎｔｉｎｕａｔｉｏｎ；ε）をコールモジュールにおいて求め、両方の遷移を削除する。最後に、リターン遷移（ｒ；α∈Σr；ｃ）→（ｃｏｎｔｉｎｕａｔｉｏｎ；ε）を対象モジュールに追加する。上述したように継続遷移の削除が可能であるため、ＭＦＡが継続遷移を持つことが推測される。
【００７１】
また、ＭＦＡが、フォレストの入力スタックと呼ばれるスタック対するアクセスを有する、と推測することができる。ＭＦＡの実行は、入力スタックが元の入力フォレストを含むＭＦＡの開始状態で始まる。ＭＦＡには、カレントツリーの概念が含まれる。カレントツリーは、入力スタックのトップにあるフォレスト内の何かのツリーである。これらの構想を使用して、ＭＦＡの特定の実装にマップすることができる。コールは、カレントツリーの子を入力スタックにプッシュする。リターンは子をスタックからポップさせる。
【００７２】
モジュールＭのローカル遷移のみを考慮すると、Ｍは、フォレストのコンテンツを認識する正規文字列オートマトンである。理解されるように、これを使用してプッシュダウンフォレストオートマトン（ＰＦＡ）のクラスを定義することができる。プッシュダウンフォレストオートマトンは、フォレスト状態ＱFおよびツリー状態ＱTという２つの状態の集合を持つ。プッシュダウンフォレストオートマトンは、フォレスト状態の互いに素な集合に連結するＥｎｔｒｙ（入場）遷移およびＥｘｉｔ（退場）遷移を持つ。プッシュダウンフォレストオートマトンはまた、退場遷移からの情報を組み込み、かつ、制御をツリー状態からフォレスト状態に渡す、遷移関係Ｃｏｍｂを有する。
【００７３】
タグがＭＦＡから削除されると、ＰＦＡはＭＦＡと同一構造となる。所与のＰＦＡであるＰを、等価のＭＦＡであるＭPに以下のように変換することができる。Ｐの各フォレスト状態に対して、Ｍpにおける状態を作成する。Ｐにおける各ツリー状態に対して、Ｍpにおける状態を作成する。Ｐの入場遷移、退場遷移、その組み合わせの遷移、およびローカル遷移を直接ＭPにコピーする。これらは、コール遷移、リターン遷移、継続遷移、ローカル遷移にそれぞれ対応する。各コール状態ｃをフォレスト状態とツリー状態ｔとに分割すること、かつ、初期状態がｔである継続遷移となるべき継続遷移を適合させることにより、タグの無いＭＦＡを、等価のＰＦＡに変換することができる。
【００７４】
プリプロセッサＰｒｅｐ（ｓ）を、任意のＭＦＡの状態ｓと関連付けることができる。Ｐｒｅｐ（ｓ）は、有効なＭＦＡに対してまたは⊥に対して設定されなければならない。所与のモジュール内では、全ての状態が同じプリプロセッサ値を共有しなければならない。状態が⊥以外のプリプロセッサを有するモジュールは、プリプロセシングモジュールと呼ばれる。入力フォレストをｉとすると、プリプロセシングモジュールは、ｉの各エレメントに対してそのエレメントを処理する前にプリプロセッサを呼び出す。プリプロセッサを使用して、入力の同値類間を区別する。プリプロセッサを再帰的に呼び出すことはできない。特に、プリプロセシングモジュールｐｒｅｐの状態には、Ｐｒｅｐ（ｔ）＝ｐｒｅｐであるような対象状態ｔを有する遷移を含むパスを初期化できるものはない。プリプロセッサを使用して、マルチ集合パターンをマッチンング可能なＭＦＡを構成することができる。
【００７５】
プリプロセシングモジュールを追加することは、ＭＦＡの基本のプロパティを変更することではない。プリプロセシングモジュールは、その各入力ｉをΨ［ｉ］（ここでΨは予約ラベル）に変換することにより動作するものと考えることができる。そして、プリプロセッシングのステップは、Ψでラベル付けされるネストに対してコール遷移として符号化することができる。
【００７６】
また、セマンティックアクションＡｃｔｉｏｎ（ｔｒ）を、任意のローカルＭＦＡ遷移ｔｒに追加することができる。このようにして拡張される遷移は、アクション遷移と呼ばれる。１つまたは複数のアクション遷移を持つＭＦＡは、モジュラフォレストトランスデューサ（ＭＦＴ）と呼ばれる。セマンティックアクションの順序付けは、ＭＦＴ決定化の間、保持される。
【００７７】
ＭＦＡへのツリーパターンの翻訳
半順序正規ツリーパターンは、ＭＦＡに変換することができる。共通集合および補集合の方法には、決定化ステップが含まれるため、非決定性ＭＦＡ（ＮＭＦＡ）の決定化のための方法の詳細を最初に提供する。
【００７８】
ツリーパターンからＮＭＦＡを形成するための構築プロシージャは、他の既知の構築プロシージャとは異なる。第１に、ツリーパターンには、ネスト演算子が含まれる。第２に、ツリーパターンは、アクションおよび変数束縛を含むことができる。特定の実装におけるパターンコンパイラは、変数束縛をアクションに翻訳することができる。従って、変数束縛は特には扱わない。
【００７９】
ＭＦＡへの入力は、ツリー値の適格なフォレストとすることができる。適格な入力フォレストは、フォレスト終了の記号「］」で終了する。翻訳プロシージャは、あらゆる生成されたＭＦＡ状態ｓに対して、にリターン遷移を追加する］。
【００８０】
２つのＮＭＦＡの和集合Ｍ2＝Ｍ0∪Ｍ1は、タグおよびプリプロセッサに調整を加えることにより拡張される既知の標準的な方法を使用して計算される。構築においては、Ｍ0が長さｋ0のタグを持ち、Ｍ1が長さｋ1のタグを持つことを前提とする。Ｍ2は、長さｋ0＋ｋ1のタグを持つこととなる。Ｍ2の状態ｓがＭ0の最終状態を有する時、ｋ1個のゼロでできた文字列がそのタグに加えられる。そうでなければ、ｓがＭ1の最終状態である時、そのタグは左にｋ0個分シフトされ、ゼロが書き込まれる。
【００８１】
プリプロセシングモジュールの組み合わせをサポートするには、和集合の構築を以下のように修正する。Ｍ2＝Ｍ0∪Ｍ1を計算する時、Ｍ0のトップレベルモジュールがプリプロセッサｐｒｅｐ0≠⊥を持ち、かつ、トップレベルモジュールＭ1がプリプロセッサｐｒｅｐ1≠⊥を持つ場合、Ｍ2のトップレベルモジュールの各状態にプリプロセッサｐｒｅｐ０∪ｐｒｅｐ1を割り当てる。
【００８２】
プリプロセシングモジュールと正規モジュールを組み合わせるには、プリプロセッサを、正規モジュールに対して合成する。ｐｒｅｐ0≠⊥かつｐｒｅｐ1＝⊥であると仮定する。Ｍlに対するプリプロセッサは、Ｍ1のローカル遷移のための遷移記号を認識するＭＦＡの集合の和集合に対して第１の設定ｐｒｅｐ1により合成される。次に、Ｍ1の遷移関係内の各コール遷移（ｃ，Ｌ，ε）→（ｃａｌｌＴａｒｇｅｔ，ｃ）に対して、ｐｒｅｐ1＝ｐｒｅｐ1∪Ｎを設定する（ここでＮは、開始状態がｃａｌｌＴａｒｇｅｔであるモジュールにより識別される子を持つＬでラベル付けされるツリーを認識するＭＦＡである）。
【００８３】
ネスト
ネスト演算子は、順序または非順序のどちらであっても翻訳される。ラベルＬおよびコンテンツｃのネスト演算子を仮定すると、まず、ｃに対してＭｃというＮＭＦＡを作成し、開始状態をｓｃとする。次に、ＭｎｅｓｔというＮＭＦＡを作成し、開始状態ｓ、最終状態ｆ、および、遷移が（ｓ，Ｌ，ε）→（ｓｃ，ｓ）（Ｍｃをコール）および（ｓ，ε，ｔａｇｃ）→（ｆ，ε）（コールから継続）とする。最後に、Ｍｃの状態をＭｎｅｓｔに組み込み、Ｍｃの各最終状態ｆｃをタグｔａｇｃに割り当て、ｆｃを、リターン遷移（ｆｃ，］，ｓ）→（ｓ；ｔａｇｃ）を持つ非最終状態に変更する。この構築において、Ｍｃの状態がＭｎｅｓｔのモジュールになる。
【００８４】
連接演算子を使用して、順序ネストのコンテンツを翻訳することができる。１対のＮＭＦＡをＭ0およびＭ1とすると、この方法では、Ｍ2に対して新しい開始状態を作成し、Ｍ0の各最終状態からＭ1の開始状態へのε遷移を作成することによりｓからＭ0の開始状態へのε遷移を作成し、最後にＭ2の最終状態としてＭ1の最終状態を採用することにより、Ｍ2＝Ｍ0，Ｍ1を構築する。
【００８５】
マルチ集合のネストされたコンテンツ
以下の戦略を使用して、非順序ネストのコンテンツを認識するＭＦＡを生成することができる。
【００８６】
一般に、マルチ集合パターンは、以下の形式を持つものと見なすことができる。
【００８７】
【数１】
【００８８】
この表記では、入力コレクションをマッチングするマルチ集合ネスト演算子の内容に対して、各パターンエレメントＰiが少なくともｌi個の入力エレメントとマッチしなければならず、また、多くともｈi個の入力エレメントとマッチすることができる、ということが指定される。
【００８９】
マルチ集合パターンは、最初に変換されて任意の発生の制約が取り除かれる。上述のように指定されるマルチ集合パターンをＰとすると、パターンコンパイラは、以下のようにＰを等価なマルチ集合パターンＰ’に変換することができる。
Ｐ内の各エレメントパターン
【００９０】
【数２】
【００９１】
に対して、
ａ）Ｐ’にｐiのｌ1個のコピーを追加する。
これらのコピーをＰ’の要求されるパターンエレメントとする。
ｂ）ｈiが有限ならば、ｐ１＊をＰ’に追加する。
追加されたパターンをＰ’の非束縛パターンエレメントとする。
そうでなければ、ｐi？のｈi−ｌi個のコピーをＰ’に追加する。
これらのコピーをＰ’の選択的パターンエレメントとする。
リスト４ 変換マルチ集合パターン
パターンコンパイラは次に、パターンエレメント∪iｐiの和集合をマッチングするエレメントＭＦＡと呼ばれるプリプロセシングＭＦＡを構築する。第３に、パターンコンパイラは、置換ＭＦＡを構築する。置換ＭＦＡは、その入力上にプリプロセッサとしてエレメントＭＦＡを呼び出す。各呼び出しにおいて、エレメントＭＦＡは、どのｐiがカレント入力とマッチするかを示すタグを戻す。置換ＭＦＡは、要求されるパターンまたは選択的パターンとマッチする入力に遭遇すると、状態を変更する。状態変更は、要求されるパターンまたは選択的パターンをカウントする。置換ＭＦＡは、非束縛パターンに遭遇すると、カレント状態にループバックする。
【００９２】
置換ＭＦＡが、カウントオートマトンの形式であることは認識されるであろう。置換ＭＦＡは、そのプリプロセッサステップでの使用における他のカウントオートマトンとは異なる。図２は、置換ＭＦＡが入力をどのようにカウントするかを例示する。図２に例示されるＭＦＡ２００は、以下のパターンのネストされたコンテンツをマッチングする。
Ｐｏｎｄ＝Ｐｏｎｄ｛ｗａｔｅｒ，ｆｒｏｇ＋，ｃａｎｏｅ*，ｂｒｉｄｇｅ？｝
【００９３】
Ｒｅｐｅｔｉｔｉｏｎ（繰り返し）、Ｒｅｆｅｒｅｎｃｅ（参照）、Ｔｙｐｅ Ｐａｒａｍｅｔｅｒ（型引数）
リスト１の繰り返し構造を翻訳するには、パターンコンパイラでは、周知の技術を使用する。この構造を拡張して、繰り返されるパターンをマッチングして入力項目を蓄積する変数束縛を実装することができる。
【００９４】
記号参照を翻訳するには、パターンコンパイラが、記号のいくつかのクラス間を区別しなければならない。基本型すなわちリテラル記号ｓｙｍは、ｓｙｍに対する単一のローカル遷移として翻訳される。型引数ｐａｒａｍへの参照は、ｐａｒａｍに対する形式的遷移として翻訳される。形式的遷移は実行することができない。コンパイラは、形式的遷移を含むパラメータ化されたモジュールを生成することができるが、実行可能なモジュールを作成するためには、モジュールの形式的遷移に対して実際のパターンを与えることにより、パラメータ化されたモジュールをインスタンス化しなければならない。インスタンス化の間、コンパイラは、各形式的遷移の代わりに、対応する実際のパターンの翻訳を用いる。
【００９５】
パターンコンパイラは、パターンＰへの参照を、Ｐを参照した文脈に、Ｐを翻訳して変換することで代用して、翻訳する。知られているように、正規ツリーの文法は、ｎｅｘｔ演算子の文脈の外への再帰的な参照を許可しない。パターンコンパイラは、このプロパティと、ネストがコールとしてコンパイルされるという不変条件と、を組み合わせて、全てのインライン展開が、ネスト演算子またはパターン参照を含まないパターン等の基本事例に到達することを確実にすることができる。
【００９６】
例えば、図３は、以下の再帰的パターンに対する翻訳を例示する。
Ｅｘｐｒ＝ｃ｜ｐｌｕｓ［Ｅｘｐｒ，Ｅｘｐｒ］
図３では、各ノードがそのタグでラベル付けされる。図３には２つのモジュールが含まれ、それぞれ、３００および３１０で示され、Ｅｘｐｒ３００およびＰｌｕｓＮｅｓｔ３１０と名付けられる。Ｅｘｐｒ３００は、和集合をマッチングするためタグ長２を持つ。ＰｌｕｓＮｅｓｔ３１０はタグ長１を持つ。モジュールＥｘｐｒ３００は、ＭＦＡの開始状態を含み、ｃをマッチングすることにより、または、ＰｌｕｓＮｅｓｔ３１０を呼び出して、ＰｌｕｓＮｅｓｔからタグ１が復帰した時に、１０がタグ付けされた最終状態に継続することにより、Ｅｘｐｒパターンをマッチングする。ＰｌｕｓＮｅｓｔ３１０は、パターンＥｘｐｒの２つのインラインインスタンスを連接させることにより、パターンフラグメント［Ｅｘｐｒ，Ｅｘｐｒ］をマッチングする。Ｅｘｐｒのこれらのインライン展開は、ＰｌｕｓＮｅｓｔへの再帰的呼び出しを生み出す。非最終状態へつながるリターン遷移またはパスは示さない。
【００９７】
【００９８】
リスト６は、ＭＦＡを決定化するための構造を提供する。決定化を簡素化するために、コール遷移
（ｃ，Ｌａｂｅｌ，ε）→（ｃａｌｌＴａｒｇｅｔ，ｃ）
と、その関連する継続遷移
（ｃ，ε，ｔａｇ）→（ｃｏｎｔ，ε）
と、をネスト遷移と呼ばれるモジュール内遷移
（ｃ，（Ｌａｂｅｌ，ｃａｌｌＴａｒｇｅｔ，ｔａｇ），ε）→（ｃｏｎｔ，ε）
として組み合わせて表す。
この表現により、決定化メソッドでは遷移を均一に処理できるが、これはローカル遷移およびネスト遷移の両方がモジュール内遷移であるからである。リスト６の決定化メソッドにおける使用のために、関数Ｌａｂｅｌｓ（ｓ）が導入され、これにより、ｓから生じるネスト遷移において使用されるラベルの集合が生み出される。
【００９９】
トップレベルモジュールをＭとすると、決定化メソッドでは、以下の２つのステップを、ＮＦＡの決定化のためのクラスメソッドに追加する。第１に、ステップ２．ｃでは、ＣｏｍｂｉｎｅＮｅｓｔｓメソッドを使用して、状態ｔからのネスト遷移のコール対象を組み合わせる。第２に、ステップ４では、決定されたＭＦＡの最終状態Ｆ’の集合における各最終状態に対するタグを更新する。所与の最終状態ｆ’に対して、ステップ４では、ｆ’の要素であるＮＭＦＡの状態のタグ全体に亘って、ｆ’に対するタグをビットワイズ論理和に設定する。
【０１００】
決定化メソッドでは、サブルーチンとしてε閉包演算子Ｅ（ｓ）を使用する。状態をｓとすると、Ｅ（ｓ）は、ε遷移のみを含むパスによりｓから到達可能な状態の集合である。明確にするために、リスト６では、ワイルドカード遷移の扱いに関する詳細は省略する。状態ｔから生じるワイルドカード遷移を実装するために、ワイルドカード遷移に対するｍｏｖｅｓｅｔを、ｔから生じる各非ワイルドカード遷移のｍｏｖｅｓｅｔと組み合わせる。
【０１０１】
サブタイプ化
決定化の間、追加の記帳に労力を使ってタグを追跡するため、追加の記帳の利点が、１対のＭＦＡであるＭ0およびＭ1の比較において得られる。ＭＦＡを比較するためのプロシージャをリスト７に与える。
０．１対のＭＦＡをＭ0およびＭ1とし、Ｍ0およびＭ1により認識される値の集合間の包含関係を決定する。
１．Ｍ0またはＭ1の各状態ｑに対して、
Ｔａｇ（ｑ）≠０ならば、Ｔａｇ（ｑ）＝１を設定；
そうでなければ、Ｔａｇ（ｑ）＝０を設定；
２．Ｍ2＝Ｍ0∪Ｍ1を設定する。
（例えば、和集合の構造では、Ｍ0の最終状態にタグ０１を割り当て、Ｍ1の最終状態にタグ１０を割り当てる）
３．Ｄｅｔｅｒｍｉｎｉｚｅ（Ｍ２）の最終状態にある異なるタグの集合にＣを設定する。
表１のＣの値を調べることによりＭ０とＭ１との関係を求める。
リスト７ ＭＦＡ比較アルゴリズム
【０１０２】
重要な目的は、決定化プロシージャが、最終状態にあるタグを介して、Ｍ0およびＭ1が同時にアクセスされるのか、および、Ｍ0またはＭ1または両方がお互いに無関係にアクセスされるのか、について追跡することである。表１ｘｘｘｘを使用して、比較の結果に対して、Ｍ0およびＭ1の決定化された和集合における最終状態に存在するタグ値の集合Ｃをマップすることができる。図５は、表１に列挙される可能性のあるサブタイプ関係の図式的な例示である。
【０１０３】
【表１】
【０１０４】
図５は、等価５００関係、サブタイプ５１０関係、スーパータイプ５２０関係、互いに素５３０関係、および交わり５４０関係、のそれぞれを示す。
補集合、共通集合、差
追加の利点が、上述したタグの記帳から得られる。タグを使用して、ＭＦＡの補集合、共通集合、および差のためのプロシージャを実装することができる。共通集合Ｍ0∧Ｍ1を構成するために、共通集合構造はまず、決定化された和集合Ｉ＝Ｄｅｔｅｒｍｉｎｉｚｅ（Ｍ0∪Ｍ1）を計算し、次に、タグ１１を持つ最終状態が到達可能できない各状態ｔをＩから除去する。
【０１０５】
この計算の結果、ＭＦＡである、状態を持たないＩが得られた場合は、単一の非アクセス開始状態がＩに加えられ、Ｉは入力にアクセスしないＭＦＡとなる。
【０１０６】
同様の構造を使用して、Ｍ0−Ｍ1を計算することができる。そのようにするには、上記の交わりの構造においてタグ１１の代わりにタグ０１を用いる。Ｍ1−Ｍ0を計算するために、構造内にタグ１０を使用する。
【０１０７】
¬Ｍ、すなわちＭの補集合、を構築するには、補集合構造はまず、Ｍ’＝Ｄｅｔｅｒｍｉｎｉｚｅ（Ｍ）を計算する。次に、Ｍ’の各最終状態ｆに対して、構造は、ｆのタグを０に設定し、ｆを非最終とする。元のＭ’の各非最終状態ｎｆに対して、構造は、ｎｆのタグを１に設定し、ｎｆを最終とする。タグが調節されたＭ’は¬Ｍを受容する。
【０１０８】
この構造の重要な態様は、呼び出されたモジュールにより戻されたゼロのタグに対する遷移が最終状態につながるということである。ゼロのタグに対して暗黙的遷移を使用することにより空間を確保するＭＦＡの実装では、これらの遷移を補集合に対する明示的遷移に変換する方法を持たなければならない。
セマンティックアクションの順序付け
特定の本発明の実施形態の利点により、パターンコンパイラが、セマンティックアクションを任意のＮＭＦＡの遷移に置くことが可能にされる。この柔軟性をサポートするために、決定化の間、セマンティックアクションの順序を保持するための方法が必要とされる。ＮＭＦＡであるＭの全てのパス［ｔｒ1，ｔｒ2，．．．，ｔｒn］に対して、ｉ＜ｊの時に限りＡｃｔｉｏｎ（ｔｒi）はＡｃｔｉｏｎ（ｔｒj）の前に実行される、というプロパティを保持することは有益である。このプロパティを保持するために、ＭのパスがＤｅｔｅｒｍｉｎｉｚｅ（Ｍ）の遷移と関連付けられる。
【０１０９】
これを達成するために、決定性ＭＦＡの基本パス
Ｍ’＝Ｄｅｔｅｒｍｉｎｉｚｅ（Ｍ）
が、ローカル遷移またはネスト遷移のシーケンス［ｔｒ1，ｔｒ2，．．．，ｔｒn］として定義され、各遷移ｔｒi＝（ｑi，ｓｙｍ，ε）→（ｑi+1，ε）に対して、ｑi+1が入力遷移を１つだけ持つ、ｉ＝０、またはｉ＋１＝ｎ、のいずれかであるとする。この定義の目的のため、Ｍ’の開始状態は、暗黙的入力遷移を持つと考える。
【０１１０】
Ｍ’の基本パスは、複数の入力遷移を持つ状態で開始および終了することができる。しかし、基本パス中の任意の中間状態は、厳密に１つの遷移のみを持たなければならない。このプロパティから導かれる結果は、基本パスの最終遷移ｔｒnが一意的にこの基本パスを識別するということである。
【０１１１】
この結果は、各基本パスｂｐの最終遷移ｔｒnに、ｂｐに対応するＮＭＦＡのパスの集合ｎｐから順番に集められるセマンティックアクションのシーケンスの集合Ａを割り当てることにより、使用される。ＭＦＴは、ｂｐの遷移ｔｒnを実行する時に、Ａの各要素をも実行する。
【０１１２】
Ｍ’の所与の基本パスｂｐに対して、Ｍからの対応するパスｎｐの集合が、以下の方法で求められる。まず、ｂｐ内の各遷移ｔｒiに対して、ｔｒiに対応するＮＭＦＡの遷移を求める。ＮＭＦＡの遷移
ｎｔｒ＝（ｒ1，ｓｙｍ，ε）→（ｒ2，ε）
は、ｒ1∈ｑiかつｒ2∈ｑi+1である限り、ｔｒiに対応する。
【０１１３】
ｔｒiに対応する各ＮＭＦＡの遷移に対して、ＮＭＦＡのパスは、ｎｐａｔｈi＝ｐａｔｈa，ｎｔｒ，ｐａｔｈb（ここで、ｐａｔｈaは以下のプロパティを持つ）であるように構築される。第１に、ｐａｔｈaは全て、最初の状態と最後の状態がｑi内にあるε遷移から成る。第２に、ｐａｔｈaの第１の状態は、ｑi内に先行するものを持たない。最後に、ｐａｔｈaの最終的な状態は、遷移ｎｔｒの最初の状態である。同様に、ｐａｔｈbは全て、最初の状態と最後の状態がｑi+1内にあるε遷移から成り、ｐａｔｈbは、ｎｔｒの最後の状態で始まる。
【０１１４】
順に、ＮＭＦＡのパスは、ｂｐ内の何らかの遷移に対応する全てのサブパスを一続きにすることにより、基本パスｂｐに従って構築される。ｂｐの各遷移が、対応するＮＭＦＡの遷移を１つしか持たない場合、これらのサブパスは、単一のＮＭＦＡパスを形成するであろう。しかし、ｂｐのいくつかの遷移が、対応するＮＭＦＡの遷移を複数持つ場合、ｎｐａｔｈaの最終的な状態がｎｐａｔｈbの第１の状態となるＮＭＦＡのサブパスの対（ｎｐａｔｈa、ｎｐａｔｈb）を連結することにより、サブパスを組み合わせることができる。所与のＮＭＦＡのサブパスが、複数のそのような対に関与することができ、そのため、所与の基本パスに対応するいくつかのＮＭＦＡのパスは、共通のプレフィックスを共有することができる。
【０１１５】
図６および７は、パターン
ＧＴＥ＝ＧＴＥ［ａｎｙ，０］｜ＧＴＥ［０，Ｓ［ａｎｙ］］
のネストされたコンテンツに対する構造化されたＮＭＦＡ６００と、その決定された等価物７００との間の対応をそれぞれ示す。これらの図におけるＭＦＡには、表２で記載したように、シフトアクションおよび受容アクションが含まれる。図６では、記号ｅを使用してε遷移を表す。図７は、ＮＭＦＡのパスのそれぞれからのアクションシーケンス７００が、どのように集められ、かつ、決定されたＭＦＡの基本パスを終了させる遷移にどのように割り当てられたか、を例示する。これらの遷移はまた、それらに割り当てられたＮＭＦＡのパスでラベル付けされる。
【０１１６】
図７はまた、ワイルドカードａｎｙに対する翻訳の視点を与える。ＧＴＥに対して決定されたＭＦＡでは、ｏｔｈｅｒｗｉｓｅでラベル付けされる遷移を使用して、ワイルドカードを翻訳する。この翻訳はデフォルト翻訳と呼ばれ、他の翻訳が適用されない場合に実行される。状態ｓから開始されるワイルドカード遷移の対象状態ｔが、ｓからのデフォルト翻訳のｍｏｖｅｓｅｔに追加される。加えて、ｔが、ｓからの任意の非ワイルドカード遷移のｍｏｖｅｓｅｔに追加される。
【０１１７】
最後に、図７は、セマンティックアクションの順序付けを簡素化するリターン遷移を表すための技術を例示する。リターン遷移は、フォレスト終了（］）に対するローカル遷移として見ることができる。これらのローカル遷移は、セマンティックアクションのプレースホルダとなることができる。本明細書において記載するパターンコンパイラは、この技術を使用する。
【０１１８】
置換ＭＦＡの最適化
異なる入力順序を明らかにするため、置換ＭＦＡは、多数の遷移を持つことができる。置換ＭＦＡにおける遷移の数を減らすためには、パターンコンパイラは、タグオーダと呼ばれる半順序を、エレメントＭＦＡに対応するタグに割り当てることができる。コンパイラは次に、置換ＭＦＡから適切でないパスを削除することができ、ランタイムシステムが次の２つの戦略の内の１つを使用して入力フォレストをマッチングすることを予測する。第１の戦略として、ランタイムシステムは、入力コレクション全体にインデックスを使用して、要求されるパターンエレメントとマッチするであろう項目を抽出することができる。第２の戦略として、ランタイムシステムは、エレメントＭＦＡを使用して、入力フォレストを前処理することができ、そして、その結果をエレメントＭＦＡのタグオーダに従ってソートすることができる。
【０１１９】
第１の戦略は、パターンエレメントの１つがワイルドカードａｎｙ＊である場合に良く機能する。このシナリオにおいて、ランタイムシステムは、インデックスを使用してタグオーダで、要求されるパターンエレメントを「チェリーピック（良いものだけを選択）」し、残りの入力フォレストの項目をワイルドカードパターンエレメントに割り当てることができる。
【０１２０】
第２の戦略では、減少したメモリの使用と、ソートのために潜在的に増加するマッチングの時間とを交換する。置換ＭＦＡは、ラベル付き有向グラフの変換に使用すると、典型的には、入力フォレストのかなりの部分を変数に対して束縛することができる。さらに、マルチ集合パターンのユーザにおいては、マッチング操作から変数束縛の複数の集合が明らかにされることを期待することができる。これらのシナリオにおいて、ランタイムシステムは、入力フォレストのコピーを保持しなければならず、従ってソートをサポートすることになる。
【０１２１】
パターンエレメントの集合をＰとすると、対応するプリプロセッサＭＦＡのタグの全順序は、以下のように導き出すことができる。まず、パターンエレメントを順序付ける。Ｐにおける１対のパターンエレメントを（ｐi，ｐj）とすると、ｐiが要求されかつｐjが要求されない場合、または、ｐiが選択肢でありかつｐjが非束縛である場合、または、ｐiがｐjより高い優先度を持つ場合に、ｐi＜ｐjを定義する。優先度が割り当てられていない場合、優先度を辞書順に割り当て、パターンエレメント間に全順序をつける。
【０１２２】
決定化の際、プリプロセッサＭＦＡは、１つまたは複数のパターンエレメントの集合の受容を示すタグを持つ。そのような１対のタグを（ｔi、ｔj）とすると、ｍｉｎ（ｔi）＜ｍｉｎ（ｔj）ならば、ｔi＜ｔjである。ｔiおよびｔjが同じ最小エレメントを持つ場合、｜ｔi｜＞｜ｔj｜ならばｔi＜ｔjである。この最後の規則は、置換 ＭＦＡにより、いくつかのパターンエレメントとマッチする最初の入力が考慮されることを確実にする。図４は、Ｐｏｎｄパターン
Ｐｏｎｄ＝Ｐｏｎｄ｛ｗａｔｅｒ，ｆｒｏｇ＋，ｃａｎｏｅ*，ｂｒｉｄｇｅ？｝
に対するＭＦＡ４００ついてのタグオーダの最適化の効果を例示する。
【０１２３】
ＭＦＡの実装
ＭＦＡおよびＭＦＴの特定の実装において、トランスデューサと呼ばれるこれらのオートマトンのインスタンスを実装するランタイムシステムがある。別の実施形態において、パターンコンパイラは、正規ツリーパターンをトランスデューサに変換し、変数束縛と、条件のマッチングと、セマンティックアクションと、を実装する命令でトランスデューサの遷移を拡張する。特定の実施形態は、少なくとも４つの応用に適用することができる。すなわち、主張に基づく権限付与サービス、プロトコルモデル検査アプリケーション、ＸＭＬスキーマインスタンスをインポート、サブタイプ化、マッチングするためのシステム、およびクエリ表現のためのコンパイラ、である。
【０１２４】
特定の実施形態の実際の評価として、１秒当たり２４０万から８９０万ノードのレートでラベル付き有向グラフをマッチングするトランスデューサランタイムが得られた。さらに、このトランスデューサランタイムは、１秒当たり６０万から２１０万ノードのレートでラベル付き有向グラフを変換することができた。
ランタイム
【０１２５】
各変換規則
ｒｕｌｅ＝ｐａｔｔｅｒｎ，ａｃｔｉｏｎ
に対して、パターンコンパイラは、フレームテンプレートを作成する。フレームテンプレートは、規則で束縛される各変数のためのスロットを特定し、さらに、追加のスロットを特定してアクションを適用した結果を保持する。ランタイム時、トランスデューサ機構は、各規則ｒに対してフレームコレクションのスタックを割り当てることができる。各規則ｒに対するフレームコレクションは、ｆに対するフレームテンプレートにより記載される配置を持つ０個以上のフレームを含む。フレームコレクションは、複数のフレームを含むことができるが、それは、マルチ集合パターンが、その入力を複数の方法でマッチングすることができ、変数束縛の複数の集合を生み出すからである。フレームコレクションをスタックさせて、再帰を操作することができる。
トランスデューサの命令
【０１２６】
【表２】
【０１２７】
トランスデューサの状態遷移は、トランスデューサの命令のシーケンスであるアクションブロックを参照することができる。トランスデューサの命令の組には、表２に与えられる命令が含まれる。表２において、ｒでラベル付けされるオペランドは、文法規則を参照する。ｒ．ｘでラベル付けされるオペランドは、ｒの規則コレクションスタックの最上部にある規則フレーム内の変数ｘのスロットを参照する。ｉでラベル付けされるオペランドは、命令を参照する。ｔでラベル付けされるオペランドは、受容された規則の集合を示すタグを参照する。ｂでラベル付けされるオペランドは、アクションブロックの集合を参照する。
【０１２８】
明示的なオペランドに加えて、命令には、シフト型およびシフト規則を含むこともできる。シフト型は、変換エンジンがフォレスト内で次の項目にどのように移動すべきかを示す。シフト型がＳＨＩＦＴ ＮＥＳＴである場合、変換エンジンは、次のツリーノードに移る前にカレントツリーノードの後継ノードを書き換える。シフト規則は、（ネストパターンがマッチングしたものの中で）どの規則を書き換えるべきかを示す。
【０１２９】
表２の最初の４つの命令は、フレーム更新命令と呼ばれ、なぜなら、ある規則ｒについて、ｒのコレクションスタック上の各フレームに対して、変数ｒ．ｘのスロットを更新する。
【０１３０】
Ｅｘｅｃ命令は、ｒのコレクションスタックからトップのコレクションをポップさせる。ポップされたコレクションの各フレームに対して、Ｅｘｅｃ命令は、ｒに関連する書き換えアクションを実行する。それぞれの結果に対して、Ｅｘｅｃ命令は、ある変数ｔａｒｇｅｔ．ｘを更新するフレーム更新命令ｉを実行する。再帰の場合、ｔａｒｇｅｔはｒと同じ規則となる。
【０１３１】
Ｐｕｓｈ命令は、新しい規則コレクションをｒに対する規則コレクションスタックにプッシュする。Ｐａｒ命令は、アクションブロックの集合を並行して実行する。集合内の各アクションブロックに対して、Ｐａｒ命令は、カレント入力ノードを用いて開始される。集合内の各アクションブロックは、入力ポインタを同量進ませなければならない。変換エンジンは、並行するブロックの各要素を必ずしも実行するわけではない。各並行するブロックの要素は、規則識別子で示すことができる。トランスデューサは、トランスデューサが現在書き換えている規則用の識別子で示される、並行するブロックの要素のみを実行する。
【０１３２】
Ｓｈｉｆｔ命令は、トランスデューサを次の入力項目に進ませる。パターンコンパイラは、カレントパターン位置に関連する変数束縛が無い場合に、この命令を生成する。パターン位置が変数束縛を持つ場合は、コンパイラはその代わりに、シフト情報をフレーム更新命令の一部として与える。
【０１３３】
応用
特定の権限付与のポリシーエンジン（Ｔｈｏｒと呼ばれる）では、データアクセス要求の主張に基づく権限付与をサポートする権限付与ロジックを使用する。Ｔｈｏｒは、主張の大きなデータベースを備え、例えば、ａ／ｄｎｓ＝？ｘ−＞ｂ／ｄｎｓ＝？ｘ（これは、ａが、プロパティｄｎｓは変数ｘに対して束縛される値を持つ、と主張する場合、ｂが同じ主張を行う、ということを表す）という主張のような論理で表される。主張ａ／ｄｎｓ＝”ＬｏｃａｌＨｏｓｔ”は、ａが、プロパティｄｎｓに値”ＬｏｃａｌＨｏｓｔ”が割り当てられる、と主張することを示す。全てのそのような主張は、主張データベースにおいて非順序表として表され、主構とプロパティによりインデックスが付けられる。
【０１３４】
権限付与のポリシーエンジンは、構造的規約を使用してその主張データベースを非順序フォレストとして表す。主張を処理するためにまず、主張を、形式ｐｒｏｖｅ［ｃｏｎｔｅｘｔ｛ｄａｔａｂａｓｅ｝，ｇｏａｌ］のツリーに変換する。次に、エンジンは、規則の集合を使用して、定点に到達するまで主張を繰り返し変換する。エンジンが主張を証明することができる場合、主張は、証明においてステップを識別する証明木に変換される。
【０１３５】
パターンコンパイラは、エンジンの規則をトランスデューサに翻訳することができる。探索プロシージャは、このトランスデューサを呼び出して、各変換ステップを実行する。規則は、構成的論理の順次計算を実装し、デリゲーション演算子の分散規則で拡張される。この論理における典型的な規則は、以下のものである。
【０１３６】
ＩｍｐｌｉｅｓＣｏｎｄｉｔｉｏｎＭｅｔ＝
ｐｒｏｖｅ［
ｃｏｎｔｅｘｔ｛ｔｙｐｅｄＴｅｒｍ［ｐｒｏｏｆｌ：ａｎｄｙ，ａ：ａｎｙ］，
ｔｙｐｅｄＴｅｒｍ［ｐｒｏｏｆ２：ａｎｙ，ｉｍｐｌｉｅｓ［ａ：ａｎｙ，ｂ：ａｎｙ］］，
ｒｅｓｔ：ａｎｙ*｝，
ｇｏａｌ：ａｎｙ］
＝＝＞
ｐｒｏｖｅ［
ｃｏｎｔｅｘｔ｛ｒｅｓｔ，
ｔｙｐｅｄＴｅｒｍ［ｐｒｏｏｆｌ：ａｎｙ，ａ：ａｎｙ］，
ｔｙｐｅｄＴｅｒｍ［ａｐｐｌｙ［ｐｒｏｏｆ２：ａｎｙ，ｐｒｏｏｆｌ：ａｎｙ］，ｂ：ａｎｙ］｝，
ｇｏａｌ：ａｎｙ］；
【０１３７】
エンジンは、本明細書において上記に記載したインデックス付けおよびタグオーダソートを使用して、かなりのスループット（ある例では、１秒当たり２３，０００個の主張と計測された）を達成する。これにより、主張処理が、権限付与サービス全体の速度を制限する工程となってしまうことを防ぐという、可能性のある利点がもたらされる。
【０１３８】
別の応用は、処理モデルチェッカである。そのようなモデルチェッカは、シンプルな反転ビットプロトコルからＴＣＰ（通信制御プロトコル）のモデルにまで及ぶプロトコルに適用することができる。モデルチェッカは、デッドロックフリー型プロトコルを検査することができる。モデルチェッカは、多くの結果を産出する、リスト２の相互作用パターン等のパターンを使用する。そのような場合、トランスデューサは、数フレームに相当する変数束縛を、書き換えの度にバッファすることができる。
【０１３９】
別の実施形態は、ＸＭＬスキーマをインポート、認可、およびサブタイプ化する応用に適用される。この実施形態は、ＸＭＬスキーマを半順序ツリーパターンにインポートする。そのような応用では、バッチモードおよび相互作用モードの両方において機能する。相互作用モードにおいて、この応用を、パターンをコンピュータアプリケーションに組み込むためのオーサリングシステムの一部として採用することができる。
【０１４０】
さらに別の実施形態は、クエリ表現のためのコンパイラコンポーネントに適用された。そのようなコンポーネントは、ＳＱＬなどのようなデータベースのクエリアプリケーションのフロントエンドとして使用することができる。このコンポーネントは、規則の集合を使用して、クエリ表現Ｑを包括的な代数に翻訳し、代数的表現を定点に変換する第２の規則の集合を使用することによりＱを最適化する。
【０１４１】
本明細書において記載する実施形態の最適化も可能である。例えば、パターンコンパイラは、束縛された変数間の依存性を認識し、それらの依存性を使用してマッチングを駆動することができる。コンパイラは、上記に示す意味合いでこの最適化をパターンに対して使用することができる。入力フォレストから、パターンエレメント
ｔｙｐｅｄＴｅｒｍ［ｐｒｏｏｆ２：ａｎｙ，ｉｍｐｌｉｅｓ［ａ：ａｎｙ，ｂ：ａｎｙ］］
とマッチする入力項目を抽出することにより、生成されたトランスデューサは、パターンエレメント
ｔｙｐｅｄＴｅｒｍ［ｐｒｏｏｆ１：ａｎｄｙ，ａ：ａｎｙ］
に対する可能性のあるマッチングを制約することができる。
【０１４２】
モジュラフォレストオートマトンは、半順序正規ツリーパターンについての統一された記載を提供する。ＭＦＡはまた、これらのパターンの決定化、サブタイプ化、交わり、および相補のための簡素なアルゴリズムを提供する。実際には、モジュラフォレストオートマトンは、高性能のパターン分析およびマッチングをサポートする。モジュラフォレストトランスデューサにより、コンパイラが、セマンティックアクションを任意の状態遷移におくことが可能にされ、一方でラベル付き有向グラフの効率的な変換がサポートされる。
【０１４３】
本発明は、その精神または主要な特徴から逸脱することなく他の特定の形式において具現化することができる。記載される実施形態は、あらゆる点において単に例示としてみなされ、制限するものとしてみなされない。従って、本発明の範囲は、前述の記載によるのではなく、添付の請求項により示される。請求項と等価の意味および範囲に入る全ての変更は、請求項の範囲に包含される。
【特許請求の範囲】
【請求項１】
コンピュータ環境（１００）において正規ツリーパターン（２００）を分析するための方法であって、前記コンピュータ環境が少なくとも１つのコンピュータプロセッサおよび少なくとも１つのコンピュータ可読メモリを備え、
シーケンスおよび集合の内の少なくとも１つを備える正規ツリーパターンを備えるデータを受け取るステップ（８１０）と、
前記ツリーパターンがシーケンスを備える場合、シーケンスに対応する第１のマシンを決定するステップ（８２０）と、
前記ツリーパターンが集合を備える場合、集合に対応する第２のマシンを決定するステップ（８３０）と、
前記第１のマシンと第２のマシンとの和集合を作成するステップ（８４０）と、
前記マシンの和集合に対するラベル付き受容状態の集合を決定するステップ（８５０）と、
前記ラベル付き受容状態から前記第１のマシンと第２のマシンとに対するサブタイプ関係を決定するステップ（８６０）と
を含むことを特徴とする方法。
【請求項２】
ラベル付きネストへの少なくとも１つの遷移を備えるルートレベルマシンを決定するステップと、
前記ラベル付きネストに対応するモジュールを作成するステップと、
前記ラベル付きネストの復帰に対応する継続状態をスタック上に置くステップと、
前記ラベル付きネストに対応するアクションを実行するステップと、
前記ラベル付きネストに対する受容状態に到達する時、前記スタックから継続状態をポップさせ、かつ、前記ルートレベルマシンに対する処理を再開するステップと
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
当該受け取られたデータが、プログラミング言語で構造型を定義するデータに対応することを特徴とする請求項１に記載の方法。
【請求項４】
当該受け取られたデータが、データベースのスキーマを備えるデータに対応することを特徴とする請求項１に記載の方法。
【請求項５】
当該受け取られたデータが、ＸＭＬスキーマに対応することを特徴とする請求項１に記載の方法。
【請求項６】
正規ツリーパターン（２００）を分析するためのコンピュータ実行可能命令を符号化して有するコンピュータ可読媒体（１５０）を備えるコンピュータプログラム製品であって、前記コンピュータ実行可能命令は、
シーケンスおよび集合の内の少なくとも１つを備える正規ツリーパターンを備えるデータを受け取るステップ（８１０）と、
前記ツリーパターンがシーケンスを備える場合、シーケンスに対応する第１のマシンを決定するステップ（８２０）と、
前記ツリーパターンが集合を備える場合、前記集合に対応する第２のマシンを決定するステップ（８３０）と、
前記第１のマシンと第２のマシンとの和集合を作成するステップ（８４０）と、
前記マシンの和集合に対するラベル付き受容状態の集合を決定するステップ（８５０）と、
前記ラベル付き受容状態から前記第１のマシンと第２のマシンとに対するサブタイプ関係を決定するステップ（８６０）と
を含む方法をコンピュータ環境（１００）に実行させることを特徴とするコンピュータプログラム製品。
【請求項７】
ラベル付きネストへの少なくとも１つの遷移を備えるルートレベルマシンを決定するステップと、
前記ラベル付きネストに対応するモジュールを作成するステップと、
前記ラベル付きネストの復帰に対応する継続状態をスタック上に置くステップと、
前記ラベル付きネストに対応するアクションを実行するステップと、
前記ラベル付きネストに対する受容状態に到達する時、前記スタックから継続状態をポップさせ、かつ、前記ルートレベルマシンに対する処理を再開するステップと
をさらに含むことを特徴とする請求項６に記載のコンピュータプログラム製品。
【請求項８】
当該受け取られたデータが、プログラミング言語で構造型を定義するデータに対応することを特徴とする請求項６に記載のコンピュータプログラム製品。
【請求項９】
当該受け取られたデータが、データベースのスキーマを備えるデータに対応することを特徴とする請求項６に記載のコンピュータプログラム製品。
【請求項１０】
当該受け取られたデータが、ＸＭＬスキーマに対応することを特徴とする請求項６に記載のコンピュータプログラム製品。
【請求項１１】
コンピュータ環境（１００）において正規ツリーパターン（２００）の変換を表現するための方法であって、前記コンピュータ環境は少なくとも１つのコンピュータプロセッサ（１１０）および少なくとも１つのコンピュータ可読メモリ（１２０）を備え、前記方法は、
正規ツリーパターンに対応する第１のデータを受け取るステップ（９１０）と
実際のインスタンスに対応する第２のデータを受け取るステップ（９２０）と、
前記正規ツリーパターンをトランスデューサにコンパイルするステップ（９３０）と、
前記トランスデューサの遷移を所望の変換に対応する命令で拡張するステップ（９４０）と、
前記拡張されたトランスデューサの遷移と前記第２のデータとから、第２のデータのエレメントと前記正規ツリーパターンのエレメントとの間の依存性を決定するステップ（９５０）と
を含むことを特徴とする方法。
【請求項１２】
前記命令が変数束縛を含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記命令が条件のマッチングを含むことを特徴とする請求項１１に記載の方法。
【請求項１４】
前記命令がセマンティックアクションを含むことを特徴とする請求項１１に記載の方法。
【請求項１５】
前記第２のデータがＸＭＬスキーマインスタンスを含むことを特徴とする請求項１１に記載の方法。
【請求項１】
コンピュータ環境（１００）において正規ツリーパターン（２００）を分析するための方法であって、前記コンピュータ環境が少なくとも１つのコンピュータプロセッサおよび少なくとも１つのコンピュータ可読メモリを備え、
シーケンスおよび集合の内の少なくとも１つを備える正規ツリーパターンを備えるデータを受け取るステップ（８１０）と、
前記ツリーパターンがシーケンスを備える場合、シーケンスに対応する第１のマシンを決定するステップ（８２０）と、
前記ツリーパターンが集合を備える場合、集合に対応する第２のマシンを決定するステップ（８３０）と、
前記第１のマシンと第２のマシンとの和集合を作成するステップ（８４０）と、
前記マシンの和集合に対するラベル付き受容状態の集合を決定するステップ（８５０）と、
前記ラベル付き受容状態から前記第１のマシンと第２のマシンとに対するサブタイプ関係を決定するステップ（８６０）と
を含むことを特徴とする方法。
【請求項２】
ラベル付きネストへの少なくとも１つの遷移を備えるルートレベルマシンを決定するステップと、
前記ラベル付きネストに対応するモジュールを作成するステップと、
前記ラベル付きネストの復帰に対応する継続状態をスタック上に置くステップと、
前記ラベル付きネストに対応するアクションを実行するステップと、
前記ラベル付きネストに対する受容状態に到達する時、前記スタックから継続状態をポップさせ、かつ、前記ルートレベルマシンに対する処理を再開するステップと
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
当該受け取られたデータが、プログラミング言語で構造型を定義するデータに対応することを特徴とする請求項１に記載の方法。
【請求項４】
当該受け取られたデータが、データベースのスキーマを備えるデータに対応することを特徴とする請求項１に記載の方法。
【請求項５】
当該受け取られたデータが、ＸＭＬスキーマに対応することを特徴とする請求項１に記載の方法。
【請求項６】
正規ツリーパターン（２００）を分析するためのコンピュータ実行可能命令を符号化して有するコンピュータ可読媒体（１５０）を備えるコンピュータプログラム製品であって、前記コンピュータ実行可能命令は、
シーケンスおよび集合の内の少なくとも１つを備える正規ツリーパターンを備えるデータを受け取るステップ（８１０）と、
前記ツリーパターンがシーケンスを備える場合、シーケンスに対応する第１のマシンを決定するステップ（８２０）と、
前記ツリーパターンが集合を備える場合、前記集合に対応する第２のマシンを決定するステップ（８３０）と、
前記第１のマシンと第２のマシンとの和集合を作成するステップ（８４０）と、
前記マシンの和集合に対するラベル付き受容状態の集合を決定するステップ（８５０）と、
前記ラベル付き受容状態から前記第１のマシンと第２のマシンとに対するサブタイプ関係を決定するステップ（８６０）と
を含む方法をコンピュータ環境（１００）に実行させることを特徴とするコンピュータプログラム製品。
【請求項７】
ラベル付きネストへの少なくとも１つの遷移を備えるルートレベルマシンを決定するステップと、
前記ラベル付きネストに対応するモジュールを作成するステップと、
前記ラベル付きネストの復帰に対応する継続状態をスタック上に置くステップと、
前記ラベル付きネストに対応するアクションを実行するステップと、
前記ラベル付きネストに対する受容状態に到達する時、前記スタックから継続状態をポップさせ、かつ、前記ルートレベルマシンに対する処理を再開するステップと
をさらに含むことを特徴とする請求項６に記載のコンピュータプログラム製品。
【請求項８】
当該受け取られたデータが、プログラミング言語で構造型を定義するデータに対応することを特徴とする請求項６に記載のコンピュータプログラム製品。
【請求項９】
当該受け取られたデータが、データベースのスキーマを備えるデータに対応することを特徴とする請求項６に記載のコンピュータプログラム製品。
【請求項１０】
当該受け取られたデータが、ＸＭＬスキーマに対応することを特徴とする請求項６に記載のコンピュータプログラム製品。
【請求項１１】
コンピュータ環境（１００）において正規ツリーパターン（２００）の変換を表現するための方法であって、前記コンピュータ環境は少なくとも１つのコンピュータプロセッサ（１１０）および少なくとも１つのコンピュータ可読メモリ（１２０）を備え、前記方法は、
正規ツリーパターンに対応する第１のデータを受け取るステップ（９１０）と
実際のインスタンスに対応する第２のデータを受け取るステップ（９２０）と、
前記正規ツリーパターンをトランスデューサにコンパイルするステップ（９３０）と、
前記トランスデューサの遷移を所望の変換に対応する命令で拡張するステップ（９４０）と、
前記拡張されたトランスデューサの遷移と前記第２のデータとから、第２のデータのエレメントと前記正規ツリーパターンのエレメントとの間の依存性を決定するステップ（９５０）と
を含むことを特徴とする方法。
【請求項１２】
前記命令が変数束縛を含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記命令が条件のマッチングを含むことを特徴とする請求項１１に記載の方法。
【請求項１４】
前記命令がセマンティックアクションを含むことを特徴とする請求項１１に記載の方法。
【請求項１５】
前記第２のデータがＸＭＬスキーマインスタンスを含むことを特徴とする請求項１１に記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公表番号】特表２０１２−５１３０４６（Ｐ２０１２−５１３０４６Ａ）
【公表日】平成２４年６月７日（２０１２．６．７）
【国際特許分類】
【出願番号】特願２０１１−５３００８１（Ｐ２０１１−５３００８１）
【出願日】平成２１年８月２０日（２００９．８．２０）
【国際出願番号】ＰＣＴ／ＵＳ２００９／０５４４５７
【国際公開番号】ＷＯ２０１０／０３９３４８
【国際公開日】平成２２年４月８日（２０１０．４．８）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
【公表日】平成２４年６月７日（２０１２．６．７）
【国際特許分類】
【出願日】平成２１年８月２０日（２００９．８．２０）
【国際出願番号】ＰＣＴ／ＵＳ２００９／０５４４５７
【国際公開番号】ＷＯ２０１０／０３９３４８
【国際公開日】平成２２年４月８日（２０１０．４．８）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
[ Back to top ]