関数 - みる会図書館


検索対象: 月刊 C MAGAZINE 1993年5月号
97件見つかりました。

1. 月刊 C MAGAZINE 1993年5月号

には限界があるし , 前記の約束をやぶって もコンパイルエラーや実行時工ラーになる わけて、もない それは , 非常に見つけにくいバグとして 現れることてあろう。すなわち , 前記のよ うな「暗黙の約束」はプログラム設計上好ま しくない。このため , CPL / 0 を作成すると きに , 識別子の扱いを全面的に書き直した。 その手法を以下に説明する。 CPL / 0 て、はすべての識別子を symbol とい う構造体により表現する。 symbol 構造体の メンバは , ハッシュ表により管理され , 同 ーの名前を持つ symbol はただひとつ存在す る。すなわち , Lisp 系言語のシンポルと同 じ扱いて、ある。ファイルから読み込まれた 識別子はただちに symbol に変換され , もし 対応する symbol が存在していなければ , 新 しい symbol が生成される (Lisp の intern に相 以上はすべて字句解析レベルて、行われる ため , 構文解析レベルて、は識別子の保存状 況を気にかける必要はない。これにより , 字句解析と構文解析の独立性を高め , メン テナンスなどに対して「頑丈な」構造を保つ ことがて、きた。 こて , symbol 構造体と識別子を表現す る ident 構造体を List 18 に示す。 symbol と i dent の関係はわかりにくいかもしれないが , 前述のように symbol は「名前」と一対一の関 係にあるのに対して , ident は個々の変数や 手続きと一対一の関係にある。 ident は同じ 名前を持つものが複数存在してもよい れは , スコープが異なれば , 同名の識別子 があってもよい ( このあたりは C 言語とよく 似ている ) からてある。 このふたつの構造体の個々のメンバの意 味は , リスト中にコメントとして書いてお いたのて、参照してほしい。とくに ident 構造 体は大きく複雑な構造を持つ。実際のとこ ろ , この部分は PL / 0 のようなトーイコンパ イラの記号表としては本格的すぎるのて , 「鶏を割くに。篶くんぞ牛刀を用いん」という批 判を項戴したことがある。まったくもっと もな指摘なのだが , 先々本格的な言語に拡 70 C MAGAZINE 1 3 5 33 : } : 18 , LiSt CPL / 0 の識別子の宣言 るのが , lex を使うか否かという点て、ある 関数 yylex を作成する際にいつも問題にな て読みだすのがおもな仕事て、ある。 字からなる記号などを , ひとつの単位とし や関数を表す「識別子」や , 、、 > = クなど 2 文 とは , ひとまとまりの記号のことて、 , 変数 句」という単位て、読み出すことにある。字句 yylex の役割りは , ソースプログラムを「字 する。 が , すなわち字句解析部を作ることに相当 す。したがって , 関数 yylex を記述すること たびに , yylex という名前の関数を呼び出 析プログラムは , 字句 ( token ) が必要になる 先にも述べたように , yacc 記述の構文解 字句解析 ほかの部分の設計について簡単に説明しよ 設計について説明してきたが , 以下にその さて , いままて yacc と関係の深い部分の 敢えて牛刀を用いることにした。 して、流用したいという考えがあったのて , 張する際にも字句解析回りは大きな変更な が , CPL / 0 て、は lex を使わないて、 , 手書きの 字句解析プログラムを使用している。その 理由は , 字旬解析の部分は決まり切ったパ ターンなのて、 , 過去の手持ちがあればわず かな変更て、流用可能だからて、ある。また , 手書きの字句解析プログラムのほうが , lex を用いたものに比べて高速・コンパクトに なるというのも , その理由のひとって、ある。 CPL/O の yylex は , 手書きの字句解析プロ グラムの定石に従って , 常に 1 文字先読みし た状態を維持している。この「先読み」が必 要な理由は , 、、 > クと > = 〃を区別する場 合を例に取って次のように考えればわかり やすいだろう。これらを区別するためには , どうしても、、 > 〃の次の文字を読まなけれ ばならない。この結果 , > = 〃て、ないとわ かった場合 , 先読みした 1 文字をどう扱う か。これには以下のふたつの有力な方法が ある。 ひとつは , 読み込んだ文字を「読まなかっ たことにする」という方法てある。つまり , C 言語の標準関数 ungetc に相当する機能を 使えばよい。しかし , 通常の言語の場合 , かなりの頻度て、 ungetc を呼ぶことになるの て , プログラムが読みにくくなるうえに 2 : 3 : 5 : 6 : 7 : 8 : 10 : 22 : 23 : 24 : 25 : 26 : 28 : 29 : 30 : 32 : typedef struct symbol symbol-t; typedef struct ident ident-t; 4 : struct symbol { symbol-t *next; ident-t *first; Char *name; i n t t-k i nd : 11 : struct ident { ident-t *next_level; ident-t *next; symbol-t *symbol; int level; int offset; idkind-t kind; union { struct { i nt val ue : } i-const; struct { int nargs; int addr; i nt i ze : ident-t *parent; ident-t *cbi : } i-proc; struct { int narray; } i—var; / * 次の symbol * / / * 同じ綴りの symb 引のうち、先頭の識別子を指す * / / * symbol の名前 * / / * symbol の種類。、 SYMBOL など * / / * 親のプロックに属する同名の ident を指す * / / * 同じプロックに属する次の ident を指す * / / * symbol を指す逆ポインタ * / / * ネストレベル * / / * 変数 / 関数の offset 値 * / / * ident の種別 * / / * const の値 * / / * 配列の大きさ。単純変数の場合は 1 * / / * current-block-idents を保存 * / / * 親プロック * / / * ローカル変数のサイズ * / / * 関数のアドレス * / / * 引数の個数 * / / * procedure, funct ion で使用 * /

2. 月刊 C MAGAZINE 1993年5月号

次々とブッシュされ , その関数から戻ると 引数 関数の呼び出 きにスタックからポップされるのだ。 関数内で定義された自動的記憶寿命を List 4 のプログラムを考えよう。 main 関 持つオプジェクト 関数の呼び出しとスタック 数は , c 関数を呼び出す。その c 関数は , a 関 がスタック上に蓄えられるのて、ある ( ただし 数と b 関数を順次呼び出す。プログラムの実 関数呼び出しの際に , スタックが利用さ レジスタ上に保持されるものを除く ) 。もち 行開始から終了まて、の関数呼び出しの手順 れることはわかったが , 具体的にどのよう ろん , 関数から戻るときは , これらのデー を示すと , 次のようになる。 なものがスタック上に蓄えられるのかを考 タはスタック上から除去される。 ( 0 ) List 5 を例に , 関数呼び出しにおけるスタ ( 1 ) main( ) 呼び出された関数から , 呼び出し元の関 ックについて具体的に考えよう (Fig. 3 ) 。 ② main ( ) → c ( ) 数に戻るときは , その関数を呼び出した場 多くの C 言語コンパイラは , 関数呼び出し ( 3 ) main ( ) → c ( ) → a ( ) 所 ( 厳密にはその直後 ) に正しく戻ってこな の際に , 後ろのほう ( 右側 ) の引数から評価 ( 4 ) main ( ) → c ( ) ければならない。たとえば , 先の例て、は , 関数呼び出しとスタック ⑤ main ( ) → c( ) → b( ) a 関数終了後は , List 4 の 15 行目直後に戻る ( 6 ) main ( ) → c ( ) 必要がある。したがって , 一般にリターン ( 7 ) main( ) アドレス (return address) , すなわち関数終 了後に戻るべき番地を保存するのて、ある。 ( 8 ) こまて、示せば , 著者のいわんとするこ a 関数を詳しく考えよう。この関数には , とがわかるだろう。 ( 0 ) ~ ( 8 ) は , 現在呼び 引数 int 出されている関数のリストて、あるわけだが , 自動的オプジェクト int これは見事にスタック形式となっているこ a [ 10 ] ; int とが見て取れるはずだ の変数が使われる。これらの変数は , この たとえば ( 3 ) は , a 関数が呼び出されてい 関数が実行されている間のみ『生きて』い る状況を示している。そして , a 関数から c ればよい , 自動的記憶寿命を持つ。したが 関数に戻った状態が ( 4 ) て、ある。 ( 5 ) は , そ って , これらのデータもスタックに保存す の後に b 関数を呼び出した状態だ。すなわ れば都合がよい。つまり , ち , 呼び出された関数がスタックに対して リターンアドレス 関数呼び出し Fig. 3 関数呼び出しとスタック List ー func 関数 2 : void func(int a, long b, char *c) X ; 5 : 9 : 10 : / * - ー main 関数 int main(void) int int 15 : Char 17 : func(a + 3. b, c) : 18 : 19 : return ( 0 ) : i n t ー ong List 1 ーっワ 0 4 ・ LO っ叮ー 8 0 , 1 り 0 00 ・ -. 0 c_D ー 8 0 ーーワ】っ 0 ・ー・ 11 1 ー 14 ーー 1 よ 1 よー人 1 一 1 ーっ朝り 0 り乙 int a=O; int b=2; char c[]= ” ABC ” func(a 十 3,b,c) 未使用工リア x, y などの 自動的オプジェクト リターンアドレス 3 (int 型 ) 2 (long 型 ) &cCO] (char* 型 ) 使用中のスタック領域 int a [ 10 ] ; VOid func(int a, c) long b, Char int x; long y, 114 C MAGAZINE 1993 5

3. 月刊 C MAGAZINE 1993年5月号

目が追加され , 基本クラスのポイ fflush (fp) ; ンタ変数を使ったときて、も仮想関 などとしてバッフアの内容をフラ 数テープルを使ってオプジェクト ッシュしてから setftime を実行する にふさわしい関数を呼び出すこと ようにしてください がて、きます。 デストラクタも , これと同じて、 Q す。デストラクタが仮想関数とし Borland C 十十を使ってアプ て定義されていないと , 基本クラ リケーションを開発したのですが , スのポインタ変数に対して delete を ランタイムライプラリや ObjectW 実行してもオプジェクトにふさわ indows などのライプラリを DLL と しいデストラクタを呼び出すこと してリンクしています。このため , がて、きません。 アプリケーションを販売したり配 布するときには BC30RTL. DLL や OWL. DLL なども必要になります。 Q f0P00 を使 0 てオープンしたフ これらを配布するためには , 何か ァイルに対して , 契約が必要ですか。 setftime (fileno (fp) , &ft) ・ A BC3()RTL. DLL, OWL. DLL, としてタイムスタンプを設定して いるのですが , fclose を実行すると TCLASS. DLL, BWCC. DLL は , 設定されたタイムスタンプが失わ 「 BorlandC 十十て、開発したアプリ れてタイムスタンプが現在の時刻 ケーションとともに配布する」とい になってしまいます。 う条件のもとて、 , 特別な契約なし に配布することがてきます。その A setftime はタイムスタンプ ( フ 際 , DLL の著作権表示を削除した ァイルの最終書き込み時間 ) を指定 り , ファイルの改変などを行わな された時間に設定しますが , その いて、ください。また , DLL ファイ 後にファイルに対して書き込みが ルを単体て配布することはて、きま 行われると設定した内容は失われ せん。なお , BGI ファイルも同様の てしまいます。高水準入出力関数 扱いとなります。 (fopen など ) て、は , ファイルへの書 ※本誌 ' 93 年 1 月号の本コーナーに Q 一般に , 基本クラス型へのポイ 掲載されたクラスのメンバ関数 き込みはバッファリングされてい クラスを継承させています。 ンタ変数には派生クラスのオプジ るのて、 , fclose の直前て、 setftime を の制約表に関して誤りがござい 基本クラスへのポインタ変数に派 ェクトのアドレスを代入すること 実行しても fclose によってバッファ ました。コピーコンストラクタ 生クラスのオプジェクトへのポイ がて、きます。このポインタ変数を の内容が書き出されてファイルの の項目の追加と = 演算子の訂正 ンタを代入したのですが , delete 使ってメンバ関数を呼び出すとき は TabIe 1 のとおりて、す。ご迷惑 を実行しても基本クラスのデスト タイムスタンプが更新されてしま は , そのメンバ関数が仮想関数と うこともあります。こうした場合 をおかけした皆様にお詫び申し ラクタしか呼び出されません。派 して定義されていなければ , 基本 上げます。 生クラスのデストラクタを呼び出 は , クラスのメンバ関数が呼び出され させるためには , どうすればよい TabIe 1 クラスのメンバ関数の制約表の追加 / 訂正 てしまいます。仮想関数が定義さ のでしようか。 仮想関数 メンバ関数か テフォルトで 継承 戻り値 での定義 生成されるか フレンド関数 れている場合 , そのオプジェクト A 基本クラスのデストラクタを コピーコンストラクタされない 不可 なし メンバ関数 される には暗黙のうちにクラスの仮想関 = 演算子 されない 可 あり 両方 されない 仮想関数 (virtual) として宣言して 数テープルへのアドレスを指す項 メニュー情報を構築 1 : TMenuBar *TMyApp: : initMenuBar( TRect r ) 3 : / / 下端を「上端の 1 行下」に移動 r. a. y 十 1 : 4 : return nev TMenuBar ( r, *new TSubMenu("-F-ile ” , kbAltF) + 5 : 6 : *new TMenuItem(" 0 pen ” cmMyFil e0pen, kbF3, hcMenu0pen, *nev TMenuItem(" N-ev 7 : cmMyNevWi n, kbF4, hcMenuNev, ” F4 ” ) + 8 : nevLine() + *new TMenuItem("E-x-it" 9 : cmQu i t, cmQui t, hcMenuExi t, ” GRPH-X") + *new TSubMenu ("-w- indOW ' kbAltW) + *new TMenuItem(" N-ext" cmNext, kbF6, hcMenuNext, z ー 00 田 *new TMenuI tem( ” cm Zoom, kbF5, hcMenuZoom, "F5") 13 : RAW モードで標準入出力を行う List 5 1 : # i nc lude く s td i 0. h > 2 : # i nc lude く i 0. h> 3 : #define RAW_MODE 0X0020 4 : #define IOCTL-GETMODE 0 5 : #define IOCTL_SETMODE 1 6 : main() 8 : 9 : 16 : 20 : 22 : } i n t C : int stat; setbuf(stdin, NUL い ; (unsigned char)ioctl(fileno(stdin), IOCTL_GETMODE) ; stat / / 標準入力デバイスを RAW モードに設定する。 ioctl(fileno(stdin), IOCTL_SETMODE, (void * ) (stat ー RAW_MODE)) : / / ' q ' を押すまで繰り返す。 〃 ( 標準入力は、テキストモードなので復帰 (0x0D) は無視される ) vhile ()c = fgetc(stdin)) ! ニ printf( ” input char = %c%n ” / / 標準入力デバイスを元に戻す。 ioctl(fileno(stdin), IOCTL_SETMODE, (void *)stat) : return 0 ; lnformation from Compiler Makers 155

4. 月刊 C MAGAZINE 1993年5月号

プロクラミンク熨場一 第⑩回 Dr. 望洋の 柴田望洋 スタックオーノヾフロ - ー C 言語プログラマであれば , 一度くらいはスー今回は , 関数呼び出しの仕組みなどからスー タックとスタックオーパフローについて考 タックオーパフローのエラーを発生させて しまったことがあるのではないだろうか。 ー察する。 たとえば机の上に積まれた皿は , スタッ クて、ある。皿を載せるときは上に載せ , 取 るときは上から ~ すなわち最後に積んだ皿 から取り出すからだ (Fig. 1 ) 。 前回は , 2 分木のデータ構造について考察 した。その際に , スタックに関して簡単に 単純なスダヅクの実現 触れ , 再帰を非再帰的に表現する方法につ スタックを実現するデータ構造と , それ いても解説した。 さて , 千葉市の村山聡さんから次のよう を操作する手続きを考えてみよう。なお簡 クに積み上げられたときに この変数をイ 素化のために , こて、はスタックに積む要 なお葉書をいただいた ンクリメントし , スタックからデータが取 私は巨大な配列を好んで使うのですが , 素は整数て、あるとする。 り除かれた際に ' れをデクリメントする。 printf による出力を試みると , よくスタ よって , 現在スタックに積まれている要素 スタックは配列を使うことによって実現 ックオーパフローのエラーが発生する。 て、きるが , 通常の配列て、はコンパイル時に の個数を記憶することがて、きる。 Fig. 2 にス このエラーの原因や対策法などを教え その大きさがあらかじめわからないといけ タックの構造を示す。 ない。そこて、 , メモリの動的確保の機能を これらの三つをまとめてひとつの構造体 ていただきたい。 用いて , 実行時に大きさを決定て、きる可変 とすると , スタックを表現するデータ構造 ック は , List 1 のように表現て、きる。 長のスタックを設計することにする。 もちろん , データを蓄える配列だけて、は , こて、は , Stack を typedef 名としてい 前回は , スタックについて簡単に触れた。 スタックは実現て、きない。そのほかに , ふ る。これにより , 以後のスタックの構造体 に関する宣言は , 手短に行えるようになる。 たつの整数変数が必要となる。 補足の意味も込めて , ちょっと復習してみ ひとつは , スタックのサイズ ( スタックに さて , スタックの本体は , 動的に確保す 保持て、きる最大のデータ数 ) を覚えるための るのて、 , スタックの初期化を行う関数が必 スタックの概念 要となる。これは List 2 の関数 StackAIIoc 変数 max て、ある。 もうひとつは , スタックポインタ ( stack のように定義て、きる。 こて、 , メモリの確 スタック (stack) とは , 複数のデータを一 保に失敗したときに , メンバ max に 0 を代入 pointer) を表す ptr て、ある。データがスタッ 時的に蓄えるデータ構造の一種て、ある。新 しいデータは , それまて、に入っているもの スタックを表現する構造体 の後につけ加えられ , 取り出すときは常に 最後に入れたものから取り出すという機構 を持つ。 すなわち , 後入れ先出し (LIFO/Last-In -First-Out) 方式て、データの追加・削除が行 われる。 Fig. 1 スタック List typedef struct { int max ; int ptr; int *stk; 5 : } Stack; タ ン イ ポ ズタ頭 イン先 サイの のポ ( ククク タタタ ススス 112 C MAGAZINE 1993 5

5. 月刊 C MAGAZINE 1993年5月号

技法 ム グ ロ 集プ 特 O 最初に ごく簡単な例題て、も各種のアプ ローチに基づく設計がありて , 結果として 得られるプログラムはまったく異なってく るということを実感してみることにしよう。 取りあえず , まず例題 1 を考えてみてほし [ 例題 1 ] check int 関数を作成せよ。 int check int (const char * nptr) check int は , 引数に文字へのポインタ を受け取る。もし , ポインタが正しい 10 進整数文字列をポイントしていれば 1 を返 し , それ以外の場合には 0 を返すものとす る。また , 数値的なオーパフローは考慮 しない。 この問題て、は , 「正しい 10 進整数文字列」 というところが重要なポイントて、ある。 ・その後に 10 進数字 ( ' 0' ~ ' 9 ' ) の 1 個以上の ば , 問題を見ただけて、 , 10 進整数文字列の れはきちんと定義すべき問題て、ある。 並びがくる。 定義を考えることなく , 即座に解答が出て て、は次のように解釈しよう。念のためにい ・その後には任意の数の空白を含んでいて えば , これは ANSI C ライプラリの atoi など くるかもしれない List 1 の考え方を疑似コードて大ざっぱに が受け付ける構文に対して若干制限を厳し もよい。 ・その後には文字列の終わりがきているこ 表すと次のようになるだろう。 くしたものてある。また , C 言語のソースレ ・文字列の先頭の空白類文字を読み飛ばす。 ベルての「 10 進定数 (decimal-constant) 」と ※符号と数字の間 , あるいは数字と数字の ・先頭に符号があれば , 読み飛ばす。 は異なる。 C の場合 , 10 進定数は 0 て、始まっ ・次が数字であることを確認し , 数字でな 間には空白は含まない。 てはならず , かっ , 符号は定数の一部とし ければ 0 を返す。 こまて、定義を与えられると , ある程度 ては許されない ・数字がきている間読み飛ばす。 以上 C プログラミングの経験がある人て、あれ ・先頭には任意の数の空白を含んでいても ・最後に再び空白類文字を読み飛ばす。 ば , ほとんど反射的に List 1 のような解答を よい。 ・文字列の終わりであれば 1 を返す , さもな ・その後には ' 思い浮かべるのて、はないだろうか。あるい ' または ' 十 ' の符号がどち は , この種のプログラムに慣れた人て、あれ ければ 0 を返す。 らかひとつきてもよい。 check int の実装 Fig. 1 浮動小数点数文字列の形式定義 浮動小数点文字列 : 空白類。符号 浮動小数点定数 空白類 浮動小数点定数 . 仮数部指数部 仮数部 . . 数字の並び 数字の並び小数部。町 小数部 . 数字の並び。町 指数部 . 指数文字符号。 数字の並び 指数文字 : one of E e 数字の並び : 数字 数字の並び数字 数字 : one of 0 1 2 3 4 5 6 7 8 9 符号 : one of 十 ロ OPt List 1 LlSt } vhile (isdigit(*nptr)); / * 空白があれば、それを読み飛ばす * / ⅶⅱ e (isspace(*nptr) ) 十十 nptr, / * 文字列の終わりに達したかチェックする * / if (*nptr ニ return l; return 0 : 25 : 26 : 27 : 28 : 29 : 30 : 32 : 33 : 35 : 36 : $ifdef TEST 37 : # i nc lude 38 : 39 : i n t 40 : nai n( int argc, char **argv) if (argc く 2 ) return 0 : vhile (* + + argv ! = N 乢し 45 : printf("Xs = XdYn", *argv, check_int(*argv)) : return 0 ; 48 : $endif 1 : #include く ctype. h> 2 : 4 : * 10 進整数文字列のチェックを行う 6 : int 7 : check-int(const char *nptr) 9 : / * 空白があれば、それを読み飛ばす * / vhile (isspace(*nptr)) 十十 nptr, / * 符号があれば読み飛ばす * / if (*nptr : Ⅱ *nptr : = 十十 nptr; / * 数字が少なくとも 1 つあることを確認する * / if (!isdigit(*nptr)) return 0 ; / * 数字を読み飛ばす * / 22 : do { 23 : く stdio. h> 十十 nptr; 特集 C プログラム設計技法 47

6. 月刊 C MAGAZINE 1993年5月号

社交鎖 第 26 回 吉柄貴樹 今月の問題「クイーンプロプレム・プロプ 断終了して次に進みます。 12496 , 14288 , 15472 , 14536 , 14264 レム」は , パズル作りをパズルにしてしまっ て、あった。 とくに難しいアルゴリズムは使っていま たものだ。普通は , この問題を出題者が解 今回は , 「奇数の約数総和は必ずその奇数 せん。ゴリ押し試算をしているのて、 , 解答 き , その答え , つまり A, B, C, D の組み を下回る」という条件を使っている枡屋航さ を出すのは決して速くありません。あえて , 合わせのひとつを提示して , 「この 8 枚を用 んと , 約数の和の求め方を工夫した武田靖 このプログラムのミソは「 IF 文」を使ってい いて 8 x 8 の正方形を作り , クイーンプロプ 彦さんの解答を紹介しよう。 ないことて、しよう ( だから何なんてすか ? と レムを満たす並べ方は何通りあるか」とやる いわれそうだな ) 。 枡屋航さんの解答 のて、ある。出題者の楽しみ ( 苦しみ ? ) を味 使用機種 PC-9801DX ( プログラムは付録ディスク PU 圧 01 ℃ ) わっていただきたい O S MS-DOS Ver. 3.30D プログラムの説明 コンパイラ TurboC 十十 Ver. 1.00 ( ー ms ) 【 2 月号のノヾズル】 三つ以上の数て構成される「社交鎖」の最 参考文献『アルゴリズム辞典』 ( 技術評論 x の約数 ( ただし , 自分自身は除く ) の和 小数を求めます。社交鎖の基数 ( 出発点 ) を 社 , 奧村晴彦著 ) を求める関数を f ( x ) とする。 10 ( とくに根拠はない ) から順に試算してい いま , X1,X2, ・・・ Xn という , n 個の数の 武田靖彦さんの解答 列があり , 次の式が成り立っている。 きます。はっきりいって地道て、す。ただし , ( プログラムは付録ディスク PU 圧 02 ℃ ) X2=f(X1) 奇数の約数総和 ( f ( 奇数 ) ) は , 必ずその奇数 X3=f (X2) を下回るため ( 奇数 x > f ( 奇数 x ) ) , たとえ「社 プログラムの説明 交鎖」が完成しても最小数にはならないのて、 f(i Cn—1] ) て、生成される数列 Xn=f(Xn—1) X1=f(Xn) 偶数のみ試算します。 .. i Cn] は i が素数のとき f (i) = 1 とな つまり , それぞれの数の約数の和が , 試算した数値の「社交鎖」が完成したか否 るのて、 , 一般的に i [ 0 ]... 1 て、終わります。 数の列の次の数になっていて , 最後の数 かの判断は , しかし i [ 0 ]. . となれば無 の約数の和が , 最初の数になっている。 A ) 約数の総和 ( f ( x ) ) が素数になった こういった数の列の輪を「社交鎖」という。 限ループに入ります。 この鎖がふたつの数で構成される場合 B ) 出発点に戻れない永久パターンになった 1 から無限大まて、連続した数字の列をフィ ( n = 2 ) の例を示そう。 220 と 284 は , それ C ) 約数の総和が出発点の数値を下回った ールドとして用意します ( 実際にはメモリ制 ぞれ自分自身を除く約数の和が相手の数 になった場合は「社交鎖」は完成しなかった 限により 1 から 50000 て、す ) 。このフィールド になっている。 220 = 2X2X5X11 で , そ ことにします。もちろん , 出発点に戻って に i [ 0 ]. . iCn] の数列を置いてループして の約数は 1 , 2 , 4 , 5 , 10 , 11 , 20 , 22 , 44 , 55 , 110 であり ( 220 は除く ) , 足すと きたら「社交鎖」は完成て、す。 いるかどうか調べます ( 同じ数列にかえって 284 になる。また , 284 = 2X2X71 で , そ A ) については , 約数総和が 1 なのて、簡単に くればループてす ) 。ループを発見すれば記 の約数は 1 , 2 , 4 , 71 , 142 で , 合計は 22 念に表示し , そのループが n > = 3 て、あれ 判別てきます。 B) については , 出発点以降に登場した約 ば , その数値を最大値として記録します。 では , こで間題。三つ以上の数で構 成される ( n と 3 ) 社交鎖を見つけよ。その より小さい n > = 3 ループが存在するかど 数総和を , つぎつぎと BIackList として登録 うち , 「その鎖の中に登場する最小数」が し , 登録した数値のうちいすれかが再登場 うかを調べるには , 1 から最大値の間を調べ もっとも小さい社交鎖を答えなさい。 れば十分て、す。また , 一度数列を置いたフ した時点て、無限ループと判断しています。 C) は , 最小の解を得るための制限て、す。 ィールドは , ふたたび捜索する必要がない 2 月号の解答 したがって , 問題例に出されていた f ( 220 ) は のて、 , 1 て、塗りつぶします。 ふたつの「社交鎖」ということになりますが , 捜索完了後 , 最大値を含むループを解答 正解の社交鎖は , f ( 284 ) は「社交鎖の中の最小数」て、ないのて、中 として出力します。 148 C MAGAZINE 1993 5

