著者

佐々 政孝

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.2, no.3, pp.3_560-3_562, 1985-07-15 (Released:2018-11-05)

著者

伊藤陽 小濱 真樹 佐々 政孝

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.46, no.SIG14(PRO27), pp.30-42, 2005-10-15

---

SSA 形式(静的単一代入形式)は,φ 関数という仮想的な関数を用いることで,変数の定義を字面上1 カ所だけになるように表した中間表現である.しかし,SSA 形式を用いたプログラム中に現れるφ 関数が仮想的であることから,SSA 形式から直接目的コードを出すことはできない.そこで,目的コードを出す前段階として,φ 関数を消去して通常形式に戻すことが必要である.これをSSA 逆変換と呼ぶ.SSA 逆変換には主なアルゴリズムが2 つある.以前から用いられているBriggs らのアルゴリズム,およびこれとは異なるアプローチによるSreedhar らのアルゴリズムである.SSA 逆変換アルゴリズムはそれぞれ異なった特徴を持つが,これらを実際に比較した研究はほとんどなされていない.このため,SSA 形式を最適化コンパイラに採用するにあたって,どのSSA 逆変換を用いるかの選択の指標となるものがなかった.そこで本研究では,Briggs らとSreedhar らのアルゴリズムの長所と短所を明確にした.また,Briggs らのアルゴリズムに対する改良案を提案した.さらに,Briggsらのアルゴリズムとその改良案,Sreedhar らのアルゴリズムの3 つを実装し,同一のコンパイラ上で,SPEC ベンチマークを用いて種々の条件を変えながら比較した.本研究により,Briggs らの方法ではコアレッシングすることのできないコピー文が数多く挿入されること,実証的にはSreedharらの方法が最も優れていること,が判明した.

著者

中田 育男 佐々 政孝 Ikuo Nakata Masataka Sassa 筑波大学電子情報工学系 筑波大学電子情報工学系

雑誌

コンピュータソフトウェア = Computer software (ISSN:02896540)

巻号頁・発行日

vol.3, no.1, pp.47-56, 1986-01-14

---

正規表現で定義される構造をもった入力を意味処理まで含めて処理しなければならない場合は多い.そのような処理を形式的に取り扱う方法としては文脈自由文法に意味規則を付加した属性文法を使うものがあるが,それでは入力の構造との対応が必ずしもよくないし,処理方法も複雑である.本論文では,このような入力の構造と意味を自然に記述できる意味規則つき正規表現を提案し,その処理法について述べる,最初に,正規表現の中に意味規則を挿入した意味規則つき正規表現を定義し,次に,意味規則つき正規表現から意味処理つき非決定性有限オートマトン(NFA)への変換アルゴリズム,および,NFAから意味処理つき決定性有限オートマトン(DFA)への変換アルゴリズムを与える.最後に,意味規則つき正規表現を,正規表現で定義できる構造をもったデータを処理するプログラム,すなわちデータ構造直結型プログラムに応用するために必要な意味規則および変換アルゴリズムの拡張方法を述べる.

著者

佐々 政孝 石塚 治志 中田 育男

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.10, no.3, pp.3_212-3_228, 1993-05-19 (Released:2018-11-05)

---

1パス型属性文法に基づくコンパイラ生成系Rie(りえ)について述べる.LR構文解析と同時に解析木を作らずに属性評価ができる属性文法のクラスにLR属性文法というものがあるが,Rieはそれに同値類を導入したECLR属性文法というものに基づいている.Rieは属性文法によるコンパイラの記述から1パスのコンパイラを生成する.Rieにより種々の言語処理系が開発されている.生成されたコンパイラは,手書きのものに比べて1.8倍程度の時間で動き,形式的な記述から生成されたコンパイラとしてはかなり効率がよいことが確認された.

著者

佐々 政孝

雑誌

情報処理

巻号頁・発行日

vol.28, no.10, 1987-10-14

著者

