Расширяемый язык разметки

       

E Детерминистические модели содержания (Пояснения к спецификации)


Как указывалось в главе , необходимо чтобы модели содержимого, даваемые в декларациях типов элементов, были детерминистическими. Данное требование необходимо с языком SGML (в котором детерминистические модели содержания обозначаются термином "unambiguous"). XML процессоры, построенные на базе систем SGML, могут выявлять недетерминистические модели содержания как ошибочные.

К примеру, модель содержимого ((b, c) | (b, d)) является недетерминистической, поскольку, получив исходный b, XML процессор не может знать, какому b в исходной модели он соответствует, не проследив далее по строке, какой элемент следует за указанным b. В данном случае обе ссылки на b можно свести в одну общую ссылку, преобразовав рассматриваемую модель в (b, (c | d)). Теперь исходный элемент b соответствует ровно одному имени в модели содержания, и процессору нет нужды заглядывать вперед чтобы увидеть, что за ним следует. Это может быть и c, и d.

Или более формально: с помощью стандартных алгоритмов по модели содержания может быть выстроен автомат конечных состояний, например алгоритм 3.5 из главы 3.9 в книге авторов Aho, Sethi и Ullman . Во многих таких алгоритмах для каждой части в регулярном выражении строится сопроводительный набор команд (то есть, в дереве синтаксиса данного регулярного выражения стоится каждый узел листа). Если какая-либо часть выражения имеет сопроводительный набор, в котором более одной позиции сопоставлено с типом элементов с одним и тем же названием, модель содержимого ошибочна и об этом можно сообщать как об ошибке.

Существуют алгоритмы, которые способны многие (хотя и не все) недетерминистические модели содержания автоматически привести к эквивалентным детерминистическым моделям (см. Brüggemann-Klein 1991 ).



Содержание раздела