パターン変換記述における表現力向上の研究
2009SE091 伊藤佑規 2009SE095 上條敬太

2009SE145 葛谷貴亮

指導教員：吉田敦

1

はじめににありうる事例を検討する．

プログラム開発過程における保守・運用において仕様変 2.2 字句単位での否定的な書換え箇所の限定更やリファクタリングなどを行う際には，保守性や可読字句に対する否定的な限定としても 2.1 節で示した事性向上のためにプログラミングスタイルを統一してソー例について考える．この場合，返り値がない void 型関数スコードを変更する．しかし，コードクローンの同時編定義には挿入するべきでないので，型指定子を記述する集やコーディング規約に応じた書換えなど，分散して存箇所に “void” が存在しないことを制約条件として記述す在する典型的な記述に対して同じ書換えを適用する際に，る必要がある．すなわち，「特定箇所に字句が存在しない」
手作業では誤りが混入する危険性がある．そこで，誤りのということを表す制約条件が必要である．
混入を防ぎ作業効率向上のために，一律に書換えができるパターンマッチングを利用した書換え環境が提案され 2.3 構文単位での肯定的な書換え箇所の限定ている [1][2][3]．このような支援環境は有用ではあるが， 事例として，コードクローン内の特定の記述を関数呼現実的な作業に適用したときに，制約を詳細に記述でき び出しに置き換える場合を考える．コードクローンは類ず，利用できないことがある．例えば，一部の記述にお 似しているが完全には一致していないので，関数化した
いてコーディング規約で求められている表記が欠落して い箇所は，必ずしも同じ位置や同じ数になるとは限らないるときに，それを一律に追加するためには，規約を満 い．よって，コードクローンを表すパターンの中に，書たしてない箇所に限定する制約条件を記述する必要があ 換えたい内容を含めて記述することはできない．あらかる．しかし，既存の環境では，そのような制約条件を記 じめ書換え対象をコードクローンだけに限定できていれ述する方法を提供していない．
ば，記述を関数呼び出しに置き換えるパターン変換を適
本研究では，パターン変換記述に求められる現実的な 用し一律に同時編集することが可能である．よって，書制約条件を，事例を基に検討するとともに，複数の観点 換えを行う前にパターン変換記述を適用させる箇所を特から派生して考られる条件も明らかにする．さらに，制 定する方法が必要である．
約条件に対応するよう実装を行い，その実現可能性を確
2.4 字句単位での肯定的な書換え箇所の限定かめる．なお，実装にあたっては，小規模で拡張が容易
大学におけるプログラミング実習での課題の採点作業
な TEBA[2] を用いる．
以降では，第 2 章でどのような制約条件が必要なのか を手作業で行うことは，学生ごとに記述が異なるので，手を分析し，問題点を整理する．第 3 章では，どのように 間がかかり，間違いを見落とす可能性がある．一つの解パターン適用範囲を制限し拡張していくかを述べる．第 決策が，プログラムにテストケースを適用し，出力を模
4 章では，ツールを評価し考察を行う．第 5 章で更なる表 範解答と比較して自動的に判定する方法である．しかし，学生のプログラムは書式が必ずしも統一されておらず，単現力の向上のための機能拡張について述べる．
純に比較すると書式の違いによって差異が生じ，正しく2 問題分析判定できない．そこで，書式を統一する書換えを考える．
2.1 構文単位での否定的な書換え箇所の限定
しかし，計算された値のみ出力し，出力の可読性を高め事例として，コンパイル時の警告を無視して作成した， る補助的な文字列を除去しようとした場合，文字列定数
return 文が欠落した関数を含むプログラムに対し，返り の中身に対するパターン変換記述を作成する必要がある．
値を書くよう指示を付加した return 文を関数の最後に追 よって，字句を構成する文字列に対して制約条件を記述加する修正を行うことを考える．この場合，return 文を できるパターン変換記述が必要である．
正しく記述している場合には，挿入すべきではないので， 3 制約条件に対する処理の実現方法「return 文が存在しない」ということを制約条件として3.1 TEBA記述する必要がある．すなわち，「構文要素が存在しない」
TEBA における書換えは，パターン変換記述を書換えということを表す制約条件が必要である．
存在しないことを制約条件として記述するのであれば， 前を表現するテキスト断片の変換前パターンと書換え後存在することも条件として考えられる．さらに，構文要 を表現する断片の変換後断片に分割し，それぞれを構文素についての制約条件を記述するのであれば，字句を構 解析器を通して得られた字句系列パターンと置換字句系成する文字に対する制約条件も考えられる．そこで，「存 列を結合させ字句系列変換規則を生成する．しかし，パ在の有無」，「構文要素と字句」という 2 つの観点の組み合 ターン変換記述に書換え前後の断片をそのまま記述したわせで構成される 4 つの制約条件について検討する．こ だけでは意図通りには書き換えられない場合がある．その章ですでに述べた事例は「構文要素に対する否定」で こで，差異のある要素を抽象化するためにパターン変数あるので，残りの 3 つの条件について，それぞれ現実的 を用いて表現する．パターン変数は，変換前パターンでは

