プログラム解析情報のXMLデータベース化 ー 提案と実現 ー

Presentation on theme: "プログラム解析情報のXMLデータベース化 ー 提案と実現 ー"— Presentation transcript:

1 プログラム解析情報のXMLデータベース化 ー 提案と実現 ー
山中祐介，大畑文明，井上克郎 大阪大学 大学院基礎工学研究科

2 発表内容 背景、目的 データベース化手法の提案 提案手法の実現 評価 関連研究 まとめと今後の課題 発表内容です
まず、背景、目的を述べ、・・・・ そして最後に、まとめと今後の課題について述べます。

3 背景（1/2） ソフトウェアの大規模化、複雑化 プログラミング言語の高級化 プログラムのデバッグ、理解が困難なものになっている
様々なプログラミング言語に対応する、プログラム解析 手法の提案、およびツールの実装が多くされている 背景です。 近年、ソフトウェアは大規模化、複雑化しており、ソフトウェアを作るための プログラミング言語も高級化しています。 このことからプログラムのデバッグ、理解が困難なものになっています。 そのため、様々なプログラミング言語に対応するプログラム解析手法の提案がされ、 解析ツールも多数実装されてます。

4 背景（2/2） プログラム解析ツールの問題点 解析情報がメモリ上にのみ記憶される データベースを構築し、効率化を計るツールも存在する
解析情報の記憶形態が独自形式 APIが特定のプログラミング言語を前提 実行の度に対象プログラムを解析しなければならず 効率が悪い しかし、その解析ツールにも問題点があります。 まず、解析情報がメモリ上にのみ記憶されます。 そのため、実行の度に対象プログラムを解析しなければならなくなり、効率が悪いということです。 次に解析効率の改善のためデータベースを構築し、効率化を計るツールもありますが、 解析情報の記憶形態が独自形式であったり、APIが特定のプログラミング言語を 前提としているため、解析情報の二次利用が容易ではありません。 プログラム解析情報の二次利用が容易でない

5 XMLを用いたプログラム解析情報のデータベース化
目的 XMLを用いたプログラム解析情報のデータベース化 データベース化による利点 解析結果の再利用による解析効率の向上 情報の保存による解析情報の二次利用 XMLを用いる利点 データ構造の定義が容易に行える XML文書を扱うための様々なアプリケーションにより二次利用が容易に行える これらの問題を解決するため、XMLを用いたプログラム解析情報のデータベース化を 行います。 データベース化によって、 解析手順の簡略化による解析効率の向上が期待でき、 情報の保存による解析情報の二次利用が可能になります。 また、XMLを用いることによって データ構造の定義が容易に行えます。 そして、XML文書を扱うための様々なアプリケーションにより 二次利用が容易に行えます。

6 データベース化手法の提案（目次） プログラム解析情報 意味解析木 XML 意味解析木のデータベース化 方針 XML要素定義 XML属性定義
例 ここからデータベース化手法の提案をします、その目次です。 まず、プログラム解析情報について述べ、・・ そして最後に、意味解析木のデータベース化について述べます。

7 プログラム解析情報 例 意味解析木に注目 抽象構文木（Abstract Syntax Tree） 意味解析木（Semantic Tree）
手続き呼び出しグラフ（Call Flow Graph） 制御フローグラフ（Control Flow Graph） ‥ 意味解析木に注目 多くのプログラム解析手法においてその存在が前提となり、データベース化による効果が大きい プログラム解析情報は多数存在しており、例えば、 ・・・・などがあります。 これらのうち本研究では、意味解析木に注目します。 意味解析木は多くのプログラム解析手法において、その存在が前提となり データベース化による効果が大きいです。

