多次元文脈自由文法とそのLLおよびLR構文解析法

概要

論文の詳細を見る
我々の研究室では、データ構造指向型プログラミングを実現する計算モデルとして組分脈自由文法(CCFG)を提案している。CCFGは、複数の文脈自由文法を組み合せることで、終端記号列の組を生成するようにしたものである。その言語は組の集合であり、したがって、関係を表すプログラムだとも言える。そのプログラムの実行方式は、構文解析法の応用として考えられる。これまでも下向き構文解析、上向き構文解析に関する議論が行われていたが、CCFGの持つ能力の大きさから議論が複雑になりがちであった。そこで、CCFGの言語クラスを狭めた、構造がより簡単な文法として多次元文脈自由文法を定義する。それに基づいて構文解析法を考察することでプログラムとしての実行方式の議論がより簡単になると思われる。本稿では、多次元文脈自由文法の定義を示すとともに、それにおける下向き、並びに上向き構文解析法を、文脈自由文法のそれを自然に拡張して提案する。なお、紙面の都合上、正確な定義などは省略した。
一般社団法人情報処理学会の論文
1993-03-01