(57)【要約】  【課題】  プログラム解析において、プログラムの実行がそのコードに到達するまでの実行条件を効率よく抽出する方法およびそのシステムを提供し、プログラム解析の作業効率を向上させる。  【解決手段】  処理対象のプログラムを解析して、着目するコードに至るまでの条件および状態変化をノードとする条件依存グラフを作成するグラフ作成部１０と、このグラフ作成部１０により作成された条件依存グラフの中で、所定のノードに対応する条件によってパスが複数に分かれた後に再度一つのノードへ合流する部分である完全部分グラフを対象とし、この完全部分グラフの複数のノードに対応する複数の条件および状態変化を１または複数の状態変化の集合に置き換え、この状態変化の集合に対応するノードを通る１本のパスで表される部分グラフに変換するグラフ抽象化部２０とを備える。  【選択図】  図１
2006178835.tif 000002
【特許請求の範囲】
【請求項１】
処理対象のプログラムを解析して、着目するコードに至るまでの条件および状態変化をノードとする条件依存グラフを作成するグラフ作成部と、
前記グラフ作成部により作成された前記条件依存グラフの中で、所定のノードに対応する条件によってパスが複数に分かれた後に再度一つのノードへ合流する部分である完全部分グラフを対象とし、当該完全部分グラフの複数のノードに対応する複数の条件および状態変化を１または複数の状態変化の集合に置き換え、当該状態変化の集合に対応するノードを通る一本のパスで表される部分グラフに変換するグラフ抽象化部と
を備えることを特徴とするプログラム解析装置。
【請求項２】
前記グラフ作成部は、前記条件依存グラフ中に、所定の一つのノードの次に位置する複数のノードに対応する条件の論理和が常に真であってかつ排他的な分岐があり、さらに分岐先の一方がプログラムの実行を終了する終了命令に至る場合、分岐点から終了命令に至るパスを除去することを特徴とする請求項１に記載のプログラム解析装置。
【請求項３】
前記グラフ作成部は、前記終了命令に至るパスを含む分岐の他方のパスが、他の所定のパスと共に前記完全部分グラフを構成する場合に、当該完全部分グラフの始点のノードから前記終了命令までの条件の否定条件を当該始点のノードの条件とすることを特徴とする請求項２に記載のプログラム解析装置。
【請求項４】
前記グラフ作成部は、プログラムの各命令文を順次探索して前記条件依存グラフのノードおよびパスを作成していき、着目した命令文が条件分岐文である場合、当該条件分岐文の前後に何も行わない命令文があるものとして条件依存グラフを作成することを特徴とする請求項１に記載のプログラム解析装置。
【請求項５】
前記グラフ抽象化部により変換された条件依存グラフに対し、当該条件依存グラフに記載される状態変化を適用してルールツリーを生成するルールツリー生成部をさらに備えることを特徴とする請求項１に記載のプログラム解析装置。
【請求項６】
前記ルールツリー生成部により生成された前記ルールツリーに基づいてソースコードを生成する計算ルール生成部をさらに備えることを特徴とする請求項５に記載のプログラム解析装置。
【請求項７】
処理対象のプログラムを解析して、着目するコードに至るまでの条件および状態変化をノードとする条件依存グラフを作成するグラフ作成部と、
前記グラフ作成部により作成された前記条件依存グラフの所定の部分グラフに対して、前記着目するコードに対して直接関わる条件のノードを残し、他の条件および状態変化のノードを起こり得る状態の集合を表すノードに置き換えることにより、当該条件依存グラフの当該部分グラフを当該着目するコードに至る一本のパスで表される部分グラフに変換するグラフ抽象化部と
を備えることを特徴とするプログラム解析装置。
【請求項８】
前記グラフ作成部は、前記条件依存グラフ中に、所定の一つのノードの次に位置する複数のノードに対応する条件の論理和が常に真であってかつ排他的な分岐があり、さらに分岐先の一方がプログラムの実行を終了する終了命令に至る場合、分岐点から終了命令に至るパスを除去することを特徴とする請求項７に記載のプログラム解析装置。
【請求項９】
前記グラフ作成部は、プログラムの各命令文を順次探索して前記条件依存グラフのノードおよびパスを作成していき、着目した命令文が条件分岐文である場合、当該条件分岐文の前後に何も行わない命令文があるものとして条件依存グラフを作成することを特徴とする請求項７に記載のプログラム解析装置。
【請求項１０】
コンピュータが処理対象のプログラムを解析する方法であって、
前記コンピュータが、前記処理対象のプログラムにおける着目するコードに至るまでの条件および状態変化をノードとする条件依存グラフを作成し記憶装置に格納するグラフ作成ステップと、
前記コンピュータが、前記記憶装置に格納された前記条件依存グラフを読み出し、当該条件依存グラフの所定の部分グラフに対して、前記着目するコードに対して直接関わる条件のノードを残し、他の条件および状態変化のノードを起こり得る状態の集合を表すノードに置き換えることにより、当該条件依存グラフの当該部分グラフを当該着目するコードに至る一本のパスで表される部分グラフに変換する抽象化ステップと
を含むことを特徴とするプログラム解析方法。
【請求項１１】
前記抽象化ステップは、
前記コンピュータが、前記条件依存グラフの中で、所定のノードに対応する条件によってパスが複数に分かれた後に再度一つのノードへ合流する部分である完全部分グラフを処理対象として選択するステップと、
前記コンピュータが、前記完全部分グラフの複数のノードに対応する複数の条件および状態変化を１または複数の状態変化の集合に置き換えるステップと
を含むことを特徴とする請求項１０に記載のプログラム解析方法。
【請求項１２】
前記グラフ作成ステップでは、前記コンピュータが、前記条件依存グラフ中に、所定の一つのノードの次に位置する複数のノードに対応する条件の論理和が常に真であってかつ排他的な分岐があり、さらに分岐先の一方がプログラムの実行を終了する終了命令に至る場合に、分岐点から終了命令に至るパスを除去することを特徴とする請求項１０に記載のプログラム解析方法。
【請求項１３】
前記グラフ作成ステップでは、前記コンピュータが、前記終了命令に至るパスを含む分岐の他方のパスが、他の所定のパスと共に前記完全部分グラフを構成する場合に、当該完全部分グラフの始点のノードから前記終了命令までの条件の否定条件を当該始点のノードの条件とすることを特徴とする請求項１２に記載のプログラム解析方法。
【請求項１４】
コンピュータに、
処理対象のプログラムにおける着目するコードに至るまでの条件および状態変化をノードとする条件依存グラフを作成し記憶装置に格納する第１の処理と、
前記記憶装置に格納された前記条件依存グラフを読み出し、当該条件依存グラフの所定の部分グラフに対して、前記着目するコードに対して直接関わる条件のノードを残し、他の条件および状態変化のノードを起こり得る状態の集合を表すノードに置き換えることにより、当該条件依存グラフの当該部分グラフを当該着目するコードに至る一本のパスで表される部分グラフに変換する第２の処理とを実行させることを特徴とするプログラム。
【請求項１５】
前記第２の処理では、
前記条件依存グラフの中で、所定のノードに対応する条件によってパスが複数に分かれた後に再度一つのノードへ合流する部分である完全部分グラフを処理対象として選択する処理と、
前記完全部分グラフの複数のノードに対応する複数の条件および状態変化を１または複数の状態変化の集合に置き換える処理とを前記コンピュータに実行させることを特徴とする請求項１４に記載のプログラム。
【請求項１６】
前記第１の処理では、前記条件依存グラフ中に、所定の一つのノードの次に位置する複数のノードに対応する条件の論理和が常に真であってかつ排他的な分岐があり、さらに分岐先の一方がプログラムの実行を終了する終了命令に至る場合に、分岐点から終了命令に至るパスを除去する処理を前記コンピュータに実行させることを特徴とする請求項１４に記載のプログラム。
【請求項１７】
前記第１の処理では、前記終了命令に至るパスを含む分岐の他方のパスが、他の所定のパスと共に前記完全部分グラフを構成する場合に、当該完全部分グラフの始点のノードから前記終了命令までの条件の否定条件を当該始点のノードの条件とする処理を前記コンピュータに実行させることを特徴とする請求項１６に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム解析に関し、特にプログラム中の所望のコードに到達するまでの実行条件を抽出するための解析を支援する技術に関する。
【背景技術】
【０００２】
コンピュータプログラム（以下、単にプログラムと記す）の解析において、所定のコードに着目し、プログラムの実行がそのコードに到達するまでの実行条件を抽出することが行われる場合がある。例えば、業務システムのプログラム等では、データの妥当性を検査するために、条件分岐文が多く含まれる傾向がある。このようなプログラムにおいて、与えられたコード（例えば、ユーザにより任意に指定されたコード）に到達するための実行条件を求めることは、データの妥当性検査の内容を明らかにするために有効である。
【０００３】
この与えられたコードに対する実行条件を抽出する一般的な手段として、プログラム依存グラフ（Program Dependence Graph：以下、ＰＤＧ）を作成し、プログラムの始点（エントリーポイント）から対象となるコードに対応するＰＤＧ上の頂点までのパスを探索することが行われる。具体的な従来技術としては、ＰＤＧを用いて、所定の変数に代入されたデータが別の変数へ代入されるときの条件を求める、パスコンディション（path condition）と呼ばれる手法がある（例えば、非特許文献１参照）。この手法では、データの依存関係に着目し、それぞれの文（コード）に跨る制約を解き、実行条件よりも、より強い条件を求めることが行われる。そして、充足不可能な条件を見つけることにより、そのような条件に対応するパスを取り除くことができる。
【０００４】
また、プログラム解析の手法の一として、着目する条件を与え、その条件の下で実行可能な命令文を解析対象のプログラムから抽出し、プログラムスライス（以下、スライス）を求めるものがある。このようなスライスは、条件付きスライス（Conditioned Slice）と呼ばれている（例えば、非特許文献２参照）。条件付きスライスを求めることによって、いくつかの条件分岐文において、ＴＨＥＮ部とＥＬＳＥ部のどちらが実行されるかが決定でき、実行パスを抑制することができる。
【０００５】
【非特許文献１】Torsten Robschink、Gregor Snelting、“Efficient Path Condition in Dependence Graphs”、International Conference on Software Engineering (ICSE’02)、2002
【非特許文献２】S. Danicic、C. Fox、M. Harman、R. Hierons、“A conditioned program slicer”、International Conference on Software Maintenance (ICSM'00)、2000
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上述したように、プログラムにおいて、所定のコードに対する実行条件を求める手段としては、ＰＤＧを作成し、プログラムの始点から対象となるコードに対応するＰＤＧ上の頂点までのパスを探索することが一般的である。しかし、このパスの数は、条件分岐文の数に応じて、指数関数的に増加する。このため、特に業務システム等のように条件分岐が多く含まれるプログラムに対して実行条件を求める場合、探索すべきパスの数が膨大な数となり、現実的な時間で探索を終えることができなかった。
【０００７】
条件付きスライスを求めることにより、条件分岐文において実行パスを抑制する手法を用いて、ＰＤＧなどの解析グラフにおいても、探索対象のパス（以下、探索パス）を削減することができる。しかし、スライスに付与される条件は、この手法の実行目的等に基づきユーザによって与えられなければならず、プログラムから自動的に求めることができない。また、この手法によって得ることのできる部分プログラムから条件依存グラフを作成しても、条件付きの実行条件を求めることにしかならならないため、一般的に有効とは言えない。
【０００８】
そこで、本発明は、プログラム解析において、プログラムの実行がそのコードに到達するまでの実行条件を効率よく抽出する方法およびそのシステムを提供し、プログラム解析の作業効率を向上させることを目的とする。
【課題を解決するための手段】
【０００９】
上記の目的を達成するため、本発明は、次のように構成されたプログラム解析装置として実現される。この装置は、処理対象のプログラムを解析して、着目するコードに至るまでの条件および状態変化をノードとする条件依存グラフを作成するグラフ作成部と、このグラフ作成部により作成された条件依存グラフの中で、所定のノードに対応する条件によってパスが複数に分かれた後に再度一つのノードへ合流する部分である完全部分グラフを対象とし、この完全部分グラフの複数のノードに対応する複数の条件および状態変化を１または複数の状態変化の集合に置き換え、この状態変化の集合に対応するノードを通る１本のパスで表される部分グラフに変換するグラフ抽象化部とを備えることを特徴とする。
【００１０】
また、この装置は、上述のグラフ作成部と、このグラフ作成部により作成された条件依存グラフの所定の部分グラフに対して、着目するコードに対して直接関わる条件のノードを残し、他の条件および状態変化のノードを起こり得る状態の集合を表すノードに置き換えることにより、この部分グラフを着目するコードに至る１本のパスで表される部分グラフに変換するグラフ抽象化部とを備える構成とすることができる。
【００１１】
条件依存グラフ中に、所定の一つのノードの次に位置する複数のノードに対応する条件の論理和が常に真であってかつ排他的な分岐があり、さらに分岐先の一方がプログラムの実行を終了する終了命令に至るとする。そして、この分岐の他方のパスが、他の所定のパスと共に上述した完全部分グラフを構成するものとする。この場合、より好ましくは、上述したプログラム解析装置のグラフ作成部は、分岐点から終了命令に至るパスを除去し、完全部分グラフの始点のノードから終了命令までの条件の否定条件を当該始点のノードの条件とする。また、このグラフ作成部は、より詳細には、プログラムの各命令文を順次探索して条件依存グラフのノードおよびパスを作成していき、着目した命令文が条件分岐文である場合、この条件分岐文の前後に何も行わない命令文があるものとして条件依存グラフを作成する。
【００１２】
さらにこの装置は、グラフ抽象化部により変換された条件依存グラフに対し、当該条件依存グラフに記載される状態変化を適用してルールツリーを生成するルールツリー生成部と、ルールツリー生成部により生成された前記ルールツリーに基づいてソースコードを生成する計算ルール生成部をさらに備える構成とすることができる。これらの機能により生成されるルールツリーや計算ルールを用いることにより、種々の目的に応じたプログラム解析を実行することが容易になる。
【００１３】
また、上記の目的を達成する他の発明は、コンピュータが処理対象のプログラムを解析する、次のような方法としても実現される。この方法によれば、コンピュータが、処理対象のプログラムにおける着目するコードに至るまでの条件および状態変化をノードとする条件依存グラフを作成する。そして、作成された条件依存グラフの所定の部分グラフに対して、着目するコードに対して直接関わる条件のノードを残し、他の条件および状態変化のノードを起こり得る状態の集合を表すノードに置き換えることにより、この部分グラフを着目するコードに至る１本のパスで表される部分グラフに変換する。
【００１４】
さらに本発明は、コンピュータを制御して上述したプログラム解析装置として機能させるプログラム、あるいはコンピュータに上記のプログラム解析方法における各ステップに対応する処理を実行させるプログラムとしても実現される。このプログラムは、磁気ディスクや光ディスク、半導体メモリ、その他の記録媒体に格納して配布したり、ネットワークを介して配信したりすることにより提供することができる。
【発明の効果】
【００１５】
以上のように構成された本発明によれば、着目するコードに至るまでの条件および状態変化をノードとし、さらに着目するコードに対して直接関わる条件のノードを残して、他の条件および状態変化のノードを省略した条件依存グラフを作成する。この条件依存グラフを用いることにより、解析対象のプログラムの実行がそのコードに到達するまでの実行条件を効率よく抽出することができ、プログラム解析における作業効率の向上に寄与することができる。
【発明を実施するための最良の形態】
【００１６】
本発明は、プログラムの実行がそのコードに到達するまでの実行条件を効率よく抽出するため、プログラム解析に用いる新たな構成の解析グラフを提案する。この新たな解析グラフを条件依存グラフと呼ぶ。条件依存グラフは、着目するコードに至るまでのパス、またはプログラムの終了までの全てのパスを探索して得られる、代入などの状態変化、条件分岐文と繰り返し文の条件とそれらの否定条件とを頂点（ノード）とするグラフである。
以下、添付図面を参照して、本発明を実施するための最良の形態（以下、実施形態）について詳細に説明する。
【００１７】
図１は、本実施形態によるグラフ作成装置の機能構成を示す図である。
図１に示すグラフ作成装置１００は、プログラムを解析して条件依存グラフを作成するグラフ作成部１０と、グラフ作成部１０により作成された条件依存グラフのうち一定の条件を満足する部分を抽象化するグラフ抽象化部２０とを備える。このグラフ作成装置１００は、パーソナルコンピュータやワークステーション、その他のコンピュータシステムにて実現される。
【００１８】
図２は、図１のグラフ作成装置１００を実現するのに好適なコンピュータのハードウェア構成の例を模式的に示した図である。
図２に示すコンピュータは、演算手段であるＣＰＵ（Central Processing Unit：中央処理装置）１０１と、Ｍ／Ｂ（マザーボード）チップセット１０２およびＣＰＵバスを介してＣＰＵ１０１に接続されたメインメモリ１０３と、同じくＭ／Ｂチップセット１０２およびＡＧＰ（Accelerated Graphics Port）を介してＣＰＵ１０１に接続されたビデオカード１０４と、ＰＣＩ（Peripheral Component Interconnect）バスを介してＭ／Ｂチップセット１０２に接続された磁気ディスク装置（ＨＤＤ）１０５、ネットワークインタフェース１０６と、さらにこのＰＣＩバスからブリッジ回路１０７およびＩＳＡ（Industry Standard Architecture）バスなどの低速なバスを介してＭ／Ｂチップセット１０２に接続されたフレキシブルディスクドライブ１０８およびキーボードやマウス等の入力デバイス１０９とを備える。
【００１９】
なお、図２は本実施形態を実現するコンピュータのハードウェア構成を例示するに過ぎず、本実施形態を適用可能であれば、他の種々の構成を取ることができる。例えば、ビデオカード１０４を設ける代わりに、ビデオメモリのみを搭載し、ＣＰＵ１０１にてイメージデータを処理する構成としても良いし、外部記憶装置として、ＡＴＡ（AT Attachment）やＳＣＳＩ（Small Computer System Interface）などのインタフェースを介してＣＤ−Ｒ（Compact Disc Recordable）やＤＶＤ−ＲＡＭ（Digital Versatile Disc Random Access Memory）のドライブを設けても良い。
【００２０】
図１に示すグラフ作成装置１００のグラフ作成部１０は、例えば、図２のプログラム制御されたＣＰＵ１０１とメインメモリ１０３や磁気ディスク装置１０５等の記憶装置により実現され、解析対象であるプログラムの条件依存グラフを作成する。ＰＤＧは、様々なプログラム解析に用いることのできる汎用的な解析グラフであるため、実行条件の抽出という目的に対しては不要な情報が含まれている。そこで、本実施形態では、ＰＤＧから構成でき、かつ、より実行条件の抽出に適した条件依存グラフを作成する。上述したように、条件依存グラフは、着目するコードまたはプログラムの終了までのパスに関する、実行条件または状態変化を頂点（ノード）とするグラフである。条件依存グラフの詳細および具体的な作成手順については後述する。
【００２１】
グラフ抽象化部２０は、例えば、図２のプログラム制御されたＣＰＵ１０１とメインメモリ１０３や磁気ディスク装置１０５等の記憶装置により実現され、グラフ作成部１０により作成された条件依存グラフの抽象化を行う。条件依存グラフにおいて、ある条件によってパスが分かれて、いくつかの頂点を経て一つの頂点へ合流する場合がある。この場合、分岐している間の複数のパス上に現れる頂点の集合、つまり条件の集合は、対象地点（合流地点）に至るまでの条件として直接的な効果がない条件である。このような直接的な効果がない条件を除去し、この部分のグラフを１本のパスとして表すことを、条件依存グラフの抽象化と呼ぶ。条件依存グラフの抽象化を行うと、実行条件として必要な条件と計算方法を保存しながら、実行条件として必要のない条件を、条件依存グラフから取り除くことができる。条件依存グラフの抽象化の具体的な方法については後述する。
【００２２】
次に、本実施形態で作成される条件依存グラフおよびその抽象化について詳細に説明する。
図３は、擬似プログラムとその条件依存グラフを例示する図である。
図３（Ａ）のプログラムにおいて、ＥＲＲ:=１というコードまでの実行条件を抽出するために、図３（Ｂ）に示す条件依存グラフが作成される。
【００２３】
条件依存グラフを用いて実行条件を求める場合、まず始めに、グラフの始点から終点までのそれぞれのパスを探索する。一つのパス上に存在する条件の論理積を求めることによって、そのパスに対応する実行条件を得ることができる。そして、それぞれのパスに対応する実行条件を求め、それらの論理和を求めることによって、対象となるコードまでの実行条件を求めることができる。図３（Ｂ）に示す条件依存グラフの場合、
（ａ＝ｂ）ａｎｄ（ｖ＝２）
と
（ＮＯＴ  ａ＝ｂ）ａｎｄ（ｖ＝２）
がそれぞれのパスに対応する実行条件であるため、ＥＲＲ:=１に到達するための実行条件は、
（（ａ＝ｂ）ａｎｄ（ｖ＝２））ｏｒ（（ＮＯＴ ａ＝ｂ）ａｎｄ（ｖ＝２））
である。
【００２４】
条件依存グラフを形式的に記述すると、頂点の集合Ｖ、辺の集合Ｅ、グラフの始点ｖ０、条件式の集合Ｃ、状態変化の集合Σ、頂点から条件式又は状態変化へのラベル関数Ｌから構成でき、ＣＤＧ（Ｖ，Ｅ，ｖ０，Ｃ，Σ，Ｌ）と表すことができる。そして、有効グラフＧ（Ｖ，Ｅ）が与えられ、以下の制約１〜３を満たすとき、任意のラベル関数Ｌに対して、Ｇ（Ｖ，Ｅ）は、ＣＤＧ（Ｖ，Ｅ，ｖ０，Ｃ，Σ，Ｌ）である。
１．始点（入次数０の頂点）が必ず一つだけ存在する。
｜｛ｖ∈Ｖ｜｜Ｉｎ（ｖ）｜＝０｝｜＝１
２．終点（出次数０の頂点）が少なくとも一つは存在する。
｜｛ｖ∈Ｖ｜｜Ｏｕｔ（ｖ）｜＝０｝｜＞０
３．始点を含む任意の頂点ｖ’から終点へのパスが必ず存在する。
∃ｖ２，ｖ３，... ，ｖｎ∈Ｖ . （ｖ’，ｖ２），（ｖ２，ｖ３），... ，（ｖｎ，ｖ０）∈Ｅ
【００２５】
ここで、ｖ∈Ｖに対して、
Ｉｎ（ｖ）＝｛（ｖ’，ｖ）∈Ｅ｜ｖ’∈Ｖ｝、
Ｏｕｔ（ｖ）＝｛（ｖ，ｖ’）∈Ｅ｜ｖ’∈Ｖ｝
とそれぞれ定義する。頂点ｖに対してＬ（ｖ）が未定義の場合、そのような頂点を空の頂点と呼び、未定義であることを記号「⊥」で表すことにする。また、状態変化は、状態から状態への関数として表現できる。そこで、σ’＝ｆ（σ）と記述して、ｆという状態変化によって状態σが状態σ’に変化したことを表す。ここで、状態とは、変数から式への関数である。例えば、σ（Ｘ）は、変数Ｘに対応する値を計算するための式を表す。また、式Ｅに対して、Ｅの中の変数の出現を全てσにおける式に置き換えることを、Ｅ［σ］と記述することにする。一般的に、このように状態を変化させるものには、いわゆる代入文があり、Ａ:=Ｂなどと記述することが多い。そこで、このような代入文を状態変化とみなすことにする。つまり、（Ａ:=Ｂ）（σ）と記述して、Ａ:=Ｂの後の状態を表すものとする。さらに、σ［Ｘ:=Ｅ］と記述して、
σ’（ｘ）＝Ｅ［σ］      （ｘ＝Ｘのとき）
＝σ（ｘ）      （ｘ≠Ｘのとき）
となるσ’を表す。
【００２６】
次に、上述した条件２を強めて、次に示す条件２’を満たすとき、ＣＤＧ（Ｖ，Ｅ，ｖ０，Ｃ，Σ，Ｌ）が完全であると呼ぶ。そして、そのような部分グラフを完全部分条件依存グラフと呼び、ＣＣＤＧ（Ｖ，Ｅ，ｖ０，ｖ１，Ｃ，Σ，Ｌ）と表す。なお、ｖ１は、部分グラフの終点である。
２’．終点（出次数０の頂点）が必ず一つだけ存在する。
【００２７】
完全部分条件依存グラフは、ある条件によってパスが分かれて、いくつかの頂点を経て一つの頂点へ合流するようなグラフである。したがって上述したように、完全部分条件依存グラフ中に現れる条件（頂点）の集合は、対象地点に至るまでの条件として直接的な効果がない条件である。そこで、このグラフに対して抽象化を行い、１本のパスで表す。
図４は、図３に示した条件依存グラフとこれを抽象化した様子を示す図である。
図４（Ａ）の条件依存グラフ（図３（Ｂ）と同一）において、破線で囲まれた部分が完全部分条件依存グラフとなっている。この部分を抽象化して、図４（Ｂ）の条件依存グラフが作成される。
【００２８】
ＣＤＧ（Ｖ’，Ｅ’，ｖ０，ｖ１，Ｃ，Σ，Ｌ）をＣＤＧ（Ｖ，Ｅ，ｖ０，Ｃ，Σ，Ｌ）の中の完全部分条件依存グラフとする。また、以下の通りに定義した抽象状態変化をαとし、Ｌ（ｖ’）＝αとなるようにＬを再定義した関数をＬ［α／ｖ’］と表すものとする。すると、ＣＤＧ（Ｖ，Ｅ，ｖ０，Ｃ，Σ，Ｌ）の部分グラフとなるようなＣＤＧ（｛α｝，｛ｖ０，ｖ１，ｖ’｝，｛（ｖ０，ｖ’），（ｖ’，ｖ１），ｖ０，ｖ１｝，Ｃ，Σ，Ｌ［α／ｖ’］）が、ＣＤＧ（Ｖ，Ｅ，ｖ０，Ｃ，Σ，Ｌ）において、ＣＤＧ（Ｖ’，Ｅ’，ｖ０，ｖ１，Ｃ，Σ，Ｌ）を抽象化した条件依存グラフである。
α（σ）＝｛ｆ（σ）｜ｆ∈Ｆ｝
Ｆ＝∪｛ｇＮ・... ・ｇ１・ｇ０｜ｇ０，ｇ１，... ，ｇＮ∈Σはｖ０からｖ１の一つのパスに現れる実行状態変化｝
ここで、記号「・」は関数の合成を表すものとする。これは、あるプログラム断片に至るまでに直接関わることになる実行条件はそのまま残して、それ以外の命令文について分岐条件を考慮せず、起こり得る状態を集合として捉えたことになる。なお、Ｆの要素ｆ１，ｆ２，... ，ｆｎ∈Ｆについてα＝ｆ１｜ｆ２｜... ｜ｆｎと表す。また、ｆ｜ｆ・ｆ｜ｆ・ｆ・ｆ｜... をｆ＋と表し、恒等関数εに対して、ε｜ｆ＋をｆ＊と表す。
【００２９】
さて、次に、条件依存グラフにおいて、ある一つの頂点の次に位置する複数の頂点における条件の論理和が常に真であり、かつ排他的な分岐がある場合を考える。本実施形態では、このような分岐については、対象地点に至るまでのパスを残し、プログラム終了までのパスは削除することにする。
【００３０】
図５は、疑似プログラムおよびその条件依存グラフの他の例を示す図である。
図５に示すプログラムは、図３に示したプログラムと似ているが、ｖに代入される変数ｂの値が「０」である場合に、ＥＸＩＴというプログラム停止命令によりプログラムの実行が終了する。この停止命令に至るまでのパス（図中太線で表示）が存在するために、図５（Ｂ）の破線で囲まれた部分条件依存グラフは、完全部分条件依存グラフではない。そこで、条件依存グラフにこのような分岐が存在する場合、このプログラム終了に至るまでのパスを取り除く。この操作をプログラム停止パスの除去と呼ぶ。
【００３１】
プログラム停止パスを除去するためには、まず、条件依存グラフＣＤＧ（Ｖ，Ｅ，ｖ０，Ｃ，Σ，Ｌ）中の完全部分条件依存グラフとなる候補、つまり図５（Ｂ）の破線部分の部分条件依存グラフＣＤＧ（Ｖ’，Ｅ’，ｖ０’，Ｃ，Σ，Ｌ）の始点ｖ０’からプログラム終了に至るまでの実行条件を抽出する。そして、抽出された実行条件を、始点ｖ０’における条件とする（図５（Ｃ）参照）。このプログラム停止パスを除去するための手続きは次の通りである。
【００３２】
１．始点ｖ０’（完全部分条件依存グラフの候補となる部分条件依存グラフの始点）からプログラム終了までの実行条件を求める。この実行条件をＣとする。必要であれば、これ以前に抽象化を行っておく。
２．始点ｖ０’が空の頂点（Ｌ（ｖ０’）＝⊥となる頂点）であれば、（ア）の操作を、そうでなければ（イ）の操作を行う。
（ア）  ｖ０’に対応する条件を、操作１で求めた実行条件の否定条件であるとする。つまりラベル関数をＬ［¬Ｃ／ｖ０’］とする。
（イ）  操作１で求めた実行条件の否定条件に対応する頂点ｖ１を作る。つまり、Ｌ［¬Ｃ／ｖ１］をラベル関数とする。そして、（ｖ０，ｖ’）となる辺の全てのｖ’に対して（ｖ１，ｖ’）という辺を作り、（ｖ０，ｖ’）となる辺を取り除く。また、（ｖ０，ｖ１）という辺を新たに加える。
【００３３】
ところで、抽象化の対象である完全部分条件依存グラフは、命令文の意味や特徴を考慮することにより、条件依存グラフを作成するためのプログラム探索（コントロールフロー等）中に発見することができる。このような命令文として、条件分岐文が挙げられる。
図６は、条件分岐文を含むプログラムの一部と、その部分プログラムに対応する条件依存グラフを例示する図である。
【００３４】
図６（Ａ）のプログラムに対して、条件分岐文の前後に何も行わない命令文があるものとして条件依存グラフを作成する。このようにすると、作成される条件依存グラフは、図６（Ｂ）に示すように、完全部分条件依存グラフとなる。ただし、この条件分岐文には、いわゆるジャンプ命令やプログラム停止命令が含まれないものとする。もし、条件分岐文にプログラム停止命令が含まれる場合は、上述したプログラム終了パスの除去を行うことによって、完全部分条件依存グラフとすることができる。
【００３５】
次に、上記のように構成される条件依存グラフの作成手順および抽象化の手順について説明する。
図７乃至図９は、グラフ作成部１０による条件依存グラフの作成手順を説明するフローチャートである。
図７を参照すると、グラフ作成部１０は、まず、ノード（頂点）を作成し、それをｖ（現在のノード）とする。そして、ｅ（現在の式）:=⊥、ｌ（現在位置）:=０行０カラムとする（ステップ７０１）。次に、グラフ作成部１０は、グラフ作成プロセス（サブプロセス）を実行する（ステップ７０２）。このサブプロセスの詳細は後述する。この後、グラフ作成部１０は、所定のノードの次のノードに対応する条件の論理和が真となり、かつ排他的な分岐となるノードがあるとき、そのノードからプログラム終了命令に至るパスを取り除き（ステップ７０３）、得られた条件依存グラフを記憶装置（例えば図２のメインメモリ１０３や磁気ディスク装置１０５）に格納して、処理を終了する。
【００３６】
図８は、図７に示したステップ７０２のグラフ作成プロセスの詳細を示すフローチャートである。
図８を参照すると、グラフ作成部１０は、まず、vにeとlを対応付けて、（ｖ，ｅ，ｌ）を履歴に記録する（ステップ８０１）。次に、グラフ作成部１０は、プログラムの現在位置の次に命令文があるかどうかを調べ（ステップ８０２）、次の命令文があるならば、その命令文を獲得し、その位置を改めてｌとする（ステップ８０３）。
【００３７】
次に、グラフ作成部１０は、ステップ８０３で獲得した命令文が条件分岐文か否かを調べる（ステップ８０４）。そして、条件分岐文である場合は、まず、各実行系列に対する条件をeとし、次いで、各実行系列についてそれぞれノード作成プロセス（サブプロセスを実行して（ステップ８０５）、グラフ作成プロセスの動作を終了する。このサブプロセスの詳細は後述する。
【００３８】
一方、ステップ８０３で獲得した命令文が条件分岐文でなかった場合（ステップ８０４でＮｏ）、グラフ作成部１０は、その命令文が状態変化（代入等）の文か否かを調べる（ステップ８０６）。そして、状態変化であれば、その状態変化をｅとして（ステップ８０７）、ノード作成プロセスを実行して（ステップ８０８）、グラフ作成プロセスの動作を終了する。
【００３９】
ステップ８０３で獲得した命令文が状態変化でもなかった場合（ステップ８０６でＮｏ）、グラフ作成部１０は、その命令文が終了命令か否かを調べる（ステップ８０９）。そして、終了命令であれば、ｅ:=終了命令として（ステップ８１０）、ノード作成プロセスを実行して（ステップ８０８）、グラフ作成プロセスの動作を終了する。。これに対し、ステップ８０３で獲得した命令文が終了命令でもなかった場合は（ステップ８０９でＮｏ）、ステップ８０２に戻り、次の命令文を探索する。
【００４０】
ステップ８０２で次の命令文が存在しない場合、次にグラフ作成部１０は、e:=終了とし、ｌ:=プログラムの最後の位置として（ステップ８１１）、ノード作成プロセスを実行する（ステップ８０８）。
【００４１】
図９は、図８に示したステップ８０５およびステップ８０８のノード作成プロセスの詳細を示すフローチャートである。
図９を参照すると、グラフ作成部１０は、まず、履歴に、ｅ、ｌに対応するｖが記録されているか否かを調べる（ステップ９０１）。そして、そのようなｖが記録されているならば、グラフ作成部１０は、現在のノードから記録されているノードｖに辺を追加して（ステップ９０２）、ノード作成プロセスの動作を終了する。
【００４２】
一方、履歴に、ｅ、ｌに対応するｖが記録されていない場合（ステップ９０１でＮｏ）、次にグラフ作成部１０は、ｖの子ノードを作り、これを新たなｖとする（ステップ９０３）。そして、ｅが終了命令か否かを調べる（ステップ９０４）。ｅが終了命令であるならば、次にグラフ作成部１０は、ｖにｅとｌを対応付け、（ｖ，ｅ，ｌ）を履歴に記録して（ステップ９０５）、ノード作成プロセスの動作を終了する。これに対し、ｅが終了命令でない場合は（ステップ９０４でＮｏ）、グラフ作成部１０は、ノード作成プロセスを終了して、図８に示したグラフ作成プロセスに戻る（ステップ９０６）。
【００４３】
図１０は、グラフ抽象化部２０による条件依存グラフの抽象化の手順を説明するフローチャートである。
初期動作として、グラフ作成部１０により作成された条件依存グラフが記憶装置から読み出され、作成されたグラフの中から抽象化の対象となる完全部分条件依存グラフの選択が行われる。完全部分条件依存グラフは、上述したように、条件依存グラフを作成するためにプログラムを探索する過程で発見することができるので、発見された完全部分条件依存グラフをそのままグラフ抽象化部２０の処理対象とすれば良い。
【００４４】
図１０を参照すると、グラフ抽象化部２０は、まず、抽象化の対象である部分グラフ（完全部分条件依存グラフ）の始点から終点までのパスのそれぞれに対して合成プロセスを実行する（ステップ１００１）。図１１は、このサブプロセスの内容である。すなわち、グラフ抽象化部２０は、個々のパスに関して、そのパスに現れる代入などの状態変化を関数として表し、一意の名前ｇ１，ｇ２，ｇ３，... ，ｇＮをそれぞれの関数に対して付ける（ステップ１１０１）。そして、各関数をｇ１・ｇ２・... ・ｇＮのように記号「・」で連接する（ステップ１１０２）。
【００４５】
次に、グラフ抽象化部２０は、合成プロセスによって得られた各パスにおける合成関数ｆ０，ｆ１，... ，ｆＮを記号「｜」で連接して、この連接結果である状態変化の集合ｆ０｜ｆ１｜... ｜ｆＮを抽象状態変化αとし（ステップ１００２）、この抽象状態変化αに対応するノードを作成する（ステップ１００３）。次に、グラフ抽象化部２０は、このパスにおける始点と終点以外のすべてのノードと辺を取り除く（ステップ１００４）。そして、始点、「抽象状態変化α」のノード、終点をノードとし、この順序からなるグラフＰ（｛α｝，｛ｖ０，ｖ１，ｖ’｝，｛（ｖ０，ｖ’），（ｖ’，ｖ１）｝，ｖ０，ｖ１，Ｃ，Σ，Ｌ［α／ｖ’］）を作成する（ステップ１００５）。このグラフＰが抽象化された部分グラフである。
【００４６】
以上、条件依存グラフの作成およびその抽象化について説明した。なお、上記の動作例では、解析対象のプログラム全体に対して条件依存グラフを作成した後に、作成された条件依存グラフの抽象化可能な部分（完全部分条件依存グラフ）を抽象化することとした。しかしながら、上述したように、抽象化可能な部分は、条件依存グラフを作成するためにプログラムを探索する過程で発見することができる。したがって、グラフ作成部１０による条件依存グラフの作成中に、そのような部分グラフが把握された時点で、随時この部分グラフに対してグラフ抽象化部２０が抽象化を実行するようにしてもかまわない。
【００４７】
次に、本実施形態の条件依存グラフの適用例を説明する。本実施形態は、条件依存グラフが作成できるプログラムであれば、どのようなプログラムにでも適用できるが、以下の例では、代入文、複合文、条件分岐文、繰り返し文、停止命令から構成される簡単なプログラムを用いる。そして、代入文は「変数 := 式」と記述し、条件分岐文は、「ＩＦ〜ＴＨＥＮ〜ＥＬＳＥ〜ＥＮＤ」の形式で記述し、繰り返し文は「ＷＨＩＬＥ〜ＤＯ〜ＥＮＤ」で記述する。また、停止命令は「ＥＸＩＴ」とし、文を続けて記述することで複合文を表すことにする。
【００４８】
＜適用例１：実行条件の抽出と分類化（ビジネスルールの抽出）＞
ビジネスルールと呼ばれる業務上の規定や制約を、プログラムコードから抽出するためには、ある着目すべきコードまでの実行条件を求めることが行われる。なぜなら、対象コードがエラーを出力するコードであれば、その実行条件は、制約を検査していることが多く、また、代入を行っているコードであれば、ある計算を行うための前提条件を検査していることが多いためである。この実行条件を求めるために、本実施形態の条件依存グラフを用いることができる。
【００４９】
まず、プログラムの条件依存グラフを作成し、これを、状態変化を適用した状態に変換する。この状態変化が適用された条件依存グラフをルールツリーと呼ぶ。このルールツリーを用いれば、ツリーに記述されている条件の順序などを入れ替えることにより、実行条件を分類し理解することが容易になる。また、ルールツリーをユーザが参照するために表示出力する場合、状態変化適用後の変数の値（あるいは、値を求める計算式）をルールツリー上に表示すると、ユーザにとって読みにくい条件式となる場合がある。そこで、そのような場合には、変数の状態が変化したということのみをユーザに見せるために、変化のある変数にはプライム記号などの特殊な記号でマークするといった表現をとることもできる。
【００５０】
図１２は、本実施形態のグラフ作成装置１００を用いてルールツリーを作成するシステムの機能構成を示す図である。
図１２に示すように、このシステムは、図１に示したものと同様のグラフ作成部１０およびグラフ抽象化部２０を備え、さらにグラフ抽象化部２０により抽象化された条件依存グラフからルールツリーを生成するルールツリー生成部３０を備える。ルールツリー生成部３０は、例えば図２のプログラム制御されたＣＰＵ１０１およびメインメモリ１０３により実現され、条件依存グラフに対して状態変化を適用し、ルールツリーを生成する。生成されたルールツリーは、例えば図２のビデオカード１０４を介してディスプレイ装置へ表示出力することができる。
【００５１】
図１３は、疑似プログラムのソースコードとその条件依存グラフの例を示す図、図１４は、図１３の条件依存グラフから生成されるルールツリーを示す図である。
図１３（Ａ）のソースコードにおいて、「Ｘ:=Ｘ＋Ｎ」というコードに至るまでの実行条件を求めるものとする。ここで、「Ａ」は商品のＩＤを表し、「Ｘ」は仮商品ＩＤを表す。すなわち、「Ｘ:=Ｘ＋Ｎ」は、仮商品ＩＤを計算している箇所である。
【００５２】
このソースコードに対して、グラフ作成部１０により条件依存グラフが作成され、グラフ抽象化部２０により条件依存グラフの抽象化が行われる。図１３（Ａ）の３行目にＷＨＩＬＥ文があるので、グラフ作成部１０により作成される条件依存グラフには、図１３（Ｂ）に示すようなループが現れる。図１３（Ｂ）の条件依存グラフでは、４番目のノードの「Ｎ＜１０」から分岐するパスの一方がループとなっており、このループ部分は完全部分条件依存グラフである。したがって、グラフ抽象化部２０は、この部分を抽象化して図１３（Ｃ）に示す条件依存グラフを得る。
【００５３】
ここで、図１３（Ｂ）の条件依存グラフにおける各状態変化を、σを用いて次のように記述する。
ｆ１(σ)＝σ［Ｘ:=Ｘ＋Ｎ］
ｆ２(σ)＝σ［Ａ:=Ｘ］
ｇ(σ)＝σ［Ｎ:=Ｎ＋１］
ｈ(σ)＝σ［Ｎ:=１］
また、これらの状態変化が不特定回数繰り返されることを、アスタリスク（*）を付して表現する。すると、図１３（Ｂ）の条件依存グラフにおけるループ部分（完全部分条件依存グラフ）は、図１３（Ｃ）に示すように、(ｇ・ｆ２)* という一つのノードに抽象化される。これで、着目するコード「Ｘ:=Ｘ＋Ｎ」に至るパスは１本となった。
【００５４】
次に、ルールツリー生成部３０が、上記のようにして得られた条件依存グラフにおいて状態変化を適用して、図１４（Ａ）に示すルールツリーを求める。ここで、図１３（Ｃ）の条件依存グラフにおける３番目のノードの条件「Ｘ＞０」には、２番目のノードの状態変化「Ｎ:=１」が適用されるので、「Ｘ」の変化を表すために、ｈ(σ)（Ｘ）という式が用いられている。同様に、図１３（Ｃ）の条件依存グラフにおける６番目のノードの条件「ＮＯＴ Ａ＝０」には、それ以前の各状態変化が適用されるので、「Ａ」の変化を表すために（(ｇ・ｆ２)*・ｈ）（σ）（Ａ）という式が用いられている。
【００５５】
しかし、図１４（Ａ）のような表記は、ユーザが変化したという事実のみを確認したい場合には、冗長な情報を見せていることになる。そこで、実際にルールツリーをディスプレイ表示したりプリントアウトしたりする場合には、図１４（Ｂ）に示すように、「Ｘ」や「Ａ」が変化しているという事実のみを表示するために「Ｘ’」、「Ａ’」と表記することができる。
【００５６】
また、ユーザがルールツリーを参照する場合、商品ＩＤなどで分類をした方が見やすいならば、条件の順序を入れ替えて商品ＩＤについての条件を示したノードをルールツリーの上方へ移動させることができる。本実施形態で作成された条件依存グラフから生成されたルールツリーであれば、ノードには、着目コードに直接関わる条件および状態変化のみが残っており、かつ各条件に至るまでの状態変化が適用されているので、単純にノードの順番を入れ替えるといった編集が可能である。
【００５７】
図１５は、図１４（Ａ）のルールツリーにおいて、商品ＩＤの条件を示したノードをルールツリーの上方へ移動させた様子を示す図である。
図１５（Ｂ）に示すルールツリーは、「商品ＩＤの値が０のとき、仮商品ＩＤを計算する」と読むことができる。このように、変数の意味を考えて実行条件を並べ替えることにより、意味的に理解し易いルールツリーを構成できる。同じ要領によって、枝が複数に分岐する場合においては、分類すべき基準となる変数をツリーの上方に移動させることによって、カテゴリ化するといった操作も可能である。
【００５８】
＜適用例２：部分プログラムのプログラム変換（計算ルールの抽出）＞
適用例１で示したルールツリーを利用して、それぞれの条件の組み合わせ方を適宜変更することにより、一定の抽象度で、対象コードへ至るまでの部分プログラムを生成することができる。特に、対象コードが代入文などである場合、計算過程を規定するビジネスルールを抽出することができる。このようなビジネスルールを計算ルールと呼ぶ。
【００５９】
図１６は、本実施形態のグラフ作成装置１００を用いて計算ルールを抽出するシステムの機能構成を示す図である。
図１６に示すように、このシステムは、図１に示したものと同様のグラフ作成部１０およびグラフ抽象化部２０を備え、かつ図１２に示したものと同様のルールツリー生成部３０を備え、さらにルールツリー生成部３０により生成されたルールツリーから計算ルールを生成する計算ルール生成部４０を備える。計算ルール生成部４０は、例えば図２のプログラム制御されたＣＰＵ１０１およびメインメモリ１０３により実現される。
【００６０】
図１７は、図１５（Ｂ）に示したルールツリーをソースコードへ変換する様子を示す図である。この例の場合、着目コードが「Ｘへの値の代入」である。そのため、ソースコードを生成することによって、変数Ｘに対する計算ルールを求めたこととなる。
計算ルール生成部４０は、まず、ルールツリー生成部３０により生成された図１７（Ａ）のルールツリー（図１５（Ｂ）と同一）において、各変数に関係のない状態変化を取り除き、図１７（Ｂ）に示すルールツリーを得る。ここで、上述したように、
ｆ１(σ)＝σ［Ｘ:=Ｘ＋Ｎ］
ｆ２(σ)＝σ［Ａ:=Ｘ］
ｇ(σ)＝σ［Ｎ:=Ｎ＋１］
ｈ(σ)＝σ［Ｎ:=１］
であるから、図１７（Ａ）の２番目のノード「ＮＯＴ（(ｇ・ｆ２)*・ｈ）（σ）（Ａ）＝０」からは、変数Ａに関係のない状態変化であるｇ(σ)およびｈ(σ)が取り除かれ、「ＮＯＴ ｆ２*（σ）（Ａ）＝０」となっている。同様に、図１７（Ａ）の３番目のノード「ｈ(σ)（Ｘ）」からは、変数Ｘに関係のない状態変化であるｈ(σ)が取り除かれ、「Ｘ＞０」となっている。
【００６１】
次に、計算ルール生成部４０は、図１７（Ｂ）のルールツリーを元にして、図１７（Ｃ）に示すソースコードを生成する。最初に提示した図１３（Ａ）のソースコードと、図１７（Ｃ）のコードとを比較すると、「Ｘ:=Ｘ＋Ｎ」という着目コードに至るまでのプログラムを参照する場合に、後者のソースコードの方が、着目コードに関係のあるコードのみが抽出された理解し易いプログラムになっている。
【００６２】
以上説明したように、本実施形態によれば、着目するコードに至るまでの条件および状態変化をノードとし、さらに着目するコードに対して直接関わる条件のノードを残して、他の条件および状態変化を曖昧にすることによりパスの数を抑制した条件依存グラフを作成する。この条件依存グラフを用いることにより、解析対象のプログラムの実行がそのコードに到達するまでの実行条件を効率よく抽出することが可能となる。特に、条件依存グラフにおける状態変化を適用してルールツリーを生成したり、ルールツリーからさらに計算コードを生成したりすることにより、種々の目的に応じたプログラム解析を実行することが容易になる。また、本実施形態で実行される条件依存グラフの抽象化は、条件依存グラフにおけるパスの数を減らすための独立の手法である。したがって、実際にプログラム解析を実行する場合は、例えば条件付きスライスを求める手法と併用することにより、さらに一層、パスを減少させることが可能となる。
【図面の簡単な説明】
【００６３】
【図１】本実施形態によるグラフ作成装置の機能構成を示す図である。
【図２】図１のグラフ作成装置を実現するのに好適なコンピュータのハードウェア構成の例を模式的に示した図である。
【図３】本実施形態の解析対象となる擬似プログラムとその条件依存グラフを例示する図である。
【図４】図３に示した条件依存グラフとこれを抽象化した様子を示す図である。
【図５】本実施形態の解析対象となる疑似プログラムおよびその条件依存グラフの他の例を示す図である。
【図６】本実施形態の解析対象となる条件分岐文を含むプログラムの一部と、その部分プログラムに対応する条件依存グラフを例示する図である。
【図７】本実施形態のグラフ作成部による条件依存グラフの作成手順を説明するフローチャートである。
【図８】図７のフローチャートにおけるグラフ作成プロセスを説明するフローチャートである。
【図９】図８のフローチャートにおけるノード作成プロセスを説明するフローチャートである。
【図１０】本実施形態のグラフ抽象化部による条件依存グラフの抽象化の手順を説明するフローチャートである。
【図１１】図１０のフローチャートにおける合成プロセスを説明するフローチャートである。
【図１２】本実施形態のグラフ作成装置を用いてルールツリーを作成するシステムの機能構成を示す図である。
【図１３】本実施形態の解析対象となる疑似プログラムのソースコードとその条件依存グラフの例を示す図である。
【図１４】図１３の条件依存グラフから生成されるルールツリーを示す図である。
【図１５】図１４（Ａ）のルールツリーにおいて、商品ＩＤの条件を示したノードをルールツリーの上方へ移動させた様子を示す図である。
【図１６】本実施形態のグラフ作成装置を用いて計算ルールを抽出するシステムの機能構成を示す図である。
【図１７】図１５（Ｂ）に示したルールツリーをソースコードへ変換して計算ルールを生成する様子を示す図である。
【符号の説明】
【００６４】
１０…グラフ作成部、２０…グラフ抽象化部、３０…ルールツリー生成部、４０…計算ルール生成部、１００…グラフ作成装置、１０１…ＣＰＵ（Central Processing Unit：中央処理装置）、１０３…メインメモリ、１０４…ビデオカード、１０５…磁気ディスク装置（ＨＤＤ）
【図１】
2006178835.tif 000003
【図２】
2006178835.tif 000004
【図３】
2006178835.tif 000005
【図４】
2006178835.tif 000006
【図５】
2006178835.tif 000007
【図６】
2006178835.tif 000008
【図７】
2006178835.tif 000009
【図８】
2006178835.tif 000010
【図９】
2006178835.tif 000011
【図１０】
2006178835.tif 000012
【図１１】
2006178835.tif 000013
【図１２】
2006178835.tif 000014
【図１３】
2006178835.tif 000015
【図１４】
2006178835.tif 000016
【図１５】
2006178835.tif 000017
【図１６】
2006178835.tif 000018
【図１７】
2006178835.tif 000019