再帰的定義

2003年1月5日(日)更新


■要素の子要素に自分自身が出てくる例

たけち: 今回は、新しい文法というわけじゃなくて、今まで勉強した文法を使って、ちょっと変わったテクニックを勉強することにするね。

さらら: ちょっと変わったテクニック?

たけち: うん。まあ、プログラミングの分野ではそれほど変わったテクニックでもないんだけれど... まずは以下のDTDと、それに相当するXML Schemaを見てみようか。

さらら

DTD: 再帰的定義の例-1
<!ELEMENT recursion ( recursion | end )>
<!ELEMENT end EMPTY>

XML Schema: 再帰的定義の例-1

<?xml version="1.0" encoding="Shift_JIS" ?>
<xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema">

<xsd:element name="recursion" type="RecursionType" />

<xsd:complexType name="RecursionType">
<xsd:choice>
<xsd:element ref="recursion" />
<xsd:element ref="end" />
</xsd:choice>
</xsd:complexType>

<xsd:element name="end" type="EndType" />

<xsd:complexType name="EndType" />

</xsd:schema>

たけち: DTDにするとわずか2行だから、どういうスキーマかわかるよね。

さらら: えっ、recursion要素の定義の中にrecursion要素自身が出てくるの?

たけち: そうなんだよ。こういうスキーマは例えば、

<?xml version="1.0" encoding="Shift_JIS" ?>
<recursion>
<recursion>
<recursion>
<recursion>
<end />
</recursion>
</recursion>
</recursion>
</recursion>

 とか、

<?xml version="1.0" encoding="Shift_JIS" ?>
<recursion>
<end />
</recursion>

 に適合するよね。


■再帰的定義

さらら: う〜ん、わかるような、わかんないような。。。

たけち: 不思議に見えるかもしれないけれど、これはこれでちゃんとした定義なんだよ。

さらら: ふ〜ん。

たけち: こういう、自分の中に自分が出てくるような定義のことを、再帰的定義と呼ぶんだ。再帰というのは不思議に思えるかもしれないけれど、実はコンピュータの世界でも、そして実際の世界でも、あたりまえに存在しているんだよ。

さらら: へぇ〜。でも、こんなスキーマって役に立つのかしら?

たけち: あっ、これはもっとも単純な例だからね (^ ^;) 今度は実際に役立ちそうなスキーマの例を出してみようね。