中田 育男 渡邊 坦 佐々 政孝 森 公一郎 阿部 正佳

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.25, no.1, pp.1_2-1_18, 2008 (Released:2008-03-31)

---

COINSコンパイラ・インフラストラクチャは,コンパイラの研究・開発・教育を容易にする目的で開発したものである.COINSは(1)高水準中間表現と低水準中間表現の2水準の中間表現をもつ,(2)記述言語はJavaで,すべて新規開発した,(3) SSA最適化など最適化の機能が充実している,(4)リターゲッタブルなコード生成系をもつ,(5)並列化の機能を持つ,といった特徴をもっている.開発作業は10箇所以上で分散して行い,3週間に1回程度の全体打ち合わせを持ち進めた.途中いくつかの失敗もあったが,ほぼ当初の目標を達成できた.入力言語はCとFORTRANとして,対象機種はSPARC, x86など,全部で8機種のコンパイラが出来ている.Cコンパイラの目的コードの性能は,GCCのそれに匹敵するものが得られている.COINSシステムはJavaで約26万行の大きさである.本論文では,このインフラストラクチャについて,技術面と開発作業の観点から述べる.

著者

大島 芳樹 脇田 建 佐々 政孝

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.41, no.9, pp.62-77, 2000-11-15

参考文献数

16

---

高機能なSmalltalk処理系であるSqueakを携帯情報端末Zaurusに移植し,Zaurusの持つ独自のハードウェアにあわせて拡張を施したので,システムの実現方法,性能,可用性の評価について報告する.我々の行った実装作業は大きく2つに分類される.まず,基本的な機能の性能を向上させるために,Zaurus上でのイベント処理方式やビットマップ変換方式の性能について定量的評価を行い,それに基づいて最適化を行った.さらに,Zaurus独自の拡張を施すことによって,ペン入力,音声機能,デジタルカメラ,TCP/IPネットワーク,シリアル・IrDAポート,電力消費制御,およびフラッシュメモリファイルシステムのようなPDA独自のハードウェアをSqueakから操作可能とした.この移植および拡張はZaurus依存の部分を記述した4000行程度のC記述および600行ほどのSqueak記述によって達成された.我々は大小各種のベンチマークによる性能評価およびいくつかのアプリケーションによる可用性評価を行った.Zaurusシリーズの最上位機種であるMI-EX1上のSqueakは,400MHz G3 Macに対して最高1/8程度の性能を示した.このベンチマークの数字および実際の使用テストから,このシステムは十分実用に耐える性能を持つことが分かった.我々の実装によって,さまざまな周辺機器を操作できる実用的なプログラミング環境を手のひらサイズの機器上で運用できることが示された.This paper reports our effort to implement Squeak Smalltalk on a family of personal digital assistant ({エit PDAエ/}) devices called Zaurus. The Squeak on Zaurus ({エit Squeak/Zaurusエ/}) offers programmable interfaces to various Zaurus specific devices. The system is evaluated in terms of its usability and performance. Two important issues in implementation of Squeak/Zaurus are as follows. Firstly, we measured performance of several implementation strategies for event-handling and bitmap conversion, which are dominant performance issues, and adopted the best ones in Squeak/Zaurus. Secondly, we have extended Squeak to support PDA specific hardware such as pen input, audio, digital camera, TCP/IP network, serial and IrDA communication, power consumption control, and file I/O on flash memory. These PDA specific devices are made directly accessible to the programmer. Those Zaurus specific functions are written in 4,000 lines of C code and 600 lines of Squeak code. The performance of Squeak/Zaurus has been evaluated by various micro- and macro-benchmarks and its usability has been tested by applications. MI-EX1, the highest model of Zaurus family, marked 1/8 of the performance of Squeak running on 400エ,MHz G3 Mac at best. This result and the usability tests indicate that it performs sufficiently well for practical use. The Squeak/Zaurus implementation demonstrates feasibility of practical programming environment on palm size devices that can operate PDA specific hardware.

著者

新屋 良磨 光成 滋生 佐々 政孝

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.30, no.2, pp.2_191-2_206, 2013-04-25 (Released:2013-08-25)

