今僕は、明瞭正規表現なる正規表現のサブセットについて考えています。明瞭正規表現とは何であって、なぜそんなものが必要になるのかを説明します。
内容：
概要
明瞭正規表現は、Catyの型システム／スキーマ処理系で使います。2,3ヶ月(?)後のCatyコアには、正規表現型（regular expression type）が入るでしょう。Catyの正規表現型は一般的正規表現をフルサポートはしません。制限された正規表現のみを許します。その制限された正規表現を明瞭正規表現と呼ぶのです。
現状のCatyの型システム
実例で説明します。x座標とy座標が整数である座標平面の点を、JSON配列で表すとします。例えば、[2, 3] のように。この「点を表す配列の型」は、Catyの型表現（type expression）では [integer, integer] と書けます。配列の3番目には、点の名前をオプショナルに入れてもいいとしましょう。例えば、[0, 0, "Origin"], [2, 3, "p"] のように。この点の型は [integer, integer, string?] と書けます。
さらに、配列インスタンスが点を表すことを明示するために、@point [2, 3], @point [0, 0, "Origin"] のように書くこともできます。@point はタグと呼びます。“タグ付き配列で表す点”の型定義は次のように書きます。
/** 座表値が整数である2次元の点 * オプショナルに、名前（文字列）を付けてもよい */ type Point = @point [integer, integer, string?];
複数の点を結んだ折れ線は、点のリストで表すことができます。ただし、点が1個、2個だと折れ線という感じがしないので、3個以上の点を結んだ図形を折れ線（polyline）と呼ぶことにします。折れ線データの型は次のように定義できます。
/** 3個以上の点を線分で結んだ折れ線 */ type Polyline = [Point, Point, Point, Point*];
以上の型定義には疑問符「?」、星印「*」が出てきますが、これらの記号は正規表現におけるオプショナル、任意回の繰り返しの意味で使われています。
正規表現型
Catyの型表現内では、「?」と「*」、それに「|」も使えます。こう言うと正規表現をフルサポートしているようですが、実際は次の形のパターンしか使えません。
- n項のタプル形 [T1, T2, ..., Tn]
- リスト型 [T*]
- 最後が省略可能なタプル型*1 [T1, T2, ..., Tn?]
- タプルとリストが混合した型 [T1, T2, ..., Tn*]
この程度の表現／定義の能力でも、Webフォームからの入力を扱うには十分、というか相当にオーバースペックです。しかし、「拡張JSONで表現したXMLの正規形」で紹介した方法でXMLデータをXJSON（Extended JSON）に埋め込んで文書処理をしようとすると、次のような型定義が必要になります。
/** レポート文書本文の内容モデル */ type reportBody = [p*, section, section*, conclusion?];
つまり、配列の項目パターンを正規表現で記述したいという要求が発生するのです。正規表現により定義した、シーケンス型のサブタイプを正規表現型（regular expression type）と呼ぶので、この要求は「型システムに正規表現型を導入せよ」と言い換えられます。
正規表現型を実装した言語／システムとしては、細谷晴夫さんによるXDuceが有名です。類似品にXHaskellなんてのもあるようです。
高速に処理するために
Catyに正規表現型を導入するにあたって、妥当性検証処理ができるだけ高速にできて、しかもアルゴリズムが複雑にならない方法を目標にします。ここで、高速とは次の意味です。
- 正規表現からオートマトンへのコンパイルが速い。
- オートマトンの実行が速い。
オートマトンの実行を速くするには、決定性オートマトンにすればいいのです。任意の正規表現を決定性オートマトンにコンパイルすることができます。しかし、そうするとコンパイルに時間がかかります。一方、「この機会にマスターしようぜ、正規表現、構文図、オートマトン」で紹介したような、構文図をオートマトンに使うような単純なコンパイル法だと、実行時にバックトラックや先読みが必要になってパフォーマンスが出ません。
任意の正規表現を相手にしている限り、コンパイル速度と実行速度の両立は難しいでしょう。そこで、使える正規表現に制限を付けて、特定の正規表現に対する高速処理にフォーカスすることにします。
問題は、どのような正規表現サブセットを選ぶか？ そして、そのサブセットで実用性が保てるか？ です。
明瞭正規表現
単純なアルゴリズムにより「正規表現→オートマトン」と変換したとき、作られたオートマトンが決定性になるような正規表現／正規言語のクラスは１990年代から研究されています。
以下の2つの論文は同じ著者（Bruggemann-Klein & Wood）のもので、1997年の論文が1991年論文の改訂増補版となっているので、1997年版だけを読めば十分でしょう。必要なことは全部コレに書いてあります。
ところで、最初の論文では「決定性」（deterministic）という形容詞が使われていますが、二番目では「1-非曖昧」（one-unambiguous）に変わっています。正規表現と正規言語に対する形容詞として「決定性」はよろしくないので変更したのでしょうが、「イチ・ヒ・アイマイ」も「ワン・アンアンビギュアス」も言いにくい！ それに、曖昧とか非曖昧という用語の意味も人により微妙に違っていて、曖昧の意味が曖昧なんですよ。
それで、僕は「明瞭」って言葉を使うことにします。あえて新しい言葉を使うには、次の事情もあります。
- 明瞭性は正規表現（式）に関する性質であり、正規言語の性質として「明瞭」は定義しない／使わない。
- 明瞭性の条件は、実用上の要求から one-unambiguous より強くなっている。
明瞭正規表現は、それをオートマトンに単純にコンパイルしたとき決定性になります。これが明瞭正規表現の定義でもあります。身も蓋もなくご都合主義的な定義です。
明瞭正規表現に制限しても大丈夫か？
a, bを基本記号として、(a, a*)?、(a? | b)、 (a | (a, b))、(a?, b?, a?) などは明瞭正規表現ではありません。つまり、明瞭正規表現に制限をすると、これらの正規表現は使用できなくなります。それで大丈夫なのでしょうか？
実は、SGMLのISO標準には、事実上は明瞭性と同じ制限が書いてあり、SGML処理系はその制限のなかで動作します。（Bruggemann-Klein & Wood 論文の動機（のひとつ）は、SGML仕様に書いてある制限を理論的に探求することでしょう。）大雑把に言えば、SGMLのDTDはすべて、明瞭正規表現の範囲内で書かれてきたのです。これは、明瞭正規表現に制限しても実用性は担保できることの強い状況証拠です。
先にも述べたように、明瞭正規表現の定義は「実装に都合がよい形」というもので、理論的な根拠は余りありません。正規言語のクラスとしては美しくなく、応用によっては明瞭性の制限が邪魔になることもあります。しかし、僕らにとっては高速処理できることが優先度が高い要求なので、明瞭正規表現ベースの正規表現型を採用します。それと、Catyの型システムの構造上、明瞭性制限による弊害が深刻な形で出ることはないとふんでいます。
明瞭正規表現の詳しい話は次の機会に。
*1:便宜上、[S, T?, U?] のような書き方もできますが。T?, U? の部分の解釈は本来の正規表現とは異なり、Tを省略してUを書くことが許されません。
