JP2904112B2 - プログラム自動合成装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、複数用意された書
き換え規則に基づき、木構造で表現されるプログラム仕
様の変換を繰り返してプログラムを合成するプログラム
自動合成技術に関する。

【０００２】

【従来の技術】プログラム自動合成装置の一種に、左辺
部にプログラム仕様中の変換を行う部分木の構造を、右
辺部にその部分木の変換後の構造をそれぞれ定義した書
き換え規則の集合を用いて、関数記号を節とする木構造
で表現されたプログラム仕様の変換を繰り返すことによ
ってプログラムを自動生成する装置がある。なお、書き
換え対象となるプログラム仕様中に書き換え規則によっ
て書き換え可能な部分が複数ある場合、どれを優先的に
書き換えるかを定める戦略として、プログラム仕様の木
構造上で最も根に近い部分で且つ最も左側の部分を書き
換える最左最外戦略と、最も葉に近い部分で且つ最も左
側の部分を書き換える最左最内戦略とがあるが、本発明
では、このうちの後者の最左最内戦略を用いるプログラ
ム自動合成装置を対象としている。

【０００３】図２は木構造で表されたプログラム仕様の
例を、図３は書き換え規則の集合の例を、図４はそれら
の書き換え規則を木構造で表現した図を、それぞれ示
す。ここで、小文字の英数字は関数記号を、大文字の英
数字は変数を表している。また、図５は図３および図４
に示す書き換え規則を用いて図２に示すプログラム仕様
の変換を繰り返す過程を示している。従来のプログラム
自動合成装置における変換は以下のように進められる。

【０００４】最左最内戦略では、プログラム仕様の最左
最内部（最も葉に近い部分で且つ左側の部分）から書き
換えを行う。そこで先ず、図２のプログラム仕様の最左
最内部に適合する部分木を左辺部に持つ書き換え規則を
図３，図４に示す書き換え規則集合中から探索し、図５
の５０１の左辺部を持つ書き換え規則３３を得て、プロ
グラム仕様の最左最内部および規則３３の右辺部の内容
に基づき、図５に示す「書き換え１」を実行し、プログ
ラム仕様２２の最左最内部を書き換える。

【０００５】次に、この書き換え後のプログラム仕様の
最左最内部に適合する部分木を左辺部に持つ書き換え規
則を書き換え規則集合中から探索し、図５の５０２の左
辺部を持つ書き換え規則３１を得て、プログラム仕様の
最左最内部および規則３１の内容に基づき、図５に示す
「書き換え２」を実行し、プログラム仕様の最左最部を
再度書き換える。

【０００６】次に、この書き換え後のプログラム仕様の
最左最内部に適合する部分木を左辺部に持つ書き換え規
則を書き換え規則集合中から探索し、図５の５０３の左
辺部を持つ書き換え規則３２を得て、プログラム仕様の
最左最内部および規則３２の内容に基づき、図５に示す
「書き換え３」を実行し、プログラム仕様の最左最部を
再度書き換える。

【０００７】次に、この書き換え後のプログラム入力仕
様の最左最内部に適合する部分木を左辺部に持つ書き換
え規則を書き換え規則集合中から探索し、図５の５０１
の左辺部を持つ書き換え規則３３を得て、プログラム仕
様の最左最内部および規則３３の内容に基づき、図５に
示す「書き換え４」を実行し、プログラム入力仕様の最
左最内部を再び書き換える。そして、この書き換え後の
プログラム仕様は、これ以上書き換えが行われない正規
形であるため、書き換えを終了する。

【０００８】

【発明が解決しようとする課題】前述したように従来の
装置では、木構造で表現されたプログラム仕様を書き換
え規則を用いて書き換え、新たな木構造が生成された際
に再びその木構造から書き換え規則集合中の書き換え規
則のうちで適用可能な規則を選択していた。このため、
書き換え規則によって生成される構造が、直接他の書き
換え規則によって書き換えが行われることが決定的な場
合も、常にあらためて書き換え規則の選択を行わなけれ
ばならず、その結果、書き換え処理が遅くなるという問
題がある。ここで、書き換え規則によって生成される構
造が、直接他の書き換え規則によって書き換えが行われ
ることが決定的な場合が生じるのは、各々の書き換え規
則を他の全ての書き換え規則を考慮して作成しておくこ
とが困難であること、既存の書き換え規則集合に対して
不足する書き換え規則を順次追加していって書き換え規
則集合の充実を図るようにしていること、デバッグ等の
ために規則自体を利用者が理解し易い形式で作成してい
ること等が、主な要因である。

