準LL（2）文法に対する解析表の構造と解析アルゴリズム

情報処理学会 被引用文献1件

書誌事項

タイトル別名
  • The Structure of the Parsing - Table and the Parsing Algorithm for Semi - LL (2) Grammars
  • 言語処理系

この論文をさがす

説明

下降型構文解析法として代表的な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倍弱かかるが これは解析表の工夫により同程度まで速くすることができる.

収録刊行物

被引用文献 (1)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