ここではRelaxNGCCがどうやって動くかの説明をします。この説明を理解するには、オートマトンについての基礎知識が必要です。 This page describes how RelaxNGCC generates Java source code. It also assumes you are familiar with automaton.
このページですべての仕様を説明しているわけではないですし、そこまでのドキュメントを書くのも大変なのでややさぼり気味です。深く知りたい方は疑問点はソースコードを調べたりメーリングリスト等で質問してください。This explanation is not a detailed algorithm but an outline. If you hava any question about internal behavior of RelaxNGCC, please analyse source code or send me via mail.
まず、RelaxNG grammarにおいて、startまたはdefineエレメントで定義される要素と属性のブロックをスコープと定義します。includeエレメントと、startおよびdefineのcombine属性を処理することにより、grammar全体は１個以上のスコープに分解されます。 A scope is a block that consists of elements, attributes, and data defined by a start or a define element of a RelaxNG grammar. A grammar is devided into one or more scopes by processing include elements and combine attributes.
RelaxNGCCは、スコープ１個について１個の文字列オートマトンと１個のJavaクラスを生成します。 RelaxNGCC generates an automaton and a Java class per a scope.
次にそれぞれのスコープについて文字列オートマトンを作成します。このオートマトンでは、アルファベットの種類はNext step is generating an automaton about each scope. In this automaton, there are following 5 kinds of alphabet.
の５つがあります。このうち、startElement, endElement, attributeの３種類はnamespace-URIとlocalname属性を持っています。以降では、namespace-URIとlocalnameの組を単に「名前」と呼び、startElement[x]で名前 x のstartElementタイプのアルファベットを表現します。 The kinds "startElement", "endElement", and "attribute" have properties about namespace-URI and localname. We call the pair of the namespace-URI and the localname "name" simply. Additionally, we introduce an expression "startElement[x]" for a startElement type alphabet whose name is "x".
refはそれが参照するスコープで区別がなされます。スコープ S を参照するrefタイプのアルファベットをref[S]で表現します。また、refタイプのアルファベット r に対し、それが参照するスコープを scope(r) と表記します。 A "ref" type alphabet is identified by a scope it refers to. We introduce an expression ref[S] for a ref type alphabet that refers to a scope "S" and another expression scope(r) for a scope that is referred to by a ref type alphabet "r".
valueは、アルファベットの属性として型があります。型はMulti-Schema Validatorに組み込まれたW3C XML Schema Part2のデータ型です。 On the other hand, the value type alphabet has a datatype property. The data type is detailed in W3C XML Schema Part2, and RelaxNGCC uses datatype.
たとえば、次のスコープ For example, following scope
<define name="foo">
<element name="x">
<oneOrMore>
<element name="y"><text/></element>
</oneOrMore>
<attribute name="a"><text/></attribute>
</element>
</define>
に対しては、次のオートマトンgenerates following automaton
startE[x] startE[y] value[string] endE[y] attribute[a] endE[x]
S --------> O --------> O -----------> O --------> O ------------> O ------> F
∧ |
|__________________________|
startE[y]
が作成されます。ここでSは初期状態、Fは受理状態です。 where S is the initial state and F is the final state.
もう一つ例を出します。Here is another example.
<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)と表現します。
Note that there are no alphabets that represent the end of attribute.
We introduce a expression tr(x,a,y) for a transition from a state x to y with an alphabet a.
RelaxNGCCではユーザの書いたコード断片を実行するわけですが、どのタイミングで実行するかはオートマトンの遷移規則の実行時です。例えば上記の例で、 The result source code generated by RelaxNGCC must execute the code fragment embedded by the user at appropriate moment. This moment is associated with a transition of the automaton constructed in Step 2.
<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);を実行すればよいことになります。このようにして、ユーザアクションつきオートマトンを作成します。 In the example above, the code fragment System.out.println(t); is executed at the emphasized transition. Thus, RelaxNGCC associates the code fragment embedded by user with transitions of automaton.
あるスコープ S について、アルファベットの集合 FIRST(S) を次のように定義します。For each scope S, we define a set of alphabets FIRST(S) as ollows.
a ∈ FIRST(S) ⇔
Sの作るオートマトンの初期状態からrefタイプでないアルファベット a で遷移可能である。またはA Transition (initial(S),a,j) exists, where a is not "ref" type. Or,
a ∈ FIRST(S')かつ、Sの作るオートマトンの初期状態からscope(r)=S'なるrefタイプのアルファベットで遷移可能である。a ∈ FIRST(S'), and a transition (initial(S),r,j) exists where r is a ref type alphabet and scope(r)=S'.
Note that initial(S) is the initial state of the automaton constructed from S.
次に FOLLOW(S) を次のように定義します。 Next, we define a set of alphabet FOLLOW(S) as follows.
a ∈ FOLLOW(S) ⇔ あるスコープ S' において、scope(r)=Sであるようなrefタイプのアルファベット r が存在し、tr(x, r, y)かつtr(y, a, z)となる遷移規則が存在する。If there is a ref type alphabet r in a scope S' where scope(r)=S, two transition tr(x,r,y) and tr(y,a,z) must exist in the scope S.
くだけた言い方をすれば、FIRSTはスコープの開始を告げるアルファベット、FOLLOWはスコープの終了を告げるアルファベットです。すべてのスコープについてFIRSTとFOLLOWを計算します。これらは文脈自由文法からコンパイラをつくるときに使うFIRSTとFOLLOWに倣った概念です。Frankly speaking, FIRST alphabet notifies start of an scope and FOLLOW alphabet notifies end of an scope. I borrowed the concept of FIRST and FOLLOW from the compiler theory about LR context free grammar. RelaxNGCC computes FIRST and FOLLOW for all scopes.
RelaxNGCCでは、オートマトンが非決定的になる場合はサポートしていません。手をかければ先読みをしたりバックトラックをしたりといったことは理論的には可能ですが、そこまではやっていません。 As for RelaxNGCC, the automaton constructed by each scope must be deterministic. It is possible theoretically to avoid this restriction by looking ahead more tokens, but it is hard to implement.
スコープ X がつくるオートマトンが非決定的になるのは、次のいずれかの条件を満たす状態 O が１つでも存在する場合です。 An automaton generated by a scope X is non-deterministic if a state O that satisfies any of following conditions exists.
２番目の条件は、次のような例であてはまります。choiceの先頭では、startElement[x]で遷移できますが、名前aのdefineのスコープのFIRSTにもstartElement[x]が含まれるからです。Here is an example of violating the second condition. At the head of choice a transition with startElement[x] is allowd, though startElement[x] is contained the FIRST of the scope with name a.
<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]を含んでいるからです。Here is an example of violating the fourth condition. A transition with startElement[x] is allowed from the accept state of the scope a, however the line (*) indicates the FOLLOW of the scope contains startElement[x].
<define name="a"> <oneOrMore><element name="x">...</element></oneOrMore> </define> <start> <ref name="a"/> <element name="x">...</element> (*) </start>
決定性チェックに失敗した場合、RelaxNGCCはそのことを示すメッセージを出力し終了します。 If the determinacy check is failed, RelaxNGCC outputs warning message and quits.
ここまできたら、いよいよコード生成です。状態遷移のトリガはstartElement, endElementなどのSAXイベントです。SAXのstartElementで名前 x を受け取ったら、アルファベットstartElement[x]を受け取ったことになります。ただしアトリビュートはstartElementの時点で通知されるだけなので、扱いを変える必要があります。次のルールを導入します。 Then RelaxNGCC generates source code. The trigger of transition is SAX events such as startElement, endElement, and so on. But a special rule is needed since attributes are notified only at startElement.
また、スコープの開始と終了の処理のために次の処理を導入します。 Additionally, here is rules of the start and end of scope.
SAXの言葉で言えば、スコープを開始するときにContentHandlerを置換し、スコープを終了するときにContentHandlerを復帰することになります。In terms of SAX, the ContentHandler is replaced at the start of a scope, and it is recovered at the end of the scope.