Normal form

[James Clark <jjc@jclark.com>]

In considering restrictions on TREX patterns, such as the restrictions
on the patterns in attribute elements, I have found it helpful to think
in terms of a "normal form" of the syntax, which further simplifies the
primitive syntax described in the current spec.  In the normal form:

1. An "element" element only occurs as a child of "define".

2. The child of a "define" element is always an "element" element.

3. "notAllowed" is allowed only as the child of "start" (this could be
an error).

4. "empty" is allowed only as a child of "attribute", "element" and
"choice".

5. The document element is always "grammar".

6. "grammar" is allowed only as the document element.

This normal form is quite similar to schema languages with element
declarations like DTDs/RELAX/XML Schema. (A variant of this normal form
would be to treat "attribute" elements similarly to "element" elements
and always put them in a "define".)  My implementation internally
transforms things into something close to this.

To transform from the primitive syntax to this normal form:

1. Replace every "element" element by a reference to a new definition in
the outermost grammar.

2. After completing step 1, replace every "ref" element that references
a definition not created in step 1 by the referenced definition. (The
recursion restriction in 5.1 of the spec ensures this step will
terminate.)

3. After completing step 2, transform out any empty and notAllowed
elements using the obvious identities:

<group> p <notAllowed/> </group> => <notAllowed/>
<group> p <empty/> </group> => p

etc

We can then describe the restriction on attributes as follows.  It is an
error if the TREX pattern after transformation into normal form has an
"attribute" element with a descendant "ref" or "attribute" element.

James