“${名前：種別}” の形式で記述し，変換後断片では，“${名前}” の形式で記述する．また，字句系列変換規則は，字句系列に対応するように正規表現を用いて構成される．
これを用いて，書換え対象であるソースコードを構文解析器を通して得られた属性付き字句系列の書換えを行う．
属性付き字句系列とは
種別 (属性値)* ’<’ テキスト’>’で表されるものであり，種別には変数，カンマや括弧などの記号，文の始めと終わりを示すものなどがある．

3.2
3.2.1

構文単位での書換え箇所の否定的な限定方法
制約条件を付与したパターン変換記述の提案

パターン変換記述の変換後断片において，Not Exist Begin と Not Exist End の 間 の 行 に 存 在すべきでない字句を記述し，Not Exist Begin 後の括弧内に “’ 字句’:種別” の形式で，書き換える際に存在すべ
図 2 目印を用いた書換えの流れきでない字句を記述する．この 2 つの記述により，「字句が存在しない」ことを表現する．括弧内に複数の字句を できない．そこで，否定的な制約条件がないときに，書記述する場合はカンマで区切り，いずれの字句も存在し 換えの候補となる箇所から，否定的な制約条件を満たすない場合にのみ書換えが適用される．
箇所を取り除き，その残りの箇所にのみ書換えを適用す
図 1 は，「return が存在しない」という条件を付与し， る方法を用いる．
2.1 節で例として挙げた「関数定義に return 文を挿入す制約条件を含むパターン変換記述から，目印を挿入するる書換え」を表すパターン変換記述である．なお，DECR パターン変換記述，不要な目印を削除する字句変換規則，は宣言子，ID FUNC は関数名，DECL は宣言，STMT* 最終的に字句を挿入するパターン変換記述の順に生成すは複数の文を表す．
る．その後，それらのパターンを順次適用させ，対象ソースコードにおいてパターン変換記述にマッチングし，書換えにより最終的に字句を挿入する可能性のある箇所に，構文要素を構成する字句が存在しないことを判定して1 つずつ目印を付与していき，不要な目印を削除した後に書換えるためには，パターンマッチのエンジンに対し，字目印のある箇所にのみ字句を挿入する書換えを行うこと
句が存在しないことを判定する仕組を組込むことが必要
で 3.2.1 節で付与した条件を考慮した書換えを実現する．
であるが，その拡張は容易ではない．また，TEBA によreturn を関数定義に挿入する書換えの処理の流れを図 2
る書換えは，パターン変換記述を内部で文字列の正規表に示す．ここでの不要な目印とは，Not Exist Begin 後の現に変換して書換えを実現しているので，正規表現を用括弧内に記述した字句が既に存在している場合に，書換いて「字句が存在しない」という「文字列の否定」を表え対象箇所に付与されたものを指す．
現できれば制約条件を付与した形で記述できる．
「文字の各パターンの生成方法は次の通りである．図 1 の否定」は，文字の種類の数が有限なので補集合の要素でようなパターン変換記述の Not Exist Begin の行からある a 以外の文字の種類の数も有限となり，正規表現をNot Exist End の行までの記述を “mark” に置き換える
用いて “[ˆa]” と表現できる．しかし，「文字列の否定」は，ことで目印を挿入するパターン変換記述を生成する．次文字列が無数に存在し，補集合の要素である return 以外に，Not Exist Begin 後の括弧内に記述した字句 1 つに対の文字列も無数に存在するので，正規表現を用いて表現
し 1 つ，不要な目印を削除する字句系列変換規則を生成する．最後に，図 1 のパターン変換記述の Not Exist Begin
の行と Not Exist End の行を取り除くことで，最終的に% before
字句を挿入するパターン変換記述を生成する．
${decr:DECR} ${func:ID_FUNC}( ${int:DECL})