DTD: 再帰的定義の例-2
<!ELEMENT div ( div | p )+>
<!ATTLIST div title CDATA #REQUIRED>
<!ELEMENT p (#PCDATA)>

たけち: こういうDTDには、次のようなXMLデータが考えられるよね。

XMLデータ: 再帰的定義の例-2に合致するインスタンス
<?xml version="1.0" encoding="Shift_JIS" ?>
<div title="万葉への旅">
  <div title="序章">
    <p>昨年、秋、僕はふと奈良に行きたくなった。万葉の足跡を急に辿りたくなったのだ。この本はそのときのことを書いた物語である。</p>
  </div>
  <div title="第一章 旅へ">
    <div title="1.その頃僕は">
      <p>その頃、僕は仕事に疲れていた。いつものように家に帰り、何もやる気が起きずに、体をすぐに横たえた。体を動かしたとき、積み重なった本が倒れ、万葉集が出てきた。「そうだ奈良へ行こう」そう僕は決心した。</p>
    </div>
    <div title="2.汽車の切符を握りしめて">
      <p>僕はさっそく駅へ向かい、片道切符を買った。汽車に揺られながら、あすの仕事のことを忘れ、切符を握りしめていた。奈良の風景だけを思い描いていた。</p>
    </div>
  </div>
</div>

さらら: あぁ、そっかぁ。章とか節とか、要するに文章の塊をいくらでも細分化できるスキーマなのね。

たけち: そう、最初から「章の一つ下の階層は節で...」みたいに決めたスキーマを作ってもいいけれど、こういう再帰的なスキーマだと、いくらでも下の階層を細分化できる、という柔軟性があるよね。じゃあ、これのXML Schemaを書いてみようか。

さらら: え、えっと。。。。。こうかしら (^ ^;

さらら

XML Schema: 再帰的定義-2
<?xml version="1.0" encoding="Shift_JIS" ?>
<xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema">

<xsd:element name="div" type="DivType" />

<xsd:complexType name="DivType">
<xsd:choice maxOccurs="unbounded">
<xsd:element ref="div" />
<xsd:element ref="p" />
</xsd:choice>
<xsd:attribute name="title" type="xsd:string" use="required" />
</xsd:complexType>

<xsd:element name="p" type="xsd:string" />

</xsd:schema>


■XHTMLを簡素化した例をみてみましょう

たけち

さらら: ところで、こんな構造って、XHTMLにもあったんじゃないかしら。

たけち: そうだね。XHTMLなんかは再帰をよく使っている例だよね。実際にどんなふうになっているかを見てみようかな...

さらら: えっ (^ ^;

たけち: ...と思ったけれど、本物のXHTMLのDTDを示して解説したりすると大変だから、それをもうちょっと簡素化した例を見てもらおうね (^ ^;) 例えば、こんな感じかな。。。

DTD: XHTMLを簡素化したもの
<!ENTITY % Inline "(#PCDATA | font | strong | em)*">

<!ELEMENT p %Inline;>

<!ELEMENT font %Inline;>
<!ATTLIST font size CDATA #IMPLIED color CDATA #IMPLIED >

<!ELEMENT em %Inline;>
<!ELEMENT strong %Inline;>

たけち: 本物のXHTMLはもっと複雑だけれど、それを簡素化したものだよ。ここで見て欲しいのは、%Inline;というパラメータエンティティなんだ。これはp, font, strong, em要素などの内容モデルになるものだけれど、このパラメータエンティティ自身はfont, strong, em要素とテキストを含む混在内容からなるんだ。こういう再帰的定義がしてあるから、次のように、何重もネストしたXMLデータが定義できるんだね。

<?xml version="1.0" encoding="Shift_JIS" ?>
<p>僕はさっそく駅へ向かい、<em>片道切符</em>を買った。<strong>汽車</strong>に揺られながら、あすの仕事のことを忘れ、<font color="#ff0033">切符</font>を握りしめていた。<font color="#0000ff">奈良</font>の風景だけを思い描いていた。</p>

たけち: 再帰的定義というと、ちょっと特殊に見えるかもしれないけれど、実はこんなXHTMLのようなマークアップにはよく出てくるものなんだよ。

さらら: う〜ん、やっぱりややこしそうだけど、なんとなくわかるわ。

たけち: じゃあ、今のDTDをXML Schemaにしてみようね。

さらら: えっ、(^ ^;)

さらら

XML Schema: XHTMLを簡素化した例
<?xml version="1.0" encoding="Shift_JIS" ?>
<xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema">

<xsd:group name="inline">
<xsd:choice>
<xsd:element ref="em"/>
<xsd:element ref="strong"/>
<xsd:element ref="font"/>
</xsd:choice>
</xsd:group>


<xsd:complexType name="Inline" mixed="true">
<xsd:choice minOccurs="0" maxOccurs="unbounded">
<xsd:group ref="inline"/>
</xsd:choice>
</xsd:complexType>


<xsd:element name="p" type="Inline" />
<xsd:element name="em" type="Inline" />
<xsd:element name="strong" type="Inline" />

<xsd:element name="font">
<xsd:complexType mixed="true">
<xsd:complexContent>
<xsd:extension base="Inline">
<xsd:attribute name="color" type="Color" />
<xsd:attribute name="size" type="xsd:string" />
</xsd:extension>
</xsd:complexContent>
</xsd:complexType>
</xsd:element>

<xsd:simpleType name="Color">
<xsd:restriction base="xsd:string">
<xsd:pattern value="[A-Za-z]+|#[0-9A-Fa-f]{3}|#[0-9A-Fa-f]{6}"/>
</xsd:restriction>
</xsd:simpleType>
</xsd:schema>

さらら: DTDと比べるとなんとなくわかるような...(^^;) でも、これでXHTMLのようなスキーマを書く際にはどうしたらいいかわかったわ (^ ^)

たけち: そうだね。もっとも「XHTMLのようなスキーマ」を、本当は作ってはいけないんだけれどね。

さらら: えっ?

たけち: あ、それじゃあ次回は「名前空間」について話すことにするね。

さらら: あっ、はい!!

次回は名前空間とスキーマ(1)です。...... (^ ^)v

たけち

XMLスキーマのコーナーは、TAKABEさま(XSLTの遊び部屋)の全面的なご協力をいただいて作成しています。