抽象構文木を自動生成するパーサジェネレータの効率的な実装
スポンサーリンク
概要
- 論文の詳細を見る
抽象構文木はコンパイラにおける最適化や目的コード生成に使用される.抽象構文木の生成には,構文規則を表す具象構文とは別に抽象構文を利用する.抽象構文は抽象構文木の形式を決定する構文である.この構文は,プログラムの構造とユーザが用いる表現形式の対応関係を示す.この抽象構文を文法の構文規則内に記述し,抽象構文木を自動的に生成する手法を提案する.提案する手法は,構文規則に抽象構文としての情報を付加し木の生成に利用する.抽象構文木の生成には,一般的に解析木から変換する手法が用いられているが,本実装ではLALR構文解析の特徴を利用する.LALR構文解析では解析にトークンスタックを用いる.このとき,抽象構文に基づくノードを生成し,トークンスタックに保持することで動的に木を構成する.これにより,解析結果から木への変換を不要とし,かつ必要最小限のノードで木を構成する.構文解析中に抽象構文を読み取り,スタックの動的な処理で抽象構文木を決定する手法である.生成された木は抽象構文に従ったプログラム構造を持っており,中間表現やオブジェクトコード生成に利用できる.さらに提案手法に基づくパーサを作成し,抽象構文を利用した文法を用いて抽象構文木の生成を行う.提案する手法が,抽象構文木が最小限の情報によって効率的に生成できることを示す.
- 一般社団法人情報処理学会の論文
- 2009-01-27
著者
関連論文
- 信頼性を導入した構文エラー処理
- 抽象構文木を自動生成するパーサジェネレータの効率的な実装
- 動的閾値を用いた構文エラー処理
- A-027 信頼性を導入した構文エラー処理(A分野:モデル・アルゴリズム・プログラミング)
- ループ内条件分岐排除に関する新方式の提案と評価
- ループ内条件分岐排除に関する新方式の提案と評価
- 更新検知を用いて左再帰に対応するPackrat Parserの実装
- 同一入力位置で複数発生する左再帰へ対応したPackrat Parsingの設計と実装