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

書き忘れていたけど、この文書は、James Clarkの書いたderivativeのドキュメントは意味が良く分からないし、Haskellコードの説明もあまり無いから不安だ、という人向けであって、あの文書を読まなくてもこれさえ読めばderivativeが実装できる、というものではない。あの文書はかなり分かりやすく書かれているはずなので、分からないとしたら、どちらかと言えば読者の知識の問題のはずである(笑)

この一連の文章は、全て考えながらまとめているものなので、全部書き終わってから、ひとつのまとまった文章として再掲するつもりでいる。1年くらい前に書いたXML Schema Inferenceの動作に関する一連のエントリ(1,2,3,4,5)と同じような位置付けだと思ってもらえれば幸い。

さて、今回はendTagDerivまでのvalidationの流れを一気に概説してしまおう。

startTagOpenDeriv (Group p1 p2)の続き

前回の説明の切れ目がちょっと悪かったので、少し補足しておこう。

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

この変数xは「『p1に対してstartTagOpenDerivを適用した結果』にp2が続いている状態」ということになるが、in 以降の式では、p1がnullableなら、xと(startTagOpenDeriv p2 qn)とのchoiceを返すよう定義されている。これはつまり、p1がnullableであれば、上記xであっても良いし、もしxがnotAllowedになるようであれば、p1は空集合でも良いのだから、「p2に対してstartTagOpenDerivを適用した結果」であっても良い、ということである。

Afterパターン

あるElementパターンに対してstartTagOpenDerivが適用されると、その結果はこのderivativeアルゴリズムで導入されているAfterというパターンになる。これは、ある入力パターンに対して、要素の開きタグを受理された後の内容（属性・子孫）を表すものだ。(Element nc p)にstartTagOpenDerivを適用した結果がどうなるか、見てみよう:

startTagOpenDeriv (Element nc p) qn =  

  if contains nc qn then after p Empty else NotAllowed

after p Empty というのは、とりあえず(After p Empty)と同じようなものだと考えれば良い。ある開きタグの内容として、pがあり、その後Emptyが続く、ということである。

このAfterパターンは、そのstartTagOpenDerivで開いた要素が、endTagDerivで閉じるまでずっと保持されるが、endTagDerivについて今ここで詳しく説明すると段階をすっ飛ばすことになってしまうので、今はここまでとしておく。

att(s)Deriv: 属性のvalidation

startTagOpenDerivが終わると、属性のvalidationに入る。derivativeアルゴリズムでは、全ての属性を引数にattsDerivが呼び出される。

XMLをliterallyに検証していれば、要素のQNameはローカルxmlns宣言に依存するので、全ての属性をチェックしなければならず、従って開始タグのストリーミングイベント（SAXのstartElementなど）を処理する時点で、同時に全ての属性が渡されているであろう¹。そのような場合は、startTagOpenDeriv, attsDeriv, startTagCloseDerivは、全て同じストリーミングイベント内で処理することが求められる。

さて、attsDerivの定義を見てみよう:

attsDeriv :: Context -> Pattern -> [AttributeNode] -> Pattern  

attsDeriv cx p [] = p  

attsDeriv cx p ((AttributeNode qn s):t) =  

  attsDeriv cx (attDeriv cx p (AttributeNode qn s)) t

((AttributeNode qn s):t) とあるのは、’:‘の前が[AttributeNode]中の最初の属性ノード、tがそれ以降を表す。最後の1行では、先頭の属性についてattDerivを適用し、その結果と、tについて、attsDerivを再帰的に呼び出していることになる。

つまり、実際にはほとんどattDerivを繰り返し適用しているのと変わらない。途中の属性のどこかで、Patternが一度でもnotAllowedになれば、（attDeriv notAllowed はnowAllowedなので）そのattsDeriv全体がnotAllowedとなる。

従って、検証系に属性リストが実際に渡される必要は無く、属性ひとつひとつについてattDerivが呼び出されれば、それで十分にvalidationを行うことは可能である。

さて、ひとつの属性 (Attribute nc p) を引数とするattDerivの定義は次のようになっていて:

attDeriv cx (Attribute nc p) (AttributeNode qn s) =  

  if contains nc qn && valueMatch cx p s then Empty else NotAllowed

Elementに対するchildDerivを簡略化したような内容になっている（属性の内容は常に文字列なので、childrenDerivではなく、textDerivの一部であるvalueMatchが適用されていると考えればよい）。

startTagCloseDeriv: 必須属性の存在チェック

現在のXMLインスタンス要素の属性を全てチェックしたら、次に呼び出されるのはstartTagCloseDerivである。このderivative関数の主な目的は、必須属性としてパターン中で定義されているにもかかわらず、現在のインスタンスに出現しなかったものが無いかどうか、チェックすることである。

これを実現するには、AttributeパターンにstartTagCloseDerivを適用した場合にnowAllowedを返すようにすれば良い。startTagCloseDerivの定義は簡単だ:

startTagCloseDeriv :: Pattern -> Pattern  

