正規右辺文法の効率のよい LR パーサの簡単な実現法
スポンサーリンク
概要
- 論文の詳細を見る
正規右辺文法とは文脈自由文法の生成規則の右辺の記述に文法記号の正規表現を許したものである.正規右辺文法は LR 構文解析できるとき, ELR 文法であると言われる.文献6) では効率のいい ELR バーサを作成するアルゴリズムを提案したが, Lookback 状態の計算が必要であるので,アルゴリズムはやや複雑である.文献8) では ELR バーサを簡単に構成する方法を提案したが,構文解析の効率に多少問題がある.本稿では文献6) と文献8) の方法の利点を組み合わせて,効率のいい ELR バーサを簡単に構成する方法を提案する.その基本は次のようである.還元の際,その対象となる右辺を認識するために,非カーネル内の LR 項からの遷移に対しては,状態記号をパーサスタックにプッシュするが,カーネル内の LR 項からの遷移に対しては,状態記号をパーサスタックにプッシュしない.非カーネルとカーネルからの遷移がともにあったら(それをスタック競合と呼ぶ),状態記号をパーサスタックにプッシュするが,パーサスタックと並行にスタック競合の回数をカウントするためのスタックを設ける.この方法は,バーサの作成が簡単で,構文解析の効率がいい,作成時に文法の変換や Lookback 状態等の計算が不要であるという特徴をもつ.
- 一般社団法人情報処理学会の論文
- 1987-11-15
著者
関連論文
- 属性文法の複雑さ (<解説> 属性文法とその応用-IV)
- 拡張1パス型属性文法に基づくコンパイラ生成系の実現
- 組文脈自由文法に基づくプログラミング言語Grampとそのコンパイル技法
- CP-PACSのアーキテクチャの概要
- LR属性文法に基づいたインクリメンタルな属性評価
- インクリメンタルなLR構文解析の一方式の提案とその評価
- ウィンドウ・マネージャによるプログラム開発環境の統合
- 拡張1パス型属性文法によるコンパイラ生成系の実現
- 基本ソフトウェアの記述ツール(ソフトウェアツール 1 : 段計・記述)
- ストリームによるプログラミングのための言語とその実現方式
- ストリームによるプログラミングのための言語とその実現方式
- 非正準LR構文解析と拡張LR構文解析の提案
- 正規右辺文法の効率のよい LR パーサの簡単な実現法
- 1パス型属性文法に基づくコンパイラ生成系Rie
- 正規右辺属性文法と1パス再帰降下属性評価器の生成
- ストリーム・プログラミングのための図式表示を利用した開発支援環境について
- 3. 超並列計算機 CP-PACS のソフトウェア ( 計算物理学と超並列計算機 : CP-PACS計画)
- 正規右辺属性文法の一提案
- 時相属性文法によるグラフィカル・ユーザーインターフェースの記述
- 再帰的下向き構文解析における演算子順位構文解析
- 正規右辺文法の再帰降下パーサの効率のよい生成法
- 属性文法記述によるコンパイラ最適化器の生成
- 13. 動的記憶領域割付け法 (アルゴリズムの最近の動向)