【０００９】そこで本発明の目的は、書き換え規則集合
を予め解析しておくことによって、或る書き換え規則の
適用後に生成される木構造が、書き換え規則集合中の他
の書き換え規則によって書き換えられる可能性がある場
合、書き換え規則を再度選択することなく直接書き換え
られるようにして、書き換え可能な部分に適用可能な書
き換え規則の選択に要するコストを低減し、もってプロ
グラム合成処理の速度を向上させることにある。

【００１０】なお、本発明と同様に書き換えの効率化を
図った装置として、本発明者の提案にかかる特開平６−
２５１０６６号公報がある。この従来技術は、予め書き
換え規則の集合を解析して書き換え対象の候補となる関
数記号の集合を求め、この集合に含まれない関数記号は
そもそも変換の対象とはならないので、入力プログラム
仕様中のそのような関数記号に事前にマークを付けてお
き、プログラム仕様中から書き換え可能な部分を探索す
る際にマークが付けられた部分を探索範囲から除外する
ものである。この従来技術は、プログラム仕様中の探索
範囲を絞り込むことによる効率化を狙ったものである。
これに対して本発明は、書き換え規則の選択頻度の削減
による効率化を狙ったものであり、両者は同じ目的を有
するが、それを達成するためのアプローチの仕方が相違
している。

【００１１】

【課題を解決するための手段】最左最内戦略を採用する
場合、書き換え規則の集合に含まれる書き換え規則のう
ち、その右辺部に現れる関数記号が、自身の書き換え規
則または他の書き換え規則の左辺部に定義された部分木
の最外部関数記号（最も根に近い位置の関数記号）と同
じである場合、その書き換え規則によって書き換えた後
の部分木が、その直後に、自身の書き換え規則または前
記他の書き換え規則によって再度書き換えられる可能性
がある。そこで本発明では、書き換え規則の集合を事前
に解析して上述のような関係にある書き換え規則を洗い
出し、或る書き換え規則の適用後に生成される木構造
が、書き換え規則集合中の他の書き換え規則によって書
き換えられる可能性がある場合、書き換え規則を再度選
択することなく直接書き換えれるようにする。

【００１２】

【００１３】即ち、本発明は、左辺部にプログラム仕様
中の変換を行う部分木の構造を、右辺部にその部分木の
変換後の構造をそれぞれ定義した書き換え規則の集合を
用いて、関数記号を節とする木構造で表現されたプログ
ラム仕様の変換を繰り返してプログラムを生成するプロ
グラム自動合成装置において、書き換え規則の集合を入
力し、左辺部に定義された部分木の最外部関数記号が同
一である書き換え規則のグループ毎に、呼び出し元から
引数で与えられる変換対象部分木構造に基づき当該グル
ープの何れの書き換え規則の左辺部が変換対象部分木と
マッチするかを判断し、且つ、マッチする左辺部に対応
する右辺部に定義された部分木中に自グループおよび他
グループの何れかの書き換え規則の左辺部に定義された
部分木の最外部関数記号が存在するときは当該右辺部の
定義に基づく変換後の部分木の構造を引数として当該存
在した最外部関数記号に対応する書き換え関数を呼び出
してその返却値を呼び出し元に返却し、そのような最外
部関数記号が存在しないときは当該右辺部の定義に基づ
く変換後の部分木の構造を返却値として呼び出し元に返
却する書き換え関数を生成する書き換え規則コンパイル
部と、変換対象とするプログラム仕様に対して最左最内
戦略に基づいて探索した変換対象部分木の構造を引数に
してその部分木の最外部関数記号に対応する書き換え関
数を呼び出し、その返却される変換後の部分木の構造に
基づき前記変換対象部分木の書き換えを行う処理を、変
換可能な部分木が無くなるまで繰り返す書き換え装置と
を備えることを特徴とする。