3.2.2

制約条件を付与した書換えの実現方法{${stmts:STMT*}$;}% after${decr} ${func}( ${int}){${stmts}$;
Not_Exist_Begin(’return’:RESERVE)
return (${decr})NEED_RETURN_VALUE;
Not_Exist_End}% end

図 1 ユーザが記述するパターン変換記述

3.3

字句単位での書換え箇所の否定的な限定方法

3.3.1

パターン変数に条件を付与する方法の提案

パターン変換記述におけるパターン変数の種別のあとに${名前:種別!/字句パターン/}の形式で否定する字句のパターンを記述することで，「特定の場所に字句が存在しない」ことを表現する．
2.2 節で例として挙げた return 挿入の書換えを事例とした場合，型宣言子の部分に “void” という字句が存在する場合は挿入するべきでないので，

${decr:DECR!/void/}と記述する．
3.3.2

条件を付与した書換えの実現方法

3.2.2 節と同様に，目印を挿入するパターン変換記述，不要な目印を削除するパターン変換記述，字句を挿入するパターン変換記述の 3 つを生成し，順に適用する．ただし，条件を付与したパターン変数の後に目印を挿入する点が異なる．
3.4

構文単位での書換え箇所の肯定的な限定方法

書換え対象を TEBA のパターン記法における書換え前パターンのみを記述することで表現する．これをターゲッ
ト記述と呼ぶ．ターゲット記述に適合した字句の「書換え対象」属性を「対象」に設定し，それ以外を「非対象」
図 5 ターゲット機能の流れにする．パターン変換を行うときに，「対象」の部分のみを書換える．なお，実装では，「対象」の字句のみ「書換え表 1 適用させる修飾子とその役割対象」属性を取り除いて，書換えを行う．これは，TEBA修飾子
役割の書換え系が追加された属性に対応していないので，書換i
アルファベットの大文字と小文字の区別をしないえの対象外の箇所に意図的に属性値を残すことで，TEBAgすべてのマッチング箇所を探すの書換え系を拡張することなく，実現できるためである．
e
置換文字列を式として実行
例として while 文にマッチするためのパターン記述を図3 に示す．実装上の処理の流れを図 4 に示し，「書換え対象」属性を付加する流れを図 5 に示す．
前パターンと変換後断片では記述方法が異なるので，分けて説明する．
${inti:EXPR}
while (${cond:EXPR}) {${stmt:STMT*};${succ:EXPR}$;}

変換前パターン 字句を構成する文字列に対し正規表現を用いて制約条件を付与するために，パターン変数を${名前:種別 /正規表現/修飾子}と記述する．パターン変数に対応する字句が正規表現の
条件を満たす場合のみ書換えが適用される．

図 3 ターゲット記述

変換後断片 変換後断片では，字句に対する書換えを表現するために，正規表現を用いて${名前 /正規表現/置換文字列/修飾子}と記述する．パターン変数に対応する字句に対し，正規表現の記述にマッチングした箇所が置換文字列に書き換わる．正規表現には，TEBA の実装言語に合わせ Perl の表記を用いる．
正規表現に適用させる修飾子 変換前パターン・変換後断片の正規表現において，表 1 の修飾子を記述できる．変
換前パターンの正規表現では修飾子 i，変換後断片の正規表現では修飾子 g，e，i を適用させ制約条件の表現力を向上させる．

3.5.2

図 4 処理の流れ

3.5
3.5.1

字句単位での書換え箇所の肯定的な限定方法
パターン変数に制約条件を付与する方法の提案

パターン変換記述において，正規表現を用いてパターン変数に制約条件を付与することで表現する．しかし，変換

パターン変換記述における正規表現の適用方法

変換前パターンにおける制約条件は，内部で字句に適当するパターンとして単純に文字列を使用する代わりに，正規表現の記述をそのまま使うことで実現する．変換後断片における制約条件は，適用処理を行う字句を対象に，正規表現でマッチングした箇所を置換文字列に置き換える書換え処理を行うことで，適用する．

