ものがたり(旧)

atsushieno.hatenablog.com に続く

derivativeアルゴリズムについて(2)

前回は導入、childDerivおよびchildrenDerivについての解説で終わってしまったので、今回は、実際のパターン（内容モデル、みたいなもの）のvalidationについて、導入的な説明を試みる。

RELAX NGのパターンとXML Schemaの内容モデル

XML Schemaでは、内容モデルとは、要素の開きタグと閉じタグの間に出現する要素とテキストのことである。属性は含まれないし、処理命令やコメントは含まれないが、空白テキストは含まれる（xml:space="preserve"でない場合も同様）。 という要素があるとき、foo要素の型が、xs:stringから派生した、minLength=3であるfacetをもつsimpleTypeであれば、このインスタンスはinvalidである。（同様のルールがRELAX NGにも存在する。厳密な処理規則は前述）。

RELAX NGでは、内容モデルではなくパターンという概念が用いられる。パターンと内容モデルは異なる。最も重要な違いとして、パターン定義には属性を含めることができる。たとえば、属性aまたは子要素Aが出現できる（Aとaが両方存在したら文法エラー）という定義が出来る（XML Schemaでは出来ない）。

ただし、属性のvalidationは内容モデルのvalidationとは異なる側面が多い（たとえばgroupはinterleaveと同義である）ので、ここでは言及しない。あくまで要素とテキストのみを対象とする。

RELAX NGのsimple syntaxで定義されるパターンは次の通りである:

group x y
xの後にyが出現する
choice x y
xまたはyが出現する
interleave x y
xの後にy、またはyの後にxが出現する
oneOrMore x
xが1回以上出現する
text
テキストが出現する。空文字列でも良い
data qname params
特定のデータ型（型名がqname、パラメータがparams）で受容できる文字列が出現する
value qname v
特定のデータ型（型名がqname）で値がvである文字列が出現する
list x
空白文字で区切ったらそれぞれがxにマッチする文字列となるような文字列が出現する（つまり入力文字列を空白で区切ると文字列群になり、その1つ1つがxにマッチする）*1
empty
空集合にマッチする
notAllowed
何が出現することも許さない。これがderivative関数から返されると、文法エラーということになる
element qname x
名前がqnameで内容がxであるような要素が出現する
attribute qname x
名前がqnameで内容がxであるような属性が出現する

derivativeアルゴリズムでは、dataのうちexceptをもつものをDataExceptとしてdataとは区別している。さらに、後述するが、ある入力を受理した後の内容モデルというものを表現するために、Afterというモデルを用意している。

これらは全て、そのままステートレスなオートマトンとして使える（何を言ってるのか分からないという人は、とりあえず気にしなくても大丈夫だ）。

以降のderivative関数の定義では、引数パターンによって戻り値を導出する式が変わってくる。逆に言えば、JavaやC++のようなオブジェクト指向言語では、derivative関数はすべてパターンを表すクラスに定義することができる（ただしsubjectとobjectを入れ替えることになるので、ソースが読みにくくなる）。

validationを「体験」してみる

derivative関数を直感的に理解するのに一番良いのは、「体験」する、すなわち実際に手を動かしてみることである。もっとも分かりやすい例を挙げるなら、text あるいは (Element (Name "" foo) empty) という状態で<bar/>という要素が出現したら、その状態遷移の結果はnotAllowedとなる（すなわち、そんな要素はinvalidである）。

いま、上記の例を表す(Element (Name "" "bar") Empty) という要素が出現したとしよう。要素が出現したとき、ChildDerivではstartTagOpenDerivがまず計算される。

textパターンに適用されるstatTagOpenDerivは、デフォルトのものだ:

startTagOpenDeriv :: Pattern -> QName -> Pattern

これは、ある状態（パターン）において、あるQNameをもつ要素が出現した場合の状態遷移に用いられる。

startTagOpenDeriv _ qn = notAllowed

(Element (Name "" foo) Empty) には、次のものが適用される:

startTagOpenDeriv (Element nc p) qn =

  if contains nc qn then after p Empty else NotAllowed

これは、contains nc qn がfalseを返すので

contains (Name ns1 ln1) (QName ns2 ln2) =

  (ns1 == ns2) && (ln1 == ln2)
notAllowedが返される。

では、引数パターンがchoiceの場合はどうだろうか。これは簡単だ:

startTagOpenDeriv (Choice p1 p2) qn =

  choice (startTagOpenDeriv p1 qn) (startTagOpenDeriv p2 qn)

choiceの場合、その2つのブランチそれぞれに対してstartTagOpenDerivを適用して、そのいずれかがnotAllowedでなければ良い（上記Haskellコードで使われているchoice関数も別途定義されているので、James Clarkのページを参照）。

引数が (Group p1 p2) の場合は多少めんどくさい。まず、p1にstartTagOpenDerivを適用して、notAllowedでなかった場合は、そのままvalidationを続行しても良さそうだ。

しかし、もしnotAllowedであれば、今度はstartTagOpenDerivをp2に適用…とするわけにはいかない。

(Group (Element (Name "" "foo") Empty) (Element (Name "" "bar")))
というパターンがあった場合、<bar/> は<foo/>ではないのだから、invalidである。

かといって、常にnowAllowedであるとは限らない。たとえば「要素fooが0個以上あって、その後にbar」というパターンは、このbar要素の出現を許すだろう。このパターンをこのアルゴリズムのデータ構造で表すと



(Group 

  (Choice

    Empty

    (OneOrMore (Element (Name "" "foo") Empty) ))

  (Element (Name "" "bar") Empty))
となるが、最初のChoiceにstartTagOpenDerivを適用した結果がNotAllowedであっても、Group内の2つ目のElementに対してstartTagOpenDerivを適用した結果が返せるはずだ。

この違いは、最初の引数が空集合にマッチするかどうか、にかかっている。すなわち、前者のGroupの第1引数 (Element (Name "" "foo") Empty) は、<foo/> という要素が存在することを必須としている。しかし後者のGroupの第1引数はEmptyでも良い。

これは、derivativeアルゴリズムでは nullable という関数で表されている。



nullable:: Pattern -> Bool
nullable (Group p1 p2) = nullable p1 && nullable p2

nullable (Interleave p1 p2) = nullable p1 && nullable p2

nullable (Choice p1 p2) = nullable p1 || nullable p2

nullable (OneOrMore p) = nullable p

nullable (Element _ _) = False

nullable (Attribute _ _) = False

nullable (List _) = False

nullable (Value _ _ _) = False

nullable (Data _ _) = False

nullable (DataExcept _ _ _) = False

nullable NotAllowed = False

nullable Empty = True

nullable Text = True

nullable (After _ _) = False

このnullableという関数を使って、Groupに対するstartTagOpenDerivは、次のように定義されている:



startTagOpenDeriv (Group p1 p2) qn =

  let x = applyAfter (flip group p2) (startTagOpenDeriv p1 qn)

  in if nullable p1 then

       choice x (startTagOpenDeriv p2 qn)

     else

       x

applyAfterとかflipというのは後で詳しく説明するが、とにかく、xに代入されているのは、「『p1に対してstartTagOpenDerivを適用した結果』にp2が続いている状態」だと思ってもらえればいい。

ちっとも数学的ではないけど、ここまででだいたい半分くらいまで説明した（つもり）。

*1:listは文字列を表すものであって、(choice empty (oneOrMore x) ) とは異なることに注意。