(57)【要約】【課題】  すべてのパスを通過するプログラムを短時間に生成できるプログラム生成装置を提供する。【解決手段】  プログラムの制御構造を入力として受け、当該制御構造におけるすべてのパスを通過させることができる、当該制御構造の条件式挿入部分に挿入される複数の条件式を線形計画法を用いて生成する条件式生成部２２と、制御構造におけるすべてのパスについて、パスごとに当該パスを通過させるための上記複数の条件式に含まれる変数の初期値を線形計画法を用いて生成し、上記制御構造、上記条件式および上記初期値に基づいてテストプログラムを生成する初期値生成部２４とを備える。【選択図】      図２
2005032213.tif 000002
【特許請求の範囲】
【請求項１】
プログラムの制御構造を入力として受け、当該制御構造におけるすべてのパスを通過させることができる、当該制御構造の条件式挿入部分に挿入される複数の条件式を線形計画法を用いて生成する条件式生成手段と、
前記制御構造におけるすべてのパスについて、パスごとに当該パスを通過させるための前記複数の条件式に含まれる変数の初期値を生成する初期値生成手段と、
前記制御構造、前記複数の条件式および前記初期値に基づいてテストプログラムを生成するプログラム生成手段とを備える
ことを特徴とするプログラム生成装置。
【請求項２】
前記複数の条件式に含まれる変数の値は、前記初期値が代入された後は不変である
ことを特徴とする請求項１に記載のプログラム生成装置。
【請求項３】
前記複数の条件式の各々は一次不等式である
ことを特徴とする請求項１に記載のプログラム生成装置。
【請求項４】
前記条件式生成手段は、
前記制御構造の条件式挿入部分に挿入される複数の条件式の候補をランダムに生成する条件式候補生成手段と、
前記制御構造におけるすべてのパスについて、各パスを通過するために前記複数の条件式が満たすべき条件を定式化し、定式化された当該複数の条件式の各々に余裕変数または不足変数を導入することにより前記複数の条件式を等式化する等式化手段と、
等式化された前記複数の条件式の各々に補足変数を導入する補足変数導入手段と、
前記補足変数の和を目的関数とし、前記補足変数導入手段で補足変数が導入された複数の条件式を制約条件として、線形計画法により前記目的関数の最適値を算出する最適値算出手段と、
前記目的関数の最適値に基づいて、着目しているパスを通過可能か否かを判断するパス通過判断手段とを有する
ことを特徴とする請求項１に記載のプログラム生成装置。
【請求項５】
前記条件式生成手段は、
前記制御構造の条件式挿入部分に挿入される複数の条件式の候補をランダムに生成する条件式候補生成手段と、
前記制御構造におけるすべてのパスについて、各パスを通過するために前記複数の条件式が満たすべき条件を定式化し、定式化された当該複数の条件式の各々に余裕変数または不足変数を導入することにより前記複数の条件式を等式化する等式化手段と、
等式化された前記複数の条件式の各々について、前記余裕変数または前記不足変数に着目している条件式に含まれる定数を代入し、残りの変数について０を代入することにより等式を満たさない場合には、補足変数を導入する補足変数導入手段と、
前記複数の条件式のいずれかに補足変数が導入された場合に、前記補足変数の和を目的関数とし、前記余裕変数、前記不足変数または前記補足変数が含まれる等式化された前記複数の条件式を制約条件として、線形計画法により前記目的関数の最適値を算出する最適値算出手段と、
前記複数の条件式のいずれかに補足変数が導入された場合に、前記目的関数の最適値に基づいて、着目しているパスを通過可能か否かを判断するパス通過判断手段とを有する
ことを特徴とする請求項１に記載のプログラム生成装置。
【請求項６】
前記初期値生成手段は、前記制御構造におけるすべてのパスについて、パスごとに当該パスを通過させるための前記複数の条件式に含まれる変数の初期値を線形計画法を用いて生成する
ことを特徴とする請求項１に記載のプログラム生成装置。
【請求項７】
前記複数の条件式に含まれる変数の値は、前記初期値が代入された後は不変である
ことを特徴とする請求項６に記載のプログラム生成装置。
【請求項８】
前記複数の条件式の各々は一次不等式である
ことを特徴とする請求項６に記載のプログラム生成装置。
【請求項９】
前記条件式生成手段は、
前記制御構造の条件式挿入部分に挿入される複数の条件式の候補をランダムに生成する条件式候補生成手段と、
前記制御構造におけるすべてのパスについて、各パスを通過するために前記複数の条件式が満たすべき条件を定式化し、定式化された当該複数の条件式の各々に余裕変数または不足変数を導入することにより前記複数の条件式を等式化する等式化手段と、
等式化された前記複数の条件式の各々に補足変数を導入する補足変数導入手段と、
前記補足変数の和を目的関数とし、前記補足変数導入手段で補足変数が導入された複数の条件式を制約条件として、線形計画法により前記目的関数の最適値を算出する最適値算出手段と、
前記目的関数の最適値に基づいて、着目しているパスを通過可能か否かを判断するパス通過判断手段とを有する
ことを特徴とする請求項６に記載のプログラム生成装置。
【請求項１０】
前記初期値生成手段は、
前記制御構造におけるすべてのパスについて、各パスを通過するために前記条件式生成手段で求められた複数の条件式が満たすべき条件を定式化し、定式化された当該複数の条件式の各々に余裕変数または不足変数を導入することにより前記複数の条件式を等式化する等式化手段と、
等式化された前記複数の条件式の各々に補足変数を導入する補足変数導入手段と、
前記補足変数の和を目的関数とし、前記補足変数導入手段で補足変数が導入された複数の条件式を制約条件として、線形計画法により前記目的関数が最適値を取る際の前記複数の条件式に含まれる変数の値を当該変数の初期値とする初期値算出手段とを有する
ことを特徴とする請求項９に記載のプログラム生成装置。
【請求項１１】
前記条件式生成手段は、
前記制御構造の条件式挿入部分に挿入される複数の条件式の候補をランダムに生成する条件式候補生成手段と、
前記制御構造におけるすべてのパスについて、各パスを通過するために前記複数の条件式が満たすべき条件を定式化し、定式化された当該複数の条件式の各々に余裕変数または不足変数を導入することにより前記複数の条件式を等式化する等式化手段と、
等式化された前記複数の条件式の各々について、前記余裕変数または前記不足変数に着目している条件式に含まれる定数を代入し、残りの変数について０を代入することにより等式を満たさない場合には、補足変数を導入する補足変数導入手段と、
前記複数の条件式のいずれかに補足変数が導入された場合に、前記補足変数の和を目的関数とし、前記余裕変数、前記不足変数または前記補足変数が含まれる等式化された前記複数の条件式を制約条件として、線形計画法により前記目的関数の最適値を算出する最適値算出手段と、
前記複数の条件式のいずれかに補足変数が導入された場合に、前記目的関数の最適値に基づいて、着目しているパスを通過可能か否かを判断するパス通過判断手段とを有する
ことを特徴とする請求項６に記載のプログラム生成装置。
【請求項１２】
前記初期値生成手段は、
前記制御構造におけるすべてのパスについて、各パスを通過するために前記条件式生成手段で求められた複数の条件式が満たすべき条件を定式化し、定式化された当該複数の条件式の各々に余裕変数または不足変数を導入することにより前記複数の条件式を等式化する等式化手段と、
等式化された前記複数の条件式の各々について、前記余裕変数または前記不足変数に着目している条件式に含まれる定数を代入し、残りの変数について０を代入することにより等式を満たさない場合には、補足変数を導入する補足変数導入手段と、
前記複数の条件式のいずれかに補足変数が導入された場合に、前記補足変数の和を目的関数とし、前記余裕変数、前記不足変数または前記補足変数が含まれる等式化された前記複数の条件式を制約条件として、線形計画法により前記目的関数が最適値を取る際の前記複数の条件式に含まれる変数の値を当該変数の初期値とする初期値算出手段とを有する
ことを特徴とする請求項１１に記載のプログラム生成装置。
【請求項１３】
前記初期値生成手段は、
前記制御構造におけるすべてのパスについて、各パスを通過するために前記条件式生成手段で求められた複数の条件式が満たすべき条件を定式化し、定式化された当該複数の条件式の各々に余裕変数または不足変数を導入することにより前記複数の条件式を等式化する等式化手段と、
等式化された前記複数の条件式の各々に補足変数を導入する補足変数導入手段と、
前記補足変数の和を目的関数とし、前記補足変数導入手段で補足変数が導入された複数の条件式を制約条件として、線形計画法により前記目的関数が最適値を取る際の前記複数の条件式に含まれる変数の値を当該変数の初期値とする初期値算出手段とを有する
ことを特徴とする請求項６に記載のプログラム生成装置。
【請求項１４】
前記初期値生成手段は、
前記制御構造におけるすべてのパスについて、各パスを通過するために前記条件式生成手段で求められた複数の条件式が満たすべき条件を定式化し、定式化された当該複数の条件式の各々に余裕変数または不足変数を導入することにより前記複数の条件式を等式化する等式化手段と、
等式化された前記複数の条件式の各々について、前記余裕変数または前記不足変数に着目している条件式に含まれる定数を代入し、残りの変数について０を代入することにより等式を満たさない場合には、補足変数を導入する補足変数導入手段と、
前記複数の条件式のいずれかに補足変数が導入された場合に、前記補足変数の和を目的関数とし、前記余裕変数、前記不足変数または前記補足変数が含まれる等式化された前記複数の条件式を制約条件として、線形計画法により前記目的関数が最適値を取る際の前記複数の条件式に含まれる変数の値を当該変数の初期値とする初期値算出手段とを有する
ことを特徴とする請求項６に記載のプログラム生成装置。
【請求項１５】
プログラムの制御構造を入力として受け、当該制御構造におけるすべてのパスを通過させることができる、当該制御構造の条件式挿入部分に挿入される複数の条件式を生成する条件式生成手段と、
前記制御構造におけるすべてのパスについて、パスごとに当該パスを通過させるための前記複数の条件式に含まれる変数の初期値を線形計画法を用いて生成する初期値生成手段と、
前記制御構造、前記複数の条件式および前記初期値に基づいてテストプログラムを生成するプログラム生成手段とを備える
ことを特徴とするプログラム生成装置。
【請求項１６】
前記複数の条件式に含まれる変数の値は、前記初期値が代入された後は不変である
ことを特徴とする請求項１５に記載のプログラム生成装置。
【請求項１７】
前記複数の条件式の各々は一次不等式である
ことを特徴とする請求項１５に記載のプログラム生成装置。
【請求項１８】
前記初期値生成手段は、
前記制御構造におけるすべてのパスについて、各パスを通過するために前記条件式生成手段で求められた複数の条件式が満たすべき条件を定式化し、定式化された当該複数の条件式の各々に余裕変数または不足変数を導入することにより前記複数の条件式を等式化する等式化手段と、
等式化された前記複数の条件式の各々に補足変数を導入する補足変数導入手段と、
前記補足変数の和を目的関数とし、前記補足変数導入手段で補足変数が導入された複数の条件式を制約条件として、線形計画法により前記目的関数が最適値を取る際の前記複数の条件式に含まれる変数の値を当該変数の初期値とする初期値算出手段とを有する
ことを特徴とする請求項１５に記載のプログラム生成装置。
【請求項１９】
前記初期値生成手段は、
前記制御構造におけるすべてのパスについて、各パスを通過するために前記条件式生成手段で求められた複数の条件式が満たすべき条件を定式化し、定式化された当該複数の条件式の各々に余裕変数または不足変数を導入することにより前記複数の条件式を等式化する等式化手段と、
等式化された前記複数の条件式の各々について、前記余裕変数または前記不足変数に着目している条件式に含まれる定数を代入し、残りの変数について０を代入することにより等式を満たさない場合には、補足変数を導入する補足変数導入手段と、
前記複数の条件式のいずれかに補足変数が導入された場合に、前記補足変数の和を目的関数とし、前記余裕変数、前記不足変数または前記補足変数が含まれる等式化された前記複数の条件式を制約条件として、線形計画法により前記目的関数が最適値を取る際の前記複数の条件式に含まれる変数の値を当該変数の初期値とする初期値算出手段とを有する
ことを特徴とする請求項１５に記載のプログラム生成装置。
【請求項２０】
プログラムの制御構造を入力として受け、当該制御構造におけるすべてのパスを通過させることができる、当該制御構造の条件式挿入部分に挿入される複数の条件式を線形計画法を用いて生成する条件式生成ステップと、
前記制御構造におけるすべてのパスについて、パスごとに当該パスを通過させるための前記複数の条件式に含まれる変数の初期値を生成する初期値生成ステップと、
前記制御構造、前記複数の条件式および前記初期値に基づいてテストプログラムを生成するプログラム生成ステップとを含む
ことを特徴とするプログラム生成方法。
【請求項２１】
前記初期値生成ステップでは、前記制御構造におけるすべてのパスについて、パスごとに当該パスを通過させるための前記複数の条件式に含まれる変数の初期値を線形計画法を用いて生成する
ことを特徴とする請求項２０に記載のプログラム生成方法。
【請求項２２】
プログラムの制御構造を入力として受け、当該制御構造におけるすべてのパスを通過させることができる、当該制御構造の条件式挿入部分に挿入される複数の条件式を生成する条件式生成ステップと、
前記制御構造におけるすべてのパスについて、パスごとに当該パスを通過させるための前記複数の条件式に含まれる変数の初期値を線形計画法を用いて生成する初期値生成ステップと、
前記制御構造、前記複数の条件式および前記初期値に基づいてテストプログラムを生成するプログラム生成ステップとを含む
ことを特徴とするプログラム生成方法。
【請求項２３】
プログラムの制御構造を入力として受け、当該制御構造におけるすべてのパスを通過させることができる、当該制御構造の条件式挿入部分に挿入される複数の条件式を線形計画法を用いて生成する条件式生成ステップと、
前記制御構造におけるすべてのパスについて、パスごとに当該パスを通過させるための前記複数の条件式に含まれる変数の初期値を生成する初期値生成ステップと、
前記制御構造、前記複数の条件式および前記初期値に基づいてテストプログラムを生成するプログラム生成ステップとを
コンピュータに実行させるためのプログラム。
【請求項２４】
前記初期値生成ステップでは、前記制御構造におけるすべてのパスについて、パスごとに当該パスを通過させるための前記複数の条件式に含まれる変数の初期値を線形計画法を用いて生成する
ことを特徴とする請求項２３に記載のプログラム。
【請求項２５】
プログラムの制御構造を入力として受け、当該制御構造におけるすべてのパスを通過させることができる、当該制御構造の条件式挿入部分に挿入される複数の条件式を生成する条件式生成ステップと、
前記制御構造におけるすべてのパスについて、パスごとに当該パスを通過させるための前記複数の条件式に含まれる変数の初期値を線形計画法を用いて生成する初期値生成ステップと、
前記制御構造、前記複数の条件式および前記初期値に基づいてテストプログラムを生成するプログラム生成ステップとを
コンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム生成装置に関し、特に、コンパイラをテストするためのテストプログラムを生成するプログラム生成装置に関する。
【背景技術】
【０００２】
コンパイラを作成する際には、コンパイラが正常に動作するか否かをテストしなければならない。このため、コンパイラのテストプログラムを自動生成する装置が従来提案されている（たとえば、特許文献１参照）。
以下、従来のテストプログラム生成装置によるテストプログラムの生成方法の一例について説明する。従来のテストプログラム生成装置では、後述するＭＬＳＬ（ミドルレベルスクリプト言語）により記述されたプログラム（以下「ＭＬＳＬプログラム」という。）からターゲットとするコンパイラ用のテストプログラムの生成が行なわれる。
【０００３】
図１０は、従来のテストプログラム生成装置によるコンパイラのテストプログラム作成処理を示すフローチャートである。テストプログラム生成装置は、図１１（ａ）に示されるようなＭＬＳＬプログラム５２から、ＭＬＳＬプログラム５２が通過し得るパスを探索する（Ｓ７２）。ＭＬＳＬは、高級言語のプログラムの制御構造を記述するための言語である。このため、ＭＬＳＬプログラム５２には、変数や式などは記述されない。
【０００４】
なお、テストプログラム生成装置は、ＭＬＳＬプログラム５２を図１１（ｂ）に示されるＭＬＳＬプログラム５４のように解釈する。すなわち、符号Ａ〜Ｆは、プログラム実行時に通過しうる通過位置を示しており、通過位置Ａ〜Ｆには、「ａ＝ａ＋１；」等の代入文や、関数などが記述されるものと解釈される。また、条件式１および２には、不等式からなる条件式が記述されるものと解釈される。
【０００５】
図１２は、ＭＬＳＬプログラム５４が通過し得るパスの一覧を示す図である。すなわち、ＭＬＳＬプログラム５４は３つのパスを通過し得る。たとえば、条件式１および２の双方が真の場合には、パス番号１に示されるように、ＭＬＳＬプログラム５４は、Ａ、Ｂ、Ｃ、Ｄ、Ｆの順に通過位置を通過する。
【０００６】
次に、テストプログラム生成装置は、テストプログラムに挿入すべき条件式をランダムに生成する（Ｓ７４）。ランダムに生成された条件式が含まれるプログラムの一例を図１１（ｃ）に示す。ここでは条件式１として「ｘ＞０」という不等式が生成され、条件式２として「ｘ＋ｙ＋ｚ＞２」という不等式が生成されている。
【０００７】
その後、テストプログラム生成装置は、生成された条件式に含まれる変数の初期値をランダムに生成し（Ｓ７６）、テストプログラムを生成する（Ｓ７８）。ランダムに生成された初期値が含まれるテストプログラムの例を図１１（ｄ）に示す。変数ｘ、ｙおよびｚの初期値として、それぞれ２、３および４を代入する関数ｉｎｉｔ＿ｖａｌ１（）が生成される。また、コンパイラのテスト関数ｆｕｎｃ１（）の先頭で、関数ｉｎｉｔ＿ｖａｌ１（）が呼び出され、変数ｘ、ｙおよびｚの初期値が設定される。したがって、関数ｉｎｉｔ＿ｖａｌ１（）を実行することにより、変数ｘ、ｙおよびｚに、それぞれ２、３および４が設定されるため、条件式１「ｘ＞０」および条件式２「ｘ＋ｙ＋ｚ＞２」がそれぞれ真となる。このため、関数ｆｕｎｃ１（）を実行すると、図１２に示されるパス番号１のパスを通過することとなる。
【０００８】
次に、テストプログラム生成装置は、通過し得るすべてのパスを通過するテストプログラムが生成されたか否かを判断する（Ｓ８０）。すべてのパスを通過するテストプログラムが生成されたと判断された場合には（Ｓ８０でＹＥＳ）、処理を終了する。すべてのパスを通過するテストプログラムが生成されていないと判断された場合には（Ｓ８０でＮＯ）、残りのパスを通過するテストプログラムを生成するために、初期値生成処理（Ｓ７６）に制御を戻す。
【０００９】
以上のようにして、テストプログラム生成装置は、すべてのパスを通過するテストプログラムを生成することができる。
【特許文献１】特開平５−３４２０５４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、従来のテストプログラム生成装置は、すべてのパスを通過するテストプログラムを生成し終えるまでには時間がかかるという問題がある。この問題の理由について以下に説明する。図１３は、初期値生成処理（図１０のＳ７６）で生成される変数ｘ、ｙおよびｚの初期値と、その時にテストプログラムが通過するパスのパス番号との関係を示す図である。たとえば、初期値として「ｘ＝２，ｙ＝３，ｚ＝４」が設定された場合には、テストプログラムは図１２に示されるパス番号１の通過パスを通過する。図１３に示されるように、初期値をランダムに発生させる場合には、同じパス（たとえば、パス番号１のパス）を通過する初期値を重複して生成し得るために、すべてのパスを通過するテストプログラムを生成し終えるまでには時間がかかってしまう。
【００１１】
また、生成される条件式によっては、すべてのパスを通過するテストプログラムを生成できないという問題もある。図１４は、このような条件式が含まれるテストプログラムの一例を示す図である。図１４に示されるプログラムでは、条件式１「ｘ＞０」と条件式２「ｘ＜−２」との双方を真にする変数ｘの初期値を生成することは不可能である。このため、図１２に示すパス番号１の通過パスを通過させることは不可能である。
【００１２】
本発明は、このような従来の問題点に鑑みてなされたものであって、すべてのパスを通過するプログラムを短時間に生成できるプログラム生成装置を提供することを目的とする。
また、確実にすべてのパスを通過可能なテストプログラムを生成できるプログラム生成装置を提供することも目的とする。
【課題を解決するための手段】
【００１３】
本発明に係るプログラム生成装置は、プログラムの制御構造を入力として受け、当該制御構造におけるすべてのパスを通過させることができる、当該制御構造の条件式挿入部分に挿入される複数の条件式を線形計画法を用いて生成する条件式生成手段と、前記制御構造におけるすべてのパスについて、パスごとに当該パスを通過させるための前記複数の条件式に含まれる変数の初期値を生成する初期値生成手段と、前記制御構造、前記複数の条件式および前記初期値に基づいてテストプログラムを生成するプログラム生成手段とを備える。
【００１４】
この構成によると、制御構造において通過可能なすべてのパスを通過させることができる複数の条件式を線形計画法を用いて生成している。このため、すべてのパスを通過するプログラムを短時間に生成することができる。また、プログラムを実行した際に、確実にすべてのパスを通過することができる。
好ましくは、前記初期値生成手段は、前記制御構造におけるすべてのパスについて、パスごとに当該パスを通過させるための前記複数の条件式に含まれる変数の初期値を線形計画法を用いて生成する。
【００１５】
このように、初期値生成手段においても線形計画法を用い、パスごとに複数の条件式に含まれる初期値を生成している。このため、同じパスを通過させる初期値を何度も生成することがない。また、条件式生成手段の処理により、各パスを通過させる初期値が存在することが保証されている。このため、すべてのパスを通過するプログラムを短時間に生成することができる。
【００１６】
本発明の他の局面に係るプログラム生成装置は、プログラムの制御構造を入力として受け、当該制御構造におけるすべてのパスを通過させることができる、当該制御構造の条件式挿入部分に挿入される複数の条件式を生成する条件式生成手段と、前記制御構造におけるすべてのパスについて、パスごとに当該パスを通過させるための前記複数の条件式に含まれる変数の初期値を線形計画法を用いて生成する初期値生成手段と、前記制御構造、前記複数の条件式および前記初期値に基づいてテストプログラムを生成するプログラム生成手段とを備える。
【００１７】
この構成によると、線形計画法を用い、パスごとに複数の条件式に含まれる初期値が生成される。このため、同じパスを通過させる初期値を何度も生成することがなく、すべてのパスを通過するプログラムを短時間に生成することができる。
【００１８】
なお、本発明は、以上のようなプログラム生成装置として実現することができるだけでなく、その手段をステップとするプログラム生成方法として実現したり、プログラム生成方法をコンピュータに実行させるプログラムとして実現することもできる。そのようなプログラムは、ＣＤ−ＲＯＭ（Compact Disc-Read Only Memory）等の記録媒体やインターネット等の伝送媒体を介して配信することができるのは言うまでもない。
【発明の効果】
【００１９】
本発明によると、すべてのパスを通過するテストプログラムを短時間に生成することができる。
また、確実にすべてのパスを通過することができるテストプログラムを生成することができる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明の具体的な実施の形態について、図面を参照しながら説明する。
図１は、本発明の実施の形態に係るプログラム生成装置の外観図である。プログラム生成装置２０は、コンパイラのテストプログラムを自動生成する装置であり、コンピュータ１と、キーボード５と、マウス６と、コンピュータ１の演算結果等の情報を提示するためのモニタ２と、ＣＤ−ＲＯＭ装置７と、通信モデム９とを備える。
【００２１】
プログラム生成装置２０で実行されるプログラムは、ＣＤ−ＲＯＭ８に記憶され、ＣＤ−ＲＯＭ装置７により読み取られる。または、コンピュータネットワーク上に存在し、通信モデム９を介して読み取られる。
図２は、本発明の実施の形態に係るプログラム生成装置の機能的構成を示すブロック図である。テストプログラム生成装置２０は、条件式生成部２２と、初期値生成部２４とを備える。以下の例では、コンパイラとしてＣ言語のコンパイラを想定するが、この言語に限定されるものではない。
【００２２】
条件式生成部２２は、ＭＬＳＬプログラム２６を読み込み、ＭＬＳＬプログラム２６の条件式挿入部分に挿入すべき条件式を生成する。ＭＬＳＬプログラム２６とは、背景技術と同様にＭＬＳＬ（ミドルスクリプト言語）により記述されたプログラムであり、生成すべきテストプログラムの制御構造を記述している。
初期値生成部２４は、条件式生成部２２で生成された条件式に含まれる変数の初期値を生成し、テストプログラム２８を作成する。テストプログラム２８は、Ｃ言語で記述され、Ｃ言語コンパイラでコンパイルされた後、実行される。
【００２３】
以上のように構成されたテストプログラム生成装置２０の動作について以下に説明する。図３は、テストプログラム生成装置２０の実行する処理のフローチャートである。条件式生成部２２は、ＭＬＳＬプログラム２６を読み込み、ＭＬＳＬプログラム２６に記述されている制御構造が通過し得るパスの探索を行なう（Ｓ２）。たとえば、条件式生成部２２は、図４（ａ）に示されるＭＬＳＬプログラム３２を読み込むものとする。なお、条件式生成部２２は、ＭＬＳＬプログラム３２を図４（ｂ）に示されるＭＬＳＬプログラム３４のように解釈する。すなわち、従来のテストプログラム生成装置と同様、符号Ａ〜Ｆは、プログラム実行時に通過し得る通過位置を示しており、通過位置Ａ〜Ｆには、「ａ＝ａ＋１；」等の代入文や、関数などが記述されるものと解釈される。また、条件式１および２には、不等式からなる条件式が記述されるものと解釈される。
【００２４】
図５は、ＭＬＳＬプログラム３４が通過し得るパスの一覧を示す図である。すなわち、ＭＬＳＬプログラム３４は３つのパスを通過し得る。たとえば、条件式１および２の双方が真の場合には、パス番号１に示されるように、プログラムは、Ａ、Ｂ、Ｆの順に通過位置を通過する。
【００２５】
次に、条件式生成部２２は、線形計画法を用いてＭＬＳＬプログラムが通過し得るパスのすべてを確実に通過することが可能な条件式を生成し、ＭＬＳＬプログラムの条件式挿入部分に生成された条件式を挿入する（Ｓ４）。条件式生成処理については、後に詳述するが、図４（ｃ）に示されるプログラム３６のように、条件式１および２に挿入すべき不等式「２ｘ＋５ｙ＜８」および「ｘ＋３ｙ−ｚ＜＝６」がそれぞれ生成される。
【００２６】
最後に、初期値生成部２４は、線形計画法を用いて、生成された条件式に含まれる変数の初期値を生成する処理を行ない、コンパイラ用のテストプログラムを作成する（Ｓ６）。初期値生成処理については、後に詳述するが、図４（ｄ）に示されるようテストプログラム３８において、初期値設定関数ｉｎｉｔ＿ｖａｌ２（）が生成される。また、関数ｉｎｉｔ＿ｖａｌ２（）は、コンパイラのテスト関数ｆｕｎｃ２（）の先頭で呼び出され、変数ｘ、ｙおよびｚの初期値（ｘ＝０；ｙ＝１．６２；ｚ＝−１．０４）が設定される。テスト関数ｆｕｎｃ２（）では、初期値設定関数ｉｎｉｔ＿ｖａｌ２（）を呼び出すことにより、プログラム３６に示される条件式１（２ｘ＋５ｙ＝８．１＜８）が偽、条件式２（ｘ＋３ｙ−ｚ＝５．９＜＝６）が真となり、図５に示されるパス番号２のパスを通過することとなる。その他のパスを通過する初期値についても初期値生成処理（Ｓ６）で生成される。なお、条件式に含まれる変数の値は、初期値が代入された後は不変であるものとする。これは、条件式および初期値を求める際に線形計画法を用いる際の前提となる条件である。
【００２７】
次に、条件式生成部２２による条件式生成処理（図３のＳ４）について、具体例を示しながら詳細に説明する。図６は、条件式生成処理を詳細に説明するためのフローチャートである。
条件式生成部２２は、条件式をランダムに生成し、生成した条件式をＭＬＳＬプログラムの条件式挿入部分に挿入する（Ｓ１２）。なお、生成される条件式は１次不等式であるものとする。すなわち、条件式には２次以上の次数を有する式は含まれない。また、Ｃ言語における「＆＆」や「｜｜」などの論理演算子は含まれない。たとえば、条件式生成部２２は、条件式「２ｘ＋５ｙ＜８」および「ｘ＋３ｙ−ｚ＜＝６」を生成し、図４（ｂ）に示されるＭＬＳＬプログラム３４の条件式挿入部分（条件式１および２）に挿入する。すると、図４（ｃ）に示されるプログラム３６が得られる。
【００２８】
条件式生成部２２は、ＭＬＳＬプログラムが通過し得るパスの各々について、プログラム実行時にパスを通過させることが可能か否かを、線形計画法を用いて調べる。すなわち、条件式生成部２２は、着目しているパスを通過させるために条件式が満たすべき条件を定式化するとともに、定式化された条件式を等式化する（Ｓ１６）。
たとえば、プログラム３６に示される条件式において図５に示されるパス番号２のパスを通過させるためには、次式（１）および（２）にそれぞれ示されるように条件式「２ｘ＋５ｙ＜８」が偽（ＦＡＬＳＥ）となり、条件式「ｘ＋３ｙ−ｚ＜＝６」が真（ＴＲＵＥ）となることが必要である。
【００２９】
２ｘ＋５ｙ＜８＝＝ＦＡＬＳＥ                    …（１）
ｘ＋３ｙ−ｚ＜＝６＝＝ＴＲＵＥ                  …（２）
このため、式（１）および（２）は、次式（３）および（４）のように定式化される。
２ｘ＋５ｙ＞＝８                                …（３）
ｘ＋３ｙ−ｚ＜＝６                              …（４）
定式化された条件式を等式化するために、まず、不等式の左辺に存在する定数は右辺に移項し、不等式の右辺に存在する変数は左辺に移項する。それとともに、右辺の値が負の場合には両辺に（−１）を乗算することにより、右辺の定数値を非負にする。式（３）および（４）は、左辺に定数が存在せず、右辺に変数が存在せず、かつ右辺の定数値が非負であるため、ここでの処理は行なわれない。
【００３０】
次に、線形計画法に基づいて、式（３）には、余裕変数（サープラス変数）ｖ1が導入され、式（４）には、不足変数（スラック変数）ｖ2が導入される。また、式（３）および（４）に含まれる変数ｘが（ｘ1−ｘ2）（ただし、ｘ1、ｘ2＞＝０）に変数変換される。変数ｙおよびｚについても同様の変数変換が行なわれる。これにより、式（３）および（４）が次式（５）および（６）のようにそれぞれ等式化される。
【００３１】
２ｘ1−２ｘ2＋５ｙ1−５ｙ2−ｖ1＝８            …（５）
ｘ1-ｘ2+３ｙ1−３ｙ2−ｚ1＋ｚ2＋ｖ2＝６        …（６）
ただし、ｘ1、ｘ2、ｙ1、ｙ2、ｚ1、ｚ2、ｖ1、ｖ2＞＝０
【００３２】
次に、条件式生成部２２は、等式化処理（Ｓ１６）で生成された各等式の余裕変数または不足変数に右辺の値を代入し、その他の変数の値を０とすることにより等式が満たされるか否かを調べる（Ｓ２０）。等式が満たされない場合には（Ｓ２０でＮＯ）、等式の左辺に補足変数を追加する（Ｓ２２）。以上の処理をすべての等式について行なう（Ｓ１８〜Ｓ２４）。
【００３３】
たとえば、式（５）では変数ｖ1に右辺の値８を代入し、他の変数に０を代入しても等式を満たすことができない。このため、式（５）の左辺に補足変数ｍ1を追加し、次式（７）を作成する。一方、式（６）では変数ｖ2に右辺の値６を代入し、他の変数に０を代入することにより等式を満たすことができる。このため、式（６）には補足変数は追加されない。
【００３４】
２ｘ1−２ｘ2＋５ｙ1−５ｙ2−ｖ1＋ｍ1＝８        …（７）
ただし、ｘ1、ｘ2、ｙ1、ｙ2、ｖ1、ｍ1＞＝０
【００３５】
次に、条件式生成部２２は、いずれかの等式について補足変数を追加したか否かを判断する（Ｓ２６）。補足変数を追加した場合には（Ｓ２６でＹＥＳ）、補足変数の和を目的関数ｆとする（Ｓ２８）。すなわち、上述の例では、目的関数ｆは次式（８）により示される。
【００３６】
ｆ＝ｍ1                                          …（８）
条件式生成部２２は、等式化処理（Ｓ１６）または補足変数追加処理（Ｓ２２）で求められた等式の条件下で、目的関数ｆの最小値を線形計画法に従い求める（Ｓ３０）。すなわち、上述の例では、式（８）で示される目的関数ｆの最小値を式（７）および式（６）で示される制約条件下で算出する。その結果、次式（９）〜（１１）を満たす場合に、目的関数ｆの最小値は０となる。
【００３７】
ｘ＝ｘ1−ｘ2＝０                                …（９）
ｙ＝ｙ1−ｙ2＝１．６２                        …（１０）
ｚ＝ｚ1−ｚ2＝−１．０４                      …（１１）
すなわち、変数ｘ、ｙおよびｚの初期値を式（９）〜（１１）のように設定すれば図５に示されるパス番号２のパスを通過することができる。
【００３８】
目的関数ｆの最小値が０の場合（Ｓ３２でＹＥＳ）、またはいずれの等式にも補足変数を追加していなければ（Ｓ２６でＮＯ）、着目しているパスが通過可能であることが証明されたことになる。したがって、他のパスについても同一の条件式で通過することが可能か否かを調べる処理（Ｓ１６〜Ｓ３２）を繰返す（Ｓ１４〜Ｓ３４）。
目的関数ｆの最小値が０でなければ（Ｓ３２でＮＯ）、現在設定されている条件式では着目しているパスを通過することができないことになる。このため、再度、条件式をランダム生成し（Ｓ１２）、条件式に含まれる変数の初期値を変化させることによりすべてのパスを通過させることが可能な条件式が見つかるまで、上述の処理を繰返す（Ｓ１４〜Ｓ３４）。
【００３９】
以上説明した条件式生成処理を実行することにより、初期値を適切に選択することによりすべてのパスを通過可能な条件式が含まれるプログラムが生成されることになる。
【００４０】
次に、目的関数ｆの最小値が０とならない条件式の一例について、図７および図８を参照しながら説明する。条件式生成部２２は、図７（ａ）に示されるＭＬＳＬプログラム４２を読み込むものとする。条件式生成部２２は、ＭＬＳＬプログラム４２を図７（ｂ）に示されるＭＬＳＬプログラム４４のように解釈する。図７（ｃ）に示されるプログラム４６には、条件式ランダム生成処理（図６のＳ１２）でされた生成された条件式がＭＬＳＬプログラム４４の条件式挿入部分（条件式１、２および３）に挿入されている。たとえば、条件式１の挿入部分には不等式「２ｘ＋５ｙ＜８」が挿入されている。
【００４１】
図８は、ＭＬＳＬプログラム４４が通過し得るパスの一覧を示す図である。すなわち、ＭＬＳＬプログラム４４は、５つのパスを通過し得る。たとえば、プログラム４６の条件式１「２ｘ＋５ｙ＜８」が偽で、条件式２「ｘ＋３ｙ−ｚ＜＝６」が真で、条件式３「ｘ＋２ｙ＋ｚ＜＝０」が真の場合には、パス番号２のパスを通過することになる。
パス番号２のパスを通過するためには、次式（１２）〜（１４）が満たされることが必要である。
【００４２】
２ｘ＋５ｙ＜８＝＝ＦＡＬＳＥ                    …（１２）
ｘ＋３ｙ−ｚ＜＝６＝＝ＴＲＵＥ                  …（１３）
ｘ＋２ｙ＋ｚ＜＝０＝＝ＴＲＵＥ                  …（１４）
このため、式（１２）〜（１４）は、等式化処理（Ｓ１６）において、まず、次式（１５）〜（１７）のようにそれぞれ定式化される。
【００４３】
２ｘ＋５ｙ＞＝８                                …（１５）
ｘ＋３ｙ−ｚ＜＝６                              …（１６）
ｘ＋２ｙ＋ｚ＜＝０                              …（１７）
定式化された条件式の各変数を変数変換し、式（１５）に余裕変数ｖ1を導入し、式（１６）および式（１７）に不足変数ｖ2およびｖ3をそれぞれ導入することにより、式（１５）〜（１７）は、次式（１８）〜（２０）のようにそれぞれ等式化される。
【００４４】
２ｘ1−２ｘ2＋５ｙ1−５ｙ2−ｖ1＝８          …（１８）
ｘ1-ｘ2+３ｙ1−３ｙ2−ｚ1＋ｚ2＋ｖ2＝６      …（１９）
ｘ1-ｘ2＋２ｙ1−２ｙ2＋ｚ1−ｚ2＋ｖ3＝０    …（２０）
ただしｘ1、ｘ2、ｙ1、ｙ2、ｚ1、ｚ2、ｖ1、ｖ2、ｖ3＞＝０
【００４５】
補足変数追加処理（Ｓ１８〜Ｓ２４）では、式（１８）に補足変数ｍ1が追加され、次式（２１）が作成される。
【００４６】
２ｘ1−２ｘ2＋５ｙ1−５ｙ2−ｖ1＋ｍ1＝８      …（２１）
ただし、ｘ1、ｘ2、ｙ1、ｙ2、ｖ1、ｍ1＞＝０
従って、目的関数ｆは次式（２２）のように示される。
ｆ＝ｍ1                                        …（２２）
【００４７】
初期値生成部２４は、目的関数ｆの最小値を式（２１）、（１８）および（１９）で示される制約条件下で算出するが（Ｓ３０）、目的関数ｆの最小値は０よりも大きくなる。このため、式（１２）〜（１４）を同時に満たす変数ｘ、ｙおよびｚは存在しないことになり、パス番号２のパスは通過できないこととなる。
その結果、再度、条件式がランダムに生成されることになる。
【００４８】
次に、初期値生成部２４による初期値生成処理（図３のＳ６）について、具体例を示しながら詳細に説明する。図９は、初期値生成処理を詳細に説明するためのフローチャートである。
初期値生成部２４は、ＭＬＳＬプログラムが通過し得るパスの各々について、線形計画法を用いて条件式に含まれる変数の初期値を求め、テストプログラムを作成する。すなわち、初期値生成部２４は、着目しているパスを通過させるために条件式が満たすべき条件を定式化するとともに、定式化された条件式を等式化する（Ｓ４４）。この処理は、図６に示した条件式生成部２２による等式化処理（Ｓ１６）と同様であるため、その詳細な説明は繰返さない。
【００４９】
次に、初期値生成部２４は、等式化された条件式に補足変数を追加する処理（Ｓ４６〜Ｓ５２）を実行する。この処理も、図６に示した条件式生成部２２による補足変数追加処理（Ｓ１８〜Ｓ２４）と同様であるため、その詳細な説明は繰返さない。
初期値生成部２４は、等式化されたいずれかの条件式に補足変数を追加したか否かを判断する（Ｓ５４）。補足変数を追加していれば（Ｓ５４でＹＥＳ）、補足変数の和を目的関数とし（Ｓ５６）、等式化処理（Ｓ４４）または補足変数追加処理（ＳＳ５０）で求められた等式の条件下で、目的関数ｆの最小値が０となる時の変数の値を線形計画法を用いて算出する（Ｓ５８）。
【００５０】
たとえば、式（８）で示される目的関数ｆが０となるときの条件式に含まれる変数の値を式（７）および式（６）で示される制約条件下で算出すると、式（９）〜（１１）のようになる。
補足変数を追加していなければ（Ｓ５４でＮＯ）、条件式に含まれる変数の初期値を０に設定する（Ｓ６０）。
【００５１】
条件式に含まれる変数の初期値を求めた後（Ｓ５８、Ｓ６０）、初期値生成部２４は、条件式に当該初期値を設定するようなテストプログラムを生成する（Ｓ６２）。たとえば、図５に示されるパス番号２のパスを通過するテストプログラムとして、図４（ｄ）に示されるようなテストプログラム３８が作成される。テストプログラム３８では、上述したように、テスト関数ｆｕｎｃ２（）の先頭で、初期値設定関数ｉｎｉｔ＿ｖａｌ２（）が呼び出されることにより、条件式に含まれる変数に初期値が設定される。この初期値に基づいて、テスト関数ｆｕｎｃ２（）を実行することにより、パス番号２のパスを通過するテストが可能となる。
【００５２】
その他のパスについても同様の処理を行ない、テストプログラムを作成する（Ｓ４２〜Ｓ６４）。なお、その他のパスにおける初期値設定関数およびテスト関数は、テストプログラム３８と同一のファイル内に格納するようにしても良いし、異なるファイル内に格納するようにしても良い。
以上のような処理により、ＭＬＳＬプログラムが通過し得るすべてのパスを通過させることができるテストプログラムの生成が可能となる。
【００５３】
以上、本発明に係るテストプログラム生成装置について、実施の形態に基づいて説明したが、本発明はこの実施の形態に限定されるものではない。
たとえば、補足変数は、すべての等式に導入するようにしても良い。
また、上述の実施の形態では、条件式は１次不等式であるものとしたが、これに限られるものではなく、１次方程式など線形計画法を適用できるものであれば、どのような形式の式であっても良い。
【００５４】
以上説明したように、本発明によると、すべてのパスを通過するテストプログラムを短時間に生成することができる。
また、確実にすべてのパスを通過することができるテストプログラムを生成することができる。
【産業上の利用可能性】
【００５５】
本発明によると、高級言語用のコンパイラを作成する際に、そのコンパイラが正常に動作するか否かをチェックするためのテストプログラムを高速かつ正確に作成するのに適している。
【図面の簡単な説明】
【００５６】
【図１】本発明の実施の形態に係るプログラム生成装置の外観図である。
【図２】本発明の実施の形態に係るプログラム生成装置の機能的構成を示すブロック図である。
【図３】テストプログラム生成装置の実行する処理のフローチャートである。
【図４】ＭＬＳＬプログラムからテストプログラムを生成する過程を説明するための図である。（ａ）および（ｂ）は、ＭＬＳＬプログラムの一例を示す図である。（ｃ）は、条件式が生成された後のプログラムの一例を示す図である。（ｄ）は、初期値が生成された後のテストプログラムの一例を示す図である。
【図５】図４（ｂ）に示すＭＬＳＬプログラムが通過し得るパスの一覧を示す図である。
【図６】条件式生成処理を詳細に説明するためのフローチャートである。
【図７】ＭＬＳＬプログラムからテストプログラムを生成する過程において、条件式の生成に失敗する例を説明するための図である。（ａ）および（ｂ）は、ＭＬＳＬプログラムの一例を示す図である。（ｃ）は、条件式の候補が生成された後のプログラムの一例を示す図である。
【図８】図７（ｂ）に示すＭＬＳＬプログラムが通過し得るパスの一覧を示す図である。
【図９】初期値生成処理を詳細に説明するためのフローチャートである。
【図１０】従来のテストプログラム生成装置によるコンパイラのテストプログラム作成処理を示すフローチャートである。
【図１１】従来のテストプログラム生成装置により、ＭＬＳＬプログラムからテストプログラムを生成する過程を説明するための図である。（ａ）および（ｂ）は、ＭＬＳＬプログラムの一例を示す図である。（ｃ）は、条件式が生成された後のプログラムの一例を示す図である。（ｄ）は、初期値が生成された後のテストプログラムの一例を示す図である。
【図１２】図１１（ｂ）に示されるＭＬＳＬプログラムが通過し得るパスの一覧を示す図である。
【図１３】従来のテストプログラム生成装置により生成される変数ｘ、ｙおよびｚの初期値と、その時にテストプログラムが通過するパスのパス番号との関係を示す図である。
【図１４】従来のテストプログラム生成装置の問題点を説明するための図である。
【符号の説明】
【００５７】
２０  テストプログラム生成装置
２２  条件式生成部
２４  初期値生成部
２６  ＭＬＳＬプログラム
２８  テストプログラム
【図１】
2005032213.tif 000003
【図２】
2005032213.tif 000004
【図３】
2005032213.tif 000005
【図４】
2005032213.tif 000006
【図５】
2005032213.tif 000007
【図６】
2005032213.tif 000008
【図７】
2005032213.tif 000009
【図８】
2005032213.tif 000010
【図９】
2005032213.tif 000011
【図１０】
2005032213.tif 000012
【図１１】
2005032213.tif 000013
【図１２】
2005032213.tif 000014
【図１３】
2005032213.tif 000015
【図１４】
2005032213.tif 000016