準LL(2)文法に対する解析表の構造と解析アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
下降型構文解析法として代表的なLL(k)文法解析法に関するいままでの研究のほとんどはLL(1)文法に対するものであった.そして,LR(1)解析法が実用的になるにつれて,LL(1)解析法はやや退潮の兆しを示したが,LL解析法固有の特長のゆえに,根強く利用されている.そしていままた,自然言語処理へのLL(1)解析法の応用という新しい局面が開かれようとしている.しかし,LL文法は表現能力の点でLR文法に劣る.LR文法の場合,LR(k)文法,k≧2の言語クラスはLR(1)文法の言語クラスと一致することはよく知られている.しかし,LL文法ではLL(k)文法とLL(k+1)文法の間では後者の文法に対する言語クラスのほうが前者のそれより大きい.そこで,LL文法のもついくつかの特長を継承しつつ,その言語クラスを高めるにはLL(k)文法,k≧2に対する解析法の研究が待たれる.とくに,実用という点を考えるときLL(2)文法に対する解析法の確立に対する期待は少なくない,しかるに,LL(1)文法はすべて強LL(1)文法であるがLL(k),k≧2に対して強のものと強でないものとが存在し,強でない文法に対しては文脈問題がからむため,解析表作成が複雑になる.k=2の場合についてのAho-Ullmanの方法も「解析表が大きい」,「解析表の作成法が複雑」,「解析表作成法がLL(1)文法の場合と全く異なる」といったいくつかの欠点をもっている.本論文では,LL(k)文法にわずかに制限を加えた準LL(k)文法を提案し,とくにk=2の場合について,解析表の作成が容易な解析表の構造とその解析表による解析法を提案するものである.提案する方法は従来の方法の欠点を解消し,かつ表の部分(解析表と生成規則表)の大きさはAho-Ullmanの方法の約1/120程度になった.解析時間は,Aho-Ullmanの方法の約2倍弱かかるが,これは解析表の工夫により同程度まで速くすることができる.
- 一般社団法人情報処理学会の論文
- 1990-09-15
著者
関連論文
- 要約文生成のための単語抽出方式
- 単語間ネットワークを利用した関連語の抽出
- 改良型bubble sortの性質について
- LL(2)文法から強LL(2)文法への書き換えアルゴリズムの正当性について
- LL(2)文法から強LL(2)文法への書き換えアルゴリズム
- プッシュダウンリストの先読みを利用したLL(2)文法の構文解析
- テーブルを使用したLL(2)文法から準LL(2)文法への書き換えアルゴリズム
- 準LL(2)文法に対する構文解析表の作成アルゴリズム
- 準LL(2)文法に対する構文解析高速化のための解析表の構造
- 準LL(2)文法に対する解析表の構造と解析アルゴリズム
- 準LL(2)文法に対する構文解析表の作成アルゴリズム
- 生成規則番号を用いたLL(1)解析テーブル作成のアルゴリズム
- LL(1) Parsingによる汎用コンパイラの試作 : コンパイラ自動生成に関する研究
- Syntax-Directed Compilerの作成
- BNNを用いた日本語文の係り受け解析
- 確率モデルを用いた日本語形態素解析 (第2報)
- 準LL(2)文法の構文解析表の性質の応用について
- 確率モデルを用いた日本語形態素解析
- 文脈ベクトルを用いた語義の曖昧性解消
- 因果関係を用いたかな漢字変換アルゴリズム
- 企業が期待する情報科学教育 : カリキュラムのあり方を中心として
- チェック・ディジットによるエラー検出率の導出