【００１４】更に本発明は、前記書き換え規則コンパイ
ル部に、左辺最外部関数記号登録部と、書き換え規則登
録部と、入力した書き換え規則の集合に含まれる書き換
え規則を解析し、書き換え規則の左辺部に定義された部
分木の最外部関数記号の種類を前記左辺最外部関数記号
登録部に登録すると共に、入力した書き換え規則を前記
最外部関数記号の種類毎にグループ化して前記書き換え
規則登録部に登録する書き換え規則解析部と、前記書き
換え規則登録部に登録された書き換え規則の右辺部に定
義された部分木中に前記左辺最外部関数記号登録部に登
録された種類の関数記号が存在するか否かを調べ、存在
した右辺部の関数記号にマークを付ける右辺マーク部
と、前記書き換え規則登録部に登録された書き換え規則
のグループ毎に、呼び出し元から引数で与えられる変換
対象部分木構造に基づき当該グループの何れの書き換え
規則の左辺部が変換対象部分木とマッチするかを判断
し、且つ、マッチする左辺部に対応する右辺部にマーク
が付いているときは当該右辺部の定義に基づく変換後の
部分木の構造を引数として当該マークが付いている関数
記号に対応する書き換え関数を呼び出してその返却値を
呼び出し元に返却し、マークが付いていないときは当該
右辺部の定義に基づく変換後の部分木の構造を返却値と
して呼び出し元に返却する書き換え関数を生成する書き
換え関数生成部とを含むことを特徴とする。

【００１５】

【発明の実施の形態】次に本発明の実施の形態の例につ
いて図面を参照して詳細に説明する。

【００１６】図１を参照すると、本発明の一実施例のプ
ログラム自動合成装置１０は、書き換え規則集合２４を
用いて、プログラム仕様２２の変換を繰り返すことによ
ってプログラム２３を生成する装置であり、仕様入力部
１１，書き換え装置１２，プログラム出力部１３，書き
換え関数格納部１４，書き換え規則コンパイル部１５お
よび書き換え規則集合入力部２１を備えている。

【００１７】本実施例のプログラム自動合成装置１０
は、大別して、書き換え規則集合２４から書き換え関数
を生成する部分と、この生成された書き換え関数を使用
して、プログラム仕様２２からプログラム２３を生成す
る部分とに分けられる。以下では、先ず前者の部分につ
いて説明し、次いで後者の部分について説明する。

【００１８】書き換え規則集合２４から書き換え関数を
生成する部分は、書き換え規則集合２４を入力する書き
換え規則集合入力部２１と、入力された書き換え規則集
合２４から書き換え関数を生成する書き換え規則コンパ
イル部１５と、生成された書き換え関数を格納する書き
換え関数格納部１４とで構成される。

【００１９】図３に書き換え規則集合２４の一例を示
す。また、図４に図３の書き換え規則集合２４中の各々
の書き換え規則３１〜３３を木構造で表現した図を示
す。なお、図３および図４において、小文字の英数字は
関数記号を、大文字の英数字は変数を、それぞれ示す。
各々の書き換え規則３１〜３３は、図３に示すように、
左辺部と右辺部とそれらを結合する記号（矢印）とで構
成される。左辺部は、プログラム仕様中の変換を行う部
分木の構造を定義し、右辺部はその部分木の変換後の構
造を定義している。

【００２０】この例の書き換え規則集合２４は、そのま
ま適用すると、プログラム仕様中のａ（Ｘ，１）または
ａ（Ｘ，０）となる最左最内部に関して、書き換え規則
の選択が冗長になる。即ち、プログラム仕様中の最左最
部が、若しａ（Ｘ，１）ならば、書き換え規則３１が選
択されてａ（Ｘ，０）に変換されると、最左最内戦略で
は再び最左最内部に対する変換を行うので、次に書き換
え規則３２が選択されて最左最部がｂ（Ｘ）に変換さ
れ、更に書き換え規則３３が選択されて、最終的にＸに
変換され、合計３回の書き換え規則の選択が行われるか
らである。同様に、プログラム仕様中の最左最内部が、
若しａ（Ｘ，０）ならば、書き換え規則３２，書き換え
規則３３の順に選択されて、最終的にＸに変換され、合
計２回の書き換え規則の選択が必要となる。そこで、本
実施例では、このような冗長性を排するため、プログラ
ム仕様中の最左最内部が若しａ（Ｘ，１）またはａ
（Ｘ，０）ならば、その変換結果として直ちにＸを返却
するような書き換え関数を、書き換え規則集合２４に基
づき生成する。この生成は、書き換え規則コンパイル部
１５が行う。

