計算モデルとしての属性文法の制限とその対処法

概要

論文の詳細を見る
属性文法は, プログラミング言語などの文脈自由言語の意味を記述するために提案された計算モデルである. これまで, コンパイラの記述や, その自動生成など, プログラムの静的な意味の記述に利用され, 研究が進められてきた. しかしその一方で, 属性文法は, インタプリタやデバッガなど, プログラムの動的な意味の記述には適さないとされてきた. 本研究の目的は, 属性文法がプログラムの動的な意味の記述に適さないことを確認し, その理由や対処方法を明らかにすることである. 本研究では, まず, 属性文法の記述力について, 計算論の立場から考察を行った. 具体的には, 意味規則が算術式で, 属性の依存関係が非循環の場合について考えた. この場合, 属性文法に入力が与えられた時に行われる計算を, 判定命令を使用しないNプログラムとして表現できることを示した. この結果から, 属性文法がチューリングマシンと等価な記述力を持つのは, その意味規則に部分帰納的関数が許されているためであり, 属性伝播という仕組みは, なんら貢献していないことを示した. 我々は, この属性伝播という仕組みに計算力が欠如している点が, 属性文法がプログラムの動的な意味の記述に適さない理由であると考えた. そして, その対処法として, 高階属性文法を用いることで, 属性文法の制限を補い, 動的な意味の記述を容易に行う方法を示した.
社団法人情報処理学会の論文
1999-02-15

計算モデルとしての属性文法の制限とその対処法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク