(57)【要約】【課題】文の挿入や削除、変更が施されているコードクローンを検出し、検出したコードクローンに基づいてプログラムの修正コストを算出するために有効な情報を出力するソースプログラム解析システム、ソースプログラム解析方法およびプログラムを提供する。【解決手段】一致部分検出部１１は、ソースプログラム１から内容が互いに一致する一致部分を検出する。類似部分検出部１３は、一致部分検出部１１が検出した一致部分に基づいて、ソースプログラム１から内容が互いに一致する部分と一致しない部分とで構成され、かつ、基準に合致する類似部分を検出する。非一致部分解析部１４は、類似部分検出部１３が検出した類似部分を分析し、他の類似部分とどれだけ類似しているかを示す指標を出力する。【選択図】図２３
2014199569.tif 000002
【特許請求の範囲】
【請求項１】
ソースプログラムから、内容が互いに一致する一致部分を検出する一致部分検出手段と、
前記一致部分検出手段が検出した一致部分に基づいて、ソースプログラムから内容が互いに一致する部分と一致しない部分とで構成され、かつ、基準に合致する類似部分を検出する類似部分検出手段と、
前記類似部分検出手段が検出した類似部分を分析し、他の類似部分とどれだけ類似しているかを示す指標を出力する非一致部分分析手段と、を備える、
ことを特徴とするソースプログラム解析システム。
【請求項２】
前記類似部分検出手段は、前記一致部分検出手段が検出した一致部分から、間に他の一致部分を挟まずに同じ出現順番で配置されている複数の一致部分を検出し、当該複数の一致部分と、当該複数の一致部分にはさまれた一致しない部分とで構成される類似部分を検出する、
ことを特徴とする請求項１に記載のソースプログラム解析システム。
【請求項３】
前記非一致部分分析手段は、前記類似部分検出手段が検出した類似部分の一致しない部分の構文が、他の類似部分の一致しない部分の構文とどれだけ類似しているかを示す構文類似度を算出する、
ことを特徴とする請求項１または２に記載のソースプログラム解析システム。
【請求項４】
前記非一致部分分析手段は、前記類似部分検出手段が検出した類似部分の一致しない部分を構成要素に分割し、当該構成要素のうち他の類似部分の一致しない部分と共通する構成要素の割合から構文類似度を算出する、
ことを特徴とする請求項３に記載のソースプログラム解析システム。
【請求項５】
前記非一致部分分析手段は、前記類似部分検出手段が検出した類似部分の一致しない部分を構成要素に分割し、他の類似部分の一致しない部分と共通する構成要素の構文構造を出力する、
ことを特徴とする請求項３または４に記載のソースプログラム解析システム。
【請求項６】
前記非一致部分分析手段は、前記類似部分検出手段が検出した類似部分の一致しない部分を構文木構造に基づいて分析することにより、構成要素ごとに分割し、あるいは他の類似部分の一致しない部分と共通する構成要素の構文構造を出力する、
ことを特徴とする請求項４または５に記載のソースプログラム解析システム。
【請求項７】
ソースプログラムから、実行単位の開始あるいは終了を示す標識を検出する実行単位標識検出手段をさらに備え、
前記類似部分検出手段は、前記一致部分検出手段が検出した一致部分の直前にある実行単位標識検出手段が検出した第１の標識および当該一致部分の直後にある実行単位標識検出手段が検出した第２の標識を検出し、
前記類似部分検出手段は、前記ソースプログラムにおける前記第１の標識の終了位置と、前記一致部分の直前にある他の一致部分の終了位置とのうち後にある方から前記一致部分の開始位置までの部分を前部分として抽出し、かつ、前記一致部分の終了位置から前記ソースプログラムにおける前記第２の標識の開始位置と、前記一致部分の直後にある他の一致部分の開始位置とのうち前にある方までの部分を後部分として抽出し、
前記類似部分検出手段は、前記前部分と、前記一致部分と、前記後部分とを有する類似部分を検出する、
ことを特徴とする請求項１から６のいずれか１項に記載のソースプログラム解析システム。
【請求項８】
前記類似部分検出手段は、前記前部分と前記一致部分とを有する類似部分、および前記一致部分と前記後部分とを有する類似部分を検出する、
ことを特徴とする請求項７に記載のソースプログラム解析システム。
【請求項９】
ソースプログラムから、内容が互いに一致する一致部分を検出する一致部分検出ステップと、
前記一致部分検出ステップで検出した一致部分に基づいて、ソースプログラムから内容が互いに一致する部分と一致しない部分とで構成され、かつ、基準に合致する類似部分を検出する類似部分検出ステップと、
前記類似部分検出ステップで検出した類似部分を分析し、他の類似部分とどれだけ類似しているかを示す指標を出力する非一致部分分析ステップと、を備える、
ことを特徴とするソースプログラム解析方法。
【請求項１０】
コンピュータに、
ソースプログラムから、内容が互いに一致する一致部分を検出する一致部分検出機能、
前記一致部分検出機能が検出した一致部分に基づいて、ソースプログラムから内容が互いに一致する部分と一致しない部分とで構成される所定の基準を満たす類似部分を検出する類似部分検出機能、
前記類似部分検出機能が検出した類似部分を分析し、他の類似部分とどれだけ類似しているかを示す指標を出力する非一致部分分析機能、を実現させる、
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソースプログラム解析システム、ソースプログラム解析方法およびプログラムに関する。
【背景技術】
【０００２】
現在、多くの企業や組織で大規模なコンピュータシステムが様々な目的で稼働している。このようなコンピュータシステムの運営においては、稼働しているソフトウェアの不具合を修正したり、あるいは必要な機能を追加したりといった保守活動が必要となる。コンピュータシステムを利用する企業や組織には、ソフトウェアの修正や改良に必要となるコストを的確に把握したいという要求が存在する。
【０００３】
ソフトウェアの保守コストを見積もる際、いわゆるコードクローンの位置や数から保守コストを見積もる技術が存在する。コードクローンとは、プログラムのソースコード上に存在する部分的な複製を指し、コードクローンの存在はソフトウェアの保守性を低下させることが知られている。例えば、コードクローンの中に不具合が発見された場合、不具合を解消するために、開発者は同一の内容を持つコードクローンについて、個別に修正を要するか検討しなければならなくなるためである。特に大規模なシステムにおいては、一人の開発者がソフトウェア全体を検証し、全てのコードクローンについて修正の適否を検討することは困難である。
【０００４】
コードクローンを検出する技術について、現在までいろいろな研究がなされている。
非特許文献１によると、コードクローンは以下の３種類に分類される。タイプ１は、空白、括弧等を除いて完全に一致するコードクローンである。タイプ２は、変数名、ラベル名、手続き名等のユーザ定義名称、または変数の型など一部の予約語のみが異なるコードクローンである。タイプ３は、タイプ２のコードクローンに、さらに文の挿入や削除、変更が施されているコードクローンである。非特許文献１は、このうちタイプ１および２のコードクローンを検出する技術を開示している。
【０００５】
非特許文献２は、コードクローンを検出するシステムおよびソフトウェアを開示している。非特許文献２が開示するソフトウェア（ＣＣＦｉｎｄｅｒＸ）は、処理対象のソースプログラムを字句解析し、ソースプログラムに含まれるコードクローンを検出する。このソフトウェアは、上記のタイプ１およびタイプ２のコードクローンを検出することができる。
【０００６】
特許文献１は、関数単位でコードクローンを検出し、そのコードクローンの類似性を評価するシステムを開示している。特許文献１が開示するシステムは、ソースプログラムを関数単位で解析し、利用者が指定した類似度検出条件に合致するものを検出する。利用者は、内容が一致するもの（タイプ１のコードクローン）、あるいは一部が異なるもの（タイプ２または３のコードクローン）の検出を指定できる。
また、特許文献１が開示するシステムは、検出したコードクローンにおいて、ソースコードが互いに一致するか、関数インターフェースが同一かの２点から評価し、その結果からコードクローンを４カテゴリに分類する。操作者は、このカテゴリを参照することで、例えば関数インターフェースのみ異なるコードクローンが他にあるか、ソースコードが一致するコードクローンが他にあるかを知ることができ、コードクローンを再利用する際に参考にすることができる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１２−１６４２１１号公報
【非特許文献】
【０００８】
【非特許文献１】肥後芳樹、楠本信二、井上克郎、「コードクローン検出とその関連技術」電子情報通信学会論文誌Ｄ、ＶＯＬ．Ｊ９１−Ｄ、Ｎｏ６（２００８）、pp．１４６５−１４８１．
【非特許文献２】ＣＣＦｉｎｄｅｒホームページ＜URL: http://www.ccfinder.net ＞
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上述の文献で開示された技術では、文の挿入や削除、変更が施されているコードクローンの保守コストを算出するための有効な情報を出力できないという課題がある。
【００１０】
より具体的に説明すると、非特許文献１および２は、文の挿入や削除、変更が施されているコードクローンを検出する技術を開示していない。ソフトウェア開発において開発者がソースプログラムの一部をコピーして再利用する場合、そのまま利用することよりも、改変を加えて利用することのほうが多い。従って、ソフトウェアを修正や改良する際にはタイプ３のコードクローンも対象とする必要がある。この点で、非特許文献１および２の技術によるコードクローンの検出だけでは不十分である。また、非特許文献１および２は、検出したコードクローンについて、類似性などの観点から評価する技術を開示していない。従って、検出したコードクローンへの修正や改良を行う際の作業コストの見積もりの指標となる情報を提供することができない。
【００１１】
また、特許文献１が開示する技術は、関数単位で再利用判定を行うものであり、関数内部に存在するコードクローンを検出することができない。ソフトウェアを保守する上では関数内のコードクローンへの修正を要するケースもあり、そのような場合は、特許文献１が開示する技術は十分な情報を得ることができない。また、関数のないプログラム言語で記述されたソースプログラムを解析することもできない。また、特許文献１が開示するシステムは、ソースコードが互いに一致するか、関数インターフェースが同一かの２点からコードクローンを評価する。しかし、この２つの観点の評価のみでは、ソフトウェアの修正や改良を行う際に、どのコードクローンをどの程度変更する必要があるかを示すことができない。従って、ソフトウェアの保守を行う上では、有効な情報とは言えなかった。
【００１２】
本発明は、以上の問題点に着目してなされたものであり、文の挿入や削除、変更が施されているコードクローンを検出し、検出したコードクローンに基づいてそのプログラムの修正コストを算出するために有効な情報を出力するソースプログラム解析システム、ソースプログラム解析方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記の目的を達成するため、本発明の第１の観点にかかるソースプログラム解析システムは、
ソースプログラムから、内容が互いに一致する一致部分を検出する一致部分検出手段と、
前記一致部分検出手段が検出した一致部分に基づいて、ソースプログラムから内容が互いに一致する部分と一致しない部分とで構成され、かつ、基準に合致する類似部分を検出する類似部分検出手段と、
前記類似部分検出手段が検出した類似部分を分析し、他の類似部分とどれだけ類似しているかを示す指標を出力する非一致部分分析手段と、を備える、
ことを特徴とする。
【００１４】
上記の目的を達成するため、本発明の第２の観点にかかるソースプログラム解析方法は、
ソースプログラムから、内容が互いに一致する一致部分を検出する一致部分検出ステップと、
前記一致部分検出ステップで検出した一致部分に基づいて、ソースプログラムから内容が互いに一致する部分と一致しない部分とで構成され、かつ、基準に合致する類似部分を検出する類似部分検出ステップと、
前記類似部分検出ステップで検出した類似部分を分析し、他の類似部分とどれだけ類似しているかを示す指標を出力する非一致部分分析ステップと、を備える、
ことを特徴とする。
【００１５】
上記の目的を達成するため、本発明の第３の観点にかかるプログラムは、コンピュータに、
ソースプログラムから、内容が互いに一致する一致部分を検出する一致部分検出機能、
前記一致部分検出機能が検出した一致部分に基づいて、ソースプログラムから内容が互いに一致する部分と一致しない部分とで構成される所定の基準を満たす類似部分を検出する類似部分検出機能、
前記類似部分検出機能が検出した類似部分を分析し、他の類似部分とどれだけ類似しているかを示す指標を出力する非一致部分分析機能、を実現させる、
ことを特徴とする。
【発明の効果】
【００１６】
本発明によれば、文の挿入や削除、変更が施されているコードクローンを検出し、検出したコードクローンに基づいてプログラムの修正コストを算出するために有効な情報を出力するソースプログラム解析システム、ソースプログラム解析方法およびプログラムを実現できる。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施形態にかかるソースプログラム解析システムのハードウェア構成を示した図である。
【図２】ソースプログラム解析システムの機能を示したブロック図である。
【図３】ソースプログラム解析システムのデータの流れを示した図である。
【図４】一致部分情報ＤＢの内容を示した図である。
【図５】文法定義情報ＤＢの内容を示した図である。
【図６】実行単位標識情報ＤＢの内容を示した図である。
【図７】類似部分情報ＤＢの内容を示した図である。
【図８】非一致構造情報ＤＢの内容を示した図である。
【図９】実施形態の説明におけるソースプログラムを示した図である。
【図１０】ソースプログラム解析処理を示したフローチャートである。
【図１１】一致部分検出処理を示したフローチャートである。
【図１２】一致部分検出処理後の一致部分情報ＤＢの内容を示した図である。
【図１３】実行単位標識検出処理を示したフローチャートである。
【図１４】実行単位標識検出処理で参照される文法定義情報ＤＢの内容を示した図である。
【図１５】実行単位標識検出処理後の実行単位標識情報ＤＢの内容を示した図である。
【図１６】類似部分検出処理を示したフローチャートである。
【図１７】一致部分の出現順による類似部分検出処理を示したフローチャートである。
【図１８】一致部分の前後部分を含む類似部分検出処理を示したフローチャートである。
【図１９】類似部分検出処理後の類似部分情報ＤＢの内容を示した図である。
【図２０】非一致構造分析処理を示したフローチャートである。
【図２１】（ａ）〜（ｃ）は、非一致構造分析処理により得られる構文構造例を示した図である。
【図２２】非一致構造分析処理後の非一致構造情報ＤＢの内容を示した図である。
【図２３】本発明の実施形態にかかるソースプログラム解析システムの機能概要を示した図である。
【発明を実施するための形態】
【００１８】
以下、本発明の実施形態について、図面を参照しながら説明する。
【００１９】
（実施形態）
本発明の実施形態にかかるソースプログラム解析システムは、ソースプログラムを解析し、文の挿入や削除、変更が施されている（すなわち非一致部分を有する）コードクローンを検出した上で、コードクローンにおける非一致部分のプログラム構造を解析し、類似性に関する指標を出力する。操作者は、この類似性に関する指標を参照し、そのプログラムの修正コストを算出することができる。
【００２０】
本実施形態にかかるソースプログラム解析システム１００は、図１に示すように、制御部１１０、記憶部１２０、操作部１３０、画面表示部１４０を備える。ソースプログラム解析システム１００の構成要素は、バス１０１を介して相互に接続されている。
【００２１】
制御部１１０は、ＣＰＵ（Central Processing Unit）１１１、ＲＯＭ（Read Only Memory）１１２、ＲＡＭ（Random Access Memory）１１３を備える。ＣＰＵ１１１は、ＲＯＭ１１２などに記憶されている制御用のプログラムに従って、ソースプログラム解析システム１００全体の動作を制御する。ＲＯＭ１１２は、制御用のプログラムを記憶する。ＲＡＭ１１３は、ＣＰＵ１１１が使用するデータを一時的に保存する。制御部１１０は、ソースプログラム解析システム１００が備える他の構成要素との間で、バス１０１を介して信号を送受信することにより、これらの構成要素を制御する。
【００２２】
記憶部１２０は、ハードディスク、ＳＳＤ（Solid State Drive）、あるいはＣＤ−ＲＯＭ（Compact Disc - Read Only Memory）等を備え、ソースプログラム解析システム１００が稼動する上で必要な情報を記憶する。
【００２３】
操作部１３０は、操作者の操作を入力として受けとり、制御部１１０に情報として伝達する。操作部１３０は、例えばマウスやキーボード、あるいはタッチパネルなどを備える。
【００２４】
画面表示部１４０は、制御部１１０の制御に基づき、操作画面や結果表示画面などのソースプログラム解析システム１００が操作者に対して表示すべき情報を表示する。画面表示部１４０は、液晶ディスプレイや有機エレクトロルミネセンスディスプレイ等で構成される。
【００２５】
ソースプログラム解析システム１００が動作する際、図２に示すように、制御部１１０は、一致部分検出部１１、実行単位標識検出部１２、類似部分検出部１３、非一致部分分析部１４として機能する。また、記憶部１２０は、一致部分情報ＤＢ（データベース）２１、文法定義情報ＤＢ２２、実行単位標識情報ＤＢ２３、類似部分情報ＤＢ２４、非一致構造情報ＤＢ２５として機能する。
【００２６】
次に、図２に示す各部の機能及び動作を、図３を参照して説明する。
ソースプログラム解析システム１００は、全体としては、ソースプログラム１を解析し、検出したコードクローンの類似性に関する指標を非一致構造情報ＤＢ２５に記録する。
【００２７】
一致部分検出部１１は、ソースプログラム１を解析し、内容が互いに一致する一致部分を検出する。この一致部分は、上述したタイプ１あるいはタイプ２のコードクローンに該当する。一致部分検出部１１は、検出した一致部分ごとに一致部分情報を生成し、生成した一致部分情報を一致部分情報ＤＢ２１に記録する。
一致部分検出部１１の機能を実現するには、例えば非特許文献２が開示する技術およびソフトウェアを用いることができる。本実施形態においては、非特許文献２が開示するソフトウェアのひとつであるＣＣｆｉｎｄｅｒＸを使用する。
一致部分検出部１１は、一致部分を行ごとに検出し、検出した一致部分の位置をソースプログラム上の開始行番号および終了行番号で特定する。ここで行とは、ソースプログラム上において、改行を示すコードに挟まれた部分のコードの集合を指す。
【００２８】
実行単位標識検出部１２は、文法定義情報ＤＢ２２に記録された文法定義に基づき、入力されたソースプログラムの実行単位の開始あるいは終了を示す標識を検出し、実行単位標識情報を生成し、実行単位標識情報ＤＢ２３に記録する。ここで実行単位とは、各プログラム言語の構文規則で定義されているセクション（節）、ディビジョン(部）、段落、手続き（サブルーチン）、関数、ブロック等、プログラムを分割する上で基準となる単位を指す。
【００２９】
類似部分検出部１３は、一致部分情報ＤＢ２１に記録された一致部分情報に基づいて、基準に合致する類似部分を検出し、類似部分情報を生成し、類似部分情報ＤＢ２４に記録する。類似部分検出部１３は、検出した類似部分の位置をソースプログラム上の開始行番号および終了行番号で特定する。
類似部分検出部１３は、以下に示す２パターンのいずれかに合致する部分を、基準に合致する類似部分として検出する。
【００３０】
第１のパターンの類似部分は、複数の一致部分と、その一致部分にはさまれた部分からなるものである。この類似部分は、両端の一致部分と、その間の内容が一致しない非一致部分を有し、文の挿入や削除、変更が施されているコードクローン（タイプ３のコードクローン）に該当する。
第１のパターンの類似部分を検出するとき、類似部分検出部１３は、一致部分情報ＤＢ２１に記録された一致部分情報を参照し、複数の一致部分が、間に他の一致部分を挟まずに同じ出現順番でソースプログラムに配置されているものを検出する。そして、検出した複数の一致部分および当該一致部分の間にある部分を、ひとつの類似部分（第１のパターンの類似部分）として抽出する。
【００３１】
第２のパターンの類似部分は、一致部分と、ソースプログラム上その一致部分の直前にある非一致部分（前部分）と、その一致部分の直後にある非一致部分（後部分）とからなるものである。この類似部分は、一致部分と、その前あるいは後の非一致部分（前部分あるいは後部分）から構成されるため、文の挿入や削除、変更が施されているコードクローンに該当する。
類似部分検出部１３は、一致部分情報ＤＢ２１に記録された一致部分情報、および実行単位標識情報ＤＢ２３に記録された実行単位標識情報を参照し、各一致部分の前部分および後部分を検出する。ここで、前部分とは、所定の区切りからその一致部分の開始行までの部分を指し、後部分とは、その一致部分の終了行から所定の区切りまでの部分を指す。所定の区切りとは、実行単位標識または他の一致部分の開始行もしくは終了行の中で、その一致部分に最も近いものを指す。
第２のパターンの類似部分を検出するとき、類似部分検出部１３は、前部分あるいは後部分が検出された一致部分について、前部分から一致部分を経て後部分までの範囲を、ひとつの類似部分として抽出する。
なお、類似部分検出部１３は、前部分のみが検出された一致部分があると、前部分からその一致部分までを類似部分として抽出する。類似部分検出部１３は、後部分のみが検出された一致部分があると、一致部分から後部分までを類似部分として抽出する。
【００３２】
非一致部分分析部１４は、各類似部分を分析し、他の類似部分とどれだけ類似しているかを示す指標を非一致構造情報ＤＢ２５に記録する。具体的には、非一致部分分析部１４は、類似部分情報ＤＢ２４から類似部分の位置と含有一致部分情報を読み出し、また一致部分情報ＤＢ２１から一致部分の位置を読み出し、類似部分の非一致部分の位置を特定する。非一致部分分析部１４は、特定した非一致部分の位置のプログラム記述をソースプログラム１から読み出す。非一致部分分析部１４は、読み出したプログラム記述を、文法定義情報ＤＢ２２に記録された文法定義に従って構文解析し、構文構造を取得する。非一致部分分析部１４は、取得した構文構造を比較し、各類似部分の非一致部分で共通する構文構造（非一致部分共通構文構造）を検出する。非一致部分分析部１４は、各類似部分の非一致部分の構文構造と、非一致部分共通構文構造とを比較し、類似する度合いを構文類似度として算出する。
構文解析の際、非一致部分分析部１４は、ＬＲ法（Left-to-Right scanning）によって非一致部分のプログラム記述を解析し、構文木構造で表された構文構造を取得する。
【００３３】
また、図３に示す一致部分情報ＤＢ２１は、図４に示すように、コードクローンＩＤ（Ｔ２１０１）、グループＩＤ（Ｔ２１０２）、ファイル名（Ｔ２１０３）、開始行番号（Ｔ２１０４）、終了行番号（Ｔ２１０５）を有する。
コードクローンＩＤは、一致部分検出部１１が、ソースプログラム１から検出した一致部分（タイプ１あるいはタイプ２のコードクローン）にユニークに付ける識別情報である。
グループＩＤは、その一致部分が属するグループを示す識別情報である。同一のグループに属する一致部分は、互いに内容が一致する。
ファイル名は、ソースプログラム１のファイル名を指す。
開始行番号は、ソースプログラム１上で当該一致部分が存在する部分の最初の行番号を示す。
終了行番号は、ソースプログラム１上で当該一致部分が存在する部分の最後の行番号を示す。
【００３４】
図３に示す文法定義情報ＤＢ２２は、図５に示すように、プログラム言語種別（Ｔ２２０１）、文法定義（Ｔ２２０２）を有する。
プログラム言語種は、後述する文法定義がどのプログラム言語に対応するものであるかを示す情報である。例えば「Ｃ（Ｃ言語）」「ＪＡＶＡ（登録商標）」などといった形で表現される。
文法定義は、プログラム言語種別で示されたプログラム言語の文法を定義する情報である。文法定義は、例えば、関数の開始を示すコード、関数の終了を示すコード、変数の範囲、数値の範囲、演算子の種類やコード、代入演算子を示すコード、式の形式、代入式の形式等が、対象のプログラム言語ではどのように規定されているかを示す。
【００３５】
図３に示す実行単位標識情報ＤＢ２３は、図６に示すように、実行単位標識ＩＤ（Ｔ２３０１）、実行単位種別（Ｔ２３０２）、開始終了属性（Ｔ２３０３）、ファイル名（Ｔ２３０４）、開始行番号（Ｔ２３０５）、終了行番号（Ｔ２３０６）を有する。
実行単位標識ＩＤは、実行単位標識検出部１２が、ソースプログラム１から検出した実行単位の開始あるいは終了を示すコード（標識）に付ける識別情報である。
実行単位標識種別は、検出されたコードが、セクション（節）、ディビジョン(部）、段落、手続き（サブルーチン）、関数、ブロック等の実行単位のどれに対応するものであるかを示す情報である。
開始終了属性は、検出されたコードが実行単位の開始に対応するものであるか、終了に対応するものであるかを表す情報である。
ファイル名は、ソースプログラム１のファイル名を示す情報である。
開始行番号は、検出されたコードが開始する行を示す情報である。
終了行番号は、検出されたコードが終了する行を示す情報である。
【００３６】
図３に示す類似部分情報ＤＢ２４は、図７に示すように、類似部分ＩＤ（Ｔ２４０１）、類似部分グループＩＤ（Ｔ２４０２）、ファイル名（Ｔ２４０３）、開始行番号（Ｔ２４０４）、終了行番号（Ｔ２４０５）、一致部分リスト（Ｔ２４０６）からなる類似部分情報を記録する。
類似部分ＩＤ（Ｔ２４０１）は、類似部分検出部１３が、ソースプログラム１から検出した類似部分にユニークに付ける識別情報である。
類似部分グループＩＤ（Ｔ２４０２）は、類似部分が属する類似部分グループを示す情報である。同一の類似部分グループに属する類似部分は、同一のグループに属する一致部分を含む。
ファイル名（Ｔ２４０３）は、ソースプログラム１のファイル名を示す。
開始行番号（Ｔ２４０４）は、検出された類似部分が開始する行を示す。
終了行番号（Ｔ２４０５）は、検出された類似部分が終了する行を示す。
一致部分リスト（Ｔ２４０６）は、当該類似部分に含まれる一致部分のコードクローンＩＤを示す。一致部分リストは、一致部分に存在するコードクローンＩＤを出現する順にリスト化された形で保有する。
【００３７】
図３に示す非一致構造情報ＤＢ２５は、図８に示すように、類似部分ＩＤ（Ｔ２５０１）、類似部分グループＩＤ（Ｔ２５０２）、非一致部分構文構造（Ｔ２５０３）、非一致部分共通構文構造（Ｔ２５０４）非一致部分構文類似度（Ｔ２５０５）からなる非一致構造情報を記録する。
類似部分ＩＤ（Ｔ２５０１）は、類似部分を識別するための識別情報である。
類似部分グループＩＤ（Ｔ２５０２）は、類似部分のグループを識別するための識別情報である。
非一致部分構文構造（Ｔ２５０３）は、類似部分が保持する非一致部分の構文構造を示す。非一致部分構文構造は、ＸＭＬ（eXtensible Markup Language）、あるいはＤＯＭ（Document Object Model）等の方式によって階層構造で表現されたデータとして、あるいはバイナリデータとして記録される。
非一致部分共通構文構造（Ｔ２５０４）は、同一類似部分グループＩＤを有する類似部分の非一致部分が共通に保持する構文構造（非一致部分共通構文構造）を示す。非一致部分共通構文は、ＸＭＬ（eXtensible Markup Language）、あるいはＤＯＭ（Document Object Model）等の方式によって階層構造で表現されたデータとして、あるいはバイナリデータとして記録される。
非一致部分構文類似度（Ｔ２５０５）は、各類似部分の非一致部分が、非一致部分共通構文構造とどの程度類似しているかを示す数値指標である。具体的には、階層構造で表現された非一致部分構文構造において、全体のノード数のうちどれだけの割合のノードが非一致部分共通構文構造と共通しているかをパーセンテージで示す。
【００３８】
次に、ソースプログラム解析システム１００がソースプログラムを解析する動作について、図９に示すソースプログラムを解析する場合を例に説明する。
【００３９】
操作者が、操作部１３０を介してソースプログラム解析システム１００に、ソースプログラム１の解析処理を開始する指示をすると、ソースプログラム解析システム１００は、図１０に示すソースプログラム解析処理を開始する。
【００４０】
最初に、制御部１１０は、一致部分検出処理を開始する（ステップＳ１００）。
【００４１】
この一致部分検出処理（ステップＳ１００）の詳細を図１１を参照して説明する。
制御部１１０は、図１１に示すように、ソースプログラム１に存在する一致部分を検出する（ステップＳ１０１）。
具体的には、制御部１１０は図９に示すソースプログラム１のプログラム記述を解析し、第０５行から第０６行のソースコードと、第１１行から第１２行のソースコードとが内容が一致することを検出する。これを受けて、制御部１１０は、第０５行から第０６行のソースコードと、第１１行から第１２行のソースコードを一致部分として検出する。同様に、制御部１１０は、第０８行から第１０行、および第１４行から第１６行の各ソースコードも一致部分として検出する。
【００４２】
次に制御部１１０は、ステップＳ１０１で検出した各一致部分に識別番号を付与する（ステップＳ１０２）。具体的には、制御部１１０は第０５行から第０６行、第０８行から第１０行、第１１行から第１２行、および第１４行から第１６行の各ソースコードに識別番号としてコードクローンＩＤ、グループＩＤを付与する。
コードクローンＩＤを付与する際、制御部１１０は、検出した一致部分間でコードクローンＩＤが重複しないように採番する。
グループＩＤを付与する際、制御部１１０は、内容が一致する一致部分間でグループＩＤが一致するように、また内容が一致しないコードクローン間ではグループＩＤが重複しないように採番する。
以上を踏まえ、制御部１１０は第０５行から第０６行のソースコードにコードクローンＩＤ「１」、グループＩＤ「１」を付与し、第０８行から第１０行のソースコードにコードクローンＩＤ「２」グループＩＤ「２」を付与する。
また、第１１行から第１２行のソースコードは第０５行から第０６行のソースコードと内容が一致する。そこで、制御部１１０は第１１行から第１２行のソースコードにはコードクローンＩＤ「３」を付与するとともに、グループＩＤは第０５行から第０６行のソースコードと一致する「１」を付与する。同様に、制御部１１０は第１４行から第１６行のソースコードにはコードクローンＩＤ「４」グループＩＤ「２」を付与する。
【００４３】
次に制御部１１０は、ステップＳ１０１で検出した各コードクローンのそれぞれについて、一致部分情報を一致部分情報ＤＢ２１に記録する（ステップＳ１０３）。一致部分情報は、各一致部分のコードクローンＩＤ、グループＩＤ、ファイル名、開始行番号、終了行番号からなる情報である。
具体的には、第０５行から第０６行のソースコードは、コードクローンＩＤ「１」、グループＩＤ「１」であり、ファイル名はソースプログラム１のファイル名から「src.c」であり、開始行番号は「０５」であり、終了行番号は「０６」である。制御部１１０は、これらを連結し、一致部分情報ＤＢ２１に記録する。また制御部１１０は、第０８行から第１０行、第１１行から第１２行、および第１４行から第１６行の各ソースコードについても同様の処理を行う。
【００４４】
以上の処理を経て、一致部分情報ＤＢ２１には、図１２に示す情報が記録される。また、制御部１１０は、以上の処理において一致部分検出部１１として機能する。
【００４５】
以上の処理が終了すると、制御部１１０は一致部分検出処理（ステップＳ１００）を終了し、図１０に示すフローチャートに従い、次に実行単位標識検出処理（ステップＳ２００）を開始する。
ここから、制御部１１０が実行する実行単位標識検出処理について、図１３を参照しながら説明する。
【００４６】
実行単位標識検出処理の最初に、制御部１１０は、文法定義情報ＤＢ２２から、ソースプログラム１の記述言語に対応する文法定義情報を読み込む（ステップＳ２０１）。図９に示すようにソースプログラム１はＣ言語で記載されているため、制御部１１０は、図１４に示す文法定義情報ＤＢ２２から、Ｃ言語に対応する文法定義情報を読み込む。
文法定義情報ＤＢ２２は、図１４に示すとおり、Ｃ言語に対応する文法定義情報を記録している。この文法定義情報には、関数の開始として「｛」記号、関数の終了として「｝」記号が定義されている。制御部１１０はこの文法定義情報に従い、ソースプログラム１の中で「｛」を関数の開始を示す記号として、「｝」を関数の終了を示す記号として扱う。
【００４７】
次に、制御部１１０は、ソースプログラム１から実行単位の開始あるいは終了を示す標識を検出する（ステップＳ２０２）。具体的には、制御部１１０は、図９に示されたソースプログラム１を解析し、第０１行の「｛」記号、および第１８行の「｝」記号を実行単位の開始あるいは終了を示す標識として検出する。
【００４８】
次に制御部１１０は、ステップＳ２０２で検出した実行単位の開始あるいは終了を示す標識のそれぞれについて、識別番号を付与する（ステップＳ２０３）。具体的には、制御部１１０は、ソースプログラム１の第０１行にある「｛」記号、および第１８行にある「｝」記号に、それぞれ実行単位標識ＩＤとして「１」「２」を付与する。実行単位標識ＩＤを付与する際、制御部１１０は、実行単位標識ＩＤが重複しないように採番する。
【００４９】
次に制御部１１０は、ステップＳ２０２で検出した実行単位の開始あるいは終了を示す標識のそれぞれについて、実行単位標識情報を実行単位標識情報ＤＢ２３に記録する（ステップＳ２０４）。実行単位標識情報は、上述したとおり実行単位標識ＩＤ、実行単位種別、開始終了属性、ファイル名、開始行番号、終了行番号からなる情報である。
具体的には、ソースプログラム１の第０１行にある「｛」記号は、実行単位標識ＩＤ「１」を付与されており、「関数」の「開始」を示す属性を有しており、ファイル名はソースプログラム１のファイル名から「src.c」であり、開始行番号は「０１」であり、終了行番号「０１」である。制御部１１０は、これらの情報を連結し、実行単位標識情報ＤＢ２３に記録する。また制御部１１０は、ソースプログラム１の第１８行にある「｝」記号についても同様の処理を行う。
【００５０】
以上の処理を経て、実行単位標識情報ＤＢ２３には、図１５に示す情報が記録される。また、制御部１１０は、以上の処理において実行単位標識検出部１２として機能する。
【００５１】
以上の処理が終了すると、制御部１１０は実行単位標識検出処理（ステップＳ２００）を終了する。次に、図１０に示すフローチャートに従い、制御部１１０は類似部分検出処理を開始する（ステップＳ３００）。
ここから、制御部１１０が実行する類似部分検出処理について、図１６を参照しながら説明する。
【００５２】
制御部１１０は、類似部分検出処理の最初に、一致部分の出現順による類似部分検出処理（ステップＳ３１０）を行い、一致部分情報ＤＢ２１から第１のパターンの類似部分を検出する。一致部分の出現順による類似部分は、複数のタイプ１あるいはタイプ２のコードクローンと、そのコードクローンにはさまれた部分からなるものであり上述の第１のパターンの類似部分に該当する。
ここから、図１７を参照し、一致部分の出現順による類似部分検出処理について説明する。
【００５３】
制御部１１０は、一致部分の出現順による類似部分検出処理の最初に、一致部分情報ＤＢ２１から一致部分情報を読み出す（ステップＳ３１１）。具体的には、制御部１１０は、一致部分情報ＤＢ２１からコードクローンＩＤ１〜４の一致部分情報を読み出す。
【００５４】
次に制御部１１０は、読み出した一致部分情報から、複数の一致部分が、間に他の一致部分を挟まずに同じ出現順番でソースプログラムに配置されているものを検出する（ステップＳ３１２）。具体的には、制御部１１０は、読み出したコードクローンＩＤ１〜４の一致部分情報から、コードクローンＩＤ１および２の一致部分がある部分と、コードクローンＩＤ３および４の一致部分がある部分とは、どちらもグループＩＤ１と２のコードクローンが順に現れる構造を有していることを検出する。制御部１１０は、コードクローンＩＤ１の一致部分から、コードクローンＩＤ２の一致部分までを、類似部分１として検出する。同様に制御部１１０は、コードクローンＩＤ３の一致部分からコードクローンＩＤ４の一致部分までを、類似部分２として検出する。
類似部分１は、コードクローンＩＤ１の一致部分の開始位置から開始するため、開始行番号は第０５行となる。また類似部分１は、コードクローンＩＤ２のコードクローンの終了位置で終了するため、終了行番号は第１０行となる。また、類似部分１は、その両端のコードクローンが、それぞれグループＩＤ「１」と「２」を有するため、一致部分リストとして「１、２」を有する。
類似部分２は、コードクローンＩＤ３の一致部分の開始位置から開始するため、開始行番号は第１１行となる。また類似部分２は、コードクローンＩＤ４の一致部分の終了位置で終了するため、終了行番号は第１６行となる。また、類似部分２は、その両端のコードクローンが、それぞれグループＩＤ「１」と「２」を有するため、一致部分リストとして「１、２」を有する。
【００５５】
以上の処理が終了すると、制御部１１０は一致部分の出現順による類似部分検出処理（ステップＳ３１０）を終了する。次に制御部１１０は、図１６に示すフローに従い、一致部分の前後部分を含む類似部分検出処理を開始する（ステップＳ３２０）。
ここから、図１８を参照し、一致部分の前後部分を含む類似部分検出処理について説明する。
【００５６】
制御部１１０は、一致部分の前後部分を含む類似部分検出処理の最初に、一致部分情報ＤＢ２１から一致部分情報を読み出す（ステップＳ３２１）。具体的には、制御部１１０は、一致部分情報ＤＢ２３からコードクローンＩＤ１〜４の一致部分情報を読み出す。
【００５７】
次に制御部１１０は、実行単位標識情報ＤＢ２３から実行単位標識情報を読み出す（ステップＳ３２２）。具体的には、制御部１１０は、一致部分情報ＤＢ２１から実行単位標識ＩＤ１〜２の実行単位標識情報を読み出す。
【００５８】
次に制御部１１０は、読み出した各一致部分の前部分を検出する（ステップＳ３２３）。一致部分の前部分とは、ソースコード上にある所定の区切り部分からその一致部分の開始行までの部分のことをいう。ここで所定の区切り部分とは、（１）その一致部分直前の他の一致部分の終了行、あるいは（２）その一致部分直前の実行単位の開始あるいは終了を示すコードのある行を指し、制御部１１０は（１）（２）のうち後にある方からその一致部分の開始行までの部分を前部分として抽出する。
【００５９】
具体的には、制御部１１０は、一致部分情報ＤＢ２１から読み出したコードクローンＩＤ１の一致部分について、（１）その直前には他の一致部分がないこと、および（２）その直前の実行単位の開始あるいは終了を示すコードは、第０１行の「｛」であることを検出する。（１）では他の一致部分を検出できなかったため、制御部１１０は（２）の検出に基づいて前部分を判別する。その結果、制御部１１０はコードクローンＩＤ１のコードクローンの前部分として、第０２行（記号「｛」がある行の次行）から第０４行まで（その一致部分開始行の前行）を検出する。
【００６０】
同様に制御部１１０は、コードクローンＩＤ２の一致部分についても前部分を検出する。この場合、制御部１１０は、（１）コードクローンＩＤ２の一致部分の直前の一致部分はコードクローンＩＤ１の一致部分であり、その終了行は第０６行であること、（２）コードクローンＩＤ２の一致部分の直前の実行単位の開始あるいは終了を示すコードは、第０１行の「｛」であることを検出する。この結果、制御部１１０は（１）で検出した第０６行のほうが後にあるため、（１）の検出に基づいて前部分を抽出する。従って、制御部１１０は、コードクローンＩＤ２の一致部分の前部分として、第０７行（直前コードクローンの終了行の次行）から第０７行まで（そのコードクローン開始行の前行）を検出する。
【００６１】
続いて制御部１１０は、コードクローンＩＤ３の一致部分についても前部分を検出する。この場合、制御部１１０は、（１）コードクローンＩＤ３の一致部分の直前の他の一致部分はコードクローンＩＤ２の一致部分であり、その終了行は第１０行であること、（２）コードクローンＩＤ２の一致部分の直前の実行単位の開始あるいは終了を示すコードは、第０１行の「｛」であることを検出する。この結果、制御部１１０は（１）で検出した第１０行のほうが後にあるため、（１）の検出に基づいて前部分を検出する。
ここで、制御部１１０は、（１）に基づいて検出した所定の区切り部分が、コードクローンＩＤ３の一致部分の開始行（第１１行）の前行であることを検出する。その結果、制御部１１０は、コードクローンＩＤ３の一致部分は前部分を持たないと検出する。
【００６２】
続いて制御部１１０は、コードクローンＩＤ４の一致部分についても前部分を検出する。上記同様の処理により、制御部１１０は、コードクローンＩＤ４の一致部分の前部分として、第１３行（直前の一致部分の終了行の次行）から第１３行まで（その一致部分開始行の前行）を検出する。
【００６３】
次に制御部１１０は、読み出した各一致部分の後部分を検出する（ステップＳ３２４）。一致部分の後部分とは、その一致部分の終了行から、ソースコード上にある所定の区切り部分までの部分のことをいう。ここで所定の区切り部分とは、（１）その一致部分直後の他の一致部分の開始行、あるいは（２）その一致部分直後の実行単位の開始あるいは終了を示すコードのある行を指し、制御部１１０はその一致部分の終了行から（１）（２）のうち前にある方までの部分を後部分として検出する。
【００６４】
具体的には、制御部１１０は、一致部分情報ＤＢ２１から読み出したコードクローンＩＤ１のコードクローンについて、（１）コードクローンＩＤ１の一致部分の直後の一致部分はコードクローンＩＤ２の一致部分であり、その開始行は第０８行であること、（２）コードクローンＩＤ１の一致部分の直後の実行単位の開始あるいは終了を示すコードは、第１８行の「｝」であることを検出する。この結果、制御部１１０は（１）で検出した第０８行のほうが前にあるため、（１）の検出に基づいて後部分を抽出する。従って、制御部１１０は、コードクローンＩＤ１の一致部分の後部分として、第０７行（その一致部分終了行の次行）から第０７行まで（直後にある他の一致部分開始行の前行）を検出する。
【００６５】
続いて制御部１１０は、同様の処理によりコードクローンＩＤ２〜４の一致部分について後部分を検出する。制御部１１０は、コードクローンＩＤ２の一致部分は後部分を持たないと検出する。また制御部１１０は、コードクローンＩＤ３の一致部分の後部分は第１３行から第１３行まで、コードクローンＩＤ４の一致部分の後部分は第１７行から第１７行までと検出する。
【００６６】
次に制御部１１０は、読み出した各一致部分に基づいて、検出した前部分、一致部分、検出した後部分から構成される部分を類似部分として検出する（ステップＳ３２５）。
具体的には、制御部１１０は、コードクローンＩＤ１の一致部分に基づいて、前部分（第０２行から第０４行）、一致部分（第０５行から第０６行）、後部分（第０７行から第０７行）を連結し、類似部分３として検出する。類似部分３は、開始行番号は第０２行であり、終了行番号は第０７行である。また、類似部分３は、グループＩＤ「１」を有する一致部分に基づいて検出されており、一致部分リストとして「１」を有する。
同様にコードクローンＩＤ２〜４に基づき、類似部分４〜６を検出する。ただし、コードクローンＩＤ２の一致部分は後部分を有さず、またコードクローンＩＤ３の一致部分は前部分を有さないため、それぞれ一致部分自身の終了行、開始行が類似部分の終了行、開始行となる。この結果、制御部１１０は、類似部分４（第０７行から第１０行まで、一致部分リストは「２」）、類似部分５（第１１行から第１３行まで、一致部分リストは「１」）、類似部分６（第１３行から第１７行まで、一致部分リストは「２」）を検出する。
【００６７】
次に制御部１１０は、図１６に示すとおり、ステップＳ３１０およびステップＳ３２０で検出した各類似部分について、識別番号を付与する（ステップＳ３３０）。具体的には、制御部１１０は類似部分（類似部分１〜６）に、類似部分ＩＤおよび類似部分グループＩＤを付与する。
類似部分ＩＤを付与する際、制御部１１０は、検出した類似部分間で類似部分ＩＤが重複しないように採番する。本実施例においては、制御部１１０は、類似部分１に類似部分ＩＤ「１」を付与し、以降類似部分６まで順に類似部分ＩＤを付与する。
また類似部分グループＩＤを付与する際、制御部１１０は、同一のグループＩＤを有するコードクローンに基づいて、同一のステップ（ステップＳ３１０またはステップＳ３２０）で検出された類似部分は同一の類似部分グループＩＤを有するように採番する。ステップＳ３１０で制御部１１０が検出した類似部分はすべて第１のパターンの類似部分であり、すべて同一のパターンで検出されたものである。同様に、ステップＳ３２０で制御部１１０が検出した類似部分はすべて第２のパターンの類似部分であり、同一のパターンで検出されたものである。
具体的には、上記ステップＳ３１０において、類似部分１と２が、同一のグループＩＤ（１および２）を有するコードクローンから検出されているため、制御部１１０は、類似部分１と２に同一の類似部分グループＩＤ「１」を付与する。また上記ステップＳ３２０において、類似部分３と５が、同一のグループＩＤ「１」を有するコードクローンから検出されているため、制御部１１０は、類似部分３と５に同一の類似部分グループＩＤ「２」を付与する。同様に制御部１１０は、類似部分４と６に同一の類似部分グループＩＤ「３」を付与する。
【００６８】
次に制御部１１０は、図１６に示すとおり、各類似部分に基づいて類似部分情報を生成し、類似部分情報ＤＢ２４に記録する（ステップＳ３４０）。
具体的には、制御部１１０は、ステップＳ３１０で検出した類似部分１に基づいて、類似部分情報（類似部分ＩＤ「１」、類似部分グループＩＤ「１」、ファイル名「src.c」、開始行番号「０５」、終了行番号「１０」、一致部分リストとして「１、２」を記録する。同様に制御部１１０は、類似部分２〜６についても類似部分情報ＤＢ２４に記録する。
【００６９】
以上の処理を経て、類似部分情報ＤＢ２４には、図１９に示す情報が記録される。また、制御部１１０は、以上の処理において類似部分検出部１３として機能する。
【００７０】
以上の処理が終了すると、制御部１１０は図１０に示す類似部分検出処理（ステップＳ３００）を終了する。次に、図１０に示すフローチャートに従い、制御部１１０は非一致構造分析処理（ステップＳ４００）を開始する。
ここから、非一致構造分析処理について、図２０を参照しながら説明する。
【００７１】
図２０に示す非一致構造分析処理の最初に、制御部１１０は、類似部分情報ＤＢ２４に格納されている類似部分の中から、同じ類似部分グループＩＤを持つ類似部分を取得する（ステップＳ４０１）。以降では、類似部分グループＩＤとして「１」を有する類似部分（類似部分１および２）を例として説明する。
【００７２】
次に制御部１１０は、同一の類似部分グループＩＤを有する各類似部分が含む非一致部分を特定し、そのプログラム記述を前記ソースプログラム１から読み出す（ステップＳ４０２）。具体的には、制御部１１０は、類似部分１に関する類似部分情報を類似部分ＤＢ２４から読み出し、開始行番号が第０５行、終了行番号が第１０行であることを読み出す。また制御部１１０は、類似部分１の一致部分リストが「１、２」であることから、ソースプログラム１の第０５行から第１０行までのソースコードのうち、コードクローンＩＤ１のコードクローンに該当する部分（第０５行から第０６行）、およびコードクローンＩＤ２のコードクローンに該当する部分（第０８行から第１０行）、を除いた部分を抽出する。すなわち、制御部１１０は、ソースプログラム１の第０７行を、類似部分１における非一致部分として特定し、抽出する。
同様に制御部１１０は、ソースプログラム１の第１３行を、類似部分２における非一致部分として特定し、抽出する。
【００７３】
次に制御部１１０は、ステップＳ４０２で特定した非一致部分の構文を解析し、構文構造を取得する（ステップＳ４０３）。具体的には、制御部１１０は、類似部分１の非一致部分（第０７行）のプログラム記述をソースプログラム１から読み出し、文法定義情報ＤＢ２２に格納されている文法定義情報に基づいて構文を解析する。本例では、上述したＬＲ法によりソースプログラム１の第０７行を構文解析する。ソースプログラム１の第０７行には、変数（ｃ）、代入演算子（＝）、数値（３０）を順に接続した式が記載されている。この式を構文木構造に基づいて解析することにより、制御部１１０は、図２１（ａ）に示す構文構造を取得する。
また同様に、制御部１１０は、類似部分２の非一致部分（第１３行）より、ソースプログラム１の第１３行を構文解析する。ソースプログラム１の第１３行には、変数（ｃ）、代入演算子（＝）、変数（ａ）、演算子（＋）、変数（ｂ）、演算子（＋）、変数（ｃ）を順に接続した式が記載されている。この式を構文木構造に基づいて解析することにより、制御部１１０は、図２１（ｂ）に示す構文構造を取得する。
【００７４】
次に制御部１１０は、同一類似部分グループＩＤを有する類似部分間で、ステップＳ４０３で取得した構文構造を比較する（ステップＳ４０４）。具体的には、制御部１１０は、同一類似部分ＩＤを有する類似部分１および２の非一致部分の構文構造（図２１（ａ）、（ｂ））を比較し、両者が共通に有する構文構造（以下、非一致部分共通構文構造と表記）を抽出する。
制御部１１０は、両者の構文構造を構文木の上部から順にたどることにより比較する。制御部１１０は、両者において代入演算子（＝）およびその左辺（変数（ｃ））は共通するが、その右辺は違う構造を有することを識別し、かつ、その右辺は「式」として共通する性質を有すると識別する。その結果、制御部１１０は、図２１（ｃ）に示すとおり、変数（ｃ）、代入演算子（＝）、式を順に接続した構文構造を非一致部分共通構文構造として抽出する。
【００７５】
次に制御部１１０は、各類似部分の非一致部分の構文構造と、ステップＳ４０４で抽出した非一致部分共通構文構造とを比較し、構文類似度を算出する（ステップＳ４０５）。具体的には、制御部１１０は、類似部分１および２の各非一致部分の構文構造と、非一致部分共通構文構造とを比較し、どれだけのノードが一致するかを示す構文類似度を算出する。
制御部１１０は、図２１（ａ）に示す類似部分１の非一致部分の構文構造と図２１（ｃ）に示す非一致部分共通構文構造とを比較する。その結果、制御部１１０は、非一致部分の構文構造が有する３ノードのうち、代入演算子（＝）のノードと、変数（ｃ）のノードとは非一致部分共通構文構造と一致し、数値（３０）のノードも非一致部分共通構文構造のノード（「式」）と一致することを検出する。非一致部分の構文構造が有する３ノードのうち、３ノードが一致することから、制御部１１０は、類似部分１の構文類似度を３／３＝１００％と算出する。
同様に制御部１１０は、類似部分２の非一致部分の構文構造と非一致部分共通構文構造とを比較する。その結果、制御部１１０は、非一致部分の構文構造が有する７ノードのうち、３ノードが一致することから、制御部１１０は、類似部分１の構文類似度を３／７＝４２．８％と算出する。
【００７６】
次に制御部１１０は、非一致構造情報を生成し、非一致構造情報ＤＢ２５に記録する（ステップＳ４０６）。制御部１１０は、上述したステップＳ４０１からステップＳ４０５までの過程で検出した情報から、類似部分ＩＤ、類似部分グループＩＤ、非一致部分の構文構造、非一致部分共通構文構造、構文類似度を抽出し、非一致構造情報として非一致構造情報ＤＢ２５に記録する。制御部１１０は、非一致部分の構文構造および非一致部分共通構文構造を、構文の階層構造を示すバイナリデータとして記録する。
制御部１１０は、類似部分１について、類似部分ＩＤ「１」、類似部分グループＩＤ「１」、非一致部分の構文構造の情報（図２１（ａ）に示す構文の階層構造を示すバイナリデータ）、非一致部分共通構文構造の情報（図２１（ｃ）に示す構文の階層構造を示すバイナリデータ）、構文類似度「１００％」からなる非一致構造情報を生成し、非一致構造情報ＤＢ２５に記録する。同様に、類似部分２についても、非一致構造情報を生成し、非一致構造情報ＤＢ２５に記録する。この結果、非一致構造情報ＤＢ２５には、図２２に示す非一致構造情報が記録される。
【００７７】
制御部１１０は、以上のステップＳ４０１からＳ４０６までの処理を、類似部分３〜６についても同様に実施する。その結果、抽出された６つの類似部分に対応する非一致構造情報が、非一致構造情報ＤＢ２５に記録される。
【００７８】
以上の処理の結果、非一致構造情報ＤＢ２５に非一致構造情報が記録される。また、制御部１１０は、以上の処理において類似部分検出部１３として機能する。
【００７９】
制御部１１０は、ステップＳ４０６の処理を完了すると、図２０に示す非一致構造分析処理を完了する。制御部１１０は、非一致構造分析処理を完了すると、図１０に示すソースプログラム解析処理を完了する。
【００８０】
以上に示したとおり、制御部１１０は、入力されたソースプログラム１にあるタイプ３のコードクローンを、類似部分として非一致構造情報ＤＢ２５に記録する。従って操作者は、非一致構造情報ＤＢ２５のデータを閲覧することにより、ソースプログラム１のどこにタイプ３のコードクローンがあるかを知ることができる。
また、制御部１１０は、各類似部分の構文類似度を非一致構造情報ＤＢ２５に記録する。この構文類似度は、プログラムを保守する観点で重要となる構造的、構文的な類似性を数値化したものである。従って、操作者は、構文類似度を参照することにより、プログラムを修正する上での作業量や所要時間を見積もることができる。
【００８１】
以上のとおり、本発明によれば、ソースプログラムからタイプ３のコードクローンを検出し、そのプログラムの修正コストを算出するために有効な情報を出力するソースプログラム解析システムを実現できる。
上記の処理によって得られた構文類似度を参照することにより、例えばシステムの移行にあたって提案された移行方法の作業量や所要時間を見積もることが可能となり、移行方法を評価することができる。また、既存システムのソースコードのリファクタリングにおいて、必要な箇所を特定し作業量を見積もることができる。
【００８２】
以上、本発明の実施形態について説明したが、本発明の実施形態はこれに限定されない。
【００８３】
本実施形態では、制御部１１０は一致部分検出処理を行う際、非特許文献２が開示するソフトウェアであるＣＣｆｉｎｄｅｒＸにより一致部分を検出したが、これに限定されない。ソースプログラムから、タイプ１あるいは２のコードクローンを検出することができるソフトウェアであれば、任意のものによって一致部分検出処理を行うことができる。
【００８４】
類似部分検出部１３は、ステップＳ３１１において、複数の一致部分が、間に他の一致部分を挟まずに同じ出現順番でソースプログラムに配置されているものを類似部分として検出している。しかし、類似部分検出部１３は、間に他の一致部分を挟んで同じ出現順番でソースプログラムに配置されているものも、類似部分として検出してもよい。このようにした場合、例えば上述の実施形態では、コードクローンＩＤ１の一致部分からコードクローンＩＤ４の一致部分までを、類似部分グループＩＤ１の類似部分として検出する。
【００８５】
本実施形態においては、ソースプログラム解析システム１００は、ソースプログラム１を行単位に解析した。しかし、解析する単位は行に限定されず、改行コードとは異なるコードにより区分けされた部分ごとに一致部分を検出してもよい。例えば、単語あるいは文字ごとに解析するようにしてもよい。
【００８６】
本実施形態においては、類似部分検出部１３は、類似部分として第１のパターンおよび第２のパターンの類似部分を検出した。これに限られず、類似部分検出部１３は、第１のパターンの類似部分のみを検出してもよいし、第２のパターンの類似部分のみを検出してもよい。また、他のスキームによって類似部分を検出してもよい。
【００８７】
本実施形態においては、一致部分検出部１１は一致部分情報を一致部分情報ＤＢ２１に記録し、類似部分検出部１３は、一致部分情報ＤＢ２１から一致部分情報を読み出した。しかし、必ずしも一旦データベースに一致部分情報を記録するものでなくともよく、一致部分検出部１１は直に類似部分検出部１３へ一致部分情報を供給してもよい。また、本実施形態において一致部分情報ＤＢ２１は記憶部１２０に存在するが、記憶部１２０上に限られず、例えば制御部１１０のＲＡＭに存在するものであってもよいし、またネットワークを介してアクセス可能な他機器に存在するものであってもよい。
同様のことは、他のＤＢ（文法定義情報ＤＢ２２、実行単位標識情報ＤＢ２３、類似部分情報ＤＢ２４、非一致構造情報ＤＢ２５）にも当てはまる。すなわち、各ＤＢが存在する場所は任意であり、また各情報が、当該情報を必要とする機能部あるいは操作者に伝わるのであればＤＢとして存在する必要はない。
また、各ＤＢのフォーマットは任意であり、一般的なファイルでも、データベース構造を有するデータセット等でも実現することができる。
【００８８】
本発明の特徴は、ソースプログラムから内容が互いに一致する一致部分を検出すること、検出された一致部分に基づいてソースプログラムに存在する類似部分を検出すること、検出された類似部分にある非一致部分の類似性を示す指標を出力することにある。本発明の対象はソースプログラムに限られず、以下のような応用も可能である。
すなわち、本発明のソースプログラム解析システムにより、例えば提出された課題の論文等における類似部分とその類似度を取得することができる。これにより、提出者間でのテキストのコピーの有無を判断する材料とすることも可能である。
【００８９】
本発明の実施形態にかかるソースプログラム解析システムは、専用のシステムによらず、通常のコンピュータシステムを用いても実現可能である。例えば、コンピュータに、上記動作を実行するためのプログラムを、フレキシブルディスク、ＣＤ−ＲＯＭ（Compact Disk-Read Only Memory）、ＤＶＤ（Digital Versatile Disk）、ＭＯ（Magnet Optical Disk）などのコンピュータ読み取り可能な記憶媒体に記憶して配布し、これをコンピュータシステムにインストールすることにより、上述の処理を実行するソースプログラム解析システムを構成しても良い。さらに、インターネット上のサーバ装置が有するディスク装置等にプログラムを記憶しておき、例えば、搬送波に重畳させて、コンピュータにダウンロード等するものとしてもよい。
【００９０】
本願発明の実施形態にかかるソースプログラム解析システム１００は、図２３に示すように、一致部分検出部１１、類似部分検出部１３、非一致部分分析部１４から構成されうるものである。
一致部分検出部１１は、ソースプログラム１から内容が互いに一致する一致部分を検出する。
類似部分検出部１３は、一致部分検出部１１が検出した一致部分に基づいて、ソースプログラム１から内容が互いに一致する部分と一致しない部分とで構成される類似部分を検出する。
非一致部分分析部１４は、類似部分検出部１３が検出した類似部分の一致しない部分の構文を分析し、他の類似部分とどれだけ類似しているかを示す指標を分析結果２として出力する。
操作者は、非一致部分分析部１４が生成した分析結果２により、ソースプログラム１にある文の挿入や削除、変更が施されているコードクローンの位置や数、構文類似度を知ることができる。すなわち、操作者は、ソースプログラム１の修正コストを算出するために有効な情報を得ることができる。
このように、上記の構成により、本発明の課題は達成され、また、本願発明の効果が奏される。
【００９１】
なお、上記の実施例の一部または全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００９２】
（付記１）
ソースプログラムから、内容が互いに一致する一致部分を検出する一致部分検出手段と、
前記一致部分検出手段が検出した一致部分に基づいて、ソースプログラムから内容が互いに一致する部分と一致しない部分とで構成され、かつ、基準に合致する類似部分を検出する類似部分検出手段と、
前記類似部分検出手段が検出した類似部分を分析し、他の類似部分とどれだけ類似しているかを示す指標を出力する非一致部分分析手段と、を備える、
ことを特徴とするソースプログラム解析システム。
【００９３】
（付記２）
前記類似部分検出手段は、前記一致部分検出手段が検出した一致部分から、間に他の一致部分を挟まずに同じ出現順番で配置されている複数の一致部分を検出し、当該複数の一致部分と、当該複数の一致部分にはさまれた一致しない部分とで構成される類似部分を検出する、
ことを特徴とする付記１に記載のソースプログラム解析システム。
【００９４】
（付記３）
前記非一致部分分析手段は、前記類似部分検出手段が検出した類似部分の一致しない部分の構文が、他の類似部分の一致しない部分の構文とどれだけ類似しているかを示す構文類似度を算出する、
ことを特徴とする付記１または２に記載のソースプログラム解析システム。
【００９５】
（付記４）
前記非一致部分分析手段は、前記類似部分検出手段が検出した類似部分の一致しない部分を構成要素に分割し、当該構成要素のうち他の類似部分の一致しない部分と共通する構成要素の割合から構文類似度を算出する、
ことを特徴とする付記３に記載のソースプログラム解析システム。
【００９６】
（付記５）
前記非一致部分分析手段は、前記類似部分検出手段が検出した類似部分の一致しない部分を構成要素に分割し、他の類似部分の一致しない部分と共通する構成要素の構文構造を出力する、
ことを特徴とする付記３または４に記載のソースプログラム解析システム。
【００９７】
（付記６）
前記非一致部分分析手段は、前記類似部分検出手段が検出した類似部分の一致しない部分を構文木構造に基づいて分析することにより、構成要素ごとに分割し、あるいは他の類似部分の一致しない部分と共通する構成要素の構文構造を出力する、
ことを特徴とする付記４または５に記載のソースプログラム解析システム。
【００９８】
（付記７）
ソースプログラムから、実行単位の開始あるいは終了を示す標識を検出する実行単位標識検出手段をさらに備え、
前記類似部分検出手段は、前記一致部分検出手段が検出した一致部分の直前にある実行単位標識検出手段が検出した第１の標識および当該一致部分の直後にある実行単位標識検出手段が検出した第２の標識を検出し、
前記類似部分検出手段は、前記ソースプログラムにおける前記第１の標識の終了位置と、前記一致部分の直前にある他の一致部分の終了位置とのうち後にある方から前記一致部分の開始位置までの部分を前部分として抽出し、かつ、前記一致部分の終了位置から前記ソースプログラムにおける前記第２の標識の開始位置と、前記一致部分の直後にある他の一致部分の開始位置とのうち前にある方までの部分を後部分として抽出し、
前記類似部分検出手段は、前記前部分と、前記一致部分と、前記後部分とを有する類似部分を検出する、
ことを特徴とする付記１から６のいずれか１つに記載のソースプログラム解析システム。
【００９９】
（付記８）
前記類似部分検出手段は、前記前部分と前記一致部分とを有する類似部分、および前記一致部分と前記後部分とを有する類似部分を検出する、
ことを特徴とする付記７に記載のソースプログラム解析システム。
【０１００】
（付記９）
ソースプログラムから、内容が互いに一致する一致部分を検出する一致部分検出ステップと、
前記一致部分検出ステップで検出した一致部分に基づいて、ソースプログラムから内容が互いに一致する部分と一致しない部分とで構成され、かつ、基準に合致する類似部分を検出する類似部分検出ステップと、
前記類似部分検出ステップで検出した類似部分を分析し、他の類似部分とどれだけ類似しているかを示す指標を出力する非一致部分分析ステップと、を備える、
ことを特徴とするソースプログラム解析方法。
【０１０１】
（付記１０）
コンピュータに、
ソースプログラムから、内容が互いに一致する一致部分を検出する一致部分検出機能、
前記一致部分検出機能が検出した一致部分に基づいて、ソースプログラムから内容が互いに一致する部分と一致しない部分とで構成される所定の基準を満たす類似部分を検出する類似部分検出機能、
前記類似部分検出機能が検出した類似部分を分析し、他の類似部分とどれだけ類似しているかを示す指標を出力する非一致部分分析機能、を実現させる、
ことを特徴とするプログラム。
【符号の説明】
【０１０２】
１：ソースプログラム
２：分析結果
１１：一致部分検出部
１２：実行単位標識検出部
１３：類似部分検出部
１４：非一致部分分析部
２１：一致部分情報ＤＢ
２２：文法定義情報ＤＢ
２３：実行単位標識情報ＤＢ
２４：類似部分情報ＤＢ
２５：非一致構造情報ＤＢ
１００：ソースプログラム解析システム
【図１】
2014199569.tif 000003
【図２】
2014199569.tif 000004
【図３】
2014199569.tif 000005
【図４】
2014199569.tif 000006
【図５】
2014199569.tif 000007
【図６】
2014199569.tif 000008
【図７】
2014199569.tif 000009
【図８】
2014199569.tif 000010
【図９】
2014199569.tif 000011
【図１０】
2014199569.tif 000012
【図１１】
2014199569.tif 000013
【図１２】
2014199569.tif 000014
【図１３】
2014199569.tif 000015
【図１４】
2014199569.tif 000016
【図１５】
2014199569.tif 000017
【図１６】
2014199569.tif 000018
【図１７】
2014199569.tif 000019
【図１８】
2014199569.tif 000020
【図１９】
2014199569.tif 000021
【図２０】
2014199569.tif 000022
【図２１】
2014199569.tif 000023
【図２２】
2014199569.tif 000024
【図２３】
2014199569.tif 000025