【００２１】書き換え規則コンパイル部１５は、図１に
示すように、書き換え関数生成部１６と、左辺最外部関
数記号登録部１７と、右辺マーク部１８と、書き換え規
則登録部１９と、書き換え規則解析部２０とから構成さ
れている。

【００２２】左辺最外部関数記号登録部１７は、書き換
え規則集合２４に含まれる書き換え規則３１〜３３の左
辺部に定義された部分木の最外部関数記号の種類を保持
する部分であり、書き換え規則解析部２０から書き込み
が行われ、書き換え関数生成部１６から参照される。こ
こで、部分木の最外部関数記号とは、その部分木の最も
根に近い位置の関数記号を意味し、書き換え規則３１，
３２の場合はａ，書き換え規則３３の場合はｂである。

【００２３】書き換え規則登録部１９は、書き換え規則
集合２４に含まれる書き換え規則３１〜３３を、左辺部
の最外部関数記号の種類毎にグループ化して保持する部
分であり、書き換え規則解析部２０から書き込みが行わ
れ、右辺マーク部１８によって参照されると共にマーク
付けされ、また書き換え関数生成部１６によって参照さ
れる。

【００２４】書き換え規則解析部２０は、書き換え規則
集合入力部２１を通じて書き換え規則集合２４を入力
し、入力した書き換え規則集合２４に含まれる書き換え
規則３１〜３３を解析し、書き換え規則の左辺部に定義
された部分木の最外部関数記号の種類を左辺最外部関数
記号登録部１７に登録すると共に、入力した書き換え規
則を最外部関数記号の種類毎にグループ化して書き換え
規則登録部１９に登録する手段である。

【００２５】右辺マーク部１８は、書き換え規則登録部
１９に登録された書き換え規則の右辺部に定義された部
分木中に左辺最外部関数記号登録部１７に登録された種
類の関数記号が存在するか否かを調べ、存在した右辺部
の関数記号にマークを付ける手段である。

【００２６】書き換え関数生成部１６は、書き換え規則
登録部１９に登録された書き換え規則のグループ毎に、
１つの書き換え関数を生成して、書き換え関数格納部１
４に格納する手段である。生成される書き換え関数は、
次のような機能、つまり呼び出し元から引数で与えられ
る変換対象部分木構造に基づき当該グループの何れの書
き換え規則の左辺部が変換対象部分木とマッチするかを
判断し、且つ、マッチする左辺部に対応する右辺部に定
義された部分木中に自グループまたは他グループの書き
換え規則の左辺部に定義された部分木の最外部関数記号
が存在するときは当該右辺部の定義に基づく変換後の部
分木の構造を引数として当該存在した最外部関数記号に
対応する書き換え関数を呼び出してその返却値を呼び出
し元に返却し、そのような最外部関数記号が存在しない
ときは当該右辺部の定義に基づく変換後の部分木の構造
を返却値として呼び出し元に返却する機能を持つ。

【００２７】図６は書き換え規則コンパイル部１５の処
理例を示すフローチャートである。以下、図１および図
６を参照して書き換え規則コンパイル部１５の動作を説
明する。

【００２８】初期の状態においては、左辺最外部関数記
号登録部１７および書き換え規則登録部１９の内容はク
リアされている。コンパイル時、先ず、書き換え規則解
析部２０は、書き換え規則集合入力部２１を通じて書き
換え規則集合２４を入力する（Ｓ１）。

【００２９】次に、入力した書き換え規則集合２４に含
まれる書き換え規則の各々に対してステップＳ２〜Ｓ５
の処理を行う。先ず、その書き換え規則の左辺部におけ
る最外部の関数記号（左辺最外部関数記号）が左辺最外
部関数記号登録部１７に登録されているか否かを調べ
（Ｓ３）、登録されていなければ登録した後（Ｓ４）、
その書き換え規則をその左辺最外部関数記号に関連付け
て書き換え規則登録部１９へ登録する（Ｓ５）。他方、
その書き換え規則の左辺最外部関数記号が既に左辺最外
部関数記号登録部１７に登録されていれば、ステップＳ
４をスキップして、今回の書き換え規則をその左辺最外
部関数記号に関連付けて書き換え規則登録部１９へ登録
する（Ｓ５）。以上の処理を全ての書き換え規則に対し
て繰り返した時点で（Ｓ６でＹＥＳ）、書き換え規則解
析部２０の処理が終了する。この時点で、左辺最外部関
数記号登録部１７に、書き換え規則集合２４に含まれる
書き換え規則の左辺部に定義された部分木の最外部関数
記号の種類が全て登録され、また、書き換え規則登録部
１９に全ての書き換え規則が左辺最外部関数記号の種類
毎にグループ化されて登録されたことになる。

