l-Orodered属性文法の有用性の検証に関する研究

l-有序属性文法有效性验证研究

• 批准号: 08780248
• 负责人: 権藤 克彦
• 金额: $ 0.64万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-08780248/
• 关键词: 属性文法; NP完全; 3型循環; 依存グラフ; l-Ordered属性文法クラス; Ordered属性文法クラス; OAG^*属性文法クラス

Ordered属性文法クラスに基づく属性評価器は(1)判定・評価器構築が多項式時間でできる,(2)インクリメンタルな属性再評価をO(|Affected|)でできる,(3)3型循環と判定されても容易とされる修正でOrdered属性文法に変換できる,という利点を持ち,実用上十分に広いクラスとして様々なシステムに応用されてきた.本研究の目的は(3)の3型循環に関する種々の性質の解明である.予想では(3)の変換がNP完全であると考えた.また多人数で属性文法仕様を記述する場合に除去が複雑になりやすいと予想した.研究成果として以下の結果を得た.・ 「3型循環をもつ属性文法をOrdered属性文法に変換する問題はNP完全である」ことを証明した.「2型循環を持たず,3型循環を持つ属性文法」を必ずしもOrdered属性文法に変換できないことを反例を示して証明した.Ordered属性文法に変換できるクラスについては,そのクラスがl-Ordered属性文法クラスと一致することを証明した.l-Ordered属性文法クラスの判定問題はNP完全問題であり,Ordered属性文法クラスは多項式時間で判定可能なので,Ordered属性文法に変換できる(=3型循環の除去可能性を判定する問題)はNP完全であることになる.・ 3型循環の除去アルゴリズムを構築した.このアルゴリズムは,属性依存グラフIDPからEDPを作成する際に付加される技の一部を反転して3型循環の除去を試みるということを全ての組合せに対して行う.・ Ordered属性文法クラスを含み,l-Ordered属性文法クラスに含まれる,新しい属性文法クラスOAG^*を考案した.3型循環を生じにくく,かつ,多項式時間で判定できるという特徴を持つ.属性依存グラフDPを全ての同一記号生起について重ねたグラフGDSを考慮して,属性を全順序化する.・ OAG^*に基づく属性評価器をThe Synthesizer Generator^<TM>の属性評価カーネルに実装し,3型循環を持つ中規模の例題を用いて実験し,良い結果を得た.この例題を複数プログラマが開発したシステムであり,規模は非終端記号数282,生成規則数598,属性数1338である.3型循環を取り除くために,人手で架空の依存を55本張られていた.OAG^*を用いて処理した所,3型循環は生じなかった.

Ordered attribute syntax: base attribute evaluator: (1) decision: evaluator construction: polynomial time: (2) attribute reevaluation: O(|Affected| (3) Type 3 loop decision is easy to modify, Ordered attribute syntax is easy to change, middle point is easy to maintain, and the upper ten points are used. The purpose of this study is to clarify the properties of the species related to the type 3 cycle (3). I want to change my mind (3). The number of attributes in the grammar is not enough. The results of the study are as follows: "Type 3 loop: attribute syntax: Ordered attribute syntax: change problem: NP complete problem": proof. "Type 2 loop is supported, type 3 loop is supported by attribute syntax" must be included in the Ordered attribute syntax change, and the counterexample is shown.Ordered attribute syntax change, and the decision problem of l-Ordered attribute syntax is NP complete problem, and the decision problem of Ordered attribute syntax is polynomial time. Ordered attribute syntax change (=3 type loop and removal possibility decision problem) NP complete Type 3 cycle is constructed by removing the ring from the ring. The attribute dependency is the attribute dependency of the IDP, the EDP, the EDP, the E Ordered attribute syntax <$<$$>$>Attribute dependency DP is fully generated from the same token, and attributes are fully sequenced.·OAG^* Basic attribute evaluator The Synthesizer Generator^<TM>attribute evaluator is installed, and the 3-type loop is used to maintain a medium-sized example. The number of non-terminal symbols is 282, the number of attributes is 1338, and the number of type 3 loops is 55.OAG^* is used to process the type 3 loops.