第 1 章 序論

第
章
序論
近年，コンピュータのハード ウェアやネットワークの急激な進歩にともない，多くの
優れた機能を持ち，品質のよいソフトウェアの必要性はますます高まっている．ま
た，この進歩と同期するようにソフトウェアはますます複雑化し，巨大化してきて
いる．このような状況におけるソフトウェア開発は一般に空間的，時間的計算量が
大きくなり，ソフトウェアを効率よく生産するための諸技術への要求は急速に高まっ
ている．
この問題を解決するために，効率のよいソフトウェア構成法に関連する各種の研
究が活発に幅広く行われている．品質を低下させずに，複雑化，巨大化傾向にある
ソフトウェアを効率よく簡単に構成するための技術が研究されている．
従来のソフトウェア作成のためのアプローチは，以下に分類できる．
既存のコード を再利用するアプローチ
これは最も古典的であるが実用的なアプローチである．このアプローチに基づ
く方法では，既存のライブラリを用いてプログラムコード を書きソフトウェア
を作成する．これは，特定の専門家向きのソフトウェアの作成法である．また，
作成者自信がコード を作成するため，自由にプログラムすることができ，実行
効率のよいコード を作成することができる．しかし一般に保守は容易ではない．
ウィンド ウシステムの基本ライブラリ を利用してソフトウェアを作成
する場合やオブジェクト指向プログラミングにおいて既存のクラス定義を利用
してコード を書く場合などがこのアプローチである．利用したいライブラリが
存在しない場合には，はじめからすべてを作成しなければならない．
多くの汎用ツールを組み合わせるアプローチ
多種多様な汎用的なツールを用意し，ほとんどコード を書かずに，それらのツー
ルをソフトウェア作成者が組み合わせて，ソフトウェアを作成するアプローチ
である．ここで用意される各種のツールは，用途が限定されていない汎用のツー
ルである． 環境におけるシェルプログラミングなどはこのアプローチで
ある． や などの各種の基本的なツール群を組み合わせるだけで多くの
ソフトウェアが簡単に作成できる．
専用の統合環境を用いるアプローチ
ソフトウェアを作成するための各種の専用ツールを統一したインタフェースで
アクセスできる環境を用意し，その上でソフトウェアを作成するアプローチで
ある．このアプローチに基づく方法では，分野を限定したソフトウェアを対象
として，便利にソフトウェアを作成する環境を提供している．このアプローチ
に基づく統合環境の例としては， !" #"$， %&'( )* +,, な
どの特定のプログラミング言語によるプログラム作成支援環境がある．
ソフトウェア生成系を用いるアプローチ
作成するソフトウェアの分野を限定し，宣言的な記述または少ないコード から
ソフトウェアを作成するシステムを利用し，ソフトウェアを作成するアプロー
チである．対象とするソフトウェアをコンパイラに限定した代表的なコンパイ
ラ生成系に -&& や .， がある．また，それらの発展型と位置づけること
ができる，対象とするソフトウェアを内部に構造を持ったエディタに限定した
ソフトウェア生成系に構造エディタ生成系がある．代表的な構造エディタ生成
系には /-!($0 1!( や 234! がある．
特定の一種類のソフトウェアを効率的に作成するためには，専用の開発環境を用
いて作成することが実際的であるが，ソフトウェアファミリを生産する場合にはソ
フトウェア生成系を利用することが実際的である．ソフトウェアファミリとは，仕
様は異なるが インタフェースは同じであるようなソフトウェア群である．例えば，
構造エディタ生成系を用いて生成した言語 2 用の構造エディタ 42 と，言語 5 用の
構造エディタ 45 などが構造エディタのファミリを形成する．
ソフトウェア生成系は，抽象度の高い仕様記述から実現可能なプログラムコード
を生成するソフトウェアである．現在，多くの場面で用いられるソフトウェア生成
系のひとつにコンパイラ生成系がある．この生成系は抽象度の高いコンパイラの仕
様記述から容易にコンパイラを生成するための環境である．このように，文字の一
次元列であるテキスト情報を扱う分野においては，多くのソフトウェア生成系が研
究され，またそれに基づくシステムが利用されてきた．
しかし 近年，テキスト情報に加えて二次元平面上に配置された構成要素，すなわ
ちダ イアグラム情報を扱う必要性が急速に高まってきた．これは，ビットマップディ
スプレ イなど 表示装置の発展，価格の低下や，ウィンド ウシステムなど の基盤ソフ
トウェアの大きな発展が要因のひとつとなっている．これによってダ イアグラム情
報を用いた情報の共有が容易になった．さらに % に代表されるように，複雑なシ
ステムの記述には視覚化した表現が不可欠となってきている．これもダ イアグラム
情報を扱う要求が高まる要因のひとつである．
このようなソフトウェアが扱うダ イアグラム情報は，各部品が二次元もし くは三
次元以上の広がりをもって他の多くの部品と接続している．このような構造は，木
構造を対象とした従来のソフトウェア生成系の文法の表現能力では効率よく扱うの
が困難である．
文脈自由文法よりも高い表現能力を持った文法として，グラフ文法や超グラフ文
法が研究されている．これらの文法によってダ イアグラムの構造を形式的に定義で
きる．また，これらの文法を基底文法とする属性文法を用いるなど の手法で，ダ イ
アグラムの意味記述を行うシステムが研究されている 67 7 8．
しかし，これらのシステムではダ イアグラム情報を専用エディタによってトップ
ダウンに生成しており，すでに生成してあるダ イアグラム情報を文法によって構造
解析することができない．また，人間が頭の中でダ イアグラムの構造を思い描くと
き，必ずしもトップダウンに思い描くわけではないため，ダ イアグラムの構造をトッ
プダウンに展開する作業は，人間の直感に反している場合がある．ダ イアグラムを
扱うソフトウェアを生成するため，またソフトウェアを生成するための記述として
ダ イアグラムを用いるためには，ダ イアグラムの構造を機械的に解析する手段が不
可欠である．
本論文では，このような背景からダ イアグラム情報を扱うソフトウェア生成系の
ための構文解析法を作成することを目的としている．
ダ イアグラムの構造を表す文法は多くの研究で提案されており，文脈自由グラフ
文法 68，文脈自由超グラフ文法 6 7 8，もしくは文脈依存グラフ文法 6 8 で表さ
れている．これらのうち文脈自由グラフ文法は，文法記号にパラメータの付いた文
脈自由文法，すなわちパラメータ付き文脈自由文法とみなすことができる．パラメー
タ付き文脈自由文法では，終端記号によってダ イアグラムを構成する部品を表し，
パラメータによって部品同士の関係を表している．この構成部品を表す終端記号を
列挙してできた列から構造を，与えられたパラメータ付き文脈自由文法をもとに解
析するには，文脈自由文法に対する従来の構文解析法は不十分である．これはパラ
メータ付き文脈自由文法の言語クラスが，パラメータのない句構造文法の言語クラ
スと等しいためである．
これを解決する支援手段として，パラメータ付き文脈自由文法の部分クラスに対
して適用できる，パラメータ付き文脈自由文法を 属性文法に変換する方法が提案
された 68．この変換法を用いて与えられたパラメータ付き文脈自由文法を 属性
文法に変換し，基底文脈自由文法部分の構文解析と意味規則部分の属性評価を行う
ことで，ダ イアグラムの構文解析を行うことができる．
パラメータ付き文脈自由文法のパラメータの部分と文脈自由文法は一般に密接に
関係している．そのため変換した 属性文法に対して，構文解析と属性評価を同時
に行う方法，すなわち同時属性評価法を適用することで，その過程で得られる解析
評価結果を利用できれば，解析可能なパラメータ付き文脈自由文法のクラスが大き
くなる可能性がある．ただし，従来の構文解析法や同時属性評価法を用いるだけで
は次の
点が不十分である．
下降型構文解析と同時に属性評価を行う場合について，仮に解析によって解析
木を作ると考える．このとき，構文解析オートマトンのひとつの状態が，作ら
れる可能性ある部分解析木の複数の候補を表している．にも関わらず，従来の
同時属性評価法はオートマトンのひとつの状態における属性値の候補を，可能
性のある部分解析木の数よりも少ない数しか許していない．
ダ イアグラムの構成部品を列挙した列は，一般に無秩序に並んでいるため，こ
の列挙列の構文解析には列の順序情報が利用できない．
本論文では，これらの問題点を回避できる同時属性評価法と構文解析法を示す．
またこれらの方法を用いたダ イアグラムの構文解析法を示し，この方法の従来のダ
イアグラムの構文解析法に対する優位性を示す．
次章以降の本論文の構成は次のとおりである． 章では本論文で用いる概念や定義
を述べる．またダ イアグラムの構造を表す従来の文法を比較し，それらの一般形と
してパラメータ付き文脈自由文法を定義する． 属性文法に対する構文解析と属性
評価の同時実行法，すなわち同時属性評価法について， 章でこの方法の意義と代表
的な構文解析法との同時評価の際の問題点，既存の同時属性評価法とその特徴を述
べる． 章では我々の同時属性評価法について述べる．まず，準備のための簡単な同
時属性評価法を用いて，意味関数の合成とその正規式による属性値表記について述
べ，次いで正規式法と呼ぶ我々の同時属性評価法を説明する． 章では，順序情報が
利用できない終端記号列に対する構文解析について，まず従来の構文解析法の不十
分な点を述べる．そして入力列の上限付き個数情報の概念を述べ，非順序構文解析
法と呼ぶ我々の構文解析法を説明する． 章では，前章までで述べた同時属性評価法
と構文解析法に基づくダ イアグラムの構文解析法について述べ，ダ イアグラムの解
析例を示す．最後に 章で結論を述べる．