インクリメンタルなLR構文解析の一方式の提案とその評価
スポンサーリンク
概要
- 論文の詳細を見る
プログラムの開発時にプログラム全体から見てごくわずかの変更を行った場合にも,開発者はコンパイラにその全体を与えてコンパイルし直さなければならない.コンパイラが変更箇所を認識し,再コンパイルを変更箇所から影響を受ける範囲内だけで行うことができれば,再コンパイルにかかる時間を大幅に削減することができるはずである.このようなコンパイルのことをインクリメンタルなコンパイルという.コンパイラの処理の中でも特に構文解析の部分を対象としたインクリメンタルな構文解析についてはかなり以前から論じられてきている.解析木を用いた方法の一つに佐々のLR構文解析法がある.佐々のアルゴリズムは通常のLR構文解析法を拡張した非常にシンプルなものである.これは,変更箇所から影響を受ける部分は別に解析(部分)木を作り,ある条件(構文照合条件)が成り立った時に元の解析木の該当する部分木と置き換えることによりインクリメンタルな構文解析を終了するものである.ところで,解析木を作りながら解析を行う解析法では,変更を受けていないトークン列からなる多くの部分木は以前の解析と同様に構成される.そのような部分木を再利用することに着目した方法としてJaliliのアルゴリズムがある.こちらは,木を分割し,変更箇所の解析後,分割された木を合成していく方法である.JaliliのアルゴリズムはLR構文解析であるにもかかわらず,木の再利用は木全体から部分木へと見ていくトップダウンなアプローチである.本研究では,佐々の方法における冗長な点を改善するため,木の再利用を考える.LR構文解析の自然な拡張である佐々の方法を改善するので,木の再利用はボトムアップパーザで木を生成する動きにそったアプローチとなる.このことはJaliliのアプローチとは対照的になる.以降では,実際に佐々,Jalili,本研究の三つのアルゴリズムを実現し比較した結果を示す.
- 一般社団法人情報処理学会の論文
- 1995-03-15
著者
関連論文
- COINSを用いるためのコンパイラの自動生成の一方式
- 学生宿舎への認証・検疫ネットワークシステムの導入(セキュリティ(2),トラヒック,経路制御)
- 遠隔ネットワーク性能・機館診断システムの構想 (情報通信マネジメント)
- 1K-8 型推論機能を持つ意味解析器の生成系(仮想化と言語処理系,学生セッション,アーキテクチャ)
- 認証デバイスを用いたOSの起動・終了制御システムにおける起動時間の短縮(パラレル,インターネットと情報倫理教育,一般)
- 認証デバイスを用いたOSの安全な起動制御(セキュリティ,サービス管理,ビジネス管理,料金管理,及び一般)
- 3ZB-2 ケーパビリティに基づくアクセス制御のためのケーパビリティ管理機構(セキュリティ(3),学生セッション,セキュリティ)
- 3ZB-1 電子メールに対するケーパビリティに基づくアクセス制御の実装(セキュリティ(3),学生セッション,セキュリティ)
- 2Y-7 USBトークン認証を用いたOSの安全な起動制御(システム運用・管理,学生セッション,ネットワーク)
- 1Y-8 PC上で動作するスケーラブルなIPネットワーク実験システム(ネットワーク構築・管理技術,学生セッション,ネットワーク)
- 1P-8 仮想計算機のゲストOSにおけるファイルアクセスに対する高水準リンクの実現(仮想化技術(1),学生セッション,アーキテクチャ)
- 1P-7 協調型仮想計算機のための二重OSシェル(仮想化技術(1),学生セッション,アーキテクチャ)
- 1P-6 協調型仮想計算機におけるホスト呼び出し機構(仮想化技術(1),学生セッション,アーキテクチャ)
- 1P-2 モード遷移削減による仮想計算機の高速化(仮想化技術(1),学生セッション,アーキテクチャ)
- A-028 自己拡張可能な構文解析器生成系における構文解析手法の選択機能の実現(A分野:モデル・アルゴリズム・プログラミング)
- 1P-1 仮想計算機におけるデバイスエミュレーションの部分評価を用いた高速化(仮想化技術(1),学生セッション,アーキテクチャ)
- 仮想計算機におけるデバイスエミュレーションの特化による高速化(仮想化(3))
- L_001 柔軟な割り当て可能な超高性能VPNシステム開発のための性能測定実験(L分野:ネットワークコンピューティング)
- UPKI認証連携基盤を用いたWebアクセス制御
- 遠隔ネットワーク性能・機能診断システムの構想
- 認証デバイスを用いたOSの起動・終了制御
- 認証デバイスを用いたOSの起動・終了制御システムにおける起動時間の短縮(パラレル,インターネットと情報倫理教育,一般)
- 認証デバイスを用いたOSの起動・終了制御システムにおける起動時間の短縮(パラレル,インターネットと情報倫理教育,一般)
- 認証デバイスを用いたOSの安全な起動制御(セキュリティ,サービス管理,ビジネス管理,料金管理,及び一般)
- 超並列計算機用NCX言語処理系の試作
- データ並列言語NCXの分散メモリMIMD並列計算機用コンパイラ
- 条件分岐を考慮したソフトウェアパイプラインにおけるレジスタ割付け
- 6N-7 JVMをターゲットとするコード生成のための生成系用モジュール(数値計算とコンパイラ技術,学生セッション,アーキテクチャ)
- 機能拡張可能なコンパイラ生成系
- A_017 Rubyと拡張可能構文解析器生成系によるCOINSを用いたコンパイラの自動生成(A分野:モデル・アルゴリズム・プログラミング)
- コンパイラにおける意味解析器の自動生成
- 構文解析器生成系と構文エラー処理
- オブジェクト指向に基づいた構文解析器構成法の提案
- ループ並列化教育支援のための可視化
- COINSコンパイラ・インフラストラクチャの開発(ソフトウェア論文,最新コンパイラ技術とCOINSによる実践)
- 疎行列演算プログラムの並列化の一方法
- 構文エラーの自動リカバリシステムの評価
- 属性文法の複雑さ (<解説> 属性文法とその応用-IV)
- 拡張1パス型属性文法に基づくコンパイラ生成系の実現
- 属性値主導型 拡張LL(1)文法の提案
- CP-PACSのアーキテクチャの概要
- 2K-11 遺伝的アルゴリズムを用いた超並列計算機CP-PACSのレジスタ割付
- スライドレジスタ割付問題の厳密解法
- スライドウィンドウを考慮したレジスタ割付
- 条件分岐を含むループの最適なソフトウェア・パイプライニング
- レジスタ割付からみたスライドウインドウアーキテクチャの優位性について
- スライドウインドウを考慮したレジスタ割付
- 5L-2 条件分岐向けソフトウェアパイプラインスケジューラの実装
- 条件分岐を考慮したループ並列化の1手法
- 4L-7 コンパイラにおける記号表処理部の自動生成系
- 字句解析器生成系での最短一致法の提案
- 5C-2 コンパイラにおけるインタラクティブなエラー処理方法の提案
- 属性文法に基づいたインクリメンタルなPascal-Sコンパイラ
- LR属性文法に基づいたインクリメンタルな属性評価
- インクリメンタルなLR構文解析の一方式の提案とその評価
- インクリメンタルなLR構文解析の一方式の提案とその評価
- インクリメンタルなLR構文解析器におけるエラー処理方式の提案
- HIRの説明と簡単な言語のフロントエンド(21世紀のコンパイラ道しるべ・・COINSをベースにして,連載2)
- 概要(21世紀のコンパイラ道しるべ : COINSをベースにして)
- 拡張1パス型属性文法によるコンパイラ生成系の実現
- 拡張1パス型属性文法の提案
- 意味情報を利用したLL(1)構文解析の一手法
- 拡張LL(1)パーサ生成系の提案
- リターゲッタブルコード生成(最新コンパイラ技術とCOINSによる実践)
- 1パス型属性文法におけるバックパッチ処理の自動生成
- LIRの説明とバックエンドの概要説明(21世紀のコンパイラ道しるべ・・COINSをべースにして)
- LIR : COINSプロジェクトの低水準中間言語
- データ並列型言語NCXにおける通信コストと仮想プロセッサマッピング
- 東日本大震災時の筑波大学情報インフラにおける対応と課題
- スライドウィンドウを考慮したレジスタ割り付け
- バイトコード変換によるActionScriptプログラムのマルチスレッド化
- 1パス型属性文法に基づくコンパイラ生成系Rie
- ソフトウェアの科学
- 時相属性文法を用いたユーザインタフェース記述のX-Windowへの適用
- 演算子順位を利用した再帰的下向き構文解析器生成系の実現
- 分散型Webブラウザの通信機能と協調動画視聴アプリケーション
- 分散型Webブラウザの通信機能と協調動画視聴アプリケーション
- 3. 超並列計算機 CP-PACS のソフトウェア ( 計算物理学と超並列計算機 : CP-PACS計画)
- 正規右辺属性文法の一提案
- 時相属性文法によるグラフィカル・ユーザーインターフェースの記述
- 多次元文脈自由文法とそのLLおよびLR構文解析法
- 再帰的下向き構文解析における演算子順位構文解析
- 東日本大震災時の筑波大学情報インフラにおける対応と課題
- レイテンシの違いを利用したネットブート配信環境の局所的な切り替え手法(システム制御,インターネットと情報倫理教育,一般)
- レイテンシの違いを利用したネットブート配信環境の局所的な切り替え手法(システム制御,インターネットと情報倫理教育,一般)