JPH08272622A - プログラム変換装置 - Google Patents

Abstract

(57)【要約】 【目的】 複雑な構造のプログラムを、煩雑な記述のル
ールを用いることなく別のプログラムに変換すること。 【構成】 変換対象の入力プログラムとその変換ルール
の構文を、構文木を構成するノードに型階層を用いた構
文解析を行い、入力プログラムの構文木および変換ルー
ルの構文木を作成する構文解析手段と、前記入力プログ
ラムの構文木を前記変換ルールの構文木で書き換える構
文木書き換え手段と、書き換えられた入力プログラムの
構文木を変換されたプログラムとして出力する出力手段
とを備える。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、プログラム変換装置に
関し、特に複雑な構文を持った入力プログラムを構文解
析し、その結果を変換ルールに基づき別のプログラムへ
変換するプログラム変換装置に関するものである。

【０００２】

【従来の技術】従来において、変換対象の入力プログラ
ムを別のプログラムへ変換する方法として、入力プログ
ラムを単なるテキストデータと見做し、文書編集ツール
をプログラムの書換えに援用する方法が知られている。

【０００３】また、記号処理用言語Ｌｉｓｐに対しては
プログラムの構造を考慮した書換えツールが言語仕様の
一部として用意され、新しい制御構造の導入の目的に標
準的に用いられているが、これはＬｉｓｐ言語の構文が
非常に簡単で、プログラムそのものがすでに構文木の形
をしているという事実に着目したものである。

【０００４】一方、特開平５−１８１６５１号の「プロ
グラム自動生成装置」に開示されているように、設計知
識を変換対象部分と変換対象にならない部分に分離する
ことにより、変換途中の仕様を小さく保ち、検索時間を
削減する方法がある。

【０００５】

【発明が解決しようとする課題】しかしながら、上記従
来技術にあっては、構文木の構造、特に複雑な構造の通
常のプログラムを変換対象として考慮していないため、
このようなプログラムを変換することは不可能である。

【０００６】一方、ソフトウェア開発に実際用いられて
いるプログラミング言語の構文は複雑であり、正確な構
文解析を行おうとすると、解析ルーチンが大規模とな
り、解析結果である構文木も複雑なものとなってしま
う。

【０００７】これは、プログラム変換装置を実現しよう
とするとき、構文解析部の実現が困難であることのみで
はなく、構文木書換え用の変換ルールを記述しようとす
る時に、ルールの記述が煩雑な形になってしまうことを
意味している。

【０００８】また、変換ツールを用いて新しい制御構造
を定義しようとする時、構文解析があまりにも厳密であ
ると、定義しようとしている新しい制御構造の解析が構
文エラーとなり、構文木の書換えの形では実現できなく
なるという問題がある。

【０００９】本発明の目的は、複雑な構造のプログラム
を、煩雑な記述のルールを用いることなく別のプログラ
ムに変換することができるプログラム変換装置を提供す
ることにある。

【００１０】

【課題を解決するための手段】上記目的を達成するた
め、本発明のプログラム変換装置は、変換対象の入力プ
ログラムとその変換ルールの構文を、構文木を構成する
ノードに型階層を用いた構文解析を行い、入力プログラ
ムの構文木および変換ルールの構文木を作成する構文解
析手段と、前記入力プログラムの構文木を前記変換ルー
ルの構文木で書き換える構文木書き換え手段と、書き換
えられた入力プログラムの構文木を変換されたプログラ
ムとして出力する出力手段とを備えることを特徴とす
る。

【００１１】そして、構文解析手段は、変換対象の入力
プログラムの構文に一致した変換ルールの構文木を出力
することを特徴とする。

【００１２】

【作用】上記手段によれば、入力された変換対象のプロ
グラムを変換ルールに従って構文解析し、変換対象のプ
ログラムの構文木を得る。

【００１３】同様に、変換ルール自体も構文解析し、変
換ルールの構文木を得る。

【００１４】次に、プログラムの構文木に構文木化され
た変換ルールを適用し、書換えられたプログラムの構文
木を得る。

【００１５】最後に、書換えられた構文木を、変換され
たプログラムとして出力する。

【００１６】ここで、構文解析手段は、構文木を構成す
るノードに型階層を用いた構文解析を行う。構文木のノ
ードに型階層を導入した場合、構文木において上位型の
ノードが出現可能である下位型のノードが出現すること
も許す。これにより、構文解析ルーチンは上位型のノー
ドのみが出現する簡約化された構文木を出力すればよい
ことになり、処理が楽になる。

【００１７】さらに、構文木の変換ルールを型に応じて
記述するオブジェクト指向プログラミングが可能とな
り、変換ルールの記述と処理が簡単かつ明確となる。