7. 月刊 C MAGAZINE 1993年5月号

NUMBERS List べてのマシンて、使用て、きるはずて、す。動作 確認は PC ー 9801 て行いました。 LSI C ー 86 Ver. 3.30 をインストールした 後 , 本誌付録の提供ファイルをひとつのデ ィレクトリに展開した後 , A> LCC NUMBERS. C と実行すれば , そのディレクトリに実行フ ァイル NUMBERS. EXE がて、きます。コマ ンドラインから A> NUMBERS とだけ入力すると画面に Fig. 7 のように表示 されるはずて、す。 NUMBERS を実行するたびに画面は上の ほうに流れていってしまいますから , Fig. 7 の内容をファイルとして保存しておくと便 利て、す。プログラムの実行結果をファイル に保存することを「ファイルに落とす」とい います。たとえば , A > N U M B E R S > N U M と入力すると新しいファイル NUM がて、き , その内容は Fig. 7 と同じものになります。 N UM の内容を見たいときには , TYPE コマン ドを使って A> TYPE NUM とします。またはエデイタを使って見るこ ともて、きます。たとえば先月号て、インスト ールした SE3 を使う場合 , A > S E3 N U M と入力すれば NUM の内容が見られます。ま た , あなたがワープロソフトとプリンタを 持っていれば , ファイル NUM を読み込んて、 印刷することもて、きます。 印刷する方法はワープロソフトによって 異なりますのて、 , ここて、は触れません。お 手持ちのワープロソフトのマニュアルを参 考にしてください N U M BERS を修正するには プログラム NUMBERS のように , 自分て、 コンノヾイルて、きるソースプログラムが手に 入ると , 自分て、アレコレ修正したくなるの が人情て、す。また , 自分て、ソースプログラ ムを修正して , 実行ファイルの動作がどう 変化したかを調べるのは C 言語が上達する道 88 C MAGAZINE 1993 5 * 名前 2 : numbers ー 2 進数、 8 進数、 1 0 進数、 1 6 進数の対応表を作るプログラム 3 : * 書式 4 : ー画面に表を表示する。 A > NUMBERS 5 : A> NUMBERS 〉 TABLE ーファイル TABLE に表を落とす。 6 : * 解説 7 : プログラム numbers は、 0 ~ 9 9 までの数値について、 2 進数、 8 進数、 8 : 1 0 進数、 1 6 進数の対応表を作るものである。 9 : * 作者 10 : 結城浩 ( C マガジン「 C 言語プログラミング・レッスン」 ) Copyright (C) 1993 bY Hiroshi Yuki. 12 : 13 : 14 : 15 : #include く stdio. h> 17 : / * 18 : * 定数 MAX_NUMBER は表示する数の個数。 * MAX_NUMBER が 100 のとき、 0 ~ 99 までを表示する。 * MAX_NUMBER は 32765 より大きくしてはいけない。 21 : 22 : #define MAX—NUMBER 100 24 : / * * 以下はこのプログラムで使用する関数の「プロトタイプ宣言」である。 * このプログラムで使用する関数の名前、引数の個数と型、返値の型を宣言する。 26 : 27 : print_binary(int n) ; 28 : VOid 29 : void main(void); 30 : 32 : * 関数 main 33 : 34 : void main(void) 36 : 38 : 40 : 41 : 42 : 43 : 44 : 46 : 48 : } 49 : 51 : * 関数 print-binary は引数 n を 2 進数として表示する。 * 例えば 52 : 53 : → 0000000000000010 54 : = 255 → 0000000011111111 print_binary(int n) 56 : VOid 63 : 64 : 65 : 66 : int i; printf( ” %16S ” , ” 2 進数” ) ; printf( ” ” 8 進数” ) % 8s ” " 10 進数も printf( ” % 8s ” " 16 進数も ; printf(" X8s*n ” for (i = 0 ; i く MAX—NUMBER; i + + ) { print_binary(i); % 80 ” , i); printf( ” printf( ” % 8d ” , i) ; printf( ” X8x*n", i) ; int 1 ; for (i = 0 ; i く 16 ; i + + ) { if (n & ( 1 くく ( 15 ー i))) ( printf( ” 1 ” ); else { printf( ” 0 ” ); いいいい ( に ~ にいに " に ~ らいに(に~に)~リリい、L@に「いい -

