とがて、きません。そのため , 任意の 1 バイト を判断するためには , 文字列バッフアの先 頭から根気よくチェックしていくわけて、す (List3) 。 なお , この関数は画面表示やプリンタ出 カて、文字列データを編集する ( 最大出力可能 桁数が , 実際のデータサイズよりも小さい ) 場合のサプルーチンとしても利用て、きます。 文字数を得る関数信 et - st 「 / n 関数 ) ライプラリて、は , 文字列の終わりを NULL ( 0X00 ) て、処理しています。しかし , キー入 カて、は NULL コードは入力されません。 こて、は , その代わりとして空白 ( 0X20 ) を用 いています。このため , 空白は特殊な扱い になります。 つまり , 今回作成するキー入力関数は , 文字列の挿入を行うめ , 文字列の終わり の空白をデータとして認識しません。した がって , 文字列バッフアの終わりの空白を 除いた文字数を得る関数を作成します / * キーポード定義 * / ☆☆☆ " , 42 ) ; List 6 44 : 45 : 46 : 47 : 48 : 49 : 50 : 51 : 52 : 53 : 54 : 55 : 56 : 57 : 58 : 59 : 60 : 62 : 63 : 64 : 65 : 66 : 68 : 69 : 74 : 77 : 80 : 83 : 84 : 85 : 88 : 89 : 90 : 92 : 93 : 94 : 95 : 99 : 101 : 102 : 103 : 104 : 105 : 106 : 107 : 108 : 109 : 1 10 : 111 : 112 : 1 13 : 120 : 122 : VO i d VOid VO i d VO i d VO i d VO i d VOid VO i d VO i d VO i d VO i d VO i d VO i d / * ma i n key-asgn(int mode) : casel ( ) : case2 ( ) : case3 ( ) : cls(); clearl(int 、 / put-str(int x, nt y,char *buf, int count) : csr-posit(int x, int y) : put-chr(int x, int y, char chr) : buzzer() : csr_fwd() : csr-back() : color(char *attr, char *colorno) : VO i d main() str[60], ichrC2]; Char int workno, x, y, cnt; key-asgn ( の : do { c 1 s ( ) : c010r(REV, SKY) : put-s tr ( 18 , 2 , " ☆☆☆キー入力サプルーチンテスト put ー str ( 25 , 14 , " 処理番号を指定してください。 " , 28 ) : coIor(0RG, SKY) : put-str(30, 10. " 9 : 終了 " , 8 ) : put-str(30,8,"3 : バイト数の取得 " , 18 ) : put-str(30,6,"2 : 文字列種別の取得 " , 2 の ; put-str(30,4,"I : 文字列入力 & 表示 " , 2 の : color(0RG, WHITE) : put ー str ( 0 , 16 , " 処理番号 = " , 10 ) : (List4) 。 画面に送らないのて、 , 表示のスヒ。ードアッ す。とくに画面表示て、は , 余分なデータを 力の際のサプルーチンとしても利用て、きま なお , この関数は画面表示やプリンタ出 プに貢献します。 116 CMAGAZINE 19 4 つけを元に戻しています。 の割りつけを変更して , さらに出口て、割り プログラムの先頭て、 , 亠および ムは , List6 のようになっています。 今回作成した関数をテストするプログラ テストプロクラムについ ( ます。 字数に関係なく , 任意の文字数を出力て、き き渡します (List5) 。これて、 , バッフアの文 引数を 1 個追加して , 最大表示文字数を引 前回紹介した put str 関数を変更します。 pu st 「関数の変更 whiIe(workno!=9) : key-asgn(l) : 100 : / * casel c010r(0RG, WHITE) : gets(str) : workno=ato i (str) : switch(workno) case 1 : casel ( ) : break; case 2 : case2() : break; case 3 : case3() : break; / * キーポード定義復旧 * / VO i d Char int casel ( ) ichr[ 幻 : if(rc==011rc==I) put-str(), 19 , " 入力文字列 = rc=get-lchar(ichr) : put-str(0,18," 入力 = c 厄 arl ( 19 ) : clearI(18); put-str(12, 19. ichr,2); csr-posit(), 20 ) : printf(" 入力データ種別 = 0xX02xYn",rc); get-lchar(ichr) : / * 確認 * / return : 121 : / * case2

emental 5 蓄「 i れ 9 5e0 「 h in ( List 2 int inc-search(STÅRRAY arr, int imax. int *ptr-start, int *ptr_end) 75 : / * く ESC > キーが押されると探索を放棄して i nc_search ( ) は一 1 を返します。 74 : / * ptr-end はそれぞれ、部分合致した最初の項目のインデクスと最後の項目のインデクスをポイントします * / 76 : 88 : 96 : 98 : 99 : 100 : 101 : 102 : 103 : } int int int STR end / * get-range() コール用の引数 * / / * get-range() からの帰値、デフォルトは 1 * / / * 最初と最後の合致項目のインデクス * / / * 探索開始位置 * / whi 厄 ( ()h = getkey() ) ! = ・ \ r ・ & & ch ! = ESC & & ()K = get-range(ch. base, inax. &first. &last))) { / * く C R> やく ESC> は押されなかったし、無合致でもない * / / * adjust val ue Of end * / / * and Of start first,last,ch; OK start, end; *base; lmax; base arr; start end start 十 last; start 十 = first; if (strcmp(arr[start], arr[end]) = 0 ) last ー first; / * 探索範囲を更新する * / = &base[first] [ 1 ] : / * 探素位置を更新する * / / * 部分合致である * / / * 完全合致が見つかれば終わる * / INX base e ー se break : if ()h = ESC) return(-l) : *ptr_start = start; *ptr-end = end : return (OK) : / * 探索中断なら一 1 を返す * / / * でなければ通常の帰値を返す * / 120 : { 28 105 : 106 : 107 : 109 : 1 10 : 112 : 113 : 114 : 115 : 116 : 118 : } 121 : 122 : 123 : 124 : 125 : 126 : 127 : 128 : 129 : 130 : 131 : 132 : 133 : 134 : 135 : 136 : 137 : 138 : 139 : 140 : 141 : 142 : 143 : 144 : 145 : 146 : } 119 : ma i n ( ) return (ch) : putch(ch) : while ((ch = toupper(getch())) ! = 'Y' & & ch ! = printf("Yn もう一度やる ? (Y/N) " ch; Char int do-again(void) / * ます。その入力文字が帰値です。 104 : / * 以下は単に、漸進的探素をデモするためのコードです * / STARRAY arr = { "Anderson" "Bradley", "Burke" "Geary , ” Byrnes ” "Pederico ” , ” Fikar" "Martino ” , ” Milne ”” M ⅱ no , ” Grando ” ” Haas" , ”し eh ” Lemke ”” Mahoney "Martin ” "Rivers"} : ” Montgomery" ” R ivera 108 : / * do_aga i n ( ) はユーザに・もう一度やる ? (Y/N) ・というプロンプトを出し、・ Y ' か・ N ・が入力されるのを待ち * / k. maxindex, start, end; int / * 探素対象の文字列を表示 * / for ( k ニ 0 : k<=MAXSTR-I : k + + ) if (arr[k] [ 0 ] / * 漸進的探素の実行 * / putch ( ・ for (k=l : k ← 80 : k + + ) else printf("X-20s",arr[k)) : break : printf("Yn"); maxindex switch (inc-search(arr,maxindex,&start. &end)) { pr i ntf (" \ n 探素文字列を入力してください・ case case case ー 1 : pr i ntf ( " Yn ユーザによる中断です . つ : break; 0 : pr i ntf ( " Yn 合致が見つかりません . つ : break; 1 : pr i ntf (" Yn 合致したのは : Yn") : for (k=start; k く =end; k + + ) printf("X-20s", arr[k]) : printf("Yn") : while (do-again() CMAGAZINE 19 4

List 1 150 : } 149 : 148 : 147 : 146 : 145 : 144 : 143 : 142 : 141 : 140 : 139 : 138 : 137 : 136 : 135 : 134 : 133 : 132 : 131 : 130 : 129 : 128 : 127 : 126 : 125 : 124 : 123 : 122 : 121 : 120 : 1 18 : 113 : 1 10 : 109 : 108 : 107 : 106 : 105 : 104 : 103 : 102 : 101 : 100 : Case 叩 -MUL: if (isConst(Ieft) Ⅱ isVariabIe(Ieft)) exchange(left, right) ; if (isConst(right)) { OPtype) : right) : gencode ("YtaddYt%aYn" popdx ( ) : genexp(right) : pushax() : genexp(left) : } else { gencode ("YtimuIYt%vYn" genexp(left) : } else if (isVariabIe(right)) { OPtype) : gencode("%timul%t%ayn" OPtYPe• right->e value) : gencode ("YtmovYt%a, XdYn" genexp(left) : genexp(left) : Case 叩 -MINUS: gencode ("YtmovYtal, ahYn") : e I se gencode ("YtmovYtax, dxYn") : if (optype = gendiv(right, left, optype, Case op-. MOD: gendiv (right, left, optype, Case OP-DIV: YES) : OPtYPe) : Case op-BNOT: gencode ("YtnegYt%rYn" genbool (), 0 , label = gensym()) : Case op-PREINC or op-PREDEC or OP-POSTINC or op_POSTDEC: genlabel(label): genbool (), b 引 = gensym ( ) , の ; Case OP ユ OR : genlabel(label) : Case 叩 -LAND: genlabel(label + l); genexp(p->e-third) : genlabel(label); genjump(label + l) : genexp(right) : genbool (left, 0 , label) : labe 1 gensym() : = gensym() : Case 叩 -COND: genexp(right) : genexp(left) : Case op ー B00 し : gensh iftop(p->opcode, left, right, optype) : Case op_SHR or op_SH し : genexp(right) : genexp(left) : Case op-COMMA: genbitop(p->opcode, left, right, optype) : Case 叩 -AND or 叩ー OR or op_XOR: OPtYPe) : gencode("YtnotYt%rYn" genexp(left) : bug("genexp") : p->opcode) : printf("p->opcode = %dYn ” Default: genassignopRef(). YES) : / * YES, we need val 0f this op * / Case op-ASSIGN-0P_R: genassign 叩 (), YES) : / * YES, we need val of this op * / Case op-ASSIGN-0P: genincdec(p->opcode, OPtYPe, left, p->misc) : コンノヾイラ の内部を詳解 ップする ⑤③ , ④の結果を加える という手順て、コードを生成します ( 54 ~ 60 行 ) 。 ほとんどの演算子についても , 加算と同 じようにして場合分けを行ってコードを出 力するようになっています。誌面にかぎり があるのて、 , ここて、は特長のある演算子の みを説明します。個々の演算子については ソースプログラムを読んて、ご理解ください 副作用をもつ演算子 通常 , 演算子はオペランドの値を利用し て何らかの計算を行います。しかし , なか にはたんに計算するだけて、はなく , オペラ ンド自体を変更してしまうものがあります。 たとえば代入演算子は , 左辺に値を代入し てしまいます。このような演算子を「副作 用 (side effect) をもっている」といいます。 これから , 副作用をもつ演算子について考 察しましよう。 副作用をもつ演算子として , 単純な代入 式 (a = b など ) のコードについて考えてみま ①右辺のコードを生成する が変数て、あるときには , のふたつのパターンに分類て、きます。左辺 ( b ) 左辺が変数でない場合 ( a ) 左辺が変数である場合 しよう。代入式は , とします。左辺が変数て、ないならば , 生成する ②①の結果を変数に格納する MOV 命令を yacc による C コンバイラブログラミング 77 とします に格納する命令を生成する ③の結果を DI レジスタのさすアドレス ップする ②て、ブッシュした値を DI レジスタにポ 右辺のコードを生成する BX レジスタをブッシュする レジスタに得られる ) 左辺のコードを生成する (l-value が BX ⑤ ④ ③ ② ①

開いているセグメントをクローズします。 コード生成のバターン 木構造をトラバースして , コードを生成 する関数は genexp( ) て、す。 genexp( ) の本 体は , ひとつの大きな switch 文から構成さ れています (List1)0 この switch 文は , ノー ドの種類によって分岐しています。処理が 簡単な演算子については , swit 曲文の中て、 直接コードを出力してしまいますが , 処理 が複雑な演算子の場合 , 下請けのルーチン を呼び出すようになっています。 コード生成の基本的な方針は , 連載第 2 回 のミニコンパイラて、説明したとおりて、す。 加算を例にとっておさらいをしてみましよ う。 List1 の 45 行目から 60 行目まて、が加算の 処理て、す。 まず , 最初に左辺が定数か変数て、あれば , 左右両辺を入れ換えます。これは , パター ンの判断を簡単にするためて、 , 可換な演算 子にのみ有効て、す。このようにすれば , 定 数と変数のチェックは , 右辺についてのみ 行えばよいことになります。もし , 右辺が 定数て、あれば , ①左辺のコードを生成する ②①の結果に定数を加える とします ( 48 ~ 50 行 ) 。左辺のコードを生成 するためには , 自分自身つまり genexp() を 再帰的に呼び出します。これ以降「左辺 ( 右 辺 ) のコードを生成する」という記述は , genexp ( ) を再帰的に呼び出す , ということ を意味しています。 右辺が変数て、あれば , ①左辺のコードを生成する ②①の結果に変数を加える とします ( 51 ~ 53 行 ) 。それ以外のケースな らば , ①左辺のコードを生成する ② AX レジスタをブッシュする ③右辺のコードを生成する ④②て、ブッシュした値を DX レジスタにポ 76 CMAGAZINE 19 4 List 1 gencode("%tmov%t%r, Xd%n", 叩 type, p->e-value) ; Case OP-STR : gencode("%tmov%tbx, offset DGROUP:@XdYn", p->e-value) : Case op-ASSIGN: genass ign (), YES) : / * YES, we need val of this exp * / Case op-Ct01 : genexp (left) : gencode ("YtcbwYn") : Case op-Ct0R: genexp ( left) : gencode ("YtcbwYn") : gencode ("%tmov%tbx, ax%n つ : Case op-It0C: genexp(left) : Case OP-I t0R: genexp(left) : gencode ("YtmovYtbx, ax%n") : Case op-Rt0C or op-Rt01 : genexp(left) : gencode("YtmovYtax, bxYn") : Case op-FUNC: genfuncall ( left, (TREE * ) right) : Case OP-ADD: if (isConst(left) Ⅱ isVariabIe(Ieft)) exchange(left, right) ; if (isConst (right)) { genexp(lett) : gencode ("Ytadd%t%r, %dYn", optype, right->e_value) : } else if (isVariabIe(right)) { genexp( left) : gencode ("YtaddYt%r, %vYn", optype, right) : } e I se { genexp(left) : pushax ( ) : genexp(right) : POPdX() : gencode ("YtaddYt%r, %aYn" Case op-SUB: if (isVariable(right)) { genexp( left) ; gencode ("YtsubYt%r, %vyn" } else if (isConst(right)) { genexp( left) : gencode ("YtsubYt%r, %dYn" } else if (isVariabIe(Ieft)) { genexp(right) : gencode ("YtnegYt%rYn" OPtYPe) : gencode ("YtaddYt%r, %vYn" 0PtYPe, left) : } else if (isConst(left)) { genexp(right) : gencode ("YtnegYt%rYn" gencode ("YtaddYt%r, %dYn" } else { genexp(right) : pushax() : genexp( left) : POPdX() : gencode ("YtsubYt%r, %aYn" Case 叩 -SCA し EADD or op-SCALESUB: genscaled(p->opcode, left, right) : Case op-DESCALESUB: gendescaled (left, right) : っ 0 4 ド 0 CD 7 8 9 0 14 ワ CO 4 LO 6 ー 8 9 0 1 よっ 0 っ 0 4 0 CD ー 8 9 0 1 っ 0 っ 0 -4 0 6 7 8 9 0 1 ワなっ 0 4 戸 0 々ー 8 9 0 1 人っ 0 っ 0 -4 0 6 行ー 8 9 0 -1 っ 0 っ 0 -4 - -0 6 っ 0 っ 0 っ 0 っ 0 り 0 っ 0 っ 0 っ 0 っ 0 っ 0 っ 0 っ 0 っ 0 っ 0 っ 0 っ 0 -4 -4 4 4 -4 4 4 4 4 4 - -0 戸 0 戸 0 戸 0 - -0 0 戸 0 戸 0 - -0 ロ 0 れ 0 6 6 ^ 0 6 ^ 0 6 6 0 ー 7 ー 7 7 7 7 行ー 7 7 8 8 8 8 8 8 8 OPtYPe, optype) : OPtYPe, right) : OPtYPe, right->e-value) : OPtype) : OPtYPe, right->e_value) : optype, optype) :

Cmqm.JTER LANGCIAGE , C によ 漸進的な文字列探索 LANGUAGE 提携記事 An lncreme String 5e0 代 h in ( Jim Ke 「「 / 岩谷宏訳 こでは , 文字列全体の合致を調べる線型探索やニ した Boyer ー M00 「 e 法もそのひとつでが , こ リズムか発表されている。本誌の 143 へ「ジ掲載 文字列探索の手法には , すでにい かのアゴ 分木探索ではなく , 部分的な合致から検索を開始 OMPUTER LANGUAGE/Dec. 1989 ) する漸進的探索を紹介する。この手法の特長は , 最初の数文字で検索を開始するので , 高速な処理 が可能になるということである。著者は , arr , base というふたつの変数を用いてこの探索アルゴリズ ムを平易に解説している。 探索とソートのルーチンは , いかなるプログラマ の道具箱にも欠かせないものです。数多くのソート ルーチンがプログラマの好みをめぐって競争してい ます。あるものは速度を売り物にし , あるものは , 複雑なデータ形式を扱えることを誇っています。 方 , 探索に関しては , 線型探索や二分木探索を使う プログラマが多いようです。本稿ではちょっと変わ った探索方法を述べますが , これは非常に有利な方 法になることもあります。 線型探索と二分木探索は , 入力としてキーとソー トすみリストを受け取り , キーと合致するリスト中 の項目の位置に関する情報を返します。どちらも , 普通のインプリメンテーションでは , 探索するキー の情報は最初にまるまる全体が渡され , 部分的な合 致を調べることはありません ( 訳注 l) 。 探索文字列の全体が渡されるのを待つのではなく , 文字列の各文字が渡され始めると同時に探索を開始 したはうがよい場合があります。たとえばキーポー ドからのユーサ入力文字列との合致を調べるときは , その文字列全体を待たなくても , 最初の 1 ないし数文 字からリスト中に合致の候補者をみつけることがで きます。この方法はふつう漸進的探索と呼ばれます。 漸進的探索のルーチンを作るときには , 設計方針 を決めなければなりません。探索文字列と合致する ものがなかったときにはどう処理すればよいか。な い文字列を探索文字列として受け入れるのか , ある いは拒否するのか。同じ項目が重複しているときは どうすべきか。ひとつの項目が , ほかの項目の部分 文字列 , とくに接頭辞である場合はどう処理するの か ( 訳注 2 ) 。リスト中に ZIMMER と ZIMMERMAN があ って , 探索文字列として ZIMMER をタイプした場 合 , 漸進探索ルーチンは戻り値として , 全合致 (ZIM MER との合致 ) を返すべきか , 部分合致 (ZIMMER MAN との合致 ) を返すべきか , ューザからの指示を 待つべきなのか。 こういう問いへの答えは別として , どんな漸進的 一般的に線型探索では , 探索対 象がソートずみのリストである ことを必要としませんが , 本記 事では線型探索もソートずみリ ストを対象にすることが前提と されています。また , 本稿で紹 介されている探索ルーチンは , 部分合致をネ探索成功″とみな してよいタイプのアプリケーシ ョン用ですから , 注意してくだ [ 訳注 1 ] [ 訳注 2 ] たとえば•program" で探索する リスト中に•program& ときに と *programming& があった場 24 CMAGAZINE 19 4 変数 ar 「と base の定義 typedef char STR[6] : STR arr ロ {"ABOVE", STR *base List 1 ” BASTE ” , ” B し UE ” , "CANE"} :

五ロ 用 応 [Tbl. 4 ] テータの種類 ANK 漢字 List 6 テータの種類 0X00 0X01 OxOd OxOc 0X08 Ox 1 2 Ox7f Ox 1 b Ox 1 e case2() ichr[2], st 「 [ 80 ] : *ptr; COUnt, rc : cIear1(18); clear1(19); clearl ( 2 の : gets(str) : count=strlen(str) : put -str ( 0 , 19 , " ←→でカーソルを検査したい位置に合せて ". 4 の : put-str ( 0 , 20 , " リターンを押してください ( E S C = 終了 ) ". 4 の : ptr=&str[0] : / * 文字列バッフアのアドレス設定 * / csr-posit(12,18); do rc=get-lchar(ichr) : switch(rc) case BACK: if(ptr>&strC0]) csr-back() : ptr-- : break; case FWD: if(ptr く &str[count csr_fwd() : ptr 十十 : break,• case CR: rc=test_str(str, ptr) : if(rc==ANK) put-str(0,21,"AN K " , 14 ) : else if(rc==KANJI 1 ) put ー str ( 0 , 21 ! " 漢字第 1 バイト " , 14 ) : e ー se put ー str ( 0 , 21 , " 漢字第 2 バイト " , 14 ) : ptr=&str[0] : csr-posit(12,18); break,• 123 : VO i d 124 : { 125 : Char 126 : Char 127 : i nt 128 : 129 : 130 : 131 : 132 : 133 : 134 : 135 : 136 : 137 : 138 : 139 : 140 : 141 : 142 : 143 : 144 : 145 : 146 : 147 : 148 : 149 : 150 : 151 : 15 2 : 15 3 : 154 : 155 : 156 : 157 : 158 : 159 : 160 : 161 : 162 : 163 : 164 : 165 : 166 : 167 : 168 : 169 : 170 : while(rc! =ESC) : c I s ( ) : 171 : 172 : return ; 173 : } 174 : 175 : / * case3 176 : 177 : case3 ( ) VOid 179 : ichr[2] . str[80] : Char 180 : scaIe[60]= static char . { " 123456789012345678901234567890123456789012345678901234567890 " } ; 181 ・ 182 : int count : 183 : 184 : 引 earl ( 18 ) : 185 : clearl(19); 186 : clearl ( 2 の : 187 : clear1(21); 188 : put ー str ( 0.18 , " 半角空白を混在して文字列を入力 " , 3 の : 189 : put-str(12. 20. scale, 6 の : 190 : put ー str ( 0 , 19. ”検査文字列 = ” , 12 ) : 191 : gets (str) : 192 : count=strlen(str) : 193 : str[count]=B し ANK; 194 : put ー str ( 0.21. " パイト数 195 : count=get-strln (str. count 十 1) : 196 : csr-posit(13,21); 197 : printf("Xd \ 0 ". count) : 198 : get-lchar(ichr) : 199 : cls(); 200 : return; DEL ESC H M E L R ( 1 ) 1 文字入力と入力データの種別表示 1 文字を入力すると , データを表示し て , データの種類 ( get lc れ ar 関数からの 戻り値 ) を表示します ( Tbl. 4 ) 。 ( 2 ) 文字列内の任意の文字の種別を判別 文字列を入力して , その文字列の任意 の場所の文字種別を表示します。このプ ログラムて、は , カーソルを左右に動かし て , 検査文字を指定するようになってい ます。 ANK, 全角文字を混在入力して , いろいろなカーソル位置て、検査してみて ~ ください またこのプログラムは , カーソル位置 とバッフア内の文字のポインタを制御す る例ともなっています。なおここて、は , 実際のカーソル座標 (), y) は制御してい ません。これについては , 次回のキー入 力関数て、解説します。 1 文字を検査するとカーソルは , 文字列 の先頭に復帰します。 ( 3 ) 文字列の正味バイト数を得る 文字列データの終端の半角空白 ( 0X20 ) を除いた正味バイト数を返します。さま ざまなデータを入力してみてください また , 全角空白 ( 0X8140 ) には対応して いませんが , 全角空白も除いたバイト数 を得るように ,get strln 関数を改造する のもよいて、しよう。 put-str(), 18 , " 検査文字列 = " , 12 ) : まとめ 今回は , キー入力のための基礎知識と周 辺の関数を作成しました。次回は , これら の関数を使って , 実際にキー入力関数を作 成します。 " , 12 ) : / * 確認 * / 応用 C 言語 117

五ロ 用 応 したい場合には , キーの割当てを変更して 第 1 バイトにそれ以外のコードを割当てる必 要があります。なぜなら ESC コードが入力 されてきたときに , ~ キーによる入力 なのか , ファンクションキーによる入力な のかが判断て、きないからて、す。 たとえば , PC -9800 て、は , ファンクション キー , 亠 , の各キーが ESC コー ドて、始まります。たとえば , ・亠 ( C 叩 y AII) て、は , テンプレートの文字列をコヒ。ーし ますが , 亠を押す代わりに ~ + と入力しても同じ機能が働きます (Fig. 2 ) 。 今回作成するキー入力関数て、は , 亠 とのキー割当てを変更しています ( フ アンクションキーなどの割当ても , 同様の 方法て、変更することがて、きます ) 。 キーの割りつけ - asgn 関数 ) ます , キーの割りつけを行います。例と して PC ー 9800 シリーズを取り上げます。 前述したように , ESC コードて、始まるキ ーを入力すると ESC との判別がて、きないの て、 , ESC コードて、始まるキーの割りつけを 変更してしまいます。ここて、は , キー入力 に直接関係する亠との割りつけ を変更します。 今回紹介するプログラムには記述してい ませんが , ファンクションキーやそのほか のキーも , 同様の方法て、キー割当てを変更 することがて、きます ( 詳細は , プログラマー ズリファレンスを参照してください ) 。 注意事項としては , プログラム中てキー 割当てを変更したら , OS へ復帰するときに は必ずキー割当てを元の状態に戻す点てす。 これは , キー割当てだけに限らず , 画面 , プリンタなど OS 環境のすべてに当てはまり ます。 現在市場に出回っているアプリケーショ ンのなかにはこのルールを守らないものも あり , そのため後から起動するソフトウェ アに原因不明の誤動作が発生してしまいま す。 OS は , 共有の環境てすからプログラム 内て変更した場合には , 必ず後始末をして から終了するように心掛けてください 応用 C 言語 113 List 2 / * 半角漢字定数 for HANKJ3 * / / * 半角漢字定数 for HANKJ4 * / / * 半角漢字定数 for その他 * / / * SPACE * / / * DE し * / / * Return * / / * BUZZER Asci i control COde / * HOME_CLR * / / * 漢字第 1 バイト * / / * 漢字第 2 バイト * / 0xlf 0X20 0X02 12 : #define CONSTI 13 : #define CONST2 14 : #define CONST3 16 : #def ine B し ANK 17 : #define FWD 18 : #define BACK 19 : #define INS 20 : #define DE し 21 : #define ESC 22 : #define CR 23 : #define BEL し 24 : #define HOME_C し R 26 : #define ANK 27 : #define KANJII 28 : #define KANJ12 29 : 30 : 31 : / * get-lchar 32 : *ichr) get-lchar(unsigned Char 33 : i nt 34 : { 35 : i nt rc , 36 : uns igned Char 37 : *ichr=0; 38 : *(ichr + 1)=0; 39 : 40 : begin: *ichr=getch() : if(*ichr く B し ANK) 42 : 43 : switch(*ichr) 44 : 45 : case BACK: 46 : case FWD: case CR: 48 : 49 : case INS: case ESC: 50 : case HOME_CLR: 52 : rc=*ichr; 53 : break; 54 : default: buzzer ( ) : 56 : goto begin; 58 : 59 : 60 : 62 : 63 : 64 : 65 : 69 : 70 : 77 : 79 : 80 : 82 : 84 : 0x0c 0X08 0X12 0x7f 0x1b 0x0d 0X07 0xle 0 1 2 hanknj; 1 バイト入力 * / / * 制御コード * / =0xfe)) else if((*ichr>=0x80 & & *ichr<=0x9f)ll(*ichr>=0xe0 *ichr く / * 全角文字 * / / * 漢字第 2 バイト入力 * / *(ichr + l)=getch() : / * 半角漢字コード * / if(*ichr==0x85) hanknj=*(ichr + I); if((hanknj く HANKJI) & & (hanknj>HANKJ2)) buzzer() : goto begin; else if(hanknj く HANKJ3) hanknj-=0xIf; else if(hanknj く HANKJ4) hanknj-=0x20; e I se hanknj + ニ0X02: *(ichr)=hanknj; / * ANK に変換する * / *(ichr + l)=o; rc=ANK; e ー se rc=KANJI 1 : else if(*ichr==DEL) rc=DE し : e ー se rc=ANK; return(rc) :

探索ルーチンでも , 探索に成功したのか失敗したの かという結果は返さなければなりません。部分合致 の場合には , どこまで合致したのかという範囲も , コール側に返さなけれはならないでしよう。 後で inc search( ) という C の関数を見ますが , れはある種の文字列の配列に対して漸進的探索を行 うルーチンです。今は詳しくは述べませんが , inc search( ) は部分的合致をみつけた場合は 1 を , 見つ からない場合は 0 を , そしてユーサが探索をアポート したら一 1 を返します。 漸進探索をインプリメントするときの基本的な考 え方を理解していただくために , 変数 arr と base を List1 のように定義する場合を考えてください。 最初の行で STR というデータ型を定義しています が , これは 5 文字以下の文字列を意味します ( C の文字 列には最後に 0 が必要であることを思い出してくださ い ) 。 2 行目で arr を 4 成分の文字列配列として宣言 し , 配列中の項目を定義しています。 3 行目で , base を STR 型の変数へのポインタとして宣言し , 配列 arr の起点を指すよう , base を初期化しています。これ らの宣言の結果を Fig. 1 に示します。 base と arr は STR 型のデータオプジェクトをポイ ントするので , Fig. 1 では , 下の関係が成立します。 Fig.1 a rr[0] base と ar 「の初期の配置 arr[l] arr[2] ↓ arr[3] ↓ A B 0 V E\O B A S T E\O B L U E\ 0 \ 0 C A N E\O \ 0 ba se [ 0 ] base[l] base[2] ba se [ 3 ] base [ 0 ] base [ 1 ] arr [ 0 ] arr [ 1 ] こで , 探索文字列の最初の文字として , ューザ が、、 B 〃を入力した場合を考えてみます。線型探索の ルーチンは単純に , 変数 base [ 1 ] と base [ 2 ] が部 分合致だと報告してくるでしよう。しかしューサが 探索文字列の次の文字を入力したときのために , 探 索ルーチンが新たな ( より絞り込まれた範囲の ) 探索 対象候補を報告してくるようにしたいものです。 れは Fig. 2 に示すように , base が arr [ ] の次の項目 の次の文字を指すようにし , base の最大インデクス を 1 とすることによって可能になります ( 訳注 3 ) 。 ューサが次の探索文字としてルクを入力したら , baseCO] から baseC1] までの探索をすればよく , そしてインデクス 1 ( base [ 1 ] ) だけが合致していると いう判断ができます。この例では , こで探索は終 了します。実質的に , base を文字列探索用の移動テ ンプレートとして使っています。探索文字が入力さ れるたびに , 合致を生じうるインデクスの範囲が計 算され , それに伴って base の値がシフトされます。 注意しなくてはいけないことが 3 つあります。 第 1 に , このアルゴリズムは探索対象文字列が文字 の 2 次元配列であることに依存しています。また , 文 字列中の文字がメモリ上で連続的に並んでいること を想定しています。第 2 に , base はここでは , 6 バイ トのデータオプジェクトをポイントしています。 れによって base [ 0 ] , base [ 1 ] , base [ 2 ] ・ のおのの間隔が正確に 6 バイトであることが保証さ れ , また arr の各成分間のオフセットもつねに 6 バイ トとなります。最後に , Fig. 1, Fig. 2 の base ポイン タで参照される文字列は , アルファベット順にソー トされています。ソートされているからこそ , 探索 文字の入力に伴って base の探索対象インデクス範囲 を一定の範囲へと絞り込んでいけるのです。 このような , オフセット ( = データオプジェクトの サイズ ) とソートという前提が崩れると , 探索は不可 能になります。たとえば Fig. 2 で base [ 2 ] が文字列 、、 ANE" を参照したとしたら , 文字列の配列はソート されていないということになります。 漸進探索のアルゴリズムが正しく動作するために は , base に加算する正しいオフセットがわかってい [ 訳注 3 ] て , 文字列がソートされていなくてはなりません。原書の Fig. 2 には , 「頭の、 B " に Fig. 2 。 B " を入力した後のポインタの配置 ↓ arr[l] ↓ arr[2] ↓ a 3 ] A B 0 V EXO B A S T E\ 0 B L U E\O \ 0 C A N E \ 0 \ 0 base [ 0 ] base[l ] ついては合致検分が終わったの で , 次はふたつ目の文字の (*BASTE& の第 A ″と•BLIJE& の in ( 5 ⅳ i れ 9 5e0 代 h An ー 0 ( 「 eme れ 0 ー 作が盛り込まれていません。 生つをポイントする」という操 C による漸進的な文字列探索 25

コンヾイラ の内部を詳解 LAND, op LOR というノードになりま す。これらの演算子は , オプジェクトコー ド中て、は比較命令 ( CMP 命令 ) と条件分岐 命令の組み合わせに展開されます。 比較・論理演算子を処理する関数は , genbool( ) , gencompare( ) , gencond jump( ) の 3 って、す ( List5 ) 。このうち , gen b001 ( ) が外部から呼び出される関数て、 , 残 りのふたつは下請けの関数て、す。まず ,gen b001 ( ) から説明しましよう。 genbool( ) は 3 つのパラメータを受け取り ます。第 1 パラメータは式の木へのポインタ て、 , ノードは op BOOL,OP LAND,OP BOOL のいずれかて、なければなりません ( と いうより , プログラムが正しければ , この いずれかになるはずて、す ) 。第 2 パラメータ は式を評価した結果が真だったときにジャ ンプするラベル番号 , 第 3 パラメータは偽だ ったときにジャンプするラベル番号て、す。 ラベル番号として 0 を渡すと , ジャンプする かわりに下に抜けるコードを生成します。 たとえば , genbool(), 10 , 0 ) ; とすると , 「式 e を評価して , 真だったら、、 @ 10 〃 このように , 「副作用のみが必要とされる 式が文として使われるときて、す。このよう というラベルにジャンプし , 偽だったらそ 場合には , 最適化したコードを出力する」と な場合には , genexp( ) のかわりに genex のまま下に抜ける」というコードを生成し いう方法は , ほかの演算子にも応用するこ ptop( ) を呼び出します。 genexptop( ) は , とがて、きます。このような演算子には代入 List4 のようになっており , 代入演算子とイ Fig. 1 論理演算子のコード生成 演算子 ( 十 = , / = など ) と , インクリメント / ンクリメント / デクリメント演算子を別扱い ( 1 ) A & & B ー ) がありま するようになっています。その他の演算子 デクリメント演算子 ( 十十 , す。代入演算子は genassignop( ) と genas の場合には ,genexp( ) を呼んて、従来どおり if A が偽 then 90t0 F signopref( ) て、処理されます。前者はオペラ の処理を行います。 if B か偽 then goto F ンドが数値て、ある場合 , 後者はオペランド goto T 比較演算子と論理演算子 がポインタて、ある場合を処理します。イン クリメント / デクリメント演算子は , 副作用 のみが必要な場合には genincdectop( ) , 式 前回に説明しましたように , Cm コンパイ の値も必要となる場合には genincdec( ) て、 ラの内部て、は比較演算 , 論理演算の結果を 処理されます。これらの関数は , パラメー 表す型として b001 型を導入しています。比 タとして , 木構造へのポインタのほかに , 較演算子 ( = 式の値が必要とされているかを示すフラグ 理否定演算子 ( ! ) は正規化され , op BOOL を受け取るようになっています。 というノードて表現されます。また , 論理 演算子の副作用のみが必要とされるのは , AND 演算子と論理 OR 演算子は , それぞれ op List 3 genexp(left->e_left) ; if (i sConst (right) & & ! needValue) gencode ("YtmovYt%oCbx] , %dYn" else { pushbx() : genexp(right) : popdi ( ) : gencode ("YtmovYt[di] , %rYn" ・ 4 戸 0 《 0 行ー 8 0 》 0 1 よっ 0 っ 0 -4 11 、 1 1 よ 11 1 人 11 っ 0 っ乙っ 0 っ 0 っ 0 right->e value) : p->optype, p->optype) : 関数 genexptop( ) 1 : / * genexptop generate COde for expression (with some optimization for top level) 3 : public void genexptop(EXPR *p) = NU しい 5 : 6 : switch (p->opcode) { 7 : Case op-ASSIGN: 8 : genass ign(), (O) : / * we only need side effect * / 9 : Case op-ASSIGN_0P: genassignop(), (O) : / * we only need side effect * / Case OP-ASSIGN-OP_R: genass ignopRef (), (O) : / * we only need side effect * / Case op-PREINC or op_POSTINC or op_PREDEC or 叩 _POSTDEC: 14 : genincdectop (P) : / * we only need side effect * / Default: genexp (p) : 18 : } List 4 return; ( 2 ) A ロ B if A が真 then goto T if B が真 then goto T goto F ※ T は真のときの飛び先 . F は偽のときの飛び先 yacc による C コンバイラブログラミング 79

を ion ( 「 5 List 3 --vprinter の使用例 * n 文字プリンタに出力する 5 : int pascal vprinter(); 5 : #define TABSIZ 8 1 : #inclu de く stdiO. h 〉 f00 DW ? bar DD ? となっていれば , mov [TYPE f00 P T R b a r ] , 0 は m 0 v CWORD PTR bar] のように機 能します。 TYPE の代わりには S 工 ZE を使ってください みてサポートされています ) 。 PC9801 版の Turbo Debugger の して起動しますにの機能は が 8086 と判定されても 80186 と仮定 プションを指定することて , CPU ger< は , コマンドラインに一 1 オ けてす。 PC9801 版 Turbo Debug- 80186 てあると認識させればよいわ す。つまり , Turbo Debugger に 80186 の命令セットを備えていま されていません。しかし , V30 は 専用の命令に対応する機能は用意 Turbo Debugger には , V30 A ませんか ? の拡張命令を使用することはでき 8086 と認識されてしまいます。 V30 るのですが , Turbo Debugger では CPI..J が V30 の機種を使ってい 0 れている命令てす。 ロセッサを操作するために用意さ ことはてきません。 ESC は , コプ X86 の命令セットを再定義して使う Turbo Assembler て、は , 80 になります。 いうシンポルを定義するとエラー Turbo Assembler で ESC と 0 Turbo Debugger でトレース しているときに GRCG / EGC に出力 した後でハングアップしてしまう ことがあります。 VX, RA など一部の機種て、 は , GRCG/EGC に特定の値 ()G モ ード = 1 , RMW モード = 1) を出力 した後て、は VRAM からの読み込み を行うとハングアップしてしまう ものがあります。 Turbo Debugger は , ューザ環境とデバッグ環境を 切り換えるために VRAM を参照し ていますのて、 , この状態て、デバッ ガに戻るとハングアップすること になります。 0 Turbo Debugger で , アセンプ ラモードで値を指定するのに OB や 2D などの値がうまく書き込めませ ん。 9E や OABC などは正しく書き 込めます。 A 数値の末尾の B , D は , 2 進 , 10 進を意味します。 16 進を表現す るためには , OBH, 2DH のように 末尾に H を付加してください 現在 , 弊社て取り扱っているス チューデントパックの価格は以下 のとおりてす ( 税別 ) 。なお , たい へん申し訳ありませんが , 振り込 み手数科などはお申し込みされる 0 2 : 4 : 6 : 8 : 9 : 11 : { 12 : 15 : 15 : 16 : 17 : 19 : 20 : 21 : 22 : 25 : 24 : 25 : 26 : 27 : 28 : 29 : 50 : 51 : 52 : 55 : 54 : 55 : 56 : 57 : 58 : } 59 : 41 : 42 : 44 : { 45 : 46 : } 47 : 49 : 50 : 52 : { 55 : 54 : } 10 : static size t pascal lputn(char * str, size t void * dontCare) static int C01 = 0 : switch ( * str) { 14 : while(n) { case case case do { if(fputc(' ' , stdprn) = =EOF) return n; } while ( 十十 C01 % TABSIZ); break; if (fputc('*r', stdprn) = =EOF) return n; if (fputc('*r', stdprn) ー = 刊 OF ) return n; C01 = 0 : break; C01 = 0 ; break; * 書式付プリンタ出力 45 : int lprintf(const char * fmt, default: if (fputc( * st, stdprn) C01 十十 ; break; str 十十 : return n; =EOF) return n; return vprinter( lputh, NULL, fmt' 51 : int vlprintf(const char * fmt, void * argp); * 書式付プリンタ出力 48 : / * return vprinter( lputn, NULL, fmt' argp); 方のご負担になります。なお , 送 料は , 価格に含まれております。 TurboC 2.0 ・ ・・・ 12 , 000 円 Turbo Assembler&Debugger 1 . 0 ・ ・・・ 12 , 000 円 Turbo PASCAL 5.5 ・・・ 12 , 000 円 Turbo PASCAL 5.5 profes ・ 24 , 000 円 sional lnformation from CompiIer Makers 151