正規右辺文法の再帰降下パーサの効率のよい生成法
スポンサーリンク
概要
- 論文の詳細を見る
正規右辺文法は構文規則の右辺の記述に文法記号の正規表現を許した文脈自由文法である.正規表現を使用することにより,構文規則の記述がコンパクトになり,文法の再帰的な構造を繰り返し構造に書き換えることができる.それにより,記述の便利さと読解性がよくなるだけでなく,効率のよい再帰降下パーサを作ることができる.本論文は正規右辺文法に対する再帰降下パーサの効率のよい生成法を示す.この方法では,入力文法の構造に対応する文法木を作り,その文法木から直接に再帰降下パーサを生成する.パーサ生成の過程中,必要な時だけ,必要となるFIRST集合やFOLLOW集合しか計算しない.それを実現するために,文法木のノード間のFIRST/FOLLOW集合の計算上の依存関係を動的に解析する.また,同じ値を持つ集合は共通集合とされ,空間的,時間的な効率が上げられる.本方法で実現した再帰降下パーサ生成系は,入力される文法がELL(1)文法であるとき,確かに効率的である.本方法をPascalの文法に適用した結果,FIRST/FOLLOW集合計算にかかった時間が従来の方法と比べて4〜9倍ぐらい短くなった.
- 一般社団法人情報処理学会の論文
- 1989-02-15
著者
関連論文
- 属性文法の複雑さ (<解説> 属性文法とその応用-IV)
- 拡張1パス型属性文法に基づくコンパイラ生成系の実現
- 組文脈自由文法に基づくプログラミング言語Grampとそのコンパイル技法
- CP-PACSのアーキテクチャの概要
- LR属性文法に基づいたインクリメンタルな属性評価
- インクリメンタルなLR構文解析の一方式の提案とその評価
- 拡張1パス型属性文法によるコンパイラ生成系の実現
- 基本ソフトウェアの記述ツール(ソフトウェアツール 1 : 段計・記述)
- ストリームによるプログラミングのための言語とその実現方式
- ストリームによるプログラミングのための言語とその実現方式
- 非正準LR構文解析と拡張LR構文解析の提案
- 正規右辺文法の効率のよい LR パーサの簡単な実現法
- 1パス型属性文法に基づくコンパイラ生成系Rie
- 正規右辺属性文法と1パス再帰降下属性評価器の生成
- ストリーム・プログラミングのための図式表示を利用した開発支援環境について
- 3. 超並列計算機 CP-PACS のソフトウェア ( 計算物理学と超並列計算機 : CP-PACS計画)
- 正規右辺属性文法の一提案
- 時相属性文法によるグラフィカル・ユーザーインターフェースの記述
- 再帰的下向き構文解析における演算子順位構文解析
- 正規右辺文法の再帰降下パーサの効率のよい生成法