準LL(2)文法に対する構文解析高速化のための解析表の構造

概要

論文の詳細を見る
筆者らは以前準LL(k)文法なるものを提案し,そのk=2の場合についての解析表作成アルゴリズム,ならびに解析アルゴリズムを示した.準LL(k)文法の文法クラスはLL(k)⊃準LL(k)⊃強LL(k)を満足するものであり,LL文法がもつ「解析法が下降型であるため見通しがよい」,「解析表が小さい」などの特徴をもつ.また,準LL(2)文法はLL(1)文法よりも大きい表現能力をもつ.AhoらはLL(k)文法に対する解析表作成アルゴリズムと解析アルゴリズムを提案しているが,表作成のアルゴリズムには多くの手続きと計算を必要とする.さらに,いくつかの文法に対して作成された解析表の大きさは筆者らの120〜400倍にもなる.ただし,構文解析の速さは筆者らよりも2倍程度高速である.本論文では吉田-竹内(1990)で提案した解析表の構造に工夫を加えることにより,構文解析の速さを従来の筆者らの方法の約2倍程度速くなり,Ahoらの方法と同程度にすることができた.この変更の結果,解析表は大きくなったが,それでもAho らのものに比べ,1/15〜1/30程度にとどまっている.
一般社団法人情報処理学会の論文
1992-02-15