8 抽象構文木と意味情報とを組み合わせたもの
意味解析木 抽象構文木と意味情報とを組み合わせたもの 抽象構文木 プログラム言語固有の文法に従い記述されたソースコードを、木構造で表現し構文情報を持たせたもの 構文情報（Syntax Information） 構文木が持つ予約語、識別子、演算子などの情報 意味情報（Semantic Information） 変数名、型名などの識別子に関する宣言と参照間の関係を表す情報 それでは、意味解析木について説明します。 意味解析木は抽象構文木と意味情報を組み合わせたものです。 抽象構文木とは、プログラム言語固有の文法に従い記述されたソースコードを、 木構造で表現し構文情報を持たせたものです。 構文情報とは、予約後、識別子、演算子などの情報のことです。 意味情報とは、変数名、型名などの識別子に関する宣言と参照との間の 関係を表す情報です。 本研究ではJavaプログラムを解析して得られる意味解析木に対してデータベース化を 行います。

9 SGMLのサブセットで文書構造化言語の一つ
XML SGMLのサブセットで文書構造化言語の一つ 特徴 データ構造とそれが持つ情報を、容易かつ的確に表現できる 要素（Element）などによる構造化 要素名、属性（Attribute）などの定義の自由さ 要素間の親子関係、属性の情報を厳密に定義できる 文書型定義、XMLスキーマ XML文書を扱うためのAPI、アプリケーションが数多くある API：SAX, DOM アプリケーション：XSLT, XLink データベース化に用いるXMLについて説明します。 XMLは文書構造化言語の一つです。 XMLの特徴として、 データ構造とそれがもつ情報を容易かつ、的確に表現できる。 要素、すなわちXMLタグなどにより、構造化できるからです。 また、タグ名やその属性などを自由に定義できるからです。 要素間の親子、すなわちタグの生成規則や属性が持つ情報を厳密に定義できます。 この定義のため、文書型定義やXMLスキーマが提供されています。 また、XML文書を扱うためのAPIとして、単純に前から走査するSAXや 文書を木構造と見なし走査するDOMがあります。 アプリケーションとして、文書変換を行うXSLTや文書間のリンクを生成するXlinkなどあります。

10 意味解析木のXMLデータベース化 方針 Javaプログラムの意味解析木に対するXML表記を、定義することでデータベース化を行う
要素に意味解析木の節点を対応させ木構造を表現 意味解析木の各節点に構文情報、意味情報がある 対応する要素の属性が情報を保持 ここから意味解析木のデータベース化について述べます。 まず、方針です。 Javaプログラムの意味解析木に対するXML表記を定義することで データベース化を行います。 XML表記の定義の方針は、 意味解析木とXML文書は共に木構造を形成しています。 そこで、要素に意味解析木の節点を対応させることで木構造を表現します。 意味解析木の各節点に構文情報、意味情報があります。 そこで、対応する要素の属性が情報を保持します。

11 XML要素定義 Javaプログラムと要素の対応表（一部） Java構文要素 XML要素名 要素が持つ子のBNF記述 メソッド宣言
Method type Variable* Exception? Block? 変数宣言 Variable type Expression_? ブロック Block (Variable | ClassType | InterfaceType | Statement_)* 演算 Operation type Expression_ Expression_? 型参照 type 子要素なし 変数参照 variable リテラル Literal このような定義の方針に従い要素と属性を定義しました。 要素の定義です。 意味解析木の木構造をXMLタグで表現するため、 Javaの構文要素とXMLタグ名が対応しています。 メソッド宣言なら、Method、変数宣言ならVariableというようにです。 また、Javaの構文に応じてタグは子を持っています。

12 XML属性定義 要素が持つ属性とその役割（一部） 属性名 役割 text 識別子、演算子などの構文情報 modifiers
修飾子情報（public, staticなど） id 意味情報の宣言側が持つ情報 ref 意味情報の参照側が持つ情報 file 参照先が同一ファイル内でない場合、別ファイルにアクセスするための情報 次に属性の定義です。 属性は構文情報や、意味情報を保持しますのでそれに対応した 属性を定義しました。 識別子、演算子などの構文情報はtextが保持します。 意味情報はidとrefで表現しており、それぞれ宣言と参照を表しています。

