制約指向型形式文法に対する構文解析法に関する研究

点击翻译按钮获取中文摘要

制約指向文法の構文解析法を考察するため、この種の文法で定義される言語のクラスを特徴付ける受理機のクラスとして、木記憶をもつ木オートマトン(TTA)を提案した.有限オートマトンの拡張として、木を入力とするオートマトンである有限状態木オートマトン(TA)やプッシュダウン木オートマトン(PDTA)が提案されている。これに対し、本研究で提案したTTAは、木を入力とし、記憶部に木(内部木と呼ぶ)をもち、ボトムアップに動作する.直観的に、TTAの内部木は、制約指向文法の素性構造に対応する.TAおよびε動作のないPDTAは、TTAの真の部分クラスとなる.本研究ではまず、TTAの受理する系列言語のクラスは帰納的可算言語のクラスと一致することを示した.次にTTAの部分クラスとしてStructure Coposing(SC-TTA)とBackward Deterministic SC-TTA(BD-TTA)を導入した.SC-TTAにおいては、入力木の各頂点における内部木が、そのすべての子頂点における内部木を部分木として含まなければならない.この条件は、制約指向文法において、「親の句の素性構造は部分句の素性構造を部分構造として包含しなければならない」ということに対応する.また、BD-TTAは、有限状態、内部木の根頂点のラベルから、適用された遷移規則が一意に定まるようなSC-TTAである.代表的な制約指向文法として、語彙機能文法(LFG)が知られている.本研究では、SC-TTAおよびBD-TTAの受理する系列言語のクラスが、それぞれ、LFGの部分クラスNC-LFGおよびDC-LFGの生成する言語のクラスと一致することを示した.また、DC-LFGの生成する言語は多項式時間認識可能であるので、BD-TTAの受理する系列言語も多項式時間認識可能であると結論される.