論 文
Pascalプログラム複雑さ評価トゥールの開発
王心潜 有沢誠（昭和60年8月31日受理）
Development of a Complexity Evaluation Tool
for Pascal Programs
OuShinSen ArisawaMakoto Abstract Correctness and performance measures are well established in software metrics researches， but maintainability measure is far behind． McCabe measure and Halstead measure are two representative but limited complexity measures． We introduce a new measure based on characteristic equation of a well−structured program． We give a brief summary in the first section． In the second section， the details of the proposed measure are discussed． We have developed a tool to measure given Pascal program according to this measure， which is described in the third section． The last section concludes the research and observe future directions．1．はじめに
ソフトウェアの評価は，従来のような正当性や性能 の評価だけでなく，ソフトウェアの保守性の評価の重 要性が増している。当研究室でも，Pascal言語に限定 して，種々のプログラム評価の尺度を研究し，また評 価トゥールを開発してきている1）2）。本論文も，その一 連の仕事のひとつとして行ったものである。 ソフトウェアの保守性のひとつの側面は，プログラ ムの複雑度である。プログラムの複雑度の尺度には， 制御の流れの構造に着目したMcCabe尺度3），プログ ラム中に現われるオペレータとオペランドの数に着目 したHalstead尺度4），およびそれらを改良した諸尺 度5）が代表的である。本論文で扱う尺度は，McCabeと Halsteadの考えかたを統合し，特性多項式の考えか た6）をとりいれたものである。 2．複雑度尺度 本論文では，プログラムをPascal言語によるもの と限定し，さらにgoto文を用いない構造化されたも のだけを対象とする。構造化されたプログラムは，連 接（sequence），反復（iteration），選択（selection） の3基本構造を，並べたり入れ子にしたりして組み合 わせることにより，整った構造にできる。この3基本 構造は，Jacksonの記法7）8）を用いて，図一1のように表 現できる。 このとき，Jacksonの記法の組み合わせによって， たとえば次のPascalプログラム9）は図一2のように表 現できる。 program VVordcount（ inPut， ouiput）； var cozant・：ゴ碗9θγ；a：char； begin count：＝0；read（a）； while a≠∵do begin if a≠㌧’then begin count：＝coμnt十1； while（a≠’；’）and（a≠’，’）《lo read（a） end else while a＝∵do read（a） ホ 中華人民共和国四川大学（山梨大学客員研究員） ＊＊ v算機科学科，Department of Computer Science一84一
end； writeln（count）Pascalプログラム複雑さ評価トゥールの開発 連接 反復 選択 A＝B・C・D E＝F＊
G＝H十J十K
図一1 3基本構造 図一2例題プログラムのJackson図 end． この図で，末端の四角には，代入文，手続き呼び出 し文などの基本文や，反復や選択のための論理式が対 応する。そこでそれらについては，Halsteadのオペラ ンド複雑度に準じた複雑度をあてはめる。 一般に与えられたPascalプログラムについて，そ の構造をJackson図で表わし，末端節点の四角にオペ ランド複雑度をあてはてることによって，McCabeと Halsteadの両方の特徴を備えた複雑度が得られる。 Jackson図そのままでは，以後の扱いに不便なため， 特性方程式の考えかたにならって，図一1のように連接 はドット（・），反復は星（＊），選択は小丸（○）を用い て表わす記法により，Jackson図を線形に表現する。 図一2の例は次のようになる。 a・b・（c・d・（e・（f・g）＊＋（h・j）＊））＊k ただしa，eは代入文， b， g， j， kは入出力文， c， d， f，hは論理式にそれぞれ対応する。これらについて， オペランド複雑度を求める。 オペランド尺度としては，その部分に現われる識別 子の数をとる。たとえばcozant：＝0という代入文で は，識別子はひとつだけだから1となり，read（a）と いう手続き呼び出しでは，識別子はふたつあるから2 となる。ただし同一の識別子が2度現われた場合，異 る識別子が1度ずつ現われた場合より低い値にするこ とが妥当であるから，2度目は1／2とする。たとえば， cozant：＝count＋1という代入文は1＋1／2＝1．5とな る。以下同様に3度目は1／3，4度目は1／4というよう に重みをかける。複数回識別子が現われることによる 重みは，Jackson図のひとつの末端節点の四角の中で のみ適用し，外側の四角には影響を及ぼさない。 ここまでで，Pascalプログラムに対して，特性多項 式に似た形で複雑度が定義できた。ただし手続き宣言 を含めた宣言部は除いてある。この段階ではまだ複雑 度は式であり，数値になっていない。式から数値に変 換するには，・＊＋のそれぞれに算術演算を対応づけ すればよい。 連接（・）に対しては，和をとるものとする。すなわ ちB・C・Dという式の値はB＋C＋Dである。 反復（＊）に対しては2通りの考えかたがある。ひと つは肩の星印を2乗とみるものであり，もうひとつは その星印の深さとの積をとるものである。すなわち， F＊という式の値としてF2をとるものと， F×dp（F）を とるものがある。ただしdp（F）はFの深さを示す。 選択（＋）に対しても2通りの考えかたがある。ひと つは連接と同様に和をとるものであり，静的な複雑さ を表わす。もうひとつは小丸の箱の最大値をとるもの であり，動的な複雑さを表わす。すなわち，H＋J＋K という式の値として，H＋J＋Kをとるものと，max｛ H，J， K／をとるものがある。一85一
昭和60年12月 山梨大学工学部研究報告 第36号 これらの値のわりあてかたの意味づけは，さきにあ げた文献2）・6）にもある通り，必ずしも理論的なものでは なく，実験的な性格をもつ。どの値のわりあてかたが， 特定の目的に照らして有効であるかは，実験的に調べ る必要がある。 3．評価トゥールの開発 これまでに述べた尺度による評価を行うために，与 えられたPascalプログラムを解析し，評価値を求め るトゥールを開発した。トゥール自体もPascalで書 かれており，計算機科学科のMelcom800システム上 にあるPascal8000処理系上にインフ゜リメントしてあ る。 トゥールはまず入力されたプログラムの構文解析を 行う。この手法はWirth1°）によるトップダウン解析手 法に基づいている。Pascalの反復構文として， while 文，repeat文， for文を識別し，条件構文として， if文， case文を識別する。連接に現われる基本文として，代 入文と手続き呼ぎ出しを識別する。反復および条件に 現われる論理式は，連接の形でJackson図に含める。 反復については，論理式の評価が反復の対象になるよ うに星印の下位に連接としておき，選択については選 択方向によらず論理式の評価が行われるように小丸印 の上位に連接としておく。このようすは図一2に具体的 に示されている。厳密なことをいえば，反復の場合に 本体の反復回数と論理式の評価回数とでは，後者が1 回多いのだが，この尺度ではその点は無視している。 解析結果は，直接Jackson図で表わさず，それと等 価な構造をもつリスト構造を内部データ構造として用 いている。Pascalの機能を生かし，レコード型とポイ ンタ型のデータ構造を駆使してこの部分を実現した。 入力プログラムの解析が終了すると，尺度による評 価値を作成する。これには次の9通りすべてを枚挙す る。 （i） シンボリックな多項式の形。・＊＋をすべて含 んだままの形である。 （ii）連接については和をとらない形。・だけはまだ 式中に残った形である。 反復について，2乗としたものと，深さとの積を とったものの2通り，選択について，和をとった ものと，最大限値をとったものの2通り，合計4通 りがある。 （iii）連接についても和をとった形。・＊＋のすべて が消え，ひとつの数値になったもので，前項と同 様にやはり4通りがある。 このトゥールに例題プログラムをかけた場合の出力 PROGRAM WORDCOUNT（INPUT，OUTPUT）； VAR COUNT ： INTEGER； A ：CHAR； BEGIN COUNT：＝0； READ（A）； WHILE A 〈〉 ，；． DO BEGIN IF A 〈〉 ，，’ THEN BEG工N COUNT：ニCOUNT＋1； WHILE （A〈〉，；りAND（A〈〉’，’） DO READ（A）
END
ELSE WH工LE Aニ，，’ DO READ（A） END； WRITELN（COUNT） END． 畏畳芙 PROGRAM WORDCOUNT 畳祈祷 （（［（（A1），（（A2）X提））＋（（A3）X畳）］）Y筈） 筈畏祷 PROGRAM WORDCOUNT 畳畳養 （（［（（ 1．5），（ 2．0）畳1）＋（ 2．0）畏1］））養2 芙養済 PROGRAM WORDCOUNT 誉筈筈 （（［（（ 1．5），（ 2．0）2蓑）＋（ 2．0）2筈］））2筈 畳済畳 PROGRAM WORDCOUNT ％済簑 （（［（（ 1．5），（ 2．0）升1）＋（ 2．0）簑1］））x2 養養筈 PROGRAM WORDCOUNT 畳蓑筈 （（［（（ 1．5），（ 2．0）2苦）＋（ 2．0）2警］））2苦 ※筈養 PROGRAM WORDCOUNT 鯖簑※ （［（ 2．O）畳1， 1．5＋（ 2．0）誉1］）筈2 苦※※ PROGRAM WORDCOUNT 馨筈畳 （［（ 2．0）2畳， 1．5＋（ 2．0）2畳］）2簑 筈蕎畏 PROGRAM WORDCOUNT 畳箭畳 （［（ 2．0）簑1， 1．5＋（ 2．0）養1］）養2 祷祈養 PROGRA図 WORDCOUNT 養養簑 （［（ 2．0）2升， 1．5＋（ 2．0）2畳］）2筈 図一3 例題と出力 結果の例を図一3にあげておく。この出力では，計算の ようすがより明確になるように，式の形を印刷してい る。4．おわりに
ソフトウェアの評価尺度の研究は，評価尺度自体の 評価をする尺度がないため，必要性が高いわりにはあ まり進んでいない。実験的に尺度間の相関係数を求め ていく方向は，特定の尺度の優位性を保証してくれな い。理論的に納得がいく尺度は，現実にはソフトウェ アのごとく限られた一面しか評価せず実用にならな い。 本論文で述べた尺度は，理論的な納得性をもち，か っプログラムの総合的な評価をねらったものである。 ここでは定めた複雑度の有効性については，今後，開 発したトゥールを用いて多くの例に適用し，他の諸尺 度との比較検討を行って研究していく計画である。 この尺度の欠点として，構造化されたプログラムの みを対象とし，非構造的なプログラムを扱えないこと一86一
Pascalプログラム複雑さ評価トゥールの開発 がある。この点についても，尺度の定義を納得できる 形で拡張することを考察中である。 謝 辞 本研究を支援していただいた，有沢研究室の諸氏， 特に中国語の意志伝達を補ってくださった，張清利， 陳昭場，鄭際雲の諸君に厚く感謝いたします。
