1 0 0 0 OA スライドウィンドウを考慮したレジスタ割り付け
超並列計算機CP-PACSの各ノードプロセッサは、多数の浮動小数点レジスタとそのレジスタ群に対するスライドウィンドウ機構を付加したRISCプロセッサを採用している。当研究室では、スライドウィンドウを付加したプロセッサをターゲットマシンとするコンパイラの研究を行っている。コンパイラにおける最適化の重要課題の一つにループの最適化がある。RISCプロセッサにおけるループの最適化には、ソフトウェア・パイプライニングが有効である。スライドウィンドウを用いると、スライド命令によってレジスタ番号が変化するため、ソフトウェア・パイプライニングにおける複数のステージにまたがるレジスタの干渉が回避でき、命令スケジューリングの自由度が増すという利点がある。しかし、レジスタ番号が変化することは、レジスタ割り付けに新たな制約条件を加えることになり、レジスタ割り付けを難しくすると考えられてきた。本稿では、スライドウィンドウを考慮していないレジスタ割り付けのアルゴリズムを比較的容易にスライドウィンドウを考慮したレジスタ割り付けアルゴリズムに拡張できることを述べ、そのアルゴリズムの評価を行う。
1 0 0 0 OA なかよしグループ問題と属性文法への応用
- 著者
- 山下 義行 佐々 政孝 中田 育男 Yoshiyuki Yamashita Masataka Sassa Ikuo Nakata 筑波大学電子情報工学系 筑波大学電子情報工学系 筑波大学電子情報工学系
- 雑誌
- コンピュータソフトウェア = Computer software (ISSN:02896540)
- 巻号頁・発行日
- vol.4, no.3, pp.212-224, 1987-07-15
「なかよしグループ問題」は,ある条件下での集合の彩色問題を一般化し,より親しみやすい表現に直したものである.この問題ではなかよしグループの子供達に最適な色のキャンディを配ることを考えるが,配色に関する制約条件,局所的な最適条件および大局的な最適条件が絡みあい,必ずしも簡単には解けない.そこで,なかよしグループの中からキーとなる子供達を見つけ出し,その子らについて彩色問題を解くだけで総ての子供達への配色が決まる,という一般的な解法を提案する.応用として,ECLR属性文法に基づくコンパイラ生成系Rieの属性スタック自動割り当てプログラムを作成し,PL/0,Pascalサブセットコンパイラについて最適な割り当てを行った.
1 0 0 0 OA 1パス型属性文法におけるバックパッチ処理の自動生成
コンパイラ生成系では文脈自由文法や属性文法に基づき構文解析器、意味解析器の自動生成を行う。その中でも特に、1パス型の属性文法が使用されることが多い。しかし1パス型の属性文法においては右依存的な属性評価は許されない。したがってこれに基づく生成系では右依存的な属性評価は使用できず、記述において右依存的な属性評価としたほうが素直な場合についても、コンパイラ作成者が右依存のない記述に修正しなければならなかった。このような処理系の制約による記述の変更を行なった場合、得られた記述は本来作成者が意図していたものとは別のものであるため、記述の読解性が低下してしまうという問題があった。本発表では、右依存的な属性評価に対してバックパッチと呼ばれる処理を自動生成することにより、記述を変更することなく右依存的な属性評価を行えるような方法を提案する。また、現在我々が開発中である属性評価器生成系EAGLEに実現を行い、その有効性について検討を行なった。
本研究は、属性文法に基づくコンパイラ生成系をフリーソフトウェアとして公開するものである。1.Rieは,1パス型属性文法に基づく生成系である.これは,GNU Bisonをベースに,C言語で実装してある.Rieについては,平成5年度に1.0.3版と1.0.4版,平成6年度に1.0.5版を公開したが,平成7年度は寄せられたコメントやバグ情報へ対応などを行い,GNU規約に基づいたフリーソフトウェアとして1.0.6版を公開した.これらは,fjのニュースグループおよび世界的なネットワークであるusenetのニュースグループcomp.compilersでアナウンスし,具体的にはfip.is.titech.ac.jp:/pub/Rieよりanonymous ftpで入手できるようにした.これに対し,海外からはGNU規約をゆるめられないか等の問合せがあったり,国内ではfjのニュースグループで取り上げられたりしている。また,Rieを用いたコンパイラ記述に関する解説を図書に掲載した.2.Junは,木の上の属性文法に基づく,コンパイラのバックエンド用の生成系である.これはCommon Lispで実装してある.Junは,属性の依存関係にサイクルがある場合も扱えることが特徴で,これにより最適化器の定式化が可能になった.Junについては,初期版に対し,入力記述の仕様を改訂し,継承属性と合成属性とを対称的に扱うよう生成される属性評価器の形を変更し,全面的な書き直しを行った.これをfj.lang.misc,fj.sources.dなどでアナウンスし,具体的にはftp.is.titech.ac.jp:/pub/Junよりanonymous ftpで入手できるようにした.3.RieとJun双方を用いた実用規模言語に対するコンパイラ作成を行った.具体的には言語Cのサブセットについて,フロントエンドをRieにより,最適化器,レジスタ割付け,コード生成器をJunにより記述することで,コンパイラ作成を行った.
1 0 0 0 演算子順位を利用した再帰的下向き構文解析器生成系の実現
コンパイラにおける構文解析法としては、LR構文解析、LL構文解析(再帰的下向き構文解析)、演算子順位構文解析の3つが代表的である。LL構文解析やLR構文解析では生成規則のみによって文法定義を行い、それに基づいて構文解析を行う。そこで、算術式のように演算に優先順位がある場合には優先順位の差を非終端記号の導入によって表現する。従って優先順位のレベルが増えると、再帰的下向き構文解析では再帰呼び出しのネストが深くなり効率が落ちるし、LR構文解析では単純な生成規則還元が多くなり効率が悪い。演算子順位構文解析は他の2つに比べて扱える言語クラスが小さいが、算術式に対しては生成規則とは別に各演算子の優先順位を宣言し、その情報とスタックを用いることにより非常に効率の良い構文解析を行うことが出来る。また、生成規則のみによる定義よりも演算子順位を使った定義の方が一般的に分かり易い。そこで、LR構文解析や再帰的下向き構文解析に演算子順位構文解析の手法を取り入れる方法が研究されている。LR構文解析の中での方法は良く知られており、構文解析器生成系yaccなどによって既に実用化されているが、再帰的下向き構文解析の中での方法はあまり報告されていない。本稿では、中田らによって提案された再帰的下向き構文解析に演算子順位構文解析を取り入れる方法を取り上げ、実用に際しての問題点を考慮し、構文解析器とその生成系の実現・評価について述べる。
1 0 0 0 再帰的下向き構文解析における演算子順位構文解析
- 著者
- 中田 育男 山下 義行
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.34, no.2, pp.239-245, 1993-02-15
- 被引用文献数
- 1
加算や乗算などの演算子を含んだ通常の式の形をしたものの文法は、生成規則だけによる定義より、演算子順位を使った定義のほうが一般には分かりやすく、構文解析の効率もよい。LR構文解析の中で演算子順位を利用した構文解析をする方法はよく知られているが、再帰的下向き構文解析の中での方法は、演算子の順位を示す数値を手続きの引数として渡す方法があるようであるが、あまり報告されていない。本論文では、後者の方法として、再帰的下向き構文解析法における再帰的手続きの呼び出しの引数として、文法のLL(1)性などを調べるのに使われるFollow集合の部分集合を使う方法を提案する。これは、引数として演算子の順位を示す数値を渡す方法より一般的である。また、この部分集合は、再矯的下向き構文解析法でエラー処理のためによく使われる集合に近いものであり、この方法を再帰的下向き構文解析に導入するのは容易である。