【００３０】次に、右辺マーク部１８は、書き換え規則
登録部１９に登録されている書き換え規則の各々に対し
てステップＳ７〜Ｓ９の処理を行う。先ず、その書き換
え規則の右辺部に、左辺最外部関数記号登録部１７に登
録されている関数記号が存在するか否かを調べ（Ｓ
８）、存在すれば、書き換え規則登録部１９上でその存
在した関数記号にマークを付ける（Ｓ９）。他方、存在
しなければマーク付け処理は行わない。以上の処理を全
ての書き換え規則に対して繰り返した時点で（Ｓ１０で
ＹＥＳ）、右辺マーク部１８の処理が終了する。この時
点で、書き換え規則登録部１９に格納されている書き換
え規則のうち、その右辺部に定義された部分木中に自グ
ループまたは他グループの書き換え規則の左辺部に定義
された部分木の最外部関数記号と同じ関数記号を持つ書
き換え規則については、その関数記号にマークが付けら
れたことになる。

【００３１】次に、書き換え関数生成部１６による書き
換え関数の生成と書き換え関数格納部１４への格納とが
実行される（Ｓ１１）。

【００３２】図７は図６のステップＳ１１の詳細を示す
フローチャートである。以下、図１および図７を参照し
て書き換え関数生成部１６の動作を説明する。

【００３３】書き換え関数生成部１６は、左辺最外部関
数記号登録部１７に登録されている関数記号単位に、ス
テップＳ２１〜Ｓ３０を実行することにより、その関数
記号に対応する書き換え関数を生成する。

【００３４】先ず、左辺最外部関数記号登録部１７に登
録されている１つの関数記号に注目し（Ｓ２１）、それ
に対応する書き換え関数名を生成し、書き換え関数スケ
ルトンを生成する（Ｓ２２）。次に、その関数記号に関
連付けられた全ての書き換え規則を書き換え規則登録部
１９から入力し（Ｓ２３）、その各々の書き換え規則に
ついて、ステップＳ２４〜Ｓ２８の処理を実行する。

【００３５】先ず、１つの書き換え規則に注目し（Ｓ２
４）、その左辺部から必要に応じパターンマッチを行う
プログラム断片をスケルトン部に生成する（Ｓ２５）。
パターンマッチを行うプログラム断片は、左辺部に定義
された部分木の構造に従ってパターンマッチを行うプロ
グラム部分、並びに左辺部に現れる変数の代入処理を行
うプログラム部分から構成される。次に、パターンがマ
ッチした場合に書き換え後の部分木の構造を返却するプ
ログラム断片を生成するが、右辺部にマークが有る場合
と無い場合とで作成するプログラム断片が異なるので、
現注目中の書き換え規則の右辺部にマークがあるか否か
を判定し、処理を切りわける（Ｓ２６）。

【００３６】右辺部にマークが有る場合は、当該右辺部
の定義に基づく変換後の部分木の構造を引数として当該
マークの付いた関数記号に対応する書き換え関数を呼び
出してその返却値を呼び出し元に返却するプログラム断
片をスケルトン部に生成する（Ｓ２８）。

【００３７】他方、右辺部にマークが無い場合は、当該
右辺部の定義に基づく変換後の部分木の構造を返却値と
して呼び出し元に返却するプログラム断片をスケルトン
部に生成する（Ｓ２７）。

【００３８】以上の処理を、ステップＳ２３で入力した
全ての書き換え規則、つまり同じ左辺最外部関数を持つ
書き換え規則に対して実行することにより（Ｓ２９）、
当該左辺最外部関数に対応する１つの書き換え関数を生
成し、これを書き換え関数格納部１４に格納する（Ｓ３
０）。