8. 月刊 C MAGAZINE 1993年5月号

特集 C プログラム 普通の読み方だと , 「読んて、から参照する」 という順序になるはずてある。 また , yylex は単純なことは自分て、行い 複雑なことは下請の関数にまかせている。 そのプログラム階層を Fig. 10 に示す。 Fig. 10 および List 19 を見ればわかるように ,yy lex は文字が必要になるたびに関数 readch を 呼び出している。つまり , Fig. 11 に示すよ うに , 構文・字句・文字の三つのレベルに それぞれ , 関数 yyparse, yylex, readch が 対応しており , 階層的に構成されている。 このような構成にしてあるおかげて、 , 仕様 変更などが非常に容易になる。たとえば以 下のような例をあげることがて、きる。 筆者は現在 CPL/O を MS-Windows に移 植中て、ある。この CPL/O for WIndows て、 は , いわゆる統合環境を実現しているのて、 , ソースプログラムは , テキストファイルか らて、はなくエデイタから読み出さなければ ならない。これは比較的大きな変更てある が , 上記のように , 文字は必ず readch を介 して読みだすようにしてあるため , readch を書き換えるだけて、この部分の修正は済ん て、しまう。つまり , Fig. 11 の階層て、いえば 「文字のレベル」の修正だけて、済むことにな 9 1 ン 字甸読み取り関数 yylex int yylex() 3 : int sym; ⅶ ile (char-class[c] 4 : 5 : readch() : svi tch (char-class[c] ) 6 : 8 : case ' % ' 9 : readch() : 10 : symbol-dump() : return yylex() : 12 : #end i f case ALPHA: case KANJI 1 : 15 : return identification(); case DIGIT: 17 : return fix-number(); case ' \ ' return get-string(); 20 : case ' ( ' readch() : 22 : 23 : ski p-comment ( ) : 24 : return yylex() : } se 25 : 26 : return ' ( ' 27 : 28 : readch() : 29 : 30 : readch() : return BECOMES; } else 32 : 33 : return 35 : 中略 36 : 37 : defau は : 38 : sym ま char-class[c] : 39 : yylval. value = char-value[c] : 40 : readch() : return sym; 42 : 43 : } / * yylex * / / * 記号の読みだし * / / * 常に一文字先読みしている * / = WHITESPACE) / * 空白の読みとばし * / / * 「文字種」による場合わけ * / / * % がソース中にあると、記号表の一覧を * / / * 表示する。 % 自体はコメント扱い * / / * 識別子または予約語 * / / * 数値 * / goto top-of-yylex; case 効率も低下すると思われる。 どちらも「定石」といっ ふたつの方法は , これに対して , 余計に読んだ文字もどう てよいものてあり , ー長一短があるのて、一 せすぐ使うのだから , いっそのこと必ず 1 文 概に優劣を決められるものて、はない。 CPL / 字先読みしておくことにすれば , せつかく 0 て、は後者の考え方を採用することにした 工ラ - 表示 読んだ文字を「読まなかったことにする」と が , これは「趣味」て、そうしたといってもよ いう不自然な操作を行う必要もないし , 効 いだろう。 率もよいだろうという考え方がある。この こて , yylex の主要部を List 19 に示す。 字句解析の後がいきなりエラー表示部の 方法はシンプルて効率もよいが , 先読みし この関数て、は , 先読みを維持するために 解説て、ある。本来ならここて、 , コード生成 た文字を静的な変数に保存しておかなけれ 常に文字を参照してから次の文字を読んて、 部やインタブリタの説明をしたいところな ばならないのがやや難点て、ある。 いることがわかるだろう。これに対して , のだが , これらは前提となる知識があまり Fig. 10 字句解析部の構造 Fig. 11 構文解析の三階層 構文レベル yylex symbol—dump identification fix—number get—string skip—comment readch トークンの読み込み 記号表の一覧表示 識別子の読み込み 数値の読み込み 文字列定数の読み込み コメルトの読み飛ばし 1 文字の読み込み YYPa 「 se 呼び出し 字句レベル yylex 呼び出し readch 文字レベル 特集 c プログラム設計技法 71

9. 月刊 C MAGAZINE 1993年5月号

ln れ川 a ⅱ行 om 膈 m 川計 Ma れ門 ライフボート WATCOM C / 386 Q WATCOM C/386 の Windows プログラムサンプルの makef ⅱ e を 見ると , w ⅱ nk の応答ファイルで m axdata で最大ヒープ領域の大きさ を指定していますが , すべての 32 ビットヒープをリンク時に指定し なければなりませんか。 A 現在 , 32 ビット Windows スー 。イザ (WATCOM C / 386 に 付属している , Windows 上て、 32 ビ ットプログラムを動かすためのモ シュール ) は , アプリケーションの ヒープメモリを割り付けるために maxdata/mindata フィールドを使 用します。スーババイザは , まず , maxdata て、指定されたバイト数の メモリを割り付けようとし , これ に失敗すると , 64K バイト少ないメ モリて、再度試み , メモリ割り付け に成功するか , 割り付けようとす るメモリの量が , mindata て、指定し たバイト数より少なくなるまて、繰 り返します omindata て、指定したバ イト数のメモリが割り付けられな いときには , アプリケーションは 実行されません。 ヒープは , 通常の C のメモリマネ ージャによって維持され , malloc 関数と free 関数て、アクセスてきま す。実行時により多くのメモリが 必要となったときには , メモリマ ネージャはヒープを拡大しようと します。ヒープを拡大すると , W indows は十分に大きな連続したメ モリを見つけようとして , リニア メモリの中のメモリを移動します。 初期のヒープを制御するために , mindata と maxdata を使用し , ヒ ープを広げるときのバイト数を制 御するために , 変数 amblksiz を使 用して , リニアメモリの移動を最 少に抑えることがて、きます。 Q 16 ビットの Windows アプリケ ーションでは , プログラムにリソ ースをつけるのに , リソースコン パイラを使いますが , 32 ビットア プリケーションでも , リソースコ ンパイラを使うのでしようか。 A リソースを 32 ビットアプリケ ーションにつけるときには , 実際 には , Windows スーババイザにつ けます。 Windows スーババイザは 16 ビット Windwos アプリケーショ ンなのて、 , リソースコンパイラを 使って , Windows スーババイザに リソースをつけることがて、きます。 実際には , Windows スーババイザ を 32 ビットアプリケーションにつ ける WBIND というユーティリティ を使用します。 WBIND ユーティリティは , 自動 的にリソースコンパイラを起動し , Windows スーババイザにリソース をつけます。リソースコンパイラ へのオプション指定は ,WBIND の R オプションて、指定することカイき ます。 Q Windows に渡されるすべての ポインタは 1 6 ビットの fa 「ポインタ でなければならないのでしようか。 A 関数ポインタはすべて , 変換 なしに Windows に渡されます。 W indows がコールバ、ツクする関数 は , ェクスポートされなければな らず , 16 ビット関数てなければ工 クスポートて、きないのて、 , ほとん ど変換は不可能て、す。 なります 16 ・・・・・・〃関数はポイン インタは変換されては困ることに 返してきた値など ) 。そのようなポ ます ( たとえば , GlobaILock 関数が トしなければならないときがあり に変換されているポインタをセッ きどきすて、に 16 ビット far ポインタ ンタに変換します。ところが , と ows て、使用てきる 16 ビット far;* イ リニアアドレスのポインタを Wind wsAPI 関数は , 自動的に 32 ビット るために使用される通常の Windo A Windows プログラムを作成す すか。 はどのようなときに使用するので ている関数がありますが , これら 用の関数には , 先頭に 16 ″がつい WATCOM C/386 の Windows Q ーチンに制御を渡します。 r0C16 関数て、指定された 32 ビットル す。このコールバック関数は GetP る 16 ビット far.-tk インタを返しま コールバック関数として使用て、き GetProc16 関数は , Windows が 出すことがて、きます。 ncti 。 n 関数を使って間接的に呼び HandIe 関数と InvokeIndirectFu ます。また , GetIndirectFunction の Windows 関数に渡すことがて、き は , 関数ポインタを要求するほか Windwos から得た関数ポインタ の方法があります。 etProc16 関数を使います ) のふたっ indows スーババイザから得るか (G etProcAddr 関数を使います ) , W Windows から得るか ( たとえば , G 得るには , 16 ビット far ポインタを 関数への 16 ビット far ポインタを タ変換を行わず , 単純に Windows に直接ポインタの値を渡します。 この 16 ・・・・・・〃 API 関数のリスト が , TWATCOM C / 386 User's G uideJ の付録「特殊な Windows A PI 関数」にあげられていますのて、 , 参考にしてください Q WATCOM C / 386 は 32 ビット フラットモデルのコードを生成す ると思いますが , Windows の 32 ビ ットコールバック関数には fa 「キー ワードがついています。なぜ , 32 ビットコールバック関数は fa 「関数 なのですか。 A コールノヾックルーチンは , FA R として宣言されているのて、 , コン パイラはそのプロシージャからの リターンとして , FAR リターンの コードを生成します。 32 ビットコ ールノヾックルーチンはスーノヾノヾイ ザから FAR コールされるのて、 , の FAR リターンが必要になりま す。 コールバックルーチンはアプリ ケーションの 32 ビットリニアアド レス空間にあるという意味て、は , まだ , near て、あるといえます。 near て、あるということは , 正し くコールバックするための 16 ビッ トプロシージャを設定するために GetProc16 関数に渡す 32 ビットコ ールバック関数のオフセットのみ を渡せばいいということを意味し ます。 実際 , GetProc16 関数は PROCP TR 型を引数とし , この型の大きさ は , 4 バイトてす。コンパイラはオ フセットのみを引数として生成し ます。 lnformation from Compiler Makers 147

10. 月刊 C MAGAZINE 1993年5月号

ープロクラミンク熨場 Dr. 望洋の - スタックを確保・初期化する関数 スタックに対する各種の操作 List LiSt int StackAIIoc(Stack *s, int max) 3 : s->ptr 4 : 5 : s—>max return ( ー 1 ) : 8 : 9 : 1 : / * - ースタックにデータをブッシュ 2 : int StackPush(Stack *s int x) if (s->ptr > = s->max) return(-l); 5 : s->stk[s- 〉 ptr 十 + ] return ( の ; 10 : / * ーーースタックからデータをポップーーー * / int StackPop(Stack *s int *x) は (s->Ptr ←の 13 : return(-l); return ( の : 1 9 : / * ーースタックを空にする 20 : void StackClear(Stack *s) 22 : 23 : } 25 : / * ーーースタックを解放する一一 * / 26 : void StackFree(Stack *s) if ()- 〉 stk ! ニ NULL) 28 : free()- 〉 stk) : 29 : 30 : } if ((s->stk ー calloc(max, sizeof(int))) = NULL) { X : s—>max max; return ( の : Fig. 2 スタックの構造 s->ptr max 個 Pt 「 末尾のデータ 先頭のテータ することに注意していただきたい。これに 予防的プログラミング よって , メモリが確保て、きなかった場合は , List 3 の 4 , 13 行目に注目していただきた 配列の大きさが 0 て、あることが記憶され , 以 降の操作て、不正に配列領域 stk にアクセスす い ① if (s->ptr > = s->max) ることはて、きなくなる。 さて , 実際にスタックに要素を積む操作 ② if (s->ptr く = の をブッシュする ( push ) といい , 取り出す操 List 3 に示した , スタック操作の関数のみ 作をポップする ( p 叩 ) という。 を正しく使用して , スタック操作を行って いれば , ptr は 0 以上かっ max 以下て、あること Stack 型に対してブッシュする関数 Stack が保証される。したがって , これらは , Push やポップする関数 StackP 叩などを Lis ① if ()- >ptr s- > max) こて、 Stack 構造体のメンバ pt t 3 に示す。 ② if ()- >ptr r は , 現在積まれている最後のデータの次の ックと関数呼び出し のように記述してもよいはずて、ある。 場所 ( = 配列の添え字 ) を指すようにしてい しかし , プログラムのバグなど何らかの る ( すなわち現在積まれているデータの個数 理由によって ptr の内容が破壊されたとき 実際に「スタック』を使用したことがあ を格納する ) 。 に , ptr は 0 以上 max 以下の値を持っとはかぎ もちろん最後の位置を指すようにしても るだろうか ? との問に対して , 前回の例 らなくなる。ここて、示したような記述を行 のように , 具体的なプログラムを作成した よいが , Stack 型を扱うすべての関数に対し うことにより , そのような場合ても正しく ことのある人を除けば , 「 No ! 」と答えるのて て一貫性を保っ必要がある。 なお , スタックの利用を終了した後は , 動作する関数となる。 はないだろうか。 このようなプログラミングの方法を予防 ところが , 読者の皆さんは , 無意識のう 必ず StackFree を呼び出して , メモリの解放 的プログラミングという。 を正しく行わなければならない ちにスタックを使用しているのて、ある。 【演習】以下の関数を作成せよ。 ( 1 ) スタックの大きさを返す関数 int StackSize(Stack * s) ; ②スタックに積まれているデータ数を 返す関数 int StackNo(Stack * s) ; ( 3 ) スタックが空てあるかどうかを返す 関数 int StacklsEmpty(Stack * s) : D 「 . 望洋のプログラミング道場 113