【００１８】構文木を簡約化したことから解析結果にあ
いまいさが生じる場合があるが、これはあいまいさを持
ち得るノード型に対して、あいまいさの解消ルールを与
えることで解決する。

【００１９】また、構文木の変換ルールとして、変換対
象となっているプログラミング言語と同じ構文を用い、
プログラム変換装置全体も対象プログラミング言語を用
いて作成すると、プログラム変換装置を自分自身に適用
することが可能となり、オペレーティングシステムが異
なる機種のプログラムへの移植、拡張を容易に行うこと
ができる。

【００２０】

【実施例】以下、図を用いて本発明の一実施例について
説明する。

【００２１】図１は、本発明の一実施例を示すブロック
構成図であり、変換対象の入力プログラム１０２とその
変換ルール１０３の構文を、構文木を構成するノードに
型階層を用いた構文解析を行い、入力プログラム１０２
の構文木１０４および変換ルール１０３の構文木（以
下、構文木書換えルールという）１０５を作成する構文
解析装置１０１と、入力プログラム１０２の構文木を書
換えルール１０５の構文木で書換える構文木書き換え装
置１０６と、書き換えられた入力プログラムの構文木１
０７を変換されたプログラム１０９として出力する出力
装置１０８とを備えている。

【００２２】構文木書き換え装置１０６は、入力プログ
ラムの構文木１０４と構文木書き換えルール１０５の構
文木を比較し、書き換えルール１０５の構文木の各ノー
ドに当てはまるノードが入力プログラムの構文木１０４
にあるか否かを調べ、当てはまるノードは書換えルール
１０５の構文木で書換える操作を行うものである。

【００２３】本実施例では、変換対象とするプログラミ
ング言語としてＣ言語を選び、構文解析は、標準的なパ
ーザ生成装置（Ｌｅｘ，Ｙａｃｃ）等の名称で知られて
いる構文解析装置を使用できるので、実現が容易であ
る。

【００２４】しかし、Ｃ言語の構文は、文脈自由文法で
は解析しきれないことが知られており、解析結果である
構文木１０４には誤りのある可能性がある。しかし、こ
の誤りの出現箇所は限られており、Ｃ言語の場合は複文
の最初の部分において宣言文と実行文を解析し間違える
場合だけである。

【００２５】そこで、複文を示す構文木ノードの型に訂
正ルールを与えることで、この誤りを訂正する。訂正ル
ールは、このシステムのユーザが記述する変換ルールの
先頭に自動的に付加される。

【００２６】Ｃ言語に対する厳密な構文木を作成しよう
とすると、構文木のノードは１００種類程度必要になる
が、型階層を導入することで１０種類程度のノード型か
らなる構文木に簡約化できる。

【００２７】例えば、実行文は、通常の構文木では、ラ
ベル付き実行文、式、複文、条件文、繰り返し文、ジャ
ンプ文、代入式、論理式など３０以上の種類が必要とな
るが、この実施例では図２に示すような型階層を用いて
おり、ノードの種類は実行文２０１、複文２０２、制御
文２０３、条件文２０４、繰返し分２０５の５種類で済
んでいる。

【００２８】このうち制御文２０３は条件文２０１、繰
り返し文２０５の上位型となるノード型として導入した
もので、元の構文木にはなかったノード型である。

【００２９】通常の構文解析では、条件文、繰り返し文
の解析処理がキーワード（ｉｆ，ｗｈｉｌｅ，ｆｏｒな
ど）をチェックするので、新しい制御構造を定義すると
構文解析がエラーとなってしまう。

【００３０】これに対し、本実施例では、制御文２０３
という上位型で解析を止めているのでエラーとなること
はなく、新しい制御構造の定義が可能となる。

【００３１】図３に、構文木書換えのアルゴリズムを示
している。

【００３２】まず、構文解析装置１０１（Ｐａｒｓｅ）
を呼び、変換対象のプログラム１０２（Ｐ）の構文木１
０４（ＴＰ）を得る（ステップ３０１）。

【００３３】次に、構文木１０４（ＴＰ）から次に書き
換えるべき部分ＴＰ’を選択する（ステップ３０２）。
この選択は書換えの戦略に依存し、最内書換え、最外書
換えなど数種類の戦略が知られているが、採用する戦略
は大域変数「ｓｔｒａｔｅｇｙ」の値により切り換える
ことができる（デフォルトは最内書換えを採用してい
る）。

【００３４】書き換えるべき部分木がないときには、Ｔ
Ｐ’の値として「Ｆａｌｓｅ」が返るので、終了してＴ
Ｐを書換え結果の構文木として返す（ステップ３０３，
３１１）。