---

正規表現によるパターンマッチングは広く用いられており,これまで様々なマッチング手法が研究されてきた.正規表現をDFAに変換してマッチングを行う手法もその1つである.本論文では2つの高速化手法を提案する.1つ目の手法は,マッチングの並列化である.マッチング対象となる文字列を複数に分割してデータ並列にマッチング可能な,同時状態有限オートマトン(Simultaneous Finite Automata, SFA)をオートマトン理論の自然な拡張によって定義した.2つ目は,DFA・SFAから,ネイティブコードを実行時に最適化して生成する手法である.コード生成によって,既存実装に比べてマッチング時のスループットの向上が見込め,また特定の正規表現における最適化も可能となる.最終的に,これらの手法を実装し,マルチコアマシン上での評価を基にその有用性を確認した.

著者

滝本 宗宏 佐々 政孝

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.25, no.1, pp.1_30-1_46, 2008 (Released:2008-03-31)

---

コンパイラでは,機械語の目的コードを生成するに際して,実行させたときにその目的コードが効率良く実行できるように,様々な変換を行う.これを「最適化」という.最適化の方法としては,従来はデータフロー解析と呼ばれる方法が使われていたが,最近は静的単一代入形式というものを用いた最適化の方法が注目を浴びている.静的単一代入形式(SSA形式)は,すべての変数の使用に対して,その値を定義(代入)している場所がテキスト上1箇所しかないように変数の名前替えをした中間表現の形式である.この性質を利用することにより,いろいろな最適化が見通し良く,容易にできるようになる.これを静的単一代入形式最適化と呼ぶ.本稿(発展編)では,静的単一代入形式最適化のあらましについて,解説する.

著者

山下 義行 佐々 政孝 中田 育男 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サブセットコンパイラについて最適な割り当てを行った.

著者

大島 芳樹 脇田 建 佐々 政孝

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.41, no.SIG09(PRO8), pp.62-77, 2000-11-15

---

高機能なSmalltalk処理系であるSqueakを携帯情報端末Zaurusに移植し,Zaurusの持つ独自のハードウェアにあわせて拡張を施したので,システムの実現方法,性能,可用性の評価について報告する.我々の行った実装作業は大きく2つに分類される.まず,基本的な機能の性能を向上させるために,Zaurus上でのイベント処理方式やビットマップ変換方式の性能について定量的評価を行い,それに基づいて最適化を行った.さらに,Zaurus独自の拡張を施すことによって,ペン入力,音声機能,デジタルカメラ,TCP/IPネットワーク,シリアル・IrDAポート,電力消費制御,およびフラッシュメモリファイルシステムのようなPDA独自のハードウェアをSqueakから操作可能とした.この移植および拡張はZaurus依存の部分を記述した4000行程度のC記述および600行ほどのSqueak記述によって達成された.我々は大小各種のベンチマークによる性能評価およびいくつかのアプリケーションによる可用性評価を行った.Zaurusシリーズの最上位機種であるMI-EX1上のSqueakは,400MHz G3 Macに対して最高1/8程度の性能を示した.このベンチマークの数字および実際の使用テストから,このシステムは十分実用に耐える性能を持つことが分かった.我々の実装によって,さまざまな周辺機器を操作できる実用的なプログラミング環境を手のひらサイズの機器上で運用できることが示された.

著者

太田 行紀 田淵 聡 脇田 建 佐々 政孝

雑誌

全国大会講演論文集

巻号頁・発行日

vol.46, pp.81-82, 1993-03-01

---

