103
プロトタイプデータベースPDB 1の
データ処理システムの設計と開発
斉 藤 邦 彦
1． はじめに 情報化社会の進行とコンピュータの普及にともない，データベースシステム が様々な場面で利用され，また新しい概念のデータベースシステムの研究開発 ホも進んでいる。またISOを中心に関係型データベースシステムのデータベース 言語SQLを国際的な標準データベース言語として制定する動きもある。 データベースシステムはハードウェア的なファイルアクセス制御システムか らユーザインターフェースシステムまで複雑多岐な構成をしている。本研究で はデータベースシステムの基本的な枠組みを理解することを目的としてプロト タイプデータベースを設計，作成した。 様々なレベルでのデータベースシステムの働きとデータの流れを全体的に把 握するためにシステムを4個のモデュールに分け設計した。また関係型データ ベースの概念に基づいて，このデータベースシステムをプロトタイプデータ ベースシステムPDB 1として設計した。 PDB 1のデータ問合わせ言語はデータ ベース言語SQLライタに設計してある。 データベースシステムPDB lは4つのモデュールに分けて設計されているが， 本稿ではその一部であるデータ操作処理システム（モデュール）とそれに付随す る問い合わせ言語（データ操作言語一DML）の設計および作成について報告する。 このデータ操作システムは，問合せ言語により記述されたプログラムの構文を ＊ ISO（lnternationai Organization for Standardization：国際標準化機構）104 彦根論叢（第257号） 処理し，それに従ってデータベースの検索や更新などのデータ処理を実行する。 ここでPDB 1のデータ操作システムは基本的なデータ処理を行う部分，特に データ検索システムを実現している。本稿ではこのデータ検索システムの部分 の設計・開発に関して報告する。 このデータ問い合わせ言語の構文処理システムはUNIXのプログラム開発 ツールであるlex， yaccを利用して作成した。システム全体はC言語を使用し てSUN 3／60上で作成を行った。構文処理部の自動生成を行うことでシステ ムの段階的な開発・機能豊富化を可能にすることも目的としている。 H．データベースシステムの構造と基本的概念 データベースシステム，特に関係型データベースシステムは，IBMのシステ ムRをはじめ同社のSQL／DS， DB 2など多くのシステムが開発されている。 データベースシステムは，データベースとDBMS（データベース管理システム） の2つに分けて考えることができる。データベースは磁気ディスクや磁気テー プ等にファイルとして物理的に格納されたデータのことであり，DBMSはそれ らのデータをデータベース利用者が容易に利用できるように，物理的記憶装置 上のファイルアクセスを管理したり，末端ユーザの問合せに応じてデータを提 供するシステムである。 ①データベースシステムPDB 1の基本的構造 データベースシステムPDB 1の基本的な構造について説明する。ここでデー タベースシステムを3階層に分割し，上からユーザインターフェースモデュー ル，データ定義・操作システムモデュール，ファイルアクセス制御モデュール とする。そしてデータ定義・操作システムモデュールを2っに分けてデータ定 義システムモデ＝一ルとデータ操作システムモデュールとしデータベースシス テムを全体で4つのモデュールに分割する。システムの各階層のデータの定義 を，上から外部スキーマ，概念スキーマ，物理スキーマと表現する。（図1参考）
プロトタイプデータベースPDB1のデータ処理システムの設計と開発 105 ユーザーの問合せ t“ ユーザーインターフェースモデュール ロ コロロコ ロ ロ コロ ロ ロロ コ コロ コ コココ ロヒ ロ ロロロ ロロの ロサロココ ロ ココサ ロロロロコロコ デ一丁定義モデュール iデータ操作モデュール ■ ファイル処理モデュール 外部スキーマ 概念スキーマ 内部スキーマ
n
データベースファイル（磁気ディスク等） 図1 簡単にそれぞれの機能を説明する。ユーザーインターフェースモデュールは データベース利用者のデータ問合せに応じて，DBMSとユーザー間のデータ入 出力を制御する。ファイル処理モデュールはOSを通じて外部記憶装置に直接 的にアクセスしデータをDBMSに送る働きをする。データ定義・操作モデュー ルは全体のデータの流れを制御するDBMSのコアとなる部分であり，データ ベースの定義や，データの検索および削除，挿入，更新などといったデータ処 理をおこなう。 またデータ処理命令に対応するデータベース言語もデータ定義言語（DDL） とデータ操作言語（DML）の2っに分割して，それぞれデータ定義モデュール， データ操作モデュールに対応させる。 本稿ではDML言語（データ操作モデュール）に関する設計，開発について報 告する。ここでデータベースシステム全体を■デュール化することによりデー タベースシステムのトップダウン的な設計，開発が容易になり，またUNIXの プログラム開発ツールであるlex， yaccを利用してデータベース言語の構文処 理部およびデータ処理部の自動生成を実現しているので，仕様変更によるデー タベースシステムの段階的な機能豊富化も容易になっている。 現在このデータベースシステムPDBlはデータ処理の基本的動作を支援して いる。またインデックス付きのデータ検索やデータ検索の最適化を実現するシ ステムをPDB 2として作成中である。 次にデータベースシステム，関係型データベースについて説明する。106 彦根論叢（第257号） ②データベースシステムについて データベースシステムでは一般にファイルという概念でデータベースを表現 している。（正確にはファイルの集合をデータベースとする）この場合ファイルとは レコードの集合である。レコードはデータ処理の基本単位であり，またレコー ド自身もいくつかのフィールド（データ項目）に分けることができる。このファ イル，レコード，データ項目等の用語はCOBOLで使用されている用語とほぼ 同じものである。 またデータベースシステムはデータの物理的格納構造によって，ネットワー
ク型，階層型の2っに分けられる。前者にはCODASYLのDBTGグループの
提案に基づき開発されたシステムIDMが有名であり，後者ではIBMのIMSが 有名である。 そして関係型データベースというデータモデルがIBMサンホセ研究所のE． F．CODDによって考え出され，現在のデータベースシステムの主流となってい る。このモデルは以前のデータベースシステムに比べて多くの長所を備えてい る。例えば物理的格納構造から独立したデータモデルを採用することによって データベースシステムの操作性，アプリケーション開発の簡便性を向上させて いることなどを特徴としてあげることができる。 本研究では以上の点をふまえ，現在多くのデータベース業務で使われるよう になった関係型データベースの方法を採用する。 ③関係型データベースシステム まず関係型データベースの特徴として次の2っをあげる。 1 データベースを表として扱う。（関係型データモデル） 2 関係操作能力がある。（関係代数） 条件1を満たすことが関係型データベースと呼ばれるための基本的な条件で ある。 条件2を完全に支援するシステム関係型データベースシステムの理想的な形 である。しかし現状では多くのシステムは条件2を完全に支援するまでにはプロトタイプデータベースPDB1のデータ処理システムの設計と開発 107 至っていない。 またここで表は「正規化」されているものとする（第一正規形）正規化され た表とは各フィールドに配列等の多重実現値を持たない表のことである。 次にキー概念について説明する。国表はそれぞれキーと呼ばれる指標を持つ。 これはインデックス（索引）とも呼ばれる。キーとなるデータ項目（属性）を指 定することによって高速かつ一意にレコードが検索できる。またある表でこの 働きをするキーを主キー呼び，また表の中の主キー以外のデータ項目で主キー の働きをしうるものを代替キーと呼ぶ。 なおこのキーの動作は物理的レベルでの実現が保証されなければならないが， その方法として例えばISAM （索引つき順アクセス）ファイルを利用する方法が ある。本システムでは索引付き順ファイルアクセスの方法を，B−TREEのア ルゴリズムを利用しC言語を用いて作成中である。（ファイル処理モデュール部） ④関係型データモデル 関係型データモデルは関係型データベースシステムの基礎となる考え方であ る。関係型データモデルはデータ構造を（論理的な）表によって表現する。これ は，階層型やネットワーク型データベースがデータの物理的な格納構造と密接 に関係していたことと比べ対照的であり，内部構造に考慮をはかることなく データベースシステムの設計が可能になるという長所を持つ。またこの表概念 は，集合論の関係概念に対応している。 関係学データベースでは，旧来のデータベースシステムではファイルとして 扱われたもの（データベース）を表としてあらわす。ここで表の横の並び（行） を組，縦の並び（列）を属性，そして表自身を関係と呼ぶ。表は属性の集まり として定義され，次の様に表現される。 関係名（属性名，属性名，……属性名） この定義は関係スキーマとも呼ばれる。またデータ定義に対し実際に入る値 を実現値と呼ぶ。例えばファイル定義，レコード定義，フィールド定義に対し てファイル実現値，レコード実現値，フィールド実現値，が対応する。
！08 彦根論叢（第257号） またひとつの表における組の個数を基数，属性の個数を次数と呼ぶ。次に簡 単な表の例をあげる。 名簿 コ コ ぼ 青木 11912DlG田U コ コ ほ 伊藤 12012D lGIHU 大橋 ilgi2BiAITI 後藤 ：19：2君lGmU r ， 1 図2 この表の定義は名流（名前，年令，クラス，出身）である。そしてこの表の関係 名は名玉であり，属性名はそれぞれ左から名前（NAME）＿年令（AGE），組 （CLASS），出身（ADRESS）である。 また4っの属性の実現値を持つ表とし，次数，基数はともに4である。属性 NAMEのデータ型は文字型で桁数は4（バイト）である。これからはレコード を次の様に表現する。 一青木，19，2 D，GIHU一（ここで”，”は各データ項目の区切り記号とする） また表の各属性に対する定義や，表自身のファイルの定義をどこかに記憶さ せておく必要がある。 これらのデータ （定義）はデータベースに対するデータ ベース，すなわちメタデータベースと呼ばれ，他のデータベースと同じく一つ 以上のファイルに記述される。 データベースシステムではこれをDD／D（データディクショナリ・ディレクト リ）と呼ぶ。DD／Dは属性のデータ型やサイズ，あるいはファイルの作成更 新年月日や所有権などの情報を保持している。 PDB lではシステム起動時にDD／Dを主記憶上に常駐させ常に参照ができ るように設計している。 ⑤関係代数について 関係型データベースシステムの表に対する基本的なデータ操作に対応する関 係演算子とし選択，投射，接合（自然接合）の3っをあげる。これは集合論の関 係演算子である和演算，差演算，共通部分演算，直積，射影，選択，商演算，
プロトタイプデータベースPDB1のデータ処理システムの設計と開発 109 接合（自然接合）の中に含まれている。 ある関係問合せ言語が関係的に完備であることを示すには，その言語がこの うちの和演算，差演算，直積，選択，射影の5つをプリミティブな演算子とし の て含まなければならないことが条件であると示されている。本システムでは データベース処理の基本的な操作を支援するという意味で上記の3っを基本演 算子としている。 基本演算子 （1）選択（Selection）与えられた関係から水平方向の部分集合を抜き出す 操作σF（R）。すなわち表から行の部分集合を抜き出す操作である。ここでFは 以下の定義で与えられる論理式である。 （a）オペランド （b）算術比較演算子〈，〉，＝，〈〉，〈＝，〉＝ （c）論理演算子 （AND） （OR） σF（R）は関係のそれぞれの組の中で論理式Fにあらわれるオペランド（属性 名）を対応する要素で置き換えたときに論理式Fが真になるものの集合である。 例 「名薄表のなかから’GIHU’に住む20歳未満の学生を求めよ。」 と言う検 索の問合せはσNAME；GIHU〈AGE〈20（名薄）の様に記述される。 （2） 射影（Prolection） 与えられた関係から垂直方向の部分集合を抜き出 す操作πA 1，A2，…， Ai（R）。すなわち表から列の部分集合を抜き出す操作 である。ここでAI， A2，…， Aiは属性名の並び， Rは関係であり，演算に よって関係Rの各組の属性名Al， A2，…， Aiに対応する要素をこの順番に 並べた集合を返す。 例 「名前と年齢を取り出せ」という検索の問合せはπNAME， AGE（名薄）と 記述できる。 （3） 自然接合 （Natural J・in）表と表を結合する操作。接合演算の特殊な 1） J．Ullman，”Princple of DATABASE inc．， 1982， p．213 SYSTEM”， Computer Science Press．
110 彦根論叢（第257号） 場合でR・Sと記すことにする。R・Sを求める方法は，まずR×S（直積）を
計算し次にR，S双方に共通に用いられる属性Aに対してR中の列AとS中
の列に関し値の一致する組だけを選ぶ。最後に重複する列を選択により1つに まとめる。 その他の演算子 （4）和（UNION）関係Rと関係Sの各組を加えたものから重複を取り除 いたものの集合RUS。同じ項数を持つ関係に適用される。（5）差（DIFFERENCE）関係Rと関係Sの差演算はR中に存在してS中に
存在しない組の集合R−S。これもまた，RとSの項数は同じであるとする。（6）直積（CARTESIAN PRODUCT）RとSがそれぞれ項数rと項数sの
関係であるとする。ここできRとSの直積は（r＋s）一組の集合であり，最初 のr個の成分はR中の組から，残りのs個はS中の組から取られる。R×S（7）共通部分（INTERSECTION）関係Rと関係Sの共通部分を取り出す
演算R∩S。これはR一（R−S）と代替表現できる。 （8）商（QUOTIENT）RとSをそれぞれ項数r， sを持つ関係とする。 r−sの部分の組tを考える。そしてSの中のそれぞれの組uに対し組tuがR中
に在るという条件を満たす組tの集合と考える。R％S 例 R：a，b， c， d S：a， b R％S：c， d 皿． データ操作言語（DML）の仕様 データ問い合わせ文（言語）は親言語方式と独立式の2つに分けられる。親言 語方式ではCOBOL等の応用プログラムの中にデータ問合わせ文が組み込まれ て利用される。 また独立式の問合わせ言語はその言語処理方式によりコンパイラ風のデータ 問合わせ言語とインタプリタ風の言語に分けられ，それぞれSQL（strucutured Query Language）， QBE（Query By Example）カs有名である。本システムでは SQL風のデータベース言語を設計した。プロトタイプデータベースPDBIのデータ処理システムの設計と開発 111 データ操作言語の働きはデータ検索と，データ挿入，更新，削除の2っに分 けて考えることができる。そして今回はデータ検索部の実現について考える。 現段階では言語の仕様はデータ検索に関する部分の記述にとどめる。次に
データ操作言語（これからは言語Qと呼ぶ）の構文の仕様を拡張BN記法
（EBNF）で記述する。言語QのEBNFによる仕様記述
問い合わせ文；関係 1 関係 ｛関係演算子 関係｝、 集合演算子＝”∩” 1”一”i”∪”1”％”i”×”． 関 係＝関係名 1 関係，関係 選択射影文． 選択射影；”SELECT”属性名｛”，”属性名｝”FROM” 関係 ”COND”条件文． （以下は条件部の仕様記述） 条 件 文＝条件式 ｛論理演算子条件式｝．条 件 式一式比較演算子式。
式 一項｛算術演算二項｝．
項 一変数 1 定数． 論理演算子＝”AND”1”OR”． 算術演算子＝”＋”1”一’H”＊”1”／”。 比較演算子＝”＝”1”＃”1”〈”1”〉”げ＝〈””＝〉”， 変 数＝名前． 定 数一文字列 1数． 文 字 列＝”’”（文字1数字） ｛（文字1数字）｝”’” 名 前＝文字 ｛（文字1数字）｝． 数 ＝［（十ト）］ （Ol［1−9］｛数字｝）。文字＝（a−zlA−Z）．
数字＝（0−9）．
次に射影，投射，接合の各演算子がどのように構文的に実現されているかを112 彦根論叢（第257号） 示す。 （1）選択文σF（R）：
SELECT FROM 関係 COND 条件文
ここでFは論理式 （条件文），Rは関係である。また論理式に当たる条件文 はオペランドとして定数や文字定数 さらに演算式も許されるものとする。こ の場合の演算式の演算記号は四則演算，および剰余演算である。 （2）射影文πA1， A 2，…Ai（R）： PROJECT 属性名リスト FROM 関係 ここでA1， A 2，…Aiは属性名のりスト。 Rは関係とする。 （3）自然接合R，S ： 関係，関係 R，Sはそれぞれ関係とする。 ここで応用プログラム作成を簡約にするために，射影文と選択文を結合して 以下の様に表現する。 π（σ（R））二SELECT属性リスト FROM 関係 COND 条件文
ここで関係は，それぞれの基本演算子の演算が返す結果か，あるいは単なる 関係名，すなわち1つの表である。また射影文や選択文のネストも可能である。 yacc， lexの入力の形に直した言語仕様を最後に載せる。 yacc入力記法にお ける細かい規則の説明は省く。アクション部には基本演算子に対応する実際の データ処理をおこなう関数（C言語により実現）を記述してある。 IV．データ処理システムの実現 データ処理実行部の作成の第一ステップとして基本演算子に対応するデータ 処理システムを実現する。本稿ではこのデータ処理システムの検索機能の実現 について報告する。次のステップとして実行処理速度の向上（インデックス付きプロトタイプデータベースPDB1のデータ処理システムの設計と開発 113 の検索，データ処理演算の最適化），機能の豊富化（SQL言語のUNIQUE， ORDERD BY等の機能の実現）を実現するシステムを作成中である。 システムの作成 データ処理の基本的な演算である選択，射影，接合の各演算の実現について 考える。ここでデータベースは論理的には表，物理的にはファイルのそれぞれ の集合として扱う。また各演算によるデータ処理はレコード単位（組単位）で実 行される。 このデータ検索システムにおいて，3っの基本演算子はそれぞれデータベー ス （1個以上のファイル）を入力として演算を行い，結果を出力ファイルとして 返す。演算が高々1回の場合の出力先は物理的記憶装置上のファイルシステム である。連続していくつもの演算が実行される場合はバッファに出力し，それ をまた次の演算の入力として次々と演算を行う。これはUNIXのパイプ処理風 の処理である。 またデータベース（ファイル群）はデータ定義言語により定義され，データ定 義システムによって作成されるが，現在はデータファイルは（データ定義システ ムの仕様に従い）手作りで作成している。 また可変長フィールドや共用フィールドは現在考えない。空値の出現もない ものとする。 また複数の表（ファイル）を処理する演算は自然接合だけである。この演算は 実際に処理を行う時に．ディスクアクセス等のオーバーヘッドが大きく，場合に よっては処理時間が非常に大きくなるので最適化を考える必要がある。現在は この最適化は行っていない。 次にデータベース管理システムにおける全体的なデータの流れについて考え る。応用プログラム（DML文で記述されているとする）はDBMSに読み込まれ解 釈される。そしてDBMSはそれに従ってデータベースにデータを要求し演算を 2） J．Ullman，”Princple of DATABASE SYSTEM”， Computer Science Press． inc．， 1982， p． 338 一 343
114 彦根論叢（第257号） 行い結果を出力する。（下図） 命令 応用プログラム → （1） デーータペース 管理システム システムバッファ
ll［圃
（2》↑ 入力 データベース データ処理部のデータの流れ 入力 出力 データベースファイル → デー・処理・・テ・一［二野 コマンド（標準入力） → 図3 次に基本演算によるデータ処理システムの実現について説明する。 選択文構文 ：FROM 関係名 COND 条件文
（処理1）選択文が読み込まれるとその中の条件文が翻訳され特定のデータ構 造に変換される。そのデータ構造をC言語の構造体で記述してみる。 typedef struct ltst｛ ltype
量nt ＊symb head tsymb ； ＊皿ext 1正8t 豊ne翼t ； ＊ta五1 struct 蔀tai置 ； ｝ List ； 図4 なおここでltypeは， LIST型かATOM型の二つのデータ型に対応する。 リスト型のデータ構造表現では，HST型がリストに， ATOM型が（リストの要 ltype ： union ｛ S臓bo艮 stru￠t ｝ head ： listプロトタイプデータベースPDB1のデータ処理システムの設計と開発 115 素である）記号＝シンボルに対応する。 またheadには1typeの値に対応して記号；シンボル（記号表へのポインタ： ＊Symbol型一構造体で定義）かリスト （そのリストへのポインタ：＊list型一構造体 で定義）がくる。 ここでこのデータ構造を理解しやすくするためにこれからLISPのデータ表 現であるS式を使用する。S式とは括弧で閉じられたデータ構造で，演算子が 要素の最初に来る。（演算子前置方式）また上記の構造体により定義されたデータ 構造はS式に簡単に変換できる。 （処理2）この条件部のリスト構造型データはデータ処理システムに送られる。 データ処理システムは （データベースからの）入力レコードをこの条件部を参照 して処理する。この動作をLISPのS式の評価系（Evalator）風に考え，簡単に 図示してみる。 （処藤野冷［構文処理系］一条刑部・・式風・デー・構造・ （処理2） データ処理システム 入力データ → r一一一…・一一1 → 出カデータ ロ ぼ 1条件部1 コ （レコード単位） L一一…一一’ 図5 次に簡単なデータ処理の例をあげる。
FROM 名前表 COND 住所 ＝ ’GIHU’AND
年令く 20 S式による条件部の中間表現 （AND （EQ ＊住所＊ ’GIHU’）（LT ＊年令＊20）） ｛＊で囲まれた名前は変数を表わすものとする｝ レコード（組）が入力されると，上記の条件部のデータ構造（s式）の変数部 （属性名を＊で囲んだもの）が，対応する入力レコード（組）のフィールド（属性）116 彦根論叢（第257号） の実現値に置き換えられて具体的な値を持つ。次にデータ処理システムにより 条件式が評価され演算が実行される。条件式を評価した結果は真（T）か偽（F） である。これはレコード（組）が与えられた条件式Fを満たしているか，つま り”選択”されるかどうかの結果に対応する。 名薄表の最初のレコード（組）についてこの働きを例示してみよう。ここで LISPの評価系風に演算過程を記述する。 レコードー青木，19，2 D，GIHU一に対して （AND （EQ ’GIFU’ ’GIHU’） （LT 19 20）） ． （AND T （LT 19
20））→ （ANDTT）→Tとなりこの組は選択される。（Tは真）
射影文 与えられたデータ問合わせ文に従がってレコード（組）単位に対応するデー タ項目（属性）を取り出し，指定の通りの順番に並べ替えて出力レコードとする という作業が繰り返される。なお選択文と射影文は一括して記述されるので物 理的なデータ処理も一括して行なう。 自然接合文 与えられた文に従がって2っの表を接合する。物理的には2っのファイルを 読み込みDD／Dを参照して接合を行い1っのファイルを返す。 2つの関係（表）の接合のアルゴリズムについて述べる。DD／Dを調べ各表 に共通の属性をn三見つける。もし共通部分がなければ両者の直積を取る。 次に1回目のファイルの各レコード（r一組）を読み込んで主記憶バッファに 常駐させる。2番目のファイルの各レコード（s一組）に対して共通する属性の 部分のn個の成分が等しいかどうか調べる。等しかった場合はその二つのレ コードを繋げて新しいレコード（（r＋s−n）一組）として返す。（ここでレコード で属性の成分の重複は除去される）また等しくないものは捨てる。以上の手続 きを最初のファイルの各レコードについて繰り返す。プロトタイプデータベースPDBIのデータ処理システムの設計と開発 117 V． ま と め 以上，データベースシステムのプロトタイプPDB lの設計，作成について報 告した。PDB 1システムは4っのモデ＝一ルに分かれており，現在は基本的な データ処理部分のみが実現されている。このデータ操作処理部はまだ多くの点 で改善の余地が残されている。今後は段階的に機能を豊富化していくとともに， データ処理演算の最適化を行うことによりデータ処理速度を実働に耐えうるよ うにしたい。（現在は処理速度に問題があり処理速度のテストは行っていない） また残りのシステムモデュール，特にデータ定義システムを設計，作成する ことを今後の課題としたい。 付録参考文献とソースリスト （ 1 ） J．Ullamn：Princple of DATABASE SYSTEM， Computer Science Press． inc． 1982（邦題データベースシステムの原理，日本コンピュータ協会，1985） （2） C．J． Date：An lntroduction To Database Systems 3 rd Editon， Wesly Publi− shing Company，1981（邦題データベースシステム概論丸善，1984） （3）穂鷹良介1データベース入門，オーム社，1978 （4）味村重臣他：データベースシステムの設計と開発，オーム社，1984 （5） James． Martin： COMPUTER DATA−BASE ORGANIZATION 2 nd Editon， prenstic−hall． inc．1977（邦題データベース，日本コンピュータ協会，1983） （6）原田勝也：データベース構築の理論と実際，コロナ社，1985 （7）戸内1順一：データベースへの招待，技術評論社，1985 （8）Tsicbritzis他：Data base managenent System， Academic Press． inc．，1977 （邦題データベース管理システム，日本コンピュータ協会，1979） （9）A．T．シュライナー他：Cコンパイラ設計yacc， lexの応用，啓学出版，1988 （10）B． Kerninghan他：UNIXプログラミング環境，アスキー出版局，1985 （11）小川唯史編；日本語UNIFY入門，新紀元社，1987 （12） C Tree Programer’s Guide 4 th Editoin， FairCom， 1987 （13） B Tree ISAM Release version 2．5， Softfocus， 1987
118 彦根論叢（第257号） ソースリスト
ファイル1：SPECI．YAC
％｛ ＃inelude 一list．h’x︸ XunSon ｛Symbol ＊sym ； List ＊lst ；1 Xtoken 〈syva＞ STRING NUMBER （言語仕様のYACCの入力部分1） 四AME Xtype 〈lst＞ eonst var relopr 瓢type ＜lst＞ term expr cndexpr cndst殿t Xleft 〈sym＞ OR XIeft 〈sym＞ AND XIeft （sym＞ GT GE tT tE EQ NE ％塾eft 〈sy鵬〉 ’十”一〇 瓢left 〈sy覇〉 ’蓉”／”鷺’ 器 list ： 1 list cnd＄tmt ’Yn’ ｛return （（int）＄2） ：｝ ； ￠ndstmt ： cndexpr 1 cndstmt AND cndstmt ｛List ＊a ＝ ＄1 ， tb ＝ ＄3 ： if （＄1一＞tail） a ＝ list（＄1，LIST） ； if （＄3一＞tail） b ＝ list（＄3，LIST） ： ＄＄ ＝ eval〈1ist（＄2，ATOM），a， b） t endstmt OR endst”t ｛List ＊a ＝ ＄1 ， “b ＝ ＄3 ； if （＄1一＞tail） a ＝ list（＄LLIST＞ ； if （＄3一＞tail） b ＝ list（＄3，LIST） ； ＄＄ ＝ eval（list〈＄2，ATOM），a，b） endexpr ： expr relopr expr ｛List ＊a ＝ ＄1 ， ＊b ＝ ＄3 ； if （＄1一＞tail） a ＝ list（＄1，LIST） ； if （＄3一‘＞tail） b ＝ list（＄3，LIST） ； ＄＄ ＝ eval〈＄2，a， b） ； ｝： expr ： term j expr ’＋’ expr ｛List ＊a ＝ ＄1 ， ＊b ＝ ＄3 ； if （＄1一’＞tail） a ＝ list（＄LLIST） ； if （＄3一＞tail） b ＝ list（＄3，LIST） ； ＄＄ 一一“ eval（list（＄2，ATOM），a， b） I e翼pr ’一’ expr ｛List 專a 冨 ＄1 ， 毒b ＝ ＄3 ； if （＄1一＞tail） a ＝ list（＄1，LIST） ： if （＄3一＞tail） b ＝ tist（＄3， LfST） ； ＄＄ ＝ eval（1ist（＄2，ATOM），a，b＞ 聾 ，， ；｝； ︸ ﹁， ︸ ・，term relopr var const プロトタイプデータベースPDB1のデータ処理システムの設計と開発 1 expr ’零’ 1 expr ’／’ l expr ●瓢’ ； ：var leonst ； lEQ ＄＄詔 NE ｛＄＄ ＝ GT ｛＄＄ ＝ GE ｛＄＄ ＝ LT ｛＄＄ ＝ LE ｛＄＄ ！ ； ： NAME I ”一鱒 阿AME ； ： NUMBER l ”一“ 1 STRING ； 器 ＃deflne ALLFRE（a， b， c） List expr expr expr ｛List
ff＄Lff＄Lff＄
ii＄一ii＄︷ii＄
＊a ＝ ＄1 ， ＊b ＝ ＄3 ； 〈＄1一＞tail） a ＝ list（＄LLIST） ； 〈＄3一＞tail） b ＝ list（＄3，LIST） ： 孝a ＝ ＄1 ， 暮b ＝ ＄3 ； （＄1一＞tail） a ＝ list（＄1，LIST） ； （＄3一＞tail＞ b ＝ list（＄3，LIST） ； ■a 冨 ＄1 ， 奪b ＝ ＄3 （＄1一＞tail） a ＝ list（＄1，LIST） （＄3一＞tai1） b ＝ list（＄3， LIST） eval〈list（＄Z，ATOM），a， b） ；｝ eval（list （＄2， ATOM）， a， b＞ ｛List ＊a ＝ ＄1， ＊b ＝ ＄3 ； ： ； eval（list（＄2，ATOM），a，b） list（＄LATOM） ； 1ist（＄1，ATOM） ： 1ist（＄1，ATOM） ： list（＄1，ATOM） ； 1ist（＄1，ATOM） ； list（＄1，ATOM） ： ｛＄＄ ＝ list（＄1，ATOM） ；1 ｛＄＄ ＝ cons（1ist（＄1，ATOM），1ist（＄2，ATOM）） ｛＄＄ ＝ list（＄1，ATOM） ：｝ 四UMBER ｛ ＄2一＞u．cval ＝ 一〈＄2一＞u．cval） ； free（＄1） ； ＄＄ ＝ list（＄2，ATOM） ； ｝ ｛＄＄ ＝ list（＄LATOM） ；｝ ｛lstfre（a） ； 零eva11（opr， a， b｝ int opr； double a ， b ；︷ List ＊1 菖 GET LST ； Symbol 零s 零 GET SYM ； 1一＞1type ＝ ATOM マ 1一＞head． sy皿b ＝ S l 1一＞tail ＝ NiL ； s一＞id ＝ CNST ； switch（opr》 ｛ case ’十’ ： S一〉閣．cval ロ の case 一 ： S一＞U．cval case ●蓼’ ： S一＞U． cval case ’／’ ： s一＞u． cva1 1stfre（b） ： lstfre｛c） ；｝ LDb﹂ULU 十︸凸？／ ∩6薩6∩6鳥d ， ， ・ ， ● ， ● ． break break break break ●， ，﹁ ■， ●● ︸ ︸ ︸ ●， 119120 List 彦根論叢（第257号） case●器’ case EQ case麗E ease GT case GE ease LT ease LE ease AND ease OR ｝ return （1） ； ’ 蓉eva重（OP， a， b） List ＊a 噛b ’ ︷ double av ， bv int af且ag 菖 if （a一＞ltype ＝＝ if if ⋮● ●● ■● o● ・● ・． ．■ ．● s一＞u．cval ＝ s一・＞u．cval ＝ s一＞u．cval ＝ S一＞U．cva且 冨 s一＞u．cval ＝ s一一＞u．cval ＝ s一＞u．cval ＝ s一＞u．cval ＝ s一＞u．cval ＝ fmod（a， b） ： break 〈a ＝＝ b） ？ TRUE ： （a 1＝ b） ？ TRUE ： （a 〉 b＞ ？ TRUE ： （a 〉＝ b） ？ TRUE ： （a 〈 b） ？ TRUE ： （a 〈＝ b） ？ TRUE ： （a ＆＆ b） ？ TRVE ： （a ll b） ？ TRIiE ： ； FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE break ； break ： break ； break ； break ； break ； break ； break ； ，零OP ； ； O ， bflag ＝ O ， opr ＝ op一＞head． symb一＞u．oper ATOM） （a一＞head． symb一＞id ＝＝ CNST） ｛ av ＝ a一＞head． syvab一＞u． cval ； af且ag ＝ 1 ； ｝ （b一＞ltype ＝＝ ATOM） if if （aflag） if （b一＞head． symb一＞id ＝＝ CNST） ｛ bv ＝ b一＞head． symb一＞u． cval ； bflag ＝ 1 ； ｝ 〈bflag） ｛ ALLFRE（op， a， b） ； return （evall（opr，av， bv）） ； ｝ else ｛ if 〈opr ＝＝ OR ＆＆ av ＝＝ TRUE） ｛ ALLFRE（op， a， b） ； return （list（put−d（CNST，av））） ； 葺 return （cons（op， cons（a， b））） ； ｝ if （bflag） ｛ if （opr ＝＝ OR ＆＆ bv ＝＝ TRUE） ｛ ALLFRE（op． a． b） ； return （list（put−d（CNST，bv））〉 ｝ if 〈opr ＝＝ AND ＆＆ bv ＝＝ FALSE） ｛ ALLFRE（op， a， b） ； return 〈list（put−d（CNST，bv））） ｝ ｝ return （eons（op， cons（a， b））） ；塾 ，， ，， ・，
プロトタイプデータベースPDBIのデータ処理システムの設計と開発 mainO ｛ lstprt〈yyparseO＞ ； ｝ ファイル2 SPEC．LEX（言語仕様のLEX入力部分） ［O−9］ ［a−zA−Z］ （｛DIGIT｝1（LETTER｝） OPERATOR ｛一＋零ノ96］ ［ Yt］ ｛SPACE｝＋ ｛；｝ ｛ DrGIT LETTER DIGLET SPACE 瓢％ ”A閥D” ●’ nR鱒 ” ＝” 層〉輔 謄〉＝・ ●ぐ 口く＝” ”〈〉” ［1−9］ ｛DIGIT｝ 1 口0鱒 yylval． sym︷ yylval．sym︷ yylval． sym︷ yylval． sym︷ yylval． sym︷ yylva1．sym︷ yy且val． sy田︷ yylval． sym ’ ｛LETTER｝ ｛DIGLET｝＊ 騨’”oLETTER｝＋需●・ ‘OPRATOR） コ Yn 駕鑑 put−i（OPER，AND）； put−i（OPER，OR） ； put−i（OPER， EQ） ； put−i（OPER，GT） ； put“i（OPER，GE） ： put−i（OPER， LT） ； put．i（OPER， LE） ； put−t〈OPER， NE） ： ｛yylval．sym t return ｛ Sy馴tab 蓼s ； double d ； if （s ＝ else ｛ d＝ s ＝ ｝ return ｝ ｛yylval． sym return lyylval，sym return 1 （return O ；｝ （NUMBER） return ｛AND＞ ；1 return （OR） ；｝ return （EQ） ；｝ return （GT） ：｝ return （GE｝ ；｝ return （LT） ；｝ return （LE｝ ；｝ returfi 〈Ne） ；｝ d（CNST， atof〈yytext）） put ；r lookup〈yytext）） yylval． sym ＝ put−s（DEF， s） ； o．o ： insta11（yytext，UNDEF，＆d） ： yy且va1．sy罰 菖 put＿s（U國DEF， s） ； （NAME） ； ＝ put−c（STR，yytext） ； （sTR！NG＞ ；r ＝ put．i（OPER，yytext［O］） ： （yyte翼t［0】ア；｝ ． ， 121