【００３５】そうでないときは、ＴＰ’に適用できるル
ールの集合を「ｇｅｔ＿ｒｕｌｅ」により取り出す（ス
テップ３０４）。「ｇｅｔ＿ｒｕｌｅ」は与えられた構
文木のルートノードの型によって適用可能ルール集合を
取り出す関数である。このルール集合の要素であるルー
ルは、（Ａ，Ｂ，Ｃ）の３組である。

【００３６】ただし、Ａは入力パターン指定、Ｂは中間
処理指定、Ｃは出力パターン指定である。

【００３７】Ａ，Ｂ，Ｃ共に、Ｃ言語の構文で記述する
が、構文中にパターン変数を用いることができ、このパ
ターン変数に関してマッチングとインスタンシエーショ
ンが行われる。

【００３８】Ａの構文解析結果の構文木ＴＡがＴＰ’と
マッチし、かつ中間処理Ｂが成功するようなルール（の
うち最初のもの）に対してルールの適用が行われる。Ｔ
Ｐ’に対するルールの集合を取り出す（ステップ３０
４）。もし、ルールの集合がＮＩＬならば（ステップ３
０５）、ステップ３０２に戻る。ルールの集合があった
場合、その先頭のルールを取り出し、ＴＡとＴＰ’のマ
ッチングからパターン変数の変数束縛「ｂｉｎｄ」を作
成する（ステップ３０６）。

【００３９】「ｂｉｎｄ」が「ｆａｌｓｅ」であれば
（ステップ３０７）、このルールは適用可能でないので
ステップ３０５に戻る。

【００４０】「ｂｉｎｄ」が「ｆａｌｓｅ」でなかった
時は、この変数束縛のもとで、中間処理指定Ｂを中間処
理評価装置「Ｅｖａｌ」により評価し、新しい変数束縛
「ｎｅｗ＿ｂｉｎｄ」を得る（ステップ３０８）。

【００４１】中間処理出失敗した場合は、「ｎｅｗ＿ｂ
ｉｎｄ」が「ｆａｌｓｅ」となるので（ステップ３０
９）、ステップ３０２に戻る。

【００４２】「ｎｅｗ＿ｂｉｎｄ」が「ｆａｌｓｅ」で
ない時は、「ｎｅｗ＿ｂｉｎｄ」により出力パターンＣ
の構文木ＴＣ内のパターン変数をインスタンシエイトし
たもものを構成し、ＴＰ内の部分木ＴＰ’をこれに置き
換える（ステップ３１０）。

【００４３】以上の処理を書換え可能な部分木ＴＰ’が
なくなるまで繰り返す。

【００４４】図４に、ルール記述の例を示す。パターン
変数は「？ｘ」のように先頭に「？」を付けて表す。ま
た、変数のあとに「＠」に続けてノード型を表す正規表
現を記述できる。

【００４５】例えば、「？ｘ＠ｓｔｍｔ＊」は「？ｘ」
が「ｓｔｍｔ型」（実行文を表すノード型）の項目の０
個以上の並びとマッチすることを表す。

【００４６】４１は不定長の引数をとる関数を定義する
例である。

【００４７】例えば、「ｆｏｏ（ａ，ｂ）」という関数
呼び出しは、最初のルールに従い、「ｂａｒ（ａ，
ｂ）」に、「ｆｏｏ（ａ，ｂ，ｃ）」という関数呼び出
しは両方のルールが適用され、「ｂａｒ（ａ，ｂａｒ
（ｂ，ｃ））」に書換えられる。

【００４８】４２はカーニハン・リッチの（古い）仕様
のＣの関数定義をＡＮＳＩＣ対応の（新しい）仕様に基
づいた関数定義に書換える例である。

【００４９】４１のルールを構文解析して構文木の書換
えルールと見做す仕方を図５および図６に示す。

【００５０】図５が最初のルール４１、図６が２番目の
ルール４２に対応する。

【００５１】図７に入力「ｆｏｏ（ａ，ｂ，ｃ）」に対
するシステムの動作を示す。入力６１は構文解析装置１
０１により構文解析され、構文木６３となる。システム
は指定された戦略に従い、この構文木あるいはその部分
木に適用可能なルールを捜す。

【００５２】この例では、図６の構文木５２１に「？ｘ
＝ａ」，「？ｙ＝ｂ」，「？ｚ＝ｃ」という変数束縛を
与えたものが構文木６３と一致するから図６のルール５
２０が適用され、構文木５２２にパターン変数に対する
上述の代入を行った構文木６４に書き換えられる。

【００５３】同様にして部分木６４の部分木６５と部分
木５１１に「？ｘ＝ｂ」，「？ｙ＝ｃ」という変数束縛
を与えたものが一致するから図５のルール５１０が適用
されて、図８の構文木６６に書き換えられる。

【００５４】このようにして書き換えられた構文木は、
出力処理装置１０８によりプログラム１０９として出力
される。

