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型循環は生じなかった.

The attribute evaluator based on the Ordered attribute grammar class has the advantages of (1) the ability to determine and construct an evaluation device in polynomial time, (2) incremental attribute reevaluation can be performed using O(|Affected|), and (3) the ability to convert it into an Ordered attribute grammar with modifications that are easy to judge if it is judged as type 3 circulation, and has been applied to various systems作为实际目的的足够广泛的班级。这项研究的目的是阐明（3）中3型循环的各种特性。根据我们的预测，我们认为（3）中的转换是NP完美的。我们还预测，在与多个人一起编写属性语法规范时，删除更有可能变得复杂。所获得的研究结果如下：我们已经证明，“将属性语法转换为3型循环的属性语法为有序的属性语法是完美的。”我们已经证明，“没有2型循环的3型循环的属性语法”不一定会转换为有序的属性语法。对于可以转换为有序属性语法的类，我们证明该类匹配L级属性语法类。 L级属性语法类是一个完整的NP问题，并且由于可以通过多项式时间来判断有序的属性语法类，因此将转换为有序属性语法的能力（=确定3型循环的去除可能性的问题）是完美的。我们已经构建了一种用于去除3型循环的算法。该算法从属性依赖关系图IDP创建EDP以尝试删除3型循环时添加了一些技术。・我们设计了一个新的属性语法类OAG^*，其中包括有序的属性属性语法类，并包含在l-ordered属性属性属性Grammar类中。它的特征是很难产生3型循环，并且可以通过多项式时间来判断。我们考虑了图形gds，该图被叠加在所有相同的符号出现上，并且属性在所有顺序中都排序。・合成器是基于OAG^*的属性评估器。我们实现了发电机^<tm>的属性评估核，并使用具有3型循环的中型示例进行了实验，并获得了良好的结果。这个示例是由多个程序员开发的，具有282个非末端符号，598个生产规则和1338个属性。为了消除3型循环，实践了55个虚拟依赖。当处理OAG^*时，未发生3型循环。