属性のための正規表現

1. はじめに

正規表現をご存じの方は多いでしょう。文字列パターンを正規表現 により表すことは、テキスト処理の基本的テクニックですね。XMLでも、要素 内容に出現する子要素およびテキストのパターンを、正規表現で表します。こ の事情は、古典的なDTDでも最近のスキーマ言語でもだいたい同様です。

ひとくちに正規表現とはいっても、随分といろいろなバリアント（方言、変 種）があります。例えば、連接（concatenation）は特に演算子（メタ文字） を用意せず、単に並べる方式（ピッタリくっつけると問題が生じるなら空白を はさんで並べる）もあれば、明示的な演算子（例えば「,」）を使うこともあ ります。

使える演算子のレパートリも色々です。多くの例では、「|」「*」「?」「+」 を使います。しかし、A+ は AA* と書けばいいので「+」は落とすことができ ます。一方、定数EMPTYを導入するなら、A? は (A | EMPTY)、A* は (EMPTY | A+) と書けるので、今度は「?」「*」を落とすことができます。AAA を A3 と 書けたり^(*注1)、さらに、(AA | AAA | AAAA) を A{2-4} と書けたりすると便 利です^(*注2)から、そういう拡張を取り入れた正規表現もあります。

さて、この記事では、かなり変わった正規表現の一種を紹介します。この正 規表現は、演算子のレパートリが違う（が、表現力は同じ）といった程度の違 いではなくて、通常の正規表現とは本質的な違いがあります。まずは、XML属 性の出現パターンの表現として、この正規表現を導入して、後でその概念を整 理しましょう

2. 事例：sleepコマンド

最初の事例を出しましょう（作為的、人為的です:-)）。XML構文のスクリプ ト言語があるとして、そのコマンドにsleepがあります。<sleep second="3"/> は3秒間のスリープです。ミリ秒単位で指定したいなら、<sleep millisec="500" /> のようにします。あ、そうそう、 属性secondも属性millisecもint型^(*注3)です。

このsleepコマンドの正しい使用法は次のとおりです。

1. 属性second、属性millisecの少なくとも1つは指定されてないとダメ。
2. secondだけが指定されていれば、指定された秒数だけスリープ。
3. millisecだけが指定されていれば、指定されたミリ秒だけスリープ。
4. secondとmillisecの両方が指定された場合は、それらを足した時間だけスリー プ。例えば、<sleep second="3" millisc="500" /> なら、3.5秒間だけス リープ。

3. 正しい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

4. 普通の正規表現で書いてみる

いま、「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つとも必須、 つまり必ず出現が要求されているとして、それを正規表現で表してください。………………

………………僕（檜山）は結果を書き下すことはしませんが、演算子「|」を イッパイ含んだ、長い正規表現になります。

5. 属性向けの正規表現

そもそも、属性は出現順序の概念がないのです。それなのに、順序が本質的 である列正規表現を使うのはバカげた話です。“出現順序の概念”や“順序を 考慮した連接演算”を考える必要はありません。

そこで順序を考慮しない正規表現を考えましょう。つまり列ではなくて、単 なる集合（有限集合）が対象です。でも、列の場合と同様に、アルファベット （基本構文素）から出発します。アルファベットとしては、先の例の{Foo, Bar, Baz, Zot}をとります。このアルファベットの部分集合はけっこうたくさ んありますが、全部列挙できます。そのうちのいくつかを挙げれば、{}, {Foo}, {Foo, Zot}, {Foo, Bar, Baz, Zot}とかです。

アルファベットの部分集合は、ちょうど属性の出現に対応します。上の4つの 部分集合は、次の4つの出現パターンに対応しますね。

1. <example />
2. <example foo=int />
3. <example foo=int zot=long />
4. <example foo=int bar=string baz=date zot=long />

さて、列ではなくて集合の正規表現は次のように定義されます。

1. アルファベットのメンバーは正規表現であり、そのメンバーの出現を表す。
2. 定数EMPTYは空集合（何も出現しない）を表す^(*注4)。
3. A、Bが正規表現のとき、(A | B)は正規表現であり、Aによるパターン、ま たはBによるパターンを表す。
4. A、Bが正規表現のとき、(A & B)は正規表現であり、Aによるパターンと Bによるパターンが同時に出現するパターンを表す。

4番目の「&」が、連接に代わる新しい演算子です。ちょっと分かりにくいの でいくつか例を出します。

• Foo & Zot ：<example foo=int zot=long />
• Foo & (Zot | EMPTY) ： <example foo=int zot=long /> または <example foo=int />
• (Foo & Bar ) & Zot ： <example foo=int bar=string zot=long />

(A | EMPTY)を A? と書くことにするとより使いやすいでしょう。 例えば、Foo & (Zot | EMPTY) は Foo & Zot? と書けます。「?」は普通通り、 省略可能である（出現しなくていい）ことを表します。

6. 属性パターンから集合正規表現へ

この節で事情をハッキリさせましょう。

アルファベットとは、構文構成素と思える記号／モノの集合です。アルファ ベットΣ上の集合とは、Σの部分集合のことだとします。集合の集合は（列の集 合が列言語であると同様に）集合言語と呼んでいいでしょう。「すべての部分 集合を考える」という操作（べき集合）が2回出てくるのでちょっとややこし いですけど。

列正規表現が列言語を表すのと同様に、前節で導入した集合正規表現は集合 言語を表します。Σ上の集合正規表現の解釈を示します。

1. アルファベットのメンバーである正規表現「a」は、単元集合{a}だけから なる言語{{a}}を表す。
2. 定数EMPTYは、空集合だけからなる言語{{}}を表す。
3. (A | B)は、(Aの意味)∪(Bの意味) を表す。
4. (A & B)は、{x∪y | x∈(Aの意味)、y∈(Bの意味)}を表す。

最後の2つの違いが分かりにくいかもしれないので、具体例を出しましょう。 正規表現Eの意味（それが表す集合言語）をM(E)と書くことにします。演算子 「&」に対応する意味的な集合演算も、便宜上同じ記号&で示します。

・ a | (b | c?)

・ a & (b | c?)

つまり、正規表現 (a | (b | c?)) が表す出現パターンは次のいずれか。

1. a
2. b
3. c
4. 空

それに対して、(a & (b | c?))が表す出現パターンは次のいずれか（出現順 序は無関係）。

1. a, b
2. a, c
3. a

7. 集合正規表現の一般的な解釈

最初の事例に戻りましょう。

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)、演算∪と演算&（本物の演 算です）は定義できるので、次のような“集合正規表現の一般的解釈”が可能にな ります。

1. アルファベットのメンバーである正規表現「a」は、適当な集合の集合 B(a)∈Pow(Pow(X))に割り当てる。
2. 定数EMPTYは、空集合だけからなる集合{{}}を表す。 {{}}は、Pow(Pow(X))のメンバーである。
3. (A | B)は、(Aの意味)∪(Bの意味) を表す。
4. (A & B)は、{x∪y | x∈(Aの意味)、y∈(Bの意味)}を表す。