【００５５】図４のルール４２に対応する構文木の書換
えルールを示したのが図９である。

【００５６】ただし、簡単のためプロトタイプ宣言にあ
たる出力部は省略してある。

【００５７】ルール４２の入力パターン４３および出力
パターン４４はそれぞれ構文木７１，７３に解析され、
フィルタ部７２による特定のノードに対する処理を伴う
構文木の書換えルールと見做される。

【００５８】このルール４２の適用を示したのが図１０
である。

【００５９】書き換えるべきプログラム８１が与えられ
ると、プログラムの構文木が作成され、構文木７１と比
較され、パターン変数とのマッチが行われ、「？ｆｃｔ
＿ｔｙｐｅ」には「ｉｎｔ」８２，「？ｆｃｔ＿ｎａｍ
ｅ」には「ｆｏｏ」８３，「？ａｒｇｓ」には「（ｘ，
ｙ，ｚ）のリスト８４，「？ａｒｇ＿ｄｅｃｌｓ」には
「ｉｎｔ ｘ，ｙ；ｌｏｎｇ ｙ；」というリスト８５，
「？ｆｃｔ＿ｂｏｄｙ」には関数定義本体８６が対応づ
けられる。

【００６０】フィルタ部８７により「？ｒｅｓｕｌｔ＿
ｄｅｃｌ」の計算が行われ、出力用構文木中７２のパタ
ーン変数が対応する値８８〜８１１に置き換えられ、変
換されたプログラム１０９が結果として得られる。

【００６１】このように本実施例によれば、構文木に型
階層を導入したことにより、プログラム変換ルールの記
述と変換処理を簡明にすることができる。

【００６２】また、構文を拡張して新しい制御構造を導
入する目的にも用いることができる。

【００６３】また、プログラムの移植、拡張に用いるこ
とができるが、変換ルールの記述も変換対象のプログラ
ムと同じ構文で記述しているので、変換ルールに対する
処理自体にプログラム変換を用いることができ、拡張性
の高い形のシステムが実現できる。

【００６４】さらに、実施例で述べたＣ言語変換システ
ムの場合は、システムの実現もＣ言語により行われてい
るので、処理系自身に変換を適用してシステムを書き換
えることができ、特に移植性の高いシステムを構築する
ことができる。

【００６５】

【発明の効果】以上説明したように、本発明によれば、
複雑な構造のプログラムを、煩雑な記述のルールを用い
ることなく別のプログラムに変換することができる。

【００６６】特に、構文木に型階層を導入したことによ
り、プログラム変換ルールの記述と変換処理を簡明にす
ることができる。

【００６７】また、構文木の変換ルールとして、変換対
象となっているプログラミング言語と同じ構文を用い、
プログラム変換装置全体も対象プログラミング言語を用
いて作成すると、プログラム変換装置を自分自身に適用
することが可能となり、オペレーティングシステムが異
なる機種のプログラムへの移植、拡張を容易に行うこと
ができる。

【図面の簡単な説明】

【図１】本発明の一実施例を示すブロック構成図であ
る。

【図２】構文木のノードの型階層の例を示す説明図であ
る。

【図３】構文木の書き換え手順を示す流れ図である。

【図４】Ｃ言語に対する変換ルールの記述例を示す説明
図である。

【図５】図４のルール４１を構文解析して構文木の変換
とみる仕方を示す説明図である。

【図６】図４の続きを示す説明図である。

【図７】ルール５１０の適用例を示す説明図である。

【図８】図７の続きを示す説明図である。

【図９】ルール４２を構文解析して構文木の変換とみる
仕方を示す説明図である。

【図１０】ルール４２の適用例を示す説明図である。

【符号の説明】

１０１…構文解析装置、１０２…変換対象のプログラ
ム、１０３…変換ルール、１０４…構文木、１０５…構
文木書換えルール、１０６…構文木書き換え装置、１０
７…書き換えられた構文木、１０８…出力処理装置、１
０９…変換されたプログラム。

Claims (2)

【特許請求の範囲】
1. 【請求項１】 変換対象の入力プログラムとその変換ル
   ールの構文を、構文木を構成するノードに型階層を用い
   た構文解析を行い、入力プログラムの構文木および変換
   ルールの構文木を作成する構文解析手段と、 前記入力プログラムの構文木を前記変換ルールの構文木
   で書き換える構文木書き換え手段と、 書き換えられた入力プログラムの構文木を変換されたプ
   ログラムとして出力する出力手段とを備えるプログラム
   変換装置。
2. 【請求項２】 前記構文解析手段は、変換対象の入力プ
   ログラムの構文に一致した変換ルールの構文木を出力す
   ることを特徴とする請求項１記載のプログラム変換装
   置。