4

評価・考察





% before

各制約条件に対する処理が実現できるか，実装を行い，${decr:DECR!/void/} ${func:ID_FUNC}( ${int:DECL}){
2 章で示した事例に基づいて書換えを行なった．その結${stmts:STMT*}$;果，いずれも書き換えられたことが確認できた．
}% after
例えば，構文単位の否定に対しては，字句単位の否定${decr} ${func}( ${int})
で示した制約条件の記述方法と構文単位の否定で示した{${stmts}$;
制約条件の記述方法を組み合わせたパターン変換記述を
Not_Exist_Begin(’return’:RESERVE)
作成し，2.1 節の事例に対し書換えを行なった．その結果，return (${decr})NEED_RETURN_VALUE;
Not_Exist_End
void 型の関数定義と正しく記述した return 文を含む関数}定義以外が書き換えられていることを確認した．これに% end
より，それぞれの限定方法を相互利用した書換えが行な えることが確認できた．使用したパターン変換記述を図
図 6 組み合わせたパターン変換記述
6 に示す．
構文単位の肯定に対しては，Coreutils 8.17[4] のディレ
クトリ src に含まれる拡張子が.c のファイル (116 個）に対し，書換える範囲を指定して書換え可能であることを確認した．このことから現実の中規模のオープンソースに対してもエラーを起こすことなく書換えられることを確認した．また，応用として，ターゲット記述で指定した箇所を否定条件とする機能も実装し，動作を確認した．
以下では，これを「エスケープ機能」と呼び，処理の流れを図 7 に示す．これらの機能を用いて構文単位で書換える範囲を限定することにより，適用するパターン変換記述は書換え内容を表現したものだけになり，パターン変換記述の再利用性の向上が期待できる．
構文単位の否定では，別の事例を用いて実験したところ，パターン変数が存在しないことを条件として記述で図 7 エスケープ機能の流れきないことが判明した．例えば，「fopen により取得したファイルポインタを返す return が関数定義内に存在しない」という条件などである．これに対処するには，条件 なパターン変換を行うことが可能になった．となる字句にパターン変数を記述できるように拡張する
今後の課題として，パターン変換記述の表現力をより方法もあるが，エスケープ機能を用いて「fopen により取 向上させるために，上記の 4 つの限定的なパターン変換得したファイルポインタを返す return が存在する関数」 記述の併用を可能にする TEBA の拡張が必要となる．
を非書換え対象とすることで，この技術的課題を解決できる．エスケープ機能を用いた場合は，複数のターゲッ 参考文献
ト記述を用いて書換え箇所の否定的な限定が可能である． [1] James R. Cordy, Thomas R. Dean, Andrew J. Mal一方，制約条件を付与したパターンを用いた書換えの場
ton, and Kevin A. Schneider, “Source Transforma合は，1 つのパターン変換記述内で「複数の字句が存在しtion in Software Engineering Using the TXL Transない」という条件を記述できる．したがって，それぞれformation System,” Journal of Information and Softの方法を使い分けることが重要である．
ware Technology, vol. 44, no. 13, pp. 827-837, 2002.
構文単位の肯定では，複数のターゲット記述を組み合 [2] 吉田 敦，蜂巣 吉成，沢田 篤史，張 漢明，野呂 昌満，“
わせるときに指定範囲が排他的でなければ正しく動作し属性付き字句系列に基づくソースコード書き換え支援なかった．これは実装上の都合であり，柔軟に制約条件環境，” 情報処理学会論文誌，vol.53，no.7，pp.1832を組み合わせられる仕組みが必要である．
1849，2012.

5

おわりに

[3] Y. Padioleau, “Parsing C/C++ Code without Preprocessing,” Proceedings of the 18th International
Conference on Compiler Construction, pp. 109-125,
2009.

本研究では，TEBA のパターン変換記述における表現力を向上を図るために，パターン変換記述において「構文要素が存在しないという条件の付与」，「特定の箇所に字句が存在しないという条件の付与」「あらかじめ書換え [4] Free Software Foundation, Inc., “Coreutils GNU core utilities,” http://www.gnu.org/
対象箇所を特定し，パターン変換記述により書換える枠
software/coreutils/, 2012.
組み」，「字句を構成する文字列に対する制約条件の付与」の 4 点を拡張することで実現した．これにより，限定的