ソフトウェア自動合成シェルSOFTEX/S(2) : 文脈自由言語と多ソート項集合の同型写像

概要

論文の詳細を見る
従来、プログラム変換理論としてunfold/fold変換や再帰関数言語の変換など様々な提案がされているが、これら理論は主にプログラムの構文的正当性についてはほとんど調べられていない。この理由は、これら対象言語はS式などの比較的単純な構文を持ち、構文的正当性の保証は自明であることが多いからである。しかしながら、CやC++,COBOLなどをターゲット言語するプログラム変換理論を考えると、これら言語構文は複雑であるので、変換されたプログラムの構文的正統性(つまり、変換結果が文法に受理されること)を保証することは自明ではなくなる。これら言語構文は、通常、BNFなどを用いて文脈自由文法として記述される。従って、CやC++などを対象としたプログラム変換系を構築するためには、文脈自由言語変換系を形式化し、変換結果が構文的正当であることを保証する理論を与えることが重要となる。本稿では、CやC++,COBOLなどをターゲット言語とするプログラム変換系を構築するための理論として、文脈自由言語から多ソート項集合への写像ξを定義し、無曖昧文法に対して、構文的正当性(項集合上ではwell-formed terms)に関して同型であることを示す。写像ξの性質として、写像された多ソート指標の多相性と文法が曖昧である場合の問題について考察する。また、文法構造と書換え規則記述能力の関係について述べる。最後に、写像ξに基づいてSOFTEX/Sバーザ部とプリンタ部を作成したことを述べる。写像ξにより、文脈自由言語変換系は多ソート項書換え系によって形式化される。また、ξの同型性のために、互換な書換え規則によって得られる結果は常に構文的正当である(文法に受理される)ことが保証される。
1993-03-01

ソフトウェア自動合成シェルSOFTEX/S(2) : 文脈自由言語と多ソート項集合の同型写像

スポンサーリンク

概要

著者

関連論文

スポンサーリンク