RelaxNGCC 動作原理

　ここではRelaxNGCCがどうやって動くかの説明をします。この説明を理解するには、オートマトンについての基礎知識が必要です。

　このページですべての仕様を説明しているわけではないですし、そこまでのドキュメントを書くのも大変なのでややさぼり気味です。深く知りたい方は疑問点はソースコードを調べたりメーリングリスト等で質問してください。

Step 1　スコープへの切り分け

　まず、RelaxNG grammarにおいて、startまたはdefineエレメントで定義される要素と属性のブロックをスコープと定義します。includeエレメントと、startおよびdefineのcombine属性を処理することにより、grammar全体は１個以上のスコープに分解されます。

　RelaxNGCCは、スコープ１個について１個の文字列オートマトンと１個のJavaクラスを生成します。

Step 2　オートマトンの作成

　次にそれぞれのスコープについて文字列オートマトンを作成します。このオートマトンでは、アルファベットの種類は

の５つがあります。このうち、startElement, endElement, attributeの３種類はnamespace-URIとlocalname属性を持っています。以降では、namespace-URIとlocalnameの組を単に「名前」と呼び、startElement[x]で名前 x のstartElementタイプのアルファベットを表現します。

　refはそれが参照するスコープで区別がなされます。スコープ S を参照するrefタイプのアルファベットをref[S]で表現します。また、refタイプのアルファベット r に対し、それが参照するスコープを scope(r) と表記します。

　valueは、アルファベットの属性として型があります。型はMulti-Schema Validatorに組み込まれたW3C XML Schema Part2のデータ型です。

　たとえば、次のスコープ

<define name="foo">
  <element name="x">
    <oneOrMore>
      <element name="y"><text/></element>
    </oneOrMore>
    <attribute name="a"><text/></attribute>
  </element>
</define>

に対しては、次のオートマトン

  startE[x]   startE[y]   value[string]  endE[y]     attribute[a]   endE[x]
S --------> O --------> O -----------> O --------> O ------------> O ------> F
                        ∧                         |
                        |__________________________|
                               startE[y]

が作成されます。ここでSは初期状態、Fは受理状態です。

　もう一つ例を出します。

<define name="foo">
  <zeroOrMore>
    <element name="y"><data type="int"/></element>
  </zeroOrMore>
  <choice>
    <ref name="a"/><
    <ref name="b"/><
  </choice>
</define>

                     startE[y]
                ------------------------
                |                      |
      startE[y] v value[int]   endE[y] |
|-- S --------> O ---------> O ------> O --
|   |                                  |  |
|   |   ref[a]           ref[a]        |  |
|   ------------> F <-------------------  |
----------------> F <----------------------
     ref[b]              ref[b]

　なお、アトリビュートの終端を示すアルファベットは存在しません。このことは後でオートマトンの遷移手順で説明します。また、状態 x からアルファベット a で状態 y へ遷移する遷移規則をtr(x,a,y)と表現します。

Step 3　ユーザアクションの付加

　RelaxNGCCではユーザの書いたコード断片を実行するわけですが、どのタイミングで実行するかはオートマトンの遷移規則の実行時です。例えば上記の例で、 

<define name="foo">
  <element name="x">
    <oneOrMore>
      <element name="y"><text c:alias="t"/><c:java>System.out.println(t);</c:java></element>
    </oneOrMore>
    <attribute name="a"><text/></attribute>
  </element>
</define>
となっていれば、 
  start "x"   start "y"   value[string]  end "y"     attribute "a"   end "x"
S --------> O --------> O -----------> O --------> O ------------> O ------> F
                        ^                          |
                        |__________________________|
                               start "y"

この強調した遷移規則を実行するときにユーザの書いたSystem.out.println(t);を実行すればよいことになります。このようにして、ユーザアクションつきオートマトンを作成します。

Step 4　FIRSTとFOLLOW

　あるスコープ S について、アルファベットの集合 FIRST(S) を次のように定義します。

a ∈ FIRST(S) ⇔
  Sの作るオートマトンの初期状態からrefタイプでないアルファベット a で遷移可能である。または
  a ∈ FIRST(S')かつ、Sの作るオートマトンの初期状態からscope(r)=S'なるrefタイプのアルファベットで遷移可能である。

　次に FOLLOW(S) を次のように定義します。

a ∈ FOLLOW(S) ⇔ あるスコープ S' において、scope(r)=Sであるようなrefタイプのアルファベット r が存在し、tr(x, r, y)かつtr(y, a, z)となる遷移規則が存在する。

　くだけた言い方をすれば、FIRSTはスコープの開始を告げるアルファベット、FOLLOWはスコープの終了を告げるアルファベットです。すべてのスコープについてFIRSTとFOLLOWを計算します。これらは文脈自由文法からコンパイラをつくるときに使うFIRSTとFOLLOWに倣った概念です。

Step 5　決定性チェック

　RelaxNGCCでは、オートマトンが非決定的になる場合はサポートしていません。手をかければ先読みをしたりバックトラックをしたりといったことは理論的には可能ですが、そこまではやっていません。

　スコープ X がつくるオートマトンが非決定的になるのは、次のいずれかの条件を満たす状態 O が１つでも存在する場合です。

  1. Oから同一のアルファベットで異なる状態へ遷移可能
  2. refタイプのアルファベット r でOから遷移可能で、FIRST(scope(r))に含まれるアルファベットでも遷移可能
  3. refタイプのアルファベット r, r' でOから遷移可能で、FIRST(scope(r))とFIRST(scope(r'))の両方に含まれるアルファベットが存在する
  4. Oが受理状態で、FOLLOW(X)に含まれるアルファベットでOから遷移可能。これは厳密にはオートマトンの非決定性ではないですが、スコープの終端が判定できなくなるためRelaxNGCCで処理できないものの１つです。

　２番目の条件は、次のような例であてはまります。choiceの先頭では、startElement[x]で遷移できますが、名前aのdefineのスコープのFIRSTにもstartElement[x]が含まれるからです。 

<define name="a">
  <element name="x">...</element>
</define>
<start>
  <choice>
    <element name="x">...</element>
    <ref name="a"/>
  </choice>
</start>

　４番目の条件は、次のような例であてはまります。名前aのスコープAの受理状態からはさらにstartElement[x]で遷移可能ですが、(*)の行を見るとFOLLOW(A)がstartElement[x]を含んでいるからです。

<define name="a">
  <oneOrMore><element name="x">...</element></oneOrMore>
</define>
<start>
  <ref name="a"/>
  <element name="x">...</element> (*)
</start>

　決定性チェックに失敗した場合、RelaxNGCCはそのことを示すメッセージを出力し終了します。

Step 6　コード生成

　ここまできたら、いよいよコード生成です。状態遷移のトリガはstartElement, endElementなどのSAXイベントです。SAXのstartElementで名前 x を受け取ったら、アルファベットstartElement[x]を受け取ったことになります。ただしアトリビュートはstartElementの時点で通知されるだけなので、扱いを変える必要があります。次のルールを導入します。

また、スコープの開始と終了の処理のために次の処理を導入します。

　SAXの言葉で言えば、スコープを開始するときにContentHandlerを置換し、スコープを終了するときにContentHandlerを復帰することになります。

RelaxNGCC home