【００３９】以上のような処理を、左辺最外部関数記号
登録部１７に登録された全ての関数記号単位に実行し終
えると（Ｓ３１）、書き換え関数格納部１４に、各左辺
最外部関数記号に対応する書き換え関数が格納されたこ
とになり、書き換え関数生成部１６の処理が終了する。

【００４０】図８は図３で例示した書き換え規則集合２
４に対して書き換え規則コンパイル部１５の書き換え規
則解析部２０および右辺マーク部１８による処理が行わ
れた後の、左辺最外部関数記号登録部１７および書き換
え規則登録部１９の内容例を示している。図３に示す３
つの書き換え規則３１〜３３には、左辺最外部関数記号
として、ａ，ｂの２種類が存在するため、図８に示すよ
うに左辺最外部関数記号登録部１７にはａ，ｂの２つが
登録される。また、書き換え規則３１，３２はａを、書
き換え規則３３はｂを左辺最外部関数として持つため、
書き換え規則登録部１９上では、書き換え規則３１およ
び３２が左辺最外部関数ａを持つグループ８１として登
録され、書き換え規則３３は左辺最外部関数ｂを持つグ
ループ８２として登録される。さらに、書き換え規則３
１および３２の右辺部には、左辺最外部関数記号登録部
１７に登録されている関数記号ａが存在するため、図８
に示すように各々にマークが付けられる。

【００４１】図９は書き換え関数格納部１４に格納され
た書き換え関数の例を示す。この例の書き換え関数は、
図８で例示した左辺最外部関数記号登録部１７および書
き換え規則登録部１９の内容に基づき書き換え関数生成
部１６によって生成されたものであり、何れもＣ言語の
一つの関数として生成されている。このうち、書き換え
関数９１は、図８の書き換え規則登録部１９に登録され
ているグループ８１に属する２つの書き換え規則３１，
３２に基づき生成された、関数記号ａを書き換える関数
であり、書き換え関数９２はグループ８２に属する１つ
の書き換え規則３３に基づき生成された、関数記号ｂを
書き換える関数である。

【００４２】書き換え関数９１には、引数として変数
Ｘ，Ｙが与えられる。また、書き換え規則３１の左辺部
の構造は（Ｘ，１）であるため、そのパターンマッチを
行うｉｆ文として、変数Ｙが１か否かを調べるプログラ
ム断片「ｉｆ（Ｙ＝＝１）」と、変数Ｙが１の場合の処
理を記述するプログラム断片「ｒｅｔｒｕｎ ａ（Ｘ，
０）」とが含まれる。この後者のプログラム断片は、マ
ークが付いていない場合は書き換え規則３１の右辺部の
構造に基づき変換後の部分木の構造「ａ（Ｘ，０）」を
返却値として呼び出し元に返却するプログラム断片とな
るが、マークが付いている場合には、この例に示すよう
に、右辺部の定義に基づく変換後の部分木の構造を引数
として関数記号ａに対応する書き換え関数９１（この例
の場合は自分自身）を直接呼び出してその返却値を呼び
出し元に返却するプログラム断片となる。同様に、書き
換え規則３２の左辺部の構造は（Ｘ，０）であるため、
そのパターンマッチを行うｉｆ文として、変数Ｙが０か
否かを調べるプログラム断片「ｉｆ（Ｙ＝＝０）」と、
変数Ｙが０の場合の処理を記述するプログラム断片「ｒ
ｅｔｒｕｎ ｂ（Ｘ）」とが含まれる。この後者のプロ
グラム断片は、マークが付いていない場合は書き換え規
則３２の右辺部の構造に基づき変換後の部分木の構造
「ｂ（Ｘ）」を返却値として呼び出し元に返却するプロ
グラム断片となるが、マークが付いている場合には、こ
の例に示すように、右辺部の定義に基づく変換後の部分
木の構造を引数として関数記号ａに対応する書き換え関
数９２を直接呼び出してその返却値を呼び出し元に返却
するプログラム断片となる。なお、変数Ｙが１でも０で
もない場合は、書き換えが失敗した旨を示すＮＵＬＬ値
を呼び出し元に返却し得るようにするために、プログラ
ム断片「ｒｅｔｕｒｎ ＮＵＬＬ」が追加されている。

【００４３】他方、書き換え関数９２は、引数として変
数Ｘが与えられる。そして、この場合、パターンマッチ
の必要性が無いので、変数Ｘを呼び出し元に返却するプ
ログラム断片（ｒｅｔｕｒｎ Ｘ）が記述されている。