プログラム開発環境においてはデバッガの存在が欠かせない。しかし,それを始めから作成するためには多大な時間と労力を要する。本稿は,インタプリタの内部情報を利用することにより,インタプリタ型のデバッガ作成に要する労力を劇的に減少することができることを報告する。われわれは言語処理系を記述する統一的な枠組として属性文法を使ってきた。これまでに,さまざまなクラスの属性文法を用いることでコンパイラの構文解析,意味解析,最適化,コード生成の各フェイスが記述できることを確認したほか,インタプリタやグラフィカルユーザインタフェイスの生成にも利用できることが分かった。このインタプリタに対して,文を実行する前にフックをかけ,コルーチン的に協調動作するデバッガフロントエンドを呼び出すように変更することで,文字端末用のデバッガが実現できた。今回作成したPL/0言語のデバッガの記述に要するコードは従来のデバッガに比べ行数比でわずかに1/65にすぎない。さらに,すでにわれわれが開発した属性文法に基づくグラフィカルユーザインタフェイス(GUI)生成系を利用し,デバッガのGUIも作成した。これにより,xdbxとほぼ同等の機能を持ったものが実現できた。

著者

佐々 政孝 山下 義行 徳田 雄洋 脇田 建

出版者

東京工業大学

雑誌

試験研究(B)

巻号頁・発行日

1994

---

本研究は、属性文法に基づくコンパイラ生成系をフリーソフトウェアとして公開するものである。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により記述することで,コンパイラ作成を行った.

著者

伊藤陽 小濱 真樹 佐々 政孝

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.46, no.14, pp.30-42, 2005-10-15

被引用文献数

3

---

SSA 形式(静的単一代入形式)は,φ 関数という仮想的な関数を用いることで,変数の定義を字面上1 カ所だけになるように表した中間表現である.しかし,SSA 形式を用いたプログラム中に現れるφ 関数が仮想的であることから,SSA 形式から直接目的コードを出すことはできない.そこで,目的コードを出す前段階として,φ 関数を消去して通常形式に戻すことが必要である.これをSSA 逆変換と呼ぶ.SSA 逆変換には主なアルゴリズムが2 つある.以前から用いられているBriggs らのアルゴリズム,およびこれとは異なるアプローチによるSreedhar らのアルゴリズムである.SSA 逆変換アルゴリズムはそれぞれ異なった特徴を持つが,これらを実際に比較した研究はほとんどなされていない.このため,SSA 形式を最適化コンパイラに採用するにあたって,どのSSA 逆変換を用いるかの選択の指標となるものがなかった.そこで本研究では,Briggs らとSreedhar らのアルゴリズムの長所と短所を明確にした.また,Briggs らのアルゴリズムに対する改良案を提案した.さらに,Briggsらのアルゴリズムとその改良案,Sreedhar らのアルゴリズムの3 つを実装し,同一のコンパイラ上で,SPEC ベンチマークを用いて種々の条件を変えながら比較した.本研究により,Briggs らの方法ではコアレッシングすることのできないコピー文が数多く挿入されること,実証的にはSreedharらの方法が最も優れていること,が判明した.The SSA form (static single assignment form) is an intermediate representation where the definition of each variable appears only once in the program by using a hypothetical function called φ-function. However, since the φ-functions appearing in the program using the SSA form are non-executable, the target code cannot be directly generated from the SSA form. Therefore, it is necessary to delete the φ-function and put the SSA form back to the normal form before generating the target code. This conversion is called SSA reverse translation'. There are two major SSA reverse translation algorithms. One is the method by Briggs et al., which is used from relatively early times. The other is the method by Sreedhar et al., which is based on a completely different approach. So far, there has been almost no research that actually compares these SSA reverse translation algorithms, although each algorithm has different characteristic features. Therefore, there have been no criteria as to which SSA reverse translation algorithm should be selected when the SSA form is used in an optimizing compiler. In this paper, we clarify merits and weak points of algorithms by Briggs and Sreedhar. We also propose an improvement of the algorithm by Briggs. Then, we implement algorithms by Briggs and its improvement and the algorithm by Sreedhar on the same compiler, and compare the three by changing the various environments using the SPEC benchmarks. The experiment has shown that the method by Briggs inserts a lot of copy statements that cannot be coalesced. Empirically, the method by Sreedhar is the most efficient.

著者

板野 肯三 中田 育男 和田 耕一 井田 哲雄 佐々 政孝 田胡 和哉

