附属書E (参考) 決定的内容モデル

3.2.1 要素内容で示したとおり,要素型宣言中の内容モデルは決定的である必要がある。この要求は,SGMLとの互換性のために導入する(SGMLでは,決定的内容モデルを"非曖昧"と呼ぶ。)。 SGMLシステムを用いて作成したXMLプロセサは,非決定的内容モデルを誤りとしてもよい。

例えば,内容モデル((b, c) | (b, d))は非決定的となる。これは,最初にbを与えたとき,モデル内のいずれのbとマッチするのか,その次の要素を先読みすることなしには,XMLプロセサは知ることができないことによる。この場合は,bの二つの出現は,一つにまとめることができ,モデルは(b, (c | d))となる。こうすれば,明らかに最初のbは,内容モデル内の一つの名前とだけマッチする。プロセサは先読みして,次にくるものを知る必要がない。cdも受理される。

形式的に示せば次のとおり。Aho, Sethi, and Ullman [Aho/Ullman]3.9のアルゴリズム3.5などの標準的なアルゴリズムを用いて,内容モデルから有限オートマトンを構成することができる。この種の多くのアルゴリズムでは,正規表現における各々の位置(つまり,正規表現の構文木における各々の末端ノード)に対して,follow setを構成する。ある位置に対するfollow setにおいて,複数の位置が同じ要素型名でラベル付けされていれば,その内容モデルは誤りとなり,誤りとして報告してもよい。

すべての非決定的内容モデルを等価な決定的内容モデルに変換することはできないが,多くの非決定的内容モデルを変換するアルゴリズムが存在する。Brüggemann-Klein 1991 [Brüggemann-Klein]を参照。