startTagCloseDeriv (After p1 p2) =  

  after (startTagCloseDeriv p1) p2  

startTagCloseDeriv (Choice p1 p2) =  

  choice (startTagCloseDeriv p1) (startTagCloseDeriv p2)  

startTagCloseDeriv (Group p1 p2) =  

  group (startTagCloseDeriv p1) (startTagCloseDeriv p2)  

startTagCloseDeriv (Interleave p1 p2) =  

  interleave (startTagCloseDeriv p1) (startTagCloseDeriv p2)  

startTagCloseDeriv (OneOrMore p) =  

  oneOrMore (startTagCloseDeriv p)  

startTagCloseDeriv (Attribute _ _) = NotAllowed  

startTagCloseDeriv p = p

Attribute以外のほぼ全てのパターンについて、再帰的にstartTagCloseDerivを適用した結果をグルーピングして返しているか、そのまま返しているかのどちらかだ。

属性が任意指定であれば、その定義は (Choice Empty (Attribute nc p))のようになっているはずなので、EmptyとNotAllowedのchoiceとなり、Emptyになる。

閉じタグの処理

ある要素から存在する子孫を全てvalidateして、その要素を閉じようとする時、注意しなければならないのは、その要素の内容として、必須のものがあるにもかかわらず、それが出現しなかった、という場合をエラーとすることだ。このチェックはendTagDerivという関数で行われる。

ということでendTagDerivの説明に入りたいところだが、実はその前にもう一つチェックしておかなければならないことがある。それは、XMLインスタンスが空要素であったら、endTagDerivをチェックする前に、「あたかも長さ0のテキストノードが存在したかのように」内容チェックをしなければならない、というものである。これは、以前に説明した通り、仕様書のセクション6.2.7のweak match 3、derivativeアルゴリズムのchildrenDerivで定義されたとおりだ。ここで再掲しておこう²:

childrenDeriv cx p [] = childrenDeriv cx p [(TextNode "")]

さて、仮定的な空文字列をvalidateしたら、ようやくendTagDerivをチェックすることが出来る:

endTagDeriv :: Pattern -> Pattern  

endTagDeriv (Choice p1 p2) = choice (endTagDeriv p1) (endTagDeriv p2)  

endTagDeriv (After p1 p2) = if nullable p1 then p2 else NotAllowed  

endTagDeriv _ = NotAllowed

ここで、Afterパターンについて復習しておこう。(After p1 p2)とは、あるタグの内容としてp1が、そのタグを閉じた後の兄弟ノードとしてp2が、それぞれ期待されている、という意味である。いま、endTagDerivはそのタグを閉じようとしているのだから、p1がもし空集合を許容しないのであれば、まだ必須の内容が残っていると考えなければならない。この場合、「必須の内容」には2通り考えられる:

• データ型を定義されたテキスト、すなわちdataまたはvalue
• 要素

「空集合が許されるかどうか」は、前述のnullable関数でチェックできる。もし許容されないのであれば、NotAllowedが返されることになる。

この関数では、Afterパターンの内容として、After, Choice, NowAllowedしか出現しないという事実³と、閉じタグは対応する開きタグが存在したはずであるという事実を、それぞれ前提としている。すなわち、startTagOpenDerivの後はChoiceまたはAfterになっていることが前提である。

（もしストリーミングプロセッサに何らかのバグがあって、イベントが適切な順序で処理されないということがあれば、正しくvalidationが行われないので、注意が必要である⁴。もし、ストリーミングプロセッサとバリデータの両方を同時に実装していて、バグ潰しに悩まされているのであれば、まずストリーミングプロセッサにバグがないかどうか、確認した方が良いかもしれない。）

もしここでAfterパターンについて、内容p1が無事nullableであれば、後続兄弟のパターンp2が返されることになる。

…さて、ここまでで、ひとつの要素をvalidateするための関数の説明は終わった。次回は、ここまで説明を簡単にするために省略してきた、複雑なパターンについて説明する。⁵

コメント

村田 — 01/10/2006 23:17:43

Jamesのアルゴリスムは、balanced context-free grammars
を使って理解するのがもっとも分かりやすいと思います。
以下の論文に書いた説明は、細部をすぺて省いているので
実装の役にはあまり立ちませんが、全体像を捕らえるのには
よいと思います。

http://web.cs.wpi.edu/~mmani/toit/taxonomy/new/taxonomy.pdf

atsushieno — 01/11/2006 02:25:56

あっ、これはXMLOpen2004の時に、村田さんに「発表内容は全部ACMにある」とされていたものではないですか（お陰様ですっかり「騙されて」裏番組だったMonoの発表に行ってしまいました）。
balanced context free grammarsの実体は
http://www.mulberrytech.com/Extreme/Proceedings/html/2004/Bruggemann-Klein01/EML2004Bruggemann-Klein01.xml
のようですが、Dyck languageとか、僕の数学のレベルではまだ読み下せませんね…PCAというのは面白そうなのでじっくり読んでみます。