【００４４】次に、図１において、生成された書き換え
関数を使用して、プログラム仕様２２からプログラム２
３を生成する部分について説明する。この部分は、仕様
入力部１１と、書き換え装置１２と、プログラム出力部
１３と、書き換え関数格納部１４とで構成される。

【００４５】図１０は書き換え装置１２の処理例を示す
フローチャートである。以下、図１および図１０を参照
してその動作を説明する。

【００４６】書き換え装置１２は、先ず、仕様入力部１
１を通じてプログラム仕様２２を入力して内部に展開す
る（Ｓ４１）。次に、このプログラム仕様２２に対して
最左最内戦略に基づいて探索した変換対象部分木の構造
を引数にしてその部分木の最外部関数記号に対応する書
き換え関数を呼び出す（Ｓ４４）。そして、その返却さ
れる変換後の部分木の構造に基づき前記変換対象部分木
の書き換えを行い（Ｓ４５）、ステップＳ４２に戻って
再び最左最内戦略に基づいて変換対象部分木を探索す
る。以上の処理を書き換え可能な部分が無くなるまで繰
り返し（Ｓ４３）、書き換え可能な部分が無くなった時
点の変換後の結果を自動生成結果のプログラムとしてプ
ログラム出力部１３を通じて出力する（Ｓ４６）。

【００４７】例えば、書き換え関数格納部１４に図９に
示される書き換え関数９１，９２が格納されており、図
２に例示したようなプログラム仕様２２が入力された場
合、書き換え装置１２は、先ず、最左最内部に現れる関
数記号ｂに対応する書き換え関数９２を変数Ｘ＝１を引
数として呼び出す。書き換え関数９２は図９に示す通
り、変数Ｘをそのまま返却するので、書き換え装置１２
は、最左最内部を変数Ｘに書き換える。つまり、図５の
「書き換え１」のような書き換えを行う。

【００４８】次に、書き換え装置１２は、最左最内部に
現れる関数記号ａに対応する書き換え関数９１（以下、
第１の関数と呼ぶ）を変数Ｘ＝１，Ｙ＝１を引数として
呼び出す。第１の関数である書き換え関数９１は図９に
示す通り、変数Ｙが１の場合、変数Ｘ＝１，Ｙ＝０を引
数として書き換え関数９１（つまり自分自身。以下第２
の関数と呼ぶ）を直接呼び出す。この呼び出された第２
の関数である書き換え関数９１では、変数Ｙが０なの
で、変数Ｘ＝１を引数として書き換え関数９２を直接呼
び出す。この呼び出された書き換え関数９２では、その
変数Ｘ＝１をそのまま呼び出し元の第２の関数に返却
し、第２の関数はそれを第１の関数に返却し、そして、
第１の関数である書き換え関数９１は、呼び出し元の書
き換え装置１２にそれを返却する。この結果、書き換え
装置１２は、変換後の部分木の構造として、Ｘ＝１を得
ることになり、最左最内部をＸ＝１に書き換える。これ
は、図５に示す「書き換え５」に相当する。つまり、従
来必要であった「書き換え２」，「書き換え３」，「書
き換え４」が、１つの「書き換え５」で済むことにな
る。

【００４９】

【発明の効果】以上説明したように本発明によれば、木
構造を持つプログラム仕様を書き換え規則の集合を用い
て書き換えを行ってプログラムを生成する場合、書き換
え規則集合を予め解析しておくことによって、或る書き
換え規則の適用後に生成される木構造が、書き換え規則
集合中の他の書き換え規則によって書き換えられる可能
性がある場合、書き換え装置は書き換え規則を再度選択
することなく直接書き換えることができ、書き換え可能
な部分に適用可能な書き換え規則の選択に要するコスト
を低減でき、高速な書き換え、つまりプログラム生成が
可能となる。

【図面の簡単な説明】

【図１】本発明の一実施例のプログラム自動合成装置の
ブロック図である。

【図２】プログラム仕様の一例を示す図である。

【図３】書き換え規則集合の一例を示す図である。

【図４】図３の書き換え規則集合に含まれる各書き換え
規則を木構造で示す図である。

【図５】書き換え規則によってプログラム仕様の変換を
繰り返す過程の説明図である。

