準LL(2)文法に対する構文解析表の作成アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
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%程度であり,文法が大きくなるほどこの比率は小さくなるという一般的傾向があるので,あまり問題にはならない.
- 一般社団法人情報処理学会の論文
- 1990-06-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)文法の構文解析表の性質の応用について
- 確率モデルを用いた日本語形態素解析
- 文脈ベクトルを用いた語義の曖昧性解消
- 因果関係を用いたかな漢字変換アルゴリズム
- 企業が期待する情報科学教育 : カリキュラムのあり方を中心として
- チェック・ディジットによるエラー検出率の導出