13 意味解析木のXML表記の例 class Sample { public static void main(String[] args) {
<Method modifiers=“public static“ text="main" id="189b"> <type text="void" ref="4"/> <Block> ‥ <Variable modifiers="" text="b" id="18ad"> <type text="int" ref="7"/> </Variable> <Operation text="="> <variable text="b" ref="18ad"/> <Operation text="+"> <variable text="a" ref="18a9"/> <Literal text="1"/> </Operation> </Block> </Method> <Method modifiers="public static“ text="main" id="189b"> <type text="void" ref="4"/> <Block> ‥ <Variable modifiers="" text="b" id="18ad"> <type text="int" ref="7"/> </Variable> <Operation text="="> <variable text="b" ref="18ad"/> <Operation text="+"> <variable text="a" ref="18a9"/> <Literal text="1"/> </Operation> </Block> </Method> <?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE Java SYSTEM "java.dtd"> <Java> <CompilationUnit> <Package text=""/> <Import text="java.lang.*"/> <ClassType modifiers="" text="Sam5" id="0x12"> <Extends> <type text="java.lang.Object" text_="Object" ref="0x18" file="java/lang/Object.xml"/> </Extends> <Variable modifiers="" text="this" id="0x13"> <type text="Sam5" ref="0x12"/> </Variable> <Variable modifiers="protected" text="super" id="0x14"> <Method modifiers="public static" text="main" id="0x189b"> <type text="void" ref="0x4"/> <Variable modifiers="" text="args" id="0x18a4"> <type text="java.lang.String[]" text_="String[]" ref="0x20"/> <Block> <Variable modifiers="" text="a" id="0x18a9"> <type text="int" ref="0x7"/> <Literal text="1"/> <Variable modifiers="" text="b" id="0x18ad"> <Operation text="="> <variable text="b" ref="0x18ad"/> </Operation> </Block> </Method> </ClassType> </CompilationUnit> </Java> class Sample { public static void main(String[] args) { int a = 1; int b; b = a + 1; System.out.println(a + “,” + b); } これで意味解析木を表現するためのXMLタグ、属性を定義できました。 ここで、XMLによる表記の例を示します。 このようなJavaプログラムがあったとします。 これをXMLで表記するとこのようになります。 これではわかりにくいのでこれらの部分を抜粋してみます。 対応はこのようになっています。 メソッド宣言であれば、Methodタグに情報があります。 修飾子情報はmodifiersに、メソッド名はtextにあります。 このように構文情報はすべてtext、赤の部分にあります。 次に意味情報です。 変数bはそれぞれ宣言と参照の関係にあります。 Variableタグで宣言され属性idの番号が変数bのidになります。 このvariableタグで変数bを参照しており、属性refがid番号を保持することで参照先を明示しています。

14 Javaプログラム解析フレームワーク 解析ライブラリ API アプリケーション 意味解析木 ユーザ ソースコード アプリケーション
ソースコードを解析し意味解析木をメモリ上に構築 API 意味解析木の参照、更新手段を提供 アプリケーション GUI、エイリアス解析ツール* 意味解析木 ユーザ 解析ライブラリ Java ソースコード API アプリケーション XMLデータベース化の手法を提案しましたので、実装を行います。 実装先は、我々が研究開発を行っているJavaプログラム解析フレームワークです。 Javaプログラム解析フレームワークは、解析ライブラリ、API、 エイリアス解析ツールから構成されています。 解析ライブラリは、ソースコードを解析し意味解析木をメモリ上に構築します。 APIは意味解析木の参照、更新手段を提供します。 アプリケーションにはGUIやエイリアス解析ツールなどがあります。 *大畑文明, 近藤和弘, 井上克郎: “エイリアスフローグラフを用いたオブジェクト指向プログラムの エイリアス解析手法“, 電子情報通信学会論文誌D-1, Vol.J84-D-1, No.5, pp.1--11

15 XMLデータベースの実装 Javaプログラム解析フレームワークに、意味解析木-XML変換ライブラリを用いて、XMLデータベースを実装
ユーザ 解析ライブラリ Java ソースコード API アプリケーション XML <?xml…> XML文書 意味解析木-XML 変換ライブラリ XMLデータベースを意味解析木-XMLライブラリを用いることで、 Javaプログラム解析フレームワークに実装します。

16 意味解析木-XML変換ライブラリ 解析によって得られる意味解析木とデータベースであるXML文書を相互変換
開発言語：C++（libxml使用）、約4000行 変換手順 意味解析木→XML 意味解析木をたどり各構文木要素に対するタグを出力 XML→意味解析木 XMLパーザによりXML文書を解析しDOMツリーを構築 構築したDOMツリーに対する構文木要素を作成 XMLデータベースの実装に用いた 意味解析木-XML変換ライブラリについて説明します。 これは、解析によって得られる意味解析木とデータベースであるXML文書を 相互変換します。 開発言語はC++でXMLパーザとしてlibxmlを使用しました。 コードは約4000行です。 解析手順は、意味解析木からXMLの場合、 意味解析木をたどり各構文木要素に対するタグを出力します。 XMLから意味解析木の場合、 XMLパーザによりXML文書を解析し、DOMツリーを構築します。 構築したDOMツリーに対する構文木要素を作成します。

17 評価（目次） 解析効率の改善 解析情報の二次利用の容易性 実際にソースコードを解析しデータベース化を行い比較
応用アプリケーションの実装による二次利用例 XML-Java変換 XML-HTML変換 XML-XML変換 XMLデータベースの実装を行いましたので、その評価をしました。 解析効率の改善を調べるために実験をしました 解析情報の二次利用の容易性のため、応用アプリケーションを実装しました。

18 解析効率の改善 JDK1.3付属ライブラリの全ソースコードを対象 XMLデータベース構築時間：45.6秒 解析時間（意味解析木の構築まで）
ソースプログラム：37秒 XMLデータベース：24秒 全ファイルサイズ ソースプログラム：25MB XMLデータベース：62MB データベース構築時間を考慮しても データベース化による恩恵は大きい データベース化によるサイズの 肥大化は少ない 解析効率の改善を調べるための実験です。 JDK1.3付属ライブラリの全ソースコードを対象に行いました。 XMLデータベース構築時間は45.6秒です。 意味解析木構築までの解析時間は、ソースプログラムだと37秒、 XMLデータベースだと24秒かかりました。 このことからライブラリは複数回の解析を行われるので、 構築時間を考慮してもデータベース化による恩恵は大きいことがわかります。 また、ファイルサイズはソースプログラムは25MBでしたが、 XMLデータベースは62MBになりました。 このことからデータベース化によるサイズの肥大化はそれほど大きくなく データベースの利用も十分可能であることがわかります。

19 解析情報の二次利用の容易性 応用アプリケーションの実装 ユーザ XMLデータベース ソースコード HTML文書 例1：XML-Java
変換プログラム テキストエディタ HTML <html> HTML文書 例2：XML- HTML変換プログラム WEBブラウザ 例3.XML-XML 変換プログラム 二次利用のための応用アプリケーションの実装を行いました。 まず、XMLからJavaに変換するプログラムです。 次に、XMLからHTMＬに変換するプログラムです。 最後に、XMLを変換編集するプログラムです。

20 応用例1：XML-Java変換 Javaプログラムのソースコードへの復元 実装 意味解析木が持つ構文情報を利用
コンパイル、閲覧が十分可能なソースコードへの復元 実装 C++（libxml使用）、約1500行 XSLT（Xalan使用）、約2000行 XMLからJavaへ変換するプログラムです。 Javaプログラムのソースコードへの復元をします。 復元には、意味解析木が持つ構文情報を利用します。 また、コンパイル、閲覧が十分可能なソースコードへの復元をします。 このプログラムの実装には、XMLパーザlibxmlを使用したC++による実装と XSLTプロセッサであるXalanを使用したXSLTによる実装があります。 それぞれコードは約1500行と、約2000行です。

21 応用例1：XML-Java変換（例） XMLデータベース 復元したJavaソースコード import java.lang.*;
<?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE Java SYSTEM "java.dtd"> <Java> <CompilationUnit> <Package text=""/> <Import text="java.lang.*"/> <ClassType modifiers="" text="Sam5" id="0x12"> <Extends> <type text="java.lang.Object" text_="Object" ref="0x18" file="java/lang/Object.xml"/> </Extends> <Variable modifiers="" text="this" id="0x13"> <type text="Sam5" ref="0x12"/> </Variable> <Variable modifiers="protected" text="super" id="0x14"> <Method modifiers="public static" text="main" id="0x189b"> <type text="void" ref="0x4"/> <Variable modifiers="" text="args" id="0x18a4"> <type text="java.lang.String[]" text_="String[]" ref="0x20"/> <Block> <Variable modifiers="" text="a" id="0x18a9"> <type text="int" ref="0x7"/> <Literal text="1"/> <Variable modifiers="" text="b" id="0x18ad"> <Operation text="="> <variable text="b" ref="0x18ad"/> </Operation> </Block> </Method> </ClassType> </CompilationUnit> </Java> XMLデータベース import java.lang.*; class Sam5 extends Object { public static void main(String[] args) { int a = 1; int b; b = a + 1; System.out.println(a + "," + b); } 復元したJavaソースコード class Sam5 { public static void main(String[] args) { int a = 1; int b; b = a + 1; System.out.println(a + “,” + b); } 元のJavaソースコード XMLからJavaへの変換例です。 このJavaプログラムを解析し、XMLデータベース化します。 これを変換するとこのようになり、元のプログラムと違うところも ありますが、コンパイルおよび実行は可能です。

22 応用例2：XML-HTML変換 XML-Java変換プログラムの拡張 実装
Webブラウザで閲覧できるようにソースコードに変換する際、HTMLタグを埋め込む 意味情報を利用することで、識別子の宣言、及び参照の関係をリンクを用いて表現 実装 XSLT（Xalan使用）、約2000行 XMLからHTMLへ変換するプログラムです。 これもJavaプログラムのソースコードへの復元をします。 これはXML-Java変換の拡張です。 Webブラウザで閲覧できるようにソースコードに変換する際、 HTMLタグを埋め込みます。 また、意味情報を利用することで、識別子の宣言、および参照の関係を リンクを用いて表現しています。

23 応用例2：XML-HTML変換（例） Sam5.html class Sam5 {
public static void main(String[] args) { int a = 1; int b; b = a + 1; System.out.println(a + “,” + b); } java/lang/System.html XMLからHTMLへの変換例です。 このJavaプログラムをHTMLにするとこのようになります。 ここで変数outをクリックすると、これを宣言しているjava.lang.Systemを 参照できます。

24 応用例3：XML-XML変換 XMLデータベースが持つ識別子情報の置換 実装
置換条件に識別子名の他に識別子のidを加えることで、異なるスコープ上に存在する同一名の識別子を区別 識別子の区別が厳密なため、変換を行ってもプログラムの整合性を保てる 実装 XSLT（Xalan使用）、約600行 XMLを変換編集するプログラムです。 XMLデータベースが持つ識別子情報の置換を行います。 これは、置換条件に識別子名の他に識別子のidを加えることで、異なるスコープ上に 存在する同一名の識別子を区別します。 このプログラムの利点は識別子の区別が厳密なため、 変換を行ってもプログラムの整合性を保てます。

25 変数valueをafter_valueに変換
応用例3：XML-XML変換（例） <Variable modifiers="private" text="value" id="34"> <type text="char[]" ref="9"/> </Variable> ‥ <Constructor modifiers="public" text="String" id="34e"> <Variable modifiers="" text="value" id="4d17"> <type text="java.lang.String" text_="String" ref="22"/> 変換前のXML文書 java.lang.String 変数valueをafter_valueに変換 class String implements java.io.Serializable, Comparable { private char value[]; ‥ public String(String value) { } <Variable modifiers="private" text="after_value" id="34"> <type text="char[]" ref=“9"/> </Variable> ‥ <Constructor modifiers="public" text="String" id="34e"> <Variable modifiers="" text="value" id="4d17"> <type text="java.lang.String" text_="String" ref="22"/> 変換後のXML文書 変換の例です。 Java.lang.String中にはこのような表記があります。 ここで、変数valueは名前は同じですが異なるスコープ上にあります。 XML文書で見るとidが違うことがわかります。 ここで、このvalueをafter_valueに変換します。 このvalueはidが違うため変換の対象に入っていなかったことがわかります。 idが違うため変換されない

26 *G.J.Badoros: “JavaML:a markup language for JAVA source code”
関連研究（1/2） JavaML* Javaソースコードの代替的な表記を可能にするXMLアプリケーション 目的：プログラム変換、プログラム理解 実装 ソースコードに対してXMLタグを埋め込むライブラリをJavaコンパイラに追加 本研究との相違点 意味情報は十分に含まれず、データベースとしては成り立たない 複数ファイル間におよぶ宣言、参照関係はサポートされていない 関連研究です。 Javaソースコードの代替的な表記を可能にするXMLアプリケーションとして JavaMLがあります。 目的は、プログラム変換、プログラム理解です。 実装は、ソースコードに対してXMLタグを埋め込むライブラリをJavaコンパイラに 追加することで行われています。 本研究との相違点としては、 意味情報は十分に含まれず、データベースとしては成り立たないということです。 それは同一ファイル間の宣言、参照関係はサポートされているが複数ファイル間は サポートされていません。 *G.J.Badoros: “JavaML:a markup language for JAVA source code” Computer Networks 33, pp , 2000.

27 関連研究（2/2） Sapid* C言語のソースプログラムを管理するためのCASEツールプラットフォーム
目的：通常のリポジトリが扱えない細かい粒度の構成要 素の管理 構成 ソフトウェアデータベース アクセスルーチン ソフトウェア操作言語 本研究との相違点 データベースへの参照、編集はSapid独自のAPI C言語のソースプログラムを管理するためのCASEツールプラットフォームとして Sapidがあります。 目的は、通常の理ポジ取りが扱えない細かい粒どの構成要素の管理です。 ソフトウェアデータベース、アクセスルーチン、ソフトウェア操作言語から 構成されています。 本研究との相違点としては、 データベースへの参照、編集はSapid独自のAPIであり、 本研究の方がXMLを利用していることから汎用的であると思われます。 *福安 直樹, 山本 晋一郎, 阿草 清滋: “細粒度ソフトウェア・リポジトリに基づいたCASEツール・ プラットフォームSapid“情報処理学会論文誌, Vol.39, No.6, pp (1998/6)

28 まとめ プログラム解析情報のXMLデータベース化 意味解析木をXMLを用いて表現 XMLデータベースの実装 評価 XMLの要素、属性を定義
変換ライブラリを用いたJavaプログラム解析フレームワークへの組み込み 評価 意味解析木の構築時間を比較し、解析効率の改善を確認 応用アプリケーションを実装し、二次利用の容易性を確認 まとめです。 プログラム解析情報のXMLデータベース化を行いました。 意味解析木をXMLを用いて表現するためXMLの要素、属性を定義しました。 XMLデータベースの実装を変換ライブラリを用いて行いました。 そして、評価を行いました。 意味解析木の構築時間を比較し、解析効率の改善を確認しました。 応用アプリケーションの実装による二次利用の容易性を確認しました。

29 今後の課題 意味解析木以外の解析情報のデータベース化 XML表記の粒度のカスタマイズ 手続き呼び出しグラフ 制御フローグラフ ‥
情報量が多いデータベースを構築すると管理コストが増大 ユーザ目的に応じて最適化されたデータベースを再構築する機能 今後の課題です。 まず、手続き呼び出しグラフ、制御フローグラフなど意味解析木以外の 解析情報のデータベース化が考えられます。 次に、XML表記の粒度のカスタマイズが考えられます。 情報量が多いデータベースを構築すると管理コストが増大します。 そのためユーザの目的に応じて最適化されたデータベースを再構築する 機構が必要だと思われます。