Java Advisor 丘 om Performance Computing David Detlefs 気分転換のための計算 コンピュータのプログラミングで生計を立てているにも かかわらす、迎未のプログラムを書きたいという彳力に駆 られたことはないだろうか。私の場合は、この発イ勧起き たらあまり逆らわないようにしている。クラシックのピア ニストがジャズのリフをかき鳴らしてみるように、気晴ら しに何か違ったことをするのはよいことだ。まったく関係 のなさそうなプログラムの開発から、あとで役に立っスキ ルを得ることも多い ( もちろん、研究という気楽な仕事を していて、プロジェクトの期限とはほとんど縁のない不劫ゞ いうのもおこがましいか ) 。 私の蜷丘の気晴らしのきっかけは、同僚の Anne An- derson か私たちのグループにメールである問題を送って きたことだった。間題とは以下のようなものである。 に、すこし壊れていて数字キーが、、 1 " しか使えない電卓が ある。この電卓でキーを 20 回以 E 打たすに、、 75 " を表示 できるだろうか。なお、電卓には十、 十という 4 構造化すべきなのだろうか。ます、 18 回以下のキー入力 のシーケンスをすべて洗い出し、それが 75 を導くかどう か試すというガ去がある。電卓には使えるキーが 8 つある ので、長さが 18 のシーケンスは 818 、つまり 254 個ある ことになる ( 18 より短いものはまだ含まれていない ) 。最 近のコンピュータは速くなったが、それでもこれを言 1 算す るには時憫がかかるだろう。 したがって、もうすこし工夫が必要である。これはそれ ほど難しいことではない。さきほどのシーケンスに、演算 キーと瓜だけの、数字をまったく含まないものが 718 個 あることに気づけばよいのだ。未のある数値を求められ る有効な文字列だけを選べば、、、無駄な " シーケンスの大 半を除外することができる。 有効な文字列の部分集合を定義する場合、文法は効果的 な手段である ( 部分集合は、言語内では文去によって定義 される ) 。そこで、私は電卓言語のための文法を作ってみ た。以下に示すのカ撮初に作ったものである ( プログラム 言語の去を定義する際に使われるバッカス記去 (BNF: Backus-Naur Form) で言己してある ) 。 つの基べ寅算キーと、 、開き括弧閉し括弧のキーがあ る。ー・縞 ; の電卓とは異なり、れ * = はれの 2 乗にならない。 電卓を手にあれこれ試してみると、 19 回のキー入力で 答を得るのはそれほど難しいことではなく、実際にほとん どの挑戦者が成功した。その一方で、これより少ないキー 入力で答を出せた者はいなかった。しかし、はたしてそれ か不可能なのか誰にも分からす、何人かは間的に可能な はずだと考えた。興未を抱いた私は、総当たり的な検索で 答をみつけだすプログラムを書いてみることにした。今回 は、このプログラムの開発過程を、間違いや行き詰まった 点 ( の一縞分も含めて紹介する。 プログラムを趣床て書いている場合でも、すこし秩序だ てて考えてみれは効率的である。最初のステップとなるべ きなのは問題の分析だ。総当たり的な検索とはどのように UNIX MAGAZINE 2001.2 Term ParenTerm ー BinaryTerm ー Equa1Term ー Numb e r B inaryTe rm , ( , Term Term ) 十 ) ー Term ー Term , / , Equa1Term Number : : = ) 1 ' ー Number Term Term , 1 ' 分析用の道具としてみると、文法にはプログラム ( すく 113

int i, init, state_offset ; int state = int last = lastst Cmach] ; 必要な変数を宣言したあと、変数 last を、 NFA を表 すために用いる添え囎物 ) なかでもっとも大きな値である lastst[mach] にしています。 次は、 firstst [mach] から上で計算した last までの for ループです。 firstst [mach] は NFA を表すために用いる 添え字君 ) なかでもっとも小さな値ですか、この硼を 調べればかならず NFA 本を謌・ヾることになります。 for ( i firstst [mach] ; i く = 1ast ; 十十 i ) こでおこなわれる処理は重要ですが、実際の処理をみ ると思ったより叫屯です。新たな状態を作成しますが、そ のとき遷移のラベルとしてはもとの状態に対応するものを コピーします。 state = mkstate( transchar[i] ) ; さらに、そこから遷移がある (transl が NO-TRAN- SITION ではない ) 場合は、その遷移を新たな状態からも 作成します。ただし、遷移先としては transl[i] 十 state—i を使います。この式は、、、 1 番から 5 番にコピーしている のであれば、遷移先が 2 番ならコピー先では 6 番に遷移 したらよいだろう " という意味です。 if ( transl [i] ! = NO—TRANSITION ) mkxtion( finalst [state] , , ・ transl [i] + state if ( transchar[i] = SYM_EPSILON & & trans2 [i] ! = NO—TRANSITION ) mkxtion( finalst Cstate] , trans2[i] 十 state accptnum [state] accptnum [i] ; trans2 についても同様に処理したあと、 accptnum を 調整してループを終了します。 驚いたことに、この関数では実際にその番号が必要かど うかはまったく関係なく、最小の値から最大の値まで、す べてをコピーしています。たしかにこれなら、 NFA に関 連するものはコピーすることかて、きます。本当にこれでよ いのか考えてみましたが、構文角 i 器での角財斤と並行して NFA を構築しているため、処理の対象はつねにいま見て 112 いる点よりもほんのすこし前のものとなっています。ま た、連結や選択をおこなう場合も、あいだにまったく無 関係な NFA が入ってくることはないため、このような簡 単なコピーガ去でも大丈夫です。万一よけいな情報までコ ピーしていたとしても、その部分は利用されす、メモリを 自するという点を除けばとくに問題はありません。 最後に、 firstst 、 finalst 、 lastst のイ直をイ正し、 init の flexfatal ( if ( state = = 値を返せば NFA のコピーは完了です。 dupmachine ( ) ” ー ( "empty machine in = init = mach 十 firstst [init] finalst [init] lastst [init] state_offset return ; state lastst [mach] 十 state—offset; finalst [mach] + state—offset ; firstst [mach] 十 state—offset ; state_offset ; 無駄な領域はすべて除いて本をコピーするにちがいな いと思いこんでいただけに、この角夬方法はすこし意汐トで ☆ 今回は flex コマンドが入力中の正規表現を NFA に変 換する部分について解説しました。 flex では、複数の酉改」 を使って NFA を表現しています。また、 NFA に必要な 領域をできるだけ分散させないようにする手法を用いて、 簡単な NFA のコピーを実現しています。 次回は、今回作成した NFA を処理して最終的に DFA を入手する過程をみていく予定です。 ( たしみ・ひさかす ) UNIX MAGAZINE 2001.2

図 7 ポインタを用いたデータ橢告 NO typedef struct struct int } state; typedef struct struct int struct } trans; NO state trans trans trans state YES trans ; accept ; next ; transchar ・ dest ; ASCII 好評発売中 ! Java フログラミング・ノート 国際化と 日本語処理 CAFE BABE 0 製ー X 国際化と日本語処理 ( A ド第第 A ・第 プログラミング・ノート ava ・本体 3 , 000 円十税 ・ ISBN 4-7561-3481-5 ・ A5 判、 312 ページ ・風間一洋著 Run Anywhere" を目指すプログラマー 解説する。真の意味での "write Once, サンプル・プログラムを示しながら平易に プログラミングに必須の知識を数多くの Java による日本語処理、さらには国際化 目次から に最適の 1 冊。 これは、 NFA を操作するにはその頁およひ末尾の状 態を操作すればよいという点に注目し、さらに状態や遷移 をそのまま構造体にマッピングしたものです。このデータ 構造を使って図 4 の NFA を表現したのか図 7 です。 このようなデータ構造を使用する場合、 NFA のコピー は不可能ではありませんが、ひどく面倒になります。たと えは、右端のノードは 2 つのポインタに指されています が、ノードをコピーしている最中につねに 2 つのノード か伺しかどうかを調べながら処理しないと、このようなノ ードでも別のノードとしてコピーしてしまうことになりま す。また、 こで作成した NFA には区しがありませ んが、一殳には NFA の前のほうに戻る遷移も多くありま す。これらをすべて正しく処理するのは、無理ではないに しろかなり面倒です。 一方、 flex では基本的にメモリ領域のコピーだけで NFA のコピーができるようになっています。この処理を おこなうのが nfa. c ファイルで定義されている dupma- chine 関数です。それでは、この関数をみていきましよう。 引数は、コピーしたい NFA を表す整数のみです。 int dupmachine ( mach ) int mach; UNIX MAGAZINE 2001.2 1 章 2 章 3 章 4 章 5 章 6 章 7 章 8 章 9 章 10 章 1 1 章 12 章 付録 Java はどんな言語か 国際化と地域化 Unicode ロケー丿レ 工ンコーティング タイムゾーン リソースパンドル フォーマット出力と解析 文字列の比較 テキストの境界解析 インブットメソッド 文字の表示 Unicode プロック / ロケール一覧 / 工ンコーディング名一覧 / タイムゾーン D 一覧 / ユーロ通貨記号への対応 株式会社アスキー 111 電話 (08) 535 ト 8194 出版営業部 〒 1 5 1 ー 8024 東京都渋谷区代々木 4 ー 33 ー 1 0