附属書E 決定的内容モデル

互換性のため,要素宣言における内容モデルは,決定的とする必要がある。

SGMLは,決定的内容モデル(SGMLでは,非あいまいと呼ぶ。)を要求する。SGMLシステムを用いて作成したXMLプロセサは,非決定的内容モデルをエラーとしてもよい。

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

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

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