Incremental Generation of LR(1) Parse Tables

本論文では,LR(1)クラスの文法に対してパージングテーブルをインクリメンタルに構成する手法について述べる.機械翻訳システムやコンパイラ等の言語処理システムを構築する場合,事前にターゲットとなる言語の文法を設計する必要がある.一般に,LR構文解析のようなテーブル駆動型の言語処理システムでは,文法の設計/修正の段階で,テーブルの生成,パージングテスト,文法の修正のサイクルを繰り返す必要があり,また,1つの文法の修正に対してもテーブル全体を構成し直さなければならないため,非常な時間的,空間的労力を要する.このような問題に対し,文脈自由文法に基づく文法を効率的に構築するために,LRパーサーをインクリメンタルに実行する手法が種々提案されている.しかし,従来の手法のほとんどは状態遷移表内のアイテムをすべて求め直す必要があるため,効率的な手法とは言えない.本論文では,LR(1)文法に対し,パージングテーブルをインクリメンタルに構成する手法を提案する.本手法により,少ない資源で効率的かつ迅速に文法を構築することが可能となる.また,本手法は,高速にパージングテーブルを再構成するため,文法の自動学習の一手法としても有効である.本稿では,まず,2.でLRパーサージェネレーションの概要を述べ,3.でLRパージングテーブルのインクリメンタルな構成手法を提案する.4.では種々の数の文法に対し,全体を構成し直す場合との速度の比較により本手法の有効性を示し,5.でまとめと今後の課題を述べる.

Incremental Generation of LR(1) Parse Tables

Bibliographic Information

Search this article

Description

Journal

Details 詳細情報について

Export

Report a problem