LR属性文法に基づいたインクリメンタルな属性評価

概要

論文の詳細を見る
一度解析したプログラムの変更に対して, 変更箇所から影響を受ける範囲のみの再解析を行うインクリメンタルな解析について研究が行われている. 構文解析に関しては, 従来からある構文解析法をもとにインクリメンタルな構文解析法が提案されてきており, また, 意味解析に関しては, 属性文法に基づいたインクリメンタルな属性評価法が提案されている. 近年のプログラミング言語は1パス型属性文法で記述できるものも多く, この属性評価は効率が良いため, それを対象にした構文・意味解析器生成系も作成されている. しかしながら, インクリメンタルな解析においては1パス型属性文法に基づいたものは提案されていない. また, 従来提案されたインクリメンタルな解析法ではエラーの存在に対してはほとんど考慮されていなかった. 本論文では, LR構文解析と同時に属性評価が可能なLR属性文法に基づいたインクリメンタルな属性評価法を提案する. まず, 最も簡単なアルゴリズムを述べ, 次に, 部分本の再利用によってエラー発生時の処理が行え, 再解析の効率を向上できるように拡張したアルゴリズムを述べる. これらに基づいて, 処理系を実現し, 解析時間の測定を行った. 前者の簡単なアルゴリズムの場合は, 最初の解析に比べ, 再解析時間がそれと同程度かかる場合が存在するが, 後者の拡張したアルゴリズムでは部分木の再利用により, かなり効率良く解析でき, 1回以上再解析をする場合は, インクリメンタルな方法の方が時間が短かくなることが分かった.
一般社団法人情報処理学会の論文
1996-12-15

LR属性文法に基づいたインクリメンタルな属性評価

スポンサーリンク

概要

著者

関連論文

スポンサーリンク