【図６】書き換え規則コンパイル部の処理例を示すフロ
ーチャートである。

【図７】図６のステップ１１の詳細な処理を示すフロー
チャートである。

【図８】左辺最外部関数記号登録部および書き換え規則
登録部の登録内容の一例を示す図である。

【図９】書き換え関数格納部に格納された書き換え関数
の例を示す図である。

【図１０】書き換え装置の処理例を示すフローチャート
である。

【符号の説明】

１０…プログラム自動合成装置 １１…仕様入力部 １２…書き換え装置 １３…プログラム出力部 １４…書き換え関数格納部 １５…書き換え規則コンパイル部 １６…書き換え関数生成部 １７…左辺最外部関数記号登録部 １８…右辺マーク部 １９…書き換え規則登録部 ２０…書き換え規則解析部 ２１…書き換え規則集合入力部 ２２…プログラム仕様 ２３…プログラム ２４…書き換え規則集合

Claims (2)

(57)【特許請求の範囲】
1. 【請求項１】 左辺部にプログラム仕様中の変換を行う
   部分木の構造を、右辺部にその部分木の変換後の構造を
   それぞれ定義した書き換え規則の集合を用いて、関数記
   号を節とする木構造で表現されたプログラム仕様の変換
   を繰り返してプログラムを生成するプログラム自動合成
   装置において、 書き換え規則の集合を入力し、左辺部に定義された部分
   木の最外部関数記号が同一である書き換え規則のグルー
   プ毎に、呼び出し元から引数で与えられる変換対象部分
   木構造に基づき当該グループの何れの書き換え規則の左
   辺部が変換対象部分木とマッチするかを判断し、且つ、
   マッチする左辺部に対応する右辺部に定義された部分木
   中に自グループおよび他グループの何れかの書き換え規
   則の左辺部に定義された部分木の最外部関数記号が存在
   するときは当該右辺部の定義に基づく変換後の部分木の
   構造を引数として当該存在した最外部関数記号に対応す
   る書き換え関数を呼び出してその返却値を呼び出し元に
   返却し、そのような最外部関数記号が存在しないときは
   当該右辺部の定義に基づく変換後の部分木の構造を返却
   値として呼び出し元に返却する書き換え関数を生成する
   書き換え規則コンパイル部と、 変換対象とするプログラム仕様に対して最左最内戦略に
   基づいて探索した変換対象部分木を引数にしてその部分
   木の最外部関数記号に対応する書き換え関数を呼び出
   し、その返却される変換後の部分木の構造に基づき前記
   変換対象部分木の書き換えを行う処理を、変換可能な部
   分木が無くなるまで繰り返す書き換え装置とを備えるこ
   とを特徴とするプログラム自動合成装置。
2. 【請求項２】 前記書き換え規則コンパイル部は、 左辺最外部関数記号登録部と、 書き換え規則登録部と、 入力した書き換え規則の集合に含まれる書き換え規則を
   解析し、書き換え規則の左辺部に定義された部分木の最
   外部関数記号の種類を前記左辺最外部関数記号登録部に
   登録すると共に、入力した書き換え規則を前記最外部関
   数記号の種類毎にグループ化して前記書き換え規則登録
   部に登録する書き換え規則解析部と、 前記書き換え規則登録部に登録された書き換え規則の右
   辺部に定義された部分木中に前記左辺最外部関数記号登
   録部に登録された種類の関数記号が存在するか否かを調
   べ、存在した右辺部の関数記号にマークを付ける右辺マ
   ーク部と、 前記書き換え規則登録部に登録された書き換え規則のグ
   ループ毎に、呼び出し元から引数で与えられる変換対象
   部分木構造に基づき当該グループの何れの書き換え規則
   の左辺部が変換元対象部分木とマッチするかを判断し、
   且つ、マッチする左辺部に対応する右辺部にマークが付
   いているときは当該右辺部の定義に基づく変換後の部分
   木の構造を引数として当該マークが付いている関数記号
   に対応する書き換え関数を呼び出してその返却値を呼び
   出し元に返却し、マークが付いていないときは当該右辺
   部の定義に基づく変換後の部分木の構造を返却値として
   呼び出し元に返却する書き換え関数を生成する書き換え
   関数生成部とを含むことを特徴とする請求項１記載のプ
   ログラム自動合成装置。