出版者

筑波大学

雑誌

一般研究(B)

巻号頁・発行日

1988

---

高水準言語によるプログラミングを効果的に支援するためには、道具としての言語処理系がきめ細かくプログラミングの過程をサポ-トすることが不可欠であることは勿論であるが、言語処理系の処理速度も重要な要素である。一方、現在の半導体技術の著しい進歩は、非常に複雑なアルゴリズムを1つのチップとして実現することを可能にしており、LSI化するのに適したハ-ドウェアの設計が与えられれば、物理的な実現は原理的にはそれほど困難ではない。一般に、ハ-ドウェアで実現すれば、汎用の計算機ア-キテクチャ上で実行するのに比較して、100ー1000倍に実行速度を高めることが可能でありこともある。しかし、ソフトウェアのアルゴリズムを単にマイクロプログラム化するだけで、このような性能を達成することは難かしく、方式の見直し、場合によってはアルゴリズムそのものの見直しも必要である。本研究では、このような状況を踏まえて、言語処理系をLSIとして実現するための設計技術の確立を目標とした。とくに、インタプリタの高速化を前提にしたプログラミングシステムを実現するためのハ-ドウェア設計に重点をおき、今年度は、シリコンコンパイラが使用可能になったので、シリコンコンパイラによるLSIの設計を行った。具体的には、手続き型言語PLOの解析木インタプリタと論理型言語のインタブリタの2つのprojectを取り上げて、具体的な設計を通じて、いろいろな経験を蓄積し、実際に言語書理系に関連したLSIをつくるための基礎技術を模索した。LSIの内部では、並列性を採用する一方、制御やデ-タの流れの局所性を高めることが重要であり、また、できるかぎり系統的に設計できることが望ましい。このような前提で、アルゴリズムレべルのハ-ドウェアの設計から始め、フルカスタムのパタ-ン設計とシミュレ-タによる検証を行った。

著者

佐々 政孝 中田 育男

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:03875806)

巻号頁・発行日

vol.27, no.1, pp.124-127, 1986-01-15

被引用文献数

2

---

正規右辺文法とは, 生成規則の右辺に文法記号の正規表現を許すような文脈自由文法のことである. 本稿では, これに対するLRパーサを簡単に構成する方法を提案する. その基本は, 構文解析スタックと並行に, 生成規則の右辺から生成される記号の列の長さをカウントするためのスタックを設けるものである. この方法は, 構文解析の効率は最良ではないが, パーサの作成が簡単で, 通常のLRパーサに対する方法を若干精密化するだけですみ, 作成時に文法の変換やlookback状態等の計算が不要であるという特徴をもつ.

著者

太田 行紀 脇田 建 佐々 政孝

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告ソフトウェア工学(SE) (ISSN:09196072)

巻号頁・発行日

vol.1995, no.25, pp.185-192, 1995-03-09

---

コンパイラをテストする際、コンパイラのすべての機能をもれなくテストするようなソースプログラムを人手によって作成することは非常な労力を要する。このテストは,構文的にも意味的にも正しいプログラムが正しく処理されることを調べる正常系試験と、その一方または両方が誤っているプログラムに対して適切なエラーメッセージが出力されることを調べる異常系試験の2つに分けられる。本論文では、そのそれぞれに対して、属性文法によるコンパイラの形式的定義より自動的にソースプログラムを生成する方法を試みた.その際,属性文法の文脈条件を意図的に真または偽にすることによって,意味的に正しいまたは誤ったプログラムを生成できたことがオリジナルな点である.In testing a compiler, it is very hard to manually generate test programs that cover all functions of the compiler. The test consist of the normality test and the abnormality test. The former checks whether the compiler works for syntactically and semantically correct programs. The latter checks whether the compiler detects errors and gives proper error messages for programs including syntax or semantic errors. In this paper, we try to automatically generate test programs for each of the above cases from formal definition by attribute grammars. The originality of this research resides in that we can generate semantically correct/incorrect programs by making context condition true/false intentionally.