XML属性の出現パターンを記述するためにふさわしい正規表現(の変種)を導 入する。この正規表現は、集合言語(アルファベットの部分集合の集合)の記 述と解釈される。
正規表現をご存じの方は多いでしょう。文字列パターンを正規表現 により表すことは、テキスト処理の基本的テクニックですね。XMLでも、要素 内容に出現する子要素およびテキストのパターンを、正規表現で表します。こ の事情は、古典的なDTDでも最近のスキーマ言語でもだいたい同様です。
ひとくちに正規表現とはいっても、随分といろいろなバリアント(方言、変 種)があります。例えば、連接(concatenation)は特に演算子(メタ文字) を用意せず、単に並べる方式(ピッタリくっつけると問題が生じるなら空白を はさんで並べる)もあれば、明示的な演算子(例えば「,」)を使うこともあ ります。
使える演算子のレパートリも色々です。多くの例では、「|」「*」「?」「+」 を使います。しかし、A+ は AA* と書けばいいので「+」は落とすことができ ます。一方、定数EMPTYを導入するなら、A? は (A | EMPTY)、A* は (EMPTY | A+) と書けるので、今度は「?」「*」を落とすことができます。AAA を A3 と 書けたり(*注1)、さらに、(AA | AAA | AAAA) を A{2-4} と書けたりすると便 利です(*注2)から、そういう拡張を取り入れた正規表現もあります。
A3 を、文字'A'と文字'3'の連接と解釈されてしまうとまずいので、何らかの 対処が必要かもしれません。対処法は、文字そのもの(リテラル)は引用符で 囲むことにして 'A'3 と書く、あるいは中括弧を特殊文字として、A{3} と書 くなどです。
(AA | AAA | AAAA) のような選択肢は、そのまま先頭から処理しようとする と、先読みが必要になるのであまり好ましくありません。ですから、A{2-4} のような記法は、書く側に便利なだけでなく、処理側にも有利になります(A の個数を勘定しながら見ていくコードに落とせます)。
さて、この記事では、かなり変わった正規表現の一種を紹介します。この正 規表現は、演算子のレパートリが違う(が、表現力は同じ)といった程度の違 いではなくて、通常の正規表現とは本質的な違いがあります。まずは、XML属 性の出現パターンの表現として、この正規表現を導入して、後でその概念を整 理しましょう
最初の事例を出しましょう(作為的、人為的です:-))。XML構文のスクリプ ト言語があるとして、そのコマンドにsleepがあります。<sleep second="3"/> は3秒間のスリープです。ミリ秒単位で指定したいなら、<sleep millisec="500" /> のようにします。あ、そうそう、 属性secondも属性millisecもint型(*注3)です。
プログラミング言語のint型に対応するsimple typeということです。 nonNegativeならもっといいですね。
このsleepコマンドの正しい使用法は次のとおりです。
次のような簡便なパターン記法で、属性secondとmillisecが両方出現し、か つ、値がint(に対する文字列)であることを示しましょう。
<sleep second=int millisec=int />
second属性だけのときは、次のとおり。
<sleep second=int />
同様に、millisec属性だけなら次。
<sleep millisec=int />
以上3通りのどれも正しいので、その事情を書き表すなら、次のように なるでしょう。
<sleep second=int millisec=int /> | <sleep second=int /> | <sleep millisec=int />
属性の部分だけをパターンで表現すれば、まー、こんな書き方でいいでしょ うか。
second=int millisec=int | second=int | millisec=int
いま、「second=int」全体をまとめてSecondで表し、同様に「millisec=int」 を1つの名前Millisecで表現します。{Second, Millisec}から作られる 正規表現で、属性の出現パターンを表すことができます。上の例なら、次のよ うでしょう。
(Second Millisec) | Second | Millisec
ん、ちょっと待ってください。属性では出現順序は問題にならないので、 (Second Millisec)ばかりではなく、(Millisec Second)でもOKです。これを考 慮すると次のようになります。
(Second Millisec) | (Millisec Second) | Second | Millisec
もうこれでパーフェクトです。何も言うことはありません。この正規表現は、 属性の出現パターンを見事に規定しています。
次にいきましょう。要素exampleの属性foo、bar、baz、 zotがあり、それぞ れの型は、「foo=int」、「bar=string」、「baz=date」、「zot=long」とし ましょう(実は何だっていいんだけどさ)。前の例と同様に、型の制限も含め た各属性の出現を、Foo、Bar、Baz、Zotで表すとしましょう。
ここで、とても簡単な問題を出します -- Foo、Bar、Baz、Zotの4つとも必須、 つまり必ず出現が要求されているとして、それを正規表現で表してください。………………
………………僕(檜山)は結果を書き下すことはしませんが、演算子「|」を イッパイ含んだ、長い正規表現になります。
そもそも、属性は出現順序の概念がないのです。それなのに、順序が本質的 である列正規表現を使うのはバカげた話です。“出現順序の概念”や“順序を 考慮した連接演算”を考える必要はありません。
そこで順序を考慮しない正規表現を考えましょう。つまり列ではなくて、単 なる集合(有限集合)が対象です。でも、列の場合と同様に、アルファベット (基本構文素)から出発します。アルファベットとしては、先の例の{Foo, Bar, Baz, Zot}をとります。このアルファベットの部分集合はけっこうたくさ んありますが、全部列挙できます。そのうちのいくつかを挙げれば、{}, {Foo}, {Foo, Zot}, {Foo, Bar, Baz, Zot}とかです。
アルファベットの部分集合は、ちょうど属性の出現に対応します。上の4つの 部分集合は、次の4つの出現パターンに対応しますね。
さて、列ではなくて集合の正規表現は次のように定義されます。
正確には、空集合だけからなる集合{{}}を表しています。
4番目の「&」が、連接に代わる新しい演算子です。ちょっと分かりにくいの でいくつか例を出します。
(A | EMPTY)を A? と書くことにするとより使いやすいでしょう。 例えば、Foo & (Zot | EMPTY) は Foo & Zot? と書けます。「?」は普通通り、 省略可能である(出現しなくていい)ことを表します。
この節で事情をハッキリさせましょう。
アルファベットとは、構文構成素と思える記号/モノの集合です。アルファ ベットΣ上の集合とは、Σの部分集合のことだとします。集合の集合は(列の集 合が列言語であると同様に)集合言語と呼んでいいでしょう。「すべての部分 集合を考える」という操作(べき集合)が2回出てくるのでちょっとややこし いですけど。
列正規表現が列言語を表すのと同様に、前節で導入した集合正規表現は集合 言語を表します。Σ上の集合正規表現の解釈を示します。
最後の2つの違いが分かりにくいかもしれないので、具体例を出しましょう。 正規表現Eの意味(それが表す集合言語)をM(E)と書くことにします。演算子 「&」に対応する意味的な集合演算も、便宜上同じ記号&で示します。
つまり、正規表現 (a | (b | c?)) が表す出現パターンは次のいずれか。
それに対して、(a & (b | c?))が表す出現パターンは次のいずれか(出現順 序は無関係)。
最初の事例に戻りましょう。
sleepコマンドに指定できる正しい属性パターンは、((Second & Millisec) | Second | Millisec)という集合正規表現で書けます。これはまた、(Second & Millisec?) | (Millisec & Second?)とも書けますね。ところで、記号Second, Millisecはホントの原子記号ではありません。「second=int」をSecondで、 「millisec=int」をMillisecで代用していました。つまり、Secondには 「second=int」の意味が閉じこめられていたのです(Millisecも同様)
ですから、M(Second) = {{Second}} という解釈は不適当です。記号Secondの 意味するものは、「second=int」が意味するものです。そして「second=int」 が意味するものとは、second="1"とかsecond="3"とかの具体的な属性指定の集 合でした。よって、次のように考えるのが適当でしょう。
この意味定義式の右辺は、属性インスタンスの集合の集合です。より一般に、 なんでもいいから集合の集合Pow(Pow(X))があれば(*注5)、演算∪と演算&(本物の演 算です)は定義できるので、次のような“集合正規表現の一般的解釈”が可能にな ります。
Pow(X)はXのベキ集合。
コンピュータで扱う典型的なコレクション・データは、列(リスト)、バッ グ(マルチセット)、そして集合です。列の正規表現は普通の正規表現、この 記事で扱ったのが集合の正規表現です。興味がある方は、メンバー重複を許す 集合であるバッグの正規表現を定義してみてください。
列正規表現が、列言語の代数だけではなくて、一般のKleene代数に対して解 釈できるように、集合正規表現は、Pow(Pow(X))上の演算∪、&をうまく公理化 した代数系に対して解釈できるでしょう。それがどんな代数系なのか、僕は知 りませんけど。