DAEM 〇 NS& DRA 〇 NS 正規表現、スノヾ対 ~ ~ 用プラックリスト •William LeFebvre 正規表現 正規表現は UNIX ならではのものだ。それが何かを 知らなくても、 UNIX を利用したり管理することはで きる。しかし、正規表現の使い方を理解していなければ UNIX の性能を十分に引き出すことはできない。 経験を積んだ UNIX ューサーでも、正規表現につい ておさらいしておけは役に立つだろう。 UNIX に実装さ れた正規表現のなかには、めったに使われず、とりあげ こでは正規表現の基礎 られることもないものがある。 を復習し、強力だがあまり利用されない記法について説 明しよう。 正規表現の歴史は 1950 年代にまで遡る。数学者 Ste- phen Kleene が、、有限オートマトン " と呼はれる数学的 構造のための記法を考案し、コンピュータ科学者はこれ がコンパイラの字句解析 (lexical analyzer) に役立つ と考えた。その結果、 UNIX のユーティリティ lex の入 カ言語には正規表現が多用され、 grep 、 ed 、 sed 、ⅵ、 Perl などの多くのユーティリティでも使われている。 のように、正規表現はたいへん有用と考えられたため、 UNIX 開発者は標準の C ライプラリにそれをサポート する関数群 (regexp) を追加した。 正規表現は入力文字列の集合を表す。コンピュータ は、与・えられた文字列が正規表現で記述された集合に含 まれるかどうかを調べて結果を返す。ほかの OS は確定 した文字列でしかファイルを検索できないが、 UNIX は 正規表現と一致する文字列によるファイル検索の仕組み を備えている。 正規表現の実装にあたって、従来の記法は正規表現の UNIX MAGAZINE 2001.1 from Performance Computing 基本的な概念を損なわないように拡張された。 UNIX の C ライプラリには regexp ( 正規表現のコンパイラとス キャナ ) が含まれるが、必要なものがすべて実装されて いるわけではない。よく使われているいくつかのプログ ラムでは正規表現による探索を再実装したが、予想どお り記法は統一されていない。そのため、コマンドやアプ リケーションによっては正規表現の記法が異なる場合が ある。幸いにも大きな違いはないので、 こでは egrep コマンドで使える正規表現に絞って説明する。 文字列のパターンは、 [ 0123456789 ] のように ( 角括弧 ) で括って指定する。これは、従来の記法よりも 簡単な形式の、選択 " の正規表現である ( 別掲のコラム 参照 ) 。角括弧内には文字の範囲も指定でき、上記の例 は [ 0 ー 9 ] とも表せる。これは ASCII コード表での順番 とみなさオ L 、その範囲のいすれかの文字と一致する。同 様に、アルファベットの大文字と小文字は [A-Za-z] で 表される。ある整数に一致する表現なら [ 0 ー 9 ] [ 0 ー 9 ] * のように記述でき、従来の記法にくらべてかなり簡略化 されている。これをさらに簡単にする記号がある。 + は、、 * " ( アスタリスク ) と同し閉包演算子で、直前の正 規表現の 1 回以の縄区しを意味する。したがって、さ きほどの整数を表す正規表現は [ 0 ー 9 ] + と省略できる。 ( ドット ) についても説明しておこう。 もう 1 つ、 この演算子は任意の 1 文字と一致する ( 実際には例外が あり、それについては彳する ) 。よく使われるのは . * で、これは 0 個以 E のすべての文字と一致する。たとえ は先頭と末尾が数字で、そのあいだに任意の文字を含む 文字列は、 [ 0 ー 9 ] . * [ 0 ー 9 ] のように記述できる。 従来の使い方では、正規表現は文字列本に一致しな けれは・ならなかった。言い換えれば、正規表現が文字列 85
Daemons & Dragons— 拡張された正規表現の記法では、、アンカー " も使用で きる。この演算子は文字には一致せす、行のなかでの位 正規表現の本来の記法には 4 つの操作しかなかった。選 置を示すために使われる。正規表現の先頭に ( キャ 択、連結、グルーフ北、閉包演算である。普通の文字はそれ 自体と一致する。正規表現 a は、文字 a のみと一致する。 a レット ) を付けると行頭を意味し、 $ ( ドル記号 ) は の後ろに b か読く文字列をみつけるには ab と記述する。 行末を示すのに使われる。正規表現のなかで使われた場 れが連結である。 a か b のいすれかを検索するには、選択を 合、これらは特別な意味をもたす、たんなる文字として 使って引 b とする。グループ化は、、 ( ) " ( 丸括弧 ) で表され のと $ を示す ( キャレットの場合、彳刻するように 1 文 るため、正規表現引 b と (alb) は同じものに -- 一致する。 閉包演算は * で表され、、 0 回以ーヒの繰返し " を意味する。 字目は除く ) 。したがって、行の先頭から始まる数字を検 正規表現 ab* は、 a とそれに続く任意の数の b と一致する。 索するには 0 ー 9 ] + という正規表現が使える。この文字 つまり、 a 、 ab 、 abb 、 abbb 、 ・・などの文字列には一致 列自体との一致を避けるには、 0 ー 9 ] + の末尾にスペー するが、 ac とは一致しない。閉包演算はかならす直前の正規 表現を操作する。閉包演算とグループ化を組み合わせれば、 a スを追加すればよい。数字だけからなる行を検索する場 と b が混在する文字列と一致する ( 引 b ) * のような正規表現 合は 0 ー 9 ] + $ とする。文字列の両端にアンカーを付け を記述できる。 ることで行全体との一致を指定している。 ファイルに文字 a と b しか含まれていなけれは、これで十 正規表現の欠点の 1 つは演算子に ASCII 文字を用い 分だろう。だが、この構文を実際のアプリケーションに適用 するとなると厄介である。たとえは、整数と一致する正規表 ることだ。たとえば、アスタリスクはどうやって検索す 現は ( 幻幻引引引引刀田 9 ) * となる。しかもこれは誤っ るのだろうか。由緒ある \ ( バックスラッシュ ) を入 た記法である。空文字列とも一致してしまうからだ。 1 桁以 力すれはいい。特別な意味をもつ文字 ( * 、 上の数字と一致させるにはその数字のパターンを繰り返さな ければならす、正規表現の長さは 2 イ部匠くになってしまう。 は、直前にバックスラッシュを挿入してエスケーフす れは、その文字自身を検索対象として指定できる。した がって、 \ * はアスタリスクと、 \ + + はプラス記号の 1 回 のパターンを表すと考えるなら、比較する文字列全体が 以上の繰返しと一致する。 そのパターンに含まれていなければならない。実装にあ 注意してほしいのは、 ーで綛介した文字の多くがシ たってはこの規則がすこし緩められ、正規表現を検索に ェルにおいても特別な意味をもっていることだ。入力し 使いやすいようにしている。たとえば、あるファイルか た文字をシェルではなく (egrep などの ) コマンドに処 ら、、 IJ ⅲ x " か、 u ⅲ x " という文字列を検索したいとしよ 理させるには、正規表現をコマンド行やシェル・スクリ う。厳密には、正規表現 [Uu] nix はこの文字列がファ プトに入力する際に、かならす ' ( 単一引用符 ) で囲 イル全体の内容でなければ一致しない。しかし、それは まなければならない。そうすれはシェルが介入すること 合理的ではないため、正規表現を用いる UNIX プログ はなくなる。ここで 1 つ間題を出そう。 ラムは、ファイルもしくはテキストプロック内にそれら が含まれるかどうかを調べる。つまり、 . * CUu]nix. * egrep ' \ * * ' と記述するようなものだ。 というコマンドの実行結果はどうなるだろうか。 大半のユーサーは検索を行単位の操作とみなしがちで 高度な正規表現 ある。純粋な正規表現は行という境界とは無縁だが、行 単位の検索を実行しやすくするための規則カ用されて 基礎についてはこれくらいにして、次はすこし難しい 記法をみてみよう。角括弧で囲まれた文字列のパターン いる。その代表例がドットである。ドットが本当に任意 は、 1 文字目の前にキャレットを付けると逆の意味にな の文字と一致するなら、改行文字とも一致するだろう。 る。たとえは、アルファベット以外の文字を検索するに すなわち、そのつもりはなくてもファイル全体と一致す は CAA-Za-z] を使う。キャレットがこのように特別な る可能性がある。実際には、ドットは改行文字 (UNIX 意味をもつのは、開き括弧の直後に置かれた場合に限ら の newline) 以外のあらゆる文字に一致する。したがっ & 、 * 、 $ 、 @のいすれかの文字 て、正規表現 . * は行全体と一致することはあっても、フ れる。したがって、 を検索したけれは [ & $@] のように指定できる。これ ァイル全体と一致することはない。 従来の記法 86 UNIX MAGAZINE 2001.1
Daemons & Dragons regexp を利用するアプリケーションではこの記法が使 がお望みどおりのものを表すのに対し、に & $@# ] はまっ たく違った意味になる。角括弧内のアスタリスクは特別 える。ただ奇妙なことに、 regexp の記法には汎用のグル ープ演算子がない。 (abc) などで括弧が正しく処理され ~ ] という な意味をもたない点に注意してほしい。い ないため、 \ ) の後ろの閉包演算子も機能しない。 egrep おもしろい記法もあり、印字できない ASCII 文字に 致する。改行には一致しないが ( 検索がかならす行単位 では abc(abc) * といった正規表現が使えるが、 regexp はそれを正しく解釈することも、 abc\(abc\)* を解釈 で実行されるため ) 、タブには一致する。 することもない。また、 regexp では選択もサポートさ UNIX の正規表現のなかには、繰返しの回数を指定 れていない。 egrep では ( 社 ) 。司刃 (phrase) のような できる記法もある。これは、ケえられたパターンか指定 記法が使えるのに、これに相当する正規表現を regexp した回数だけ繰り返されていなければならないことを示 で記述する方法はない。一般に、 egrep の記法は正規表 す。繰返しの回数は正規表現の後ろに、、 { } " ( 中括弧 ) 現を記述するのに十分である。これに対し、 regexp に で囲んで指定する。中括弧はバックスラッシュでエスケ は制限があるものの、、、正規 " とはみなされない構造が ープしなけれはならない ( バックスラッシュのはかの用 許されている。 途とは対照的である ) 。正規表現 ) x \ { 5 \ } ) は XXXXX と一致する。このとき、行に X が 8 個含まれていると、 練習問題 最初の 5 個に一致したところで処理が完了したとみな さきはどの問題の答を書こう。 される。 XXXXX の後ろに何かカく文字列を検索し たければ、 'x\{5\}[-x] ) とする必要がある。ただし egrep ) \ * * ' 、用 e これは、 X カ哘の末尾にあると正しく実行されない。こ というコマンドの正規表現は、アスタリスクが 0 回以 - ヒ の記法を利用すれば、繰返しの範囲も指定できる。 5 ~ 繰り返される行に一致する。だが、それではファイルの 9 個の X に続く 5 ~ 9 個の Y と一致する正規表現は すべての行が一致するのではないだろうか。事実、この x\{5 , 9 \ } Y \ { 5 , 9 \ } となる。 egrep では使えない記法 コマンドを実行すると川 e のすべての行カ鰾準出力に書 だが、 regexp を利用するプログラム (grep 、 ed 、 sed 、 き出される。 ⅵなど ) では正しく動作する。 さらにひねりを加えた間題をいくつか用意した。何問 もっとも風変わりな記法は、、、正規表現 " の概念にも 正解できるか試してみてほしい 1 反している。すでに一致した文字列の一部を調べるの 以下に一致する egrep での正規表現を記述せよ。 だ。この場合もバックスラッシュを使って演算子を挿入 1. スペースで区切られた 3 つのフィールドが含まれる行 する。 \ ( と \ ) で囲まれたグループは、あとから再度比 較できる部分を示す。バックスラッシュに続く数値は、 2. 負の整数 たとえは 1\1 なら括弧て話られた最初の表現、 \ 2 なら括 3. 不正なホスト名 ( ホスト名に使える文字は、数字、ア ルファベットの大文字と小文字、ハイフンだが、ハイ 弧で括られた次の表現といったように、これらの表現の フンが名前の先頭か末尾にあってはならない ) いすれかと一致する。 \ ( .. * \ ) \ 1 は、糸区しの文字列 4. スペースで囲まれた 10 進数 ( 正数または負数 ) を含むどの行にも一致する。括弧内の .. * はスペースが 続く何かと、 \ 1 は括弧で括られた最初の表現と一致す 5. 整数で始まり、その値と同し数の文字が続く文字列 る。これは強力できわめて便利だが、 regexp でしかサ ('6abcdef' など ) ポートされていない。 インターネットのプラックホール 例外 インターネットの創始者たちが電子メールを交換する 前述したように egrep は sed 、 ed 、 vi のノヾックス 仕組みを考案したとき、自分たちカ噺たな商取引手段を ラッシュ付きの演算子を受け付けない。これらの演算子 は C ライプラリの regexp パッケージの一部なので、 1 正解は http://www ・ groupsys ・ com/に掲載されている。 87 UNIX MAGAZINE 2001.1
ロプログラミング・テクニック 多治見寿和 flex 前回まで、 9 回にわたって grep コマンドについて解説 しました。 grep は、パターンカ甘旨定されると、標準入力 やファイルからそのパターンが含まれる行を取り出すコマ ンドです。この処理のためにパターンを NFA に変換し、 さらにそれを DFA に変換することで高速に検査します。 この仕組みは grep コマンドにかぎらす、一ヨ殳に正規表 現のパターンを指定できるコマンドでは必須のものです。 しかし十ヾてみると、 grep コマンドのように自前てソヾタ ーンの処理ルーチンをもっプログラムはそれはど多くない ようです。パターンの処理といえはすぐに思い浮かぶ awk コマンドは自前の処理ルーチンをもっていますが、 Free- BSD で提供される awk は grep コマンドと同しルーチン を利用しています。また、ⅵや sed などはシステムのラ イプラリに含まれる正規表現ライプラリを利用して動作し ています。 さらに探したところ、 lex コマンドが grep コマンドと は異なる自前のルーチンを作成していました。そこで、 の lex コマンドを紹介することにします。ただし、 Free- BSD で利用しているのは GNU の flex というコマンド です。今回は、 flex コマンドでの入力の角斤をとりあげ ます。 f 厄 x に与える仕様 まずは flex コマンドについて簡単にみておきましよう。 lex コマンドについては 1999 年 7 月号でもとりあげま した。 flex コマンドもその動作はほは伺じです。このとき は、キーワードなどの日様を与えると、そのキーワードを 訒識する字句角斤器を生成するプログラムとして紹介しま ルじ、 した。そのなかで、トークンのパターンとして正規表現を 74 利用できるとも書きました。今回は、この処理の部分をみ ていきます。 flex コマンドに与える仕様は 1 つのファイルです。そ の内容は、以下のように大きく 3 つに分かれます。 定義部 規則部 ューサーコード部 定義部では、次の規則部を簡単に言当するために用いる 名前や、適用可能な規則を制限するために用いる開始条件 を定義します。その規則部が flex のメイン部分です。認識 するトークンのパターンと、そのパターンを認識したとき に実行するアクションの組を指定します。最後のユーザー コード部は、 flex コマンドが出力する C 言語のファイル にそのままコピーされます。 定義部で定義する名前には正規表現を割り当てます。た とえば、 NUM ALP [ 0 ー 9 ] [a-zA-Z] として、正規表現 [ 0 ー 9 ] を NUM という名前に Ca-zA- z] を ALP という名前に割り当てておけば、規則部でパ ターンを指定するときに、 {NUM} + {ALP} ({ALP} I{NUM}) * return NUMBER ・ return IDENT ; などのように、パターンの一にとして利用することかでき ます。 定義部では、、、 % { " から、、 % } " までのあいだに C 言語 ーこに書いたコードは、 のコードを自由に言当主できます。 出力されるファイルにそのままコピーされるので、アクシ UNIX MAGAZINE 2001.1
このあとには、ふつうに演算子の優頂位を考慮した正 規表現の生成規則か読きます。 series singleton serxes re ) ー ) series singleton singleton singleton singleton singleton singleton singleton singleton fu11cc1 PREVCCL CHAR string , 十 ) , { , NUMBER , , , NUMBER ) } ) , { ) NUMBER ) } , grep コマンドでは字句角斤器で処理していた正規表現 の回数を指定しな区しも、構文としてされているの か分かります。 こでは省略しましたが、各 ( に成規則にはもちろんアク ションも付いています。アクションでは、自分自身の記号 の値 ( $ $ ) としてパターンを表す NFA を代入しています。 もっとも、 これらの多くは、 ) ー series などのように関数を使って構築されるため、その田はこ こからはよく分かりません。これらの関数は nfa. c で定義 されています。 singleton のなかの fullccl と PREVCCL の 2 つは、 しつは同しものです。いすれも文字クラスを表し、・兼の なかに最初に現れたときには fullccl を使って構文角斤し ます。 2 度目以降は、すでにその内容は構文角財斤した結果 として得られているため、あらためて構文角斤する必要は ありません。そこで、字句角財斤器側ですでに出現している かどうかを匐十ヾながら値を返すようにしています。 字旬角斤器カ黝くという未では、規則に付けられたア クションも字句角財斤器で解釈します。 flexrule は flex が 扱う規則 1 つを表すので、パターンとアクションの対に 80 なるはずですが、実際にはパターンしかありません。これ は、字句角財斤器側で頑張って処理しているためです。この UNIX MAGAZINE 2001 ユ stack オフションを使えは才舌弧の対応も調べられます。 だから括弧の対応をとることはできないと書きましたが、 します。以前紹介したときには lex は正規表現を扱うもの 値は、次の yy-popstate 関数を呼び出すと自重加勺に復帰 開始牛を内部的なスタックに積みます。ここて積まれた すると、字句角 i 器を指定した開始条件に変更し、現在の yy-push-state 関数は、引数に開始条件を指定します。 の 3 つの関数か利用できるようになります。 ・ void yy-top-state() ・ void yy-pop-state() ・ void yy-push-state(int) ションを指定すると、 なかでも強力なのが stack オプションです。このオフ しない。 nostdinit : 入出力のデフォルトとして標準入出力を使用 るために、 yy-top-state 関数を生成しない。 noyy-top-state : 生成したコードを lint などて処理す stack : 開始条件のスタックを利用可能にする。 から指定されたファイルに変史する。 outfile= ”ファイル名” : 出力するファイルを lex. yy. c 使用しないようにする。 nodefault : ー s オフションと同様、デフォルトの規則を しなくなる。 caseless : 作成する字句角斤器て大文字と小文字を区別 各オプションについて簡単に説明します。 %option nostdinit stack noyy—top—state /ooption caseless nodefault outfile="scan. = ションを宣言している点です。 ルです。このファイルでます目につくのは、数多くのオフ 次は flex の字句角斤器を構成するための scan. 1 ファイ 字句解析器のソースコード 必要をなくしています。 み飛はす ) ことで、構文角財斤器に C 言語の構文を用意する ように、字句角財斤器で C 言言韶 ) コード部分を角財斤する ( 読
UNiX MAGAZINE CONTENTS 2001 / 1 特集 12 いつでも使えるインターネット 51 VMware で UNIX " 白崎博生 個人の常時接続環境を考える ( 7 ) ・・・大江将史 インストールとネットワーク UNIX Communication Notes ・・・・ " 山口英 情報整理の技術 ( 4 ) バージョン管理システム CVS 新・倉敷芸術科学大学のネットワーク構築・・・・・・小林和真 Cisco ルータの基礎 ( 4 ) 遠隔オフィスとの接続・・・・・・荒井美千子 SOHO からの接続 ( 7 ) Samba のトラブル・シューティング BSD をハックする・・・・・・齊藤明紀 ファイル・ディスクリプタを渡す プログラミング・テクニック・・・・・・多治見寿和 flex Daemons & Dragons ・・・・••WiIIiam LeFebvre 正規表現、スバム対策用ブラックリスト Java Advisor ・・・・・・ David DetIefs クラス階層の設計を読む lnside Cygwin ・ " ・ " 藤枝和宏 マウント機構の詳細 UN Ⅸ便利帖・・・・・・宮下健輔 私的検索エンジン COV 凡 CONTENTS DESIGN ・ MORIYA, KAZUO (AUDREYTHE DESIGN) 連載 4 6 3 6 4 5 1 5 1 2 3 4 6 7 8 9 9 0 0 0
連載 /lnside Cygwin— 図 4 ドライプのマウント まで入力してからファイル名の補完甫を表示させること もできない。 bash はパス名に、、 : " カ哈まれているとは考 Windows のティレクトリ マイコンピュータ えず、 /WINNT/sys でファイルを探してしまうからだ。 ・ 3.5 インチ FD (A:) 丑 UNC ライクな記法を使う 田・ (C:) Windows でネットワーク上の資源を参照するときに使 巴 (D:) う、¥¥ホスト名¥共有名 " という表記 (UNC: Univer- 、、 / / ドライフ sal Naming Convention) によく似た、 田 =. よ 'winfs' の share(L:) 字 " て始まるパス名を利用するガ去もある。たとえば、 $ ls //C/WINNT 数 PATH の値を表示すると以下の結果カ碍られる。 を実行すると、 Cygwin DLL が、、 / / C / " を、℃ : ¥ " に変 $ printenv PATH 換するので、さきほどと同じ W ⅲ dows のシステム・ディ /usr/local/bin : /usr/bin : /bin : /cygdrive/c/WINNT/ レクトリを参照できる。 system32 : /cygdrive/c/WINNT : /cygdrive/c/WINNT/Sy stem32/Wbem : /usr/bin : が含まれないので、上交的無難に これならパスに UNIX のアプリケーションに渡すことかできる。ただし、 Cygwin DLL は、アプリケーションの main 関数を実 このガ去があるため、 Cygwin 上で 1 文字の名前をもつホ 行する前に、環竟変数 PATH や HOME などに含まれて ストの資源に UNC でアクセスする際には、パスの区切り いる Windows スタイルのノヾス名を POSIX スタイルに / ではなく、¥ " を使う必要がある。このガ去は、次 変換する。この過程で、 PATH に含まれている Windows に述べるガ去が実装された時点で削除されるはすだった。 のシステム・ディレクトリが /cygdrive/c で始まるパス いまのところは互換生のために残されているが、いつ削除 名に変換されているのが分かるだろう。 されてもいいように、なるべく使わないほうがよい。 この方式の間題点は、ルート・ディレクトリの外にある ディレクトリを頻繁に参照する際に、いちいち /cygdrive cygdrive で始まるパス名を使う と入力するのか面倒なことだ。これは mount コマンドを Cygwin B20 のころは、ドライプを参照するガ去は上 使えは、もっと短いものに付け替えることかできる。それ 己の 2 つしかなかったが、 Cygwin 1.1 で /cygdrive/ 以前に、参照したいディレクトリを Cygwin のルート・ ドライプ名 " で始まるパス名を使うガ去が導入された。 ディレクトリの下にマウントしてしまえば、ドライプのマ の方法では、 /cygdrive/c/WINNT で Windows のシ ウント機能を利用する必要もなくなる。 ステム・ディレクトリを参照できる。 Cygwin DLL は、パス名を POSIX スタイルから mount コマンドの詳細 Windows スタイルに変換する際に、まずード記の正規表現 に相当するパターン・マッチングをおこなう。 Cygwin の mount コマンドの基本的な使い方は図 5 の とおりである。たとえば、 C:*Documents and Settings */cygdrive/ [a-zA-Z] ( 川 $ ) を /home て参照できるようにしたいのなら、 マッチしたときには、これを、、 [ a - z ] : ¥ " に変換する。 れにより、すべてのドライプのルート・ディレクトリが、 $ mount —b C : /Documents* and* Settings /home /cygdrive/[a-z] " にマウントされているかのように扱え とす川まよい。以降は、図 5 に示した mount コマンドの る ( 図 4 ) 。 オプションと、それに関連する恥頁を説明する。 逆に、ノヾス名を Windows スタイルから POSIX スタ パイナリモードとテキストモード ( ー b 、—t) イルに変換する際には、 Cygwin のルート・ディレクト リの外にあるディレクトリを、、、 /cygdrive/ ドライフ名 " Windows のテキストファイルは改彳丁が CR (OxOd) と で始まるパス名に変換する。たとえば、 bash - 」 : て環竟変 LF (0x0a) の 2 文字で表現されるが、 C 言語のプログ Cygwin のティレクトリ このディレクトリは ありません cygd rive 一三ロ 97 UNIX MAGAZINE 2001.1
サイバー関西フロジェクト 震災情報提供システムの構築 NG レロジェクト ( 1 1 ) 藤川和利、下條真司 はじめに 160 " と呼はれていました。 1 開発当初は、 QoS ポリシーサー 体表現された日本地図上に飃壓也や各地の震度などの清報 関する↑帯にをユーサーに分かりやすく提示するために、立 供システム」を構築しました。このシステムでは、地震に たネットワーク・アプリケーションとして、「震災財是 NGI プロジェクトでは、次間代インターネットに向け QoS の範囲内で品質を調整する必要があります。 て、ネットワーク・アプリケーションでは、与えられた 求した品質が 100 % 得られるとはかぎりません。したがっ す。とはいえ、ネットワークを共有するわけですから、要 なり、ある程度のサーピス品質がイ焉正されることになりま れをユーサー側からみると、従来のインターネットとは異 を通してネットワーク帯域などの QoS カ鴃まります。 ク・アプリケーションを使う場合は、 BB とのやりとり の Q 。 S 管理をおこなっています。ューサーがネットワー は、 BB (Bandwidth Broker)l を用いてネットワーク サイバー関西プロジェクトの NGI プロジェクトで 効率的な共有が実現できます。 ネットワーク・アプリケーション間でのネットワークの ポリシーにもとづいてネットワークを管理すれば、複数の の QoS も確保されるでしよう。このとき、なんらかの で、大容量データの中幻幻こ不可欠なネットワーク帯域など ります。さらに、 DiffServ による QoS を導入すること 域を必要とする映像や 3 次元 CG 画像の転送が可能にな ギガピット単位と高速になり、大容量のネットワーク帯 (NGI) では、バックポーン・ネットワークの中幻速度が これまでにもみてきたように、次世代インターネット を表示します。ューサーは、画面に表示された地図 - E を自 由にナピゲーションしながら任意の地点の情報を参照でき ます。大きな地震が発生した直後には、とくに被災地に居 住している人は、できるかぎり早く飃駟也や震度などに関 する正確な情報を得たいと望むのではないでしようか。そ のような場合にこそ、 BB から与・えられた QoS に応じて、 通切な品質窈帯にを提供する必要があります。 今回は、この震災情幸財是供システムにおける QoS 調整 技術について説明します。 震災情報提供システムの概要 1995 年 1 月に発生した畴申・淡路大震災の際に、テレ ピや第などの既存のメディアによる幸直では正確な情報 か素早く伝達されないという間題カ甘商されました。その 一方で、このときにおこなわれたインターネット経由での ↑帯財是供が、上記の欠点を補うものとして大きな注目を集 めました。 NGI プロジェクトではこれらの点を勘案し、ユーサー にとってさらに分かりやすい地震報を提供するシステム を、 BB を用いたアプリケーションの一例として実現しよ うと考えました。当然のことながら、求められる情報はユ ーサーごとに異なるため、、、各ューザーのニーズに応して 局戸廂勺な被害状況を自寉に把握できること " を目標に掲げ ました。 最初に、震災情幸財是供システムの概要について説明しま す。システムの全体像を図 1 に示します。 地震が発生すると、気象月 = から地震に関する情報カ毓さ れます。通常、それらの情報はテレビ局で受信さオ、テレ ビのネ朋者はニュース速報やニュース番組などを通して地 UNIX MAGAZINE 2001 ユ
ョンのなかで利用する関数のためのヘッダファイルのイン クルードや、マクロの定義などがおこなえます。また、定 義部ではインデントされた ( 行頭に空白文字のある ) 行は、 やはりそのまま出力ファイルにコピーされます。 次の規則部では、パターンとアクションの組を指定し ます。パターンにはもちろん正規表肋甘旨定でき、定義部 で定義した名前も使えます。アクションはパターンの後ろ に、空白文字に続けてします。アクションには C 言 言韶 ) コードをします。複雑なコードを記したい場合 、 { } " ( 中括弧 ) で括れはそのなかがアクションとし は、 て登録されます。 規則部の知頁では、定義部と同様に % { と % } のあい だやインデントした行に C 言語のコードを記述できます。 : 咽したコードは、字句角斤ルーチンの内部の宣言 部か終った直後に出力されるため、字句角斤ルーチンだけ て利用するローカル変数の旦暠や、字句角斤ルーチンを呼 び出すたびに実行したいコードなどか第己主できます。これ らのコードは、実際には字句角斤ルーチンとなる yylex 関 数の地頁部分に置かれます。そのため、構文角斤ルーチン がトークンを要求して yylex 関数を呼び出すたびに実行 されることになります。字句角財斤ルーチンを初期化するた めに 1 度だけ実行したいコードなどの場合は、 static と して宣言した変数を利用して繰り返し実行されないように ガードする必要があります。 static int flag = 0 ; if (flag = = の { flag = 1 ; 1 度だけ実行したい初期化のコード 最後のユーサーコード部に言したコードは、そのまま 出力の C 言言韶 ) ファイルに追加されます。そのため、字旬 角財斤ルーチンのアクション部で利用する関数などを定義す ることができます。ここで注意しなければならないのは、 この部分が yylex 関数よりもあとに出力される点です。し たがって、ユーザーコード部に指定した関数を yylex 関 数で利用する場合には、あらかしめその関数の型を知らせ ておく必要があります。具体的には、定義部や規則部で、 c 言語のコードとして関数のプロトタイプなどを指定して おきます。 UNIX MAGAZINE 2001.1 プログラミング・テクニック 開始条件 を紹介しました。 は、 C 言語のコメントを処理するガ去として次のような例 ものも記できるようになっています。 1999 年 7 月号で な規則を制限することで、正規表現だけでは記述しにくい flex では、開始条件を使ってそれぞれの点で適用可能 %s C OMMENT {BEGIN (COMMENT) ; } {BEGIN(INITIAL) ; } く COMMENT>" * / " く COMMENT>. ハⅡ / * eat up * / この仕様では、定義部で開始条件として COMMENT を宣言しています。 %s の後ろに複数の名前を空白で区切 って列挙すると、それぞれの名前が開始条件となります。 規則を指定する際にく開始条件 > をパターンの前に付ける と、その開始条件でのみ有効な規則となります。複数の開 始条件で有効にするには、それらをすべてカンマで区切っ て並べます。一方、最初の規則のように開始条件を指定し ないものは任意の開始条件で有効になります。さらに、最 初の規則ではアクションで BEGIN(COMMENT) とし ています。このアクションを実行すると、現在の開始条 件が COMMENT に変更されます。開始条件としては COMMENT だけを宣言していますが、 flex ではとくに 宣言しなくても INITIAL という開始条件か利用できま す。字句角斤器は、初期状態では INITIAL となってい ます。 しつは、一屬己のプログラムは正確ではありません。たと 、、 / * / * / " という入力を考えてみましよう。最初は えば、 INITIAL 状態にあり、地頁の / * を認識すると字句角財斤器 の開始条件は COMMENT に変わります。次の入力を読 み込んだときに最後のパターンにマッチして 1 文字が認 識さオリばよいのですが、その前に最初のパターンと一致 してしまいます。すると次の 2 文字 / * か認識されるため、 残りは / だけになってコメントを終了できません。これ は、開始条件が COMMENT でも最初の規則カ陏効なた めに起こる問題です。 このような場合には、排 f 勺な開始条件として宣言する ことができます。孑羽勺な開始条件では、明示的に開始条 件カ甘旨定された規則だけを利用します。つまり、開始条件 75
図 2 VRML データの階層本告 ント PC での描画速度は、その 3 次元空間に含まれるポ リゴン数に反比例します。したがって、 LoD ノードを利 メッシュ領域 : 大 データ詳細度 : 低 用すれはクライアント PC での不必要な描画がなくなり、 3 次元仮想空間をスムーズに移動できるだろうという考え 方です。 しかし、現在の LoD ノードの定義では、ユーサーとオ プジェクトの距離に応したレベルの切替えしか言当できま せん。これでは、クライアント PC のメモリ量か不十分 であっても、近くに寄っていけばポリゴン数の多いものが 描画されてしまい、空間内のスムーズな移動が困難になり ます。 問題への対処 NGI プロジェクトでは、震災情幸財是供システムの構築 にあたり、大容量のデータも扱えるように VRML ファ り、遠ざかって日本地図本をて被災或の範囲を確 イルを構成する手法を考案し、 BB と協調して動作する 訒するといった重川乍が考えられます。 VRML プラウサを開発しました [ 3 ] 。システムの基本的 川じ、 さきほども述べたように、市町村レベルの地震情報では な要件は以下の 3 つです。 詳細な 3 次元の日本地図か必要になりますが、日本本を 起重加芋に、 3 次元仮想空間か即座に表示される。 0 御敢するときにはおおまかなデータで十分です。そこで、 ・ネットワークの状況やクライアント端末の処理能力を考 近ついたときにも遠ざかったときにもユーサーが地図ーヒを 慮したうえで、スムーズな空間移動を可能にする。 スムーズに移動できるように、 VRML の LoD ノードの 氏限の表示品質寺する。 機能を用いて 3 段階の言田度を用意することにしました。 さらに、ユーサーの視界に合わせて 3 次元データの送信 このシステムでは、これらの要件を実現するために、利 や表示がおこなえるように、もっとも田度の高いデータ 用可能なネットワーク帯域に関する情報を BB との協調 ( 市町村レベル ) では地図を細かく分割し、もっとも詳細 によって取得し、ネットワークの状況とクライアント PC 度の低いデータではおおまかにうリして、階層構造をもつ の表示能力に応した VRML オプジェクトの中幻をおこな VRML データを作成しました ( 図 2 ) 。なお、データ作成 います。 にあたってはウエサーニューズの協力を得て、同社の所有 以下では、これらの要件を満たすシステムをいかにして する日本全土の VRML データをこの形式に加工していた 構築したかを説明します。 だきました。 図 2 のメッシュ状に分割された部うゞ、 1 つのオプジェ 拡張 VRML システム クトとして扱われます。 1 つのオプジェクトは、地形のポ リゴンデータを表現する VRML ファイルとそのテクス 3 次元テータの構成 チャデータである PNG ファイルから橢及されています。 もっとも諞田度の低いレベルでは 4 個のオプジェクト、中 ます、ユーサーの現在位置に応して、必要とされるオ プジェクトから順次送信して表示するように空間データを 程度のレベルでは 146 個のオプジェクト、そしてもっと も言岩田度の高いレベルでは 4 , 176 個のオプジェクトで日 構成することを考えました。これは、日本地図の任意の地 本全土を表現します。これらすべてのオプジェクトのデー 点間をユーサーがスムーズに移重丿けることを想定していま タサイズの合計は、 416MB にもなります。 す。具ー勺には、 j 止プいて市町村レベルの地震情報を見た 連載 /Cyber Kansai project—@ 中中 域度 領細 シタ メデ 小高 域度 領細 メデ 163 UNIX MAGAZINE 2001.1