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

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

書誌事項

タイトル別名
  • A Constructing Algorithm for Semi - LL (2) Grammar's Parsing - table
  • 構文解析

この論文をさがす

説明

LL(k) 文法の解析表作成に関する研究は そのほとんどが k=1 の場合に関するものである.k≧2に関する研究は全くといってよいほど行われていない.わずかに Aho らの研究があるにすぎない.その理由は k=1の場合は必ず強 LL(1)文法であるが k≧2の場合には 強でないものと強の種類の文法が存在するためである.強LL(k)文法に対してはLL(1)文法とほほ同じ方法で表作成の実現が可能であるが 強でないものに対しては文脈問題がからむので 全く異なる方法をとらなければならない.本論文では LL(k)文法にわずかに制限を加えた準LL(k)文法の k=2 の場合の表作成のアルゴリズムとその正当性を示すものである.準LL(k)文法にも強のものと強でないものとが存在するが その表作成のアルゴリズムは比較的平易である.具体例にもとづき そのアルゴリズムの性能についても実験した結果 表作成の時間は Aho らの方法の1/10程度で 表(解析表と生成規則表)の大きさは1/120?1/400程度ですむことがわかった.また 文法に依存しないコード部分は7%程度筆者らのほうが大きくなったが プログラム全体に占める割合はPASCAL-の場合で約29% ISOPSAL の場合で10%程度であり 文法が大きくなるほどこの比率は小さくなるという一般的傾向があるので あまり問題にはならない.

収録刊行物

被引用文献 (1)*注記

もっと見る

キーワード

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

問題の指摘

ページトップへ