著者

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

雑誌

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

巻号頁・発行日

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

---

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

著者

中田 育男

雑誌

情報処理

巻号頁・発行日

vol.21, no.5, 1980-05-15

著者

中田 育男

雑誌

情報処理

巻号頁・発行日

vol.53, no.8, pp.808-808, 2012-07-15

著者

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

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (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倍程度の時間で動き,形式的な記述から生成されたコンパイラとしてはかなり効率がよいことが確認された.

著者

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

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (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万行の大きさである.本論文では,このインフラストラクチャについて,技術面と開発作業の観点から述べる.

著者

添野 元秀 山下 義行 中田 育男

雑誌

全国大会講演論文集

巻号頁・発行日

vol.第52回, no.ソフトウェア, pp.13-14, 1996-03-06

---

超並列計算機CP-PACSの各ノードプロセッサは、多数の浮動小数点レジスタとそのレジスタ群に対するスライドウィンドウ機構を付加したRISCプロセッサを採用している。当研究室では、スライドウィンドウを付加したプロセッサをターゲットマシンとするコンパイラの研究を行っている。コンパイラにおける最適化の重要課題の一つにループの最適化がある。RISCプロセッサにおけるループの最適化には、ソフトウェア・パイプライニングが有効である。スライドウィンドウを用いると、スライド命令によってレジスタ番号が変化するため、ソフトウェア・パイプライニングにおける複数のステージにまたがるレジスタの干渉が回避でき、命令スケジューリングの自由度が増すという利点がある。しかし、レジスタ番号が変化することは、レジスタ割り付けに新たな制約条件を加えることになり、レジスタ割り付けを難しくすると考えられてきた。本稿では、スライドウィンドウを考慮していないレジスタ割り付けのアルゴリズムを比較的容易にスライドウィンドウを考慮したレジスタ割り付けアルゴリズムに拡張できることを述べ、そのアルゴリズムの評価を行う。

著者

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

著者

平見 知久 山下 義行 中田 育男

雑誌

全国大会講演論文集

巻号頁・発行日

vol.第52回, no.ソフトウェア, pp.7-8, 1996-03-06

---

コンパイラ生成系では文脈自由文法や属性文法に基づき構文解析器、意味解析器の自動生成を行う。その中でも特に、1パス型の属性文法が使用されることが多い。しかし1パス型の属性文法においては右依存的な属性評価は許されない。したがってこれに基づく生成系では右依存的な属性評価は使用できず、記述において右依存的な属性評価としたほうが素直な場合についても、コンパイラ作成者が右依存のない記述に修正しなければならなかった。このような処理系の制約による記述の変更を行なった場合、得られた記述は本来作成者が意図していたものとは別のものであるため、記述の読解性が低下してしまうという問題があった。本発表では、右依存的な属性評価に対してバックパッチと呼ばれる処理を自動生成することにより、記述を変更することなく右依存的な属性評価を行えるような方法を提案する。また、現在我々が開発中である属性評価器生成系EAGLEに実現を行い、その有効性について検討を行なった。

著者

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

出版者

筑波大学

雑誌

一般研究(B)

巻号頁・発行日

1988

---

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

著者

川口 さおり 山下 義行 中田 育男

雑誌

全国大会講演論文集

巻号頁・発行日

vol.52, pp.9-10, 1996-03-06

---

コンパイラにおける構文解析法としては、LR構文解析、LL構文解析(再帰的下向き構文解析)、演算子順位構文解析の3つが代表的である。LL構文解析やLR構文解析では生成規則のみによって文法定義を行い、それに基づいて構文解析を行う。そこで、算術式のように演算に優先順位がある場合には優先順位の差を非終端記号の導入によって表現する。従って優先順位のレベルが増えると、再帰的下向き構文解析では再帰呼び出しのネストが深くなり効率が落ちるし、LR構文解析では単純な生成規則還元が多くなり効率が悪い。演算子順位構文解析は他の2つに比べて扱える言語クラスが小さいが、算術式に対しては生成規則とは別に各演算子の優先順位を宣言し、その情報とスタックを用いることにより非常に効率の良い構文解析を行うことが出来る。また、生成規則のみによる定義よりも演算子順位を使った定義の方が一般的に分かり易い。そこで、LR構文解析や再帰的下向き構文解析に演算子順位構文解析の手法を取り入れる方法が研究されている。LR構文解析の中での方法は良く知られており、構文解析器生成系yaccなどによって既に実用化されているが、再帰的下向き構文解析の中での方法はあまり報告されていない。本稿では、中田らによって提案された再帰的下向き構文解析に演算子順位構文解析を取り入れる方法を取り上げ、実用に際しての問題点を考慮し、構文解析器とその生成系の実現・評価について述べる。

著者

中田 育男 渡邊 坦

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.47, no.5, pp.526-539, 2006-05-15

被引用文献数

2

著者

阿草 清滋 落水 浩一郎 片山 卓也 中田 育男 佐伯 元司 鯵坂 恒夫

出版者

名古屋大学

雑誌

重点領域研究

巻号頁・発行日

1997

---

阿草は、既存ソースプログラムを解析しその結果を蓄積するために、細粒度のリポジトリを開発した。CASEツール作成者は、このリポジトリを使うことにより、構文解析や依存解析などのモジュールを作成する手間を省くことができる。ソースプログラムの解析によりライブラリの典型的な利用パターンを発見した。片山は、要求仕様変更とプログラム変更の関係を代数束により形式化し、ソフトウェア発展関係の理論的基礎を与えた。ソフトウェアの段階的詳細化において各段階でプログラムテストを可能とする方式として、抽象実行に基づくソフトウェア構成法を開発した。また、オブジェクト指向開発法の形式化を試み、分析モデルの統合と分析モデルの検証法を与えた。落水は、近年のソフトウェア開発は、分散環境における共同作業であることに注目し、このような環境下でのソフトウェア開発支援のために、開発状況を保持する情報リポジトリを用いて漸進的に情報の矛盾や不確実さの解消を行うモデルを提案し、それに基づく支援環境を構築した。中田は、スライディングウィンドウを持つ計算機の命令レベルの並列化のために、ループのソフトウェアパイプライニングのレジスタ割付方式としてスパイラルグラフを提案した。また、コメントの処理などに必要とされる字句解析器の最短一致法を開発した。佐伯は、再利用プロセスの形式化をユースケースのパターン化とその構造変換規則として行った。分析パターンや設計パターンの構造をパターン化し、必要に応じてホットスポットを埋める手法を提案した。また、ソフトウェアアーキテクチャをカラーペトリネットで形式化し、非機能要求の検証を可能とした。

著者

中田 育男

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.21, no.5, pp.p574-582, 1980-05-15

著者

佐々 政孝 中田 育男

出版者

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

雑誌

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

巻号頁・発行日

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

被引用文献数

2

---

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

著者

中田 育男 山下 義行

出版者

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

雑誌

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

巻号頁・発行日

vol.34, no.2, pp.239-245, 1993-02-15

被引用文献数

1

---

加算や乗算などの演算子を含んだ通常の式の形をしたものの文法は、生成規則だけによる定義より、演算子順位を使った定義のほうが一般には分かりやすく、構文解析の効率もよい。LR構文解析の中で演算子順位を利用した構文解析をする方法はよく知られているが、再帰的下向き構文解析の中での方法は、演算子の順位を示す数値を手続きの引数として渡す方法があるようであるが、あまり報告されていない。本論文では、後者の方法として、再帰的下向き構文解析法における再帰的手続きの呼び出しの引数として、文法のLL(1)性などを調べるのに使われるFollow集合の部分集合を使う方法を提案する。これは、引数として演算子の順位を示す数値を渡す方法より一般的である。また、この部分集合は、再矯的下向き構文解析法でエラー処理のためによく使われる集合に近いものであり、この方法を再帰的下向き構文解析に導入するのは容易である。