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

互換性のため,要素型宣言における内容モデルは,決定的でなければならない。

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

例えば,内容モデル((b, c) | (b, d))は非決定的となる。これは,最初にbを与えたとき,モデル内のいずれのbとマッチするのか,その次の要素を先読みすることなしには,パーサは知ることができないことによる。この場合は,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]を参照のこと。