各種正規表現の（仮）記法

• 関連記事：属性のための正規表現
• 関連記事：属性か内容か？それは問題ではない
• 関連記事：Kleene代数とその周辺

1. はじめに

通常の正規表現は、列（シーケンス、リスト）言語を定める正規表現である。 しかし、項目（item, member）の順序を問題にしない場合もあり、そのときは、列言 語よりもバッグ（マルチセット）言語がふさわしい。さらに、重複出現があり 得ないときは集合（セット）言語が適切となる。

列言語に対して正規表現（通常の正規表現）があるのと同様に、バッグ言語、 集合言語に対する正規表現も定義できる。これら3種の正規表現に同じ記法を 使ってもよいのだが、混乱のおそれがある。正規表現の種類（列／バッグ／集 合）をすぐさま区別できるような記法があれば便利だろう。

この記事では、そのような記法（構文）を提案する。

2. 演算子記号

通常の正規表現で使われている演算子記号（結合子、メタ文字）は次のもの である。

バッグ正規表現、集合（セット）正規表現では、「,」に代えて「&」を使う ことにする。「&」は、バッグまたは集合の合併（ユニオン）を意味する。 AとBがバッグ（または集合）言語のとき、A & B の意味は次のように定義される。

• A & B = {a∪b | a∈A, b∈B}

• x∈(A & B) ⇔ 適当なa∈Aとb∈Bがあって、x = a∪b と書ける。

「,」の代わりに「&」を使う以外は、通常の正規表現と同じ演算子記号を使 う。ただし、集合正規表現のときは「+」は意味がなく（a+ = aだから）、「*」 と「?」は同じ意味である。よって、標準的に「?」だけを使うことにする。

3. 種別を区別する

正規表現の種別（列／バッグ／集合）を区別するために、次のルールを設ける。

• 列正規表現は、一番外側を丸括弧（パーレン）で囲む。
• バッグ正規表現は、一番外側を角括弧（ブラケット）で囲む。
• 集合正規表現は、一番外側を波括弧（ブレイス）で囲む。

例えば次のようになる。

• (a?, (b|c)*, d)
• [a? & (b|c)* & d]
• {a? & (b|c)? & d}

正規表現の種別（列／バッグ／集合）判定は、一番外側の括弧で行うので、 内部の括弧は丸括弧でよい。

別案として、一番外側にキーワードを付けることが考えられる。例えば：

• Seq(a?, (b|c)*, d)
• Bag(a? & (b|c)* & d)
• Set(a? & (b|c)? & d)

4. 補足 OR 蛇足

正規表現はKleene代数により解釈されるべきものだが、表現自体には解釈の 場や方法の指定は含まれない。種別を指定した正規表現は、（ある程度は）解 釈（意味論）に対する指示を含んでいる。つまり、列正規表現が 一般のKleene代数で解釈されるのに対して、バッグ正規表現は可換Kleene代数、 集合正規表現は乗法が可換かつベキ等であるKleene代数で解釈される。