XML - статьи



              

Классы регулярных грамматик


В этом разделе мы приводим классификацию структурных схем. Данный метод заимствован из работы [13], где он используется для классификации грамматик деревьев.

Определение 8 (Локальные структурные схемы) Структурная схема называется локальной, если не существует двух типов элементов с одинаковым именем.

Структурная схема из примера 3 является локальной, в то время как схема из примера 4 не является таковой. Следующее утверждение выполняется для локальных схем.

Утверждение 3 (Единственность интерпретации) Пусть S=(T,E,A,p,a,r) локальная структурная схема и XML документ D валиден для S. Пусть также любые два домена из множества Т не пересекаются и для любого типа элемента e, мультимножество имен типов атрибутов из множества a(e) содержит только уникальные значения. Тогда существует и притом единственная интерпретация документа D в терминах S.

Существование интерпретации следует из самой формулировки утверждения. Для доказательства единственности воспользуемся формулировкой интерпретации. Из правила согласования имён элементов, и локальности схемы следует, что в любой интерпретации каждый элемент документа XML должен отображаться на один и тот же тип элемента, так как имена всех типов уникальны. Из того, что любые два домена не пересекаются и из свойства согласования текстовых узлов следует, что в любой интерпретации каждый узел документа XML должен отображаться на один и тот же домен. Таким образом, достаточно проверить, что отображение атрибутов сохраняется в любой интерпретации. Это следует из свойств согласования атрибутов с элементами, согласования имен и значений атрибутов и из того, что для любого типа элемента e, мультимножество имен типов атрибутов из множества a(e) содержит только уникальные значения.

Прежде чем описать следующий класс структурных схем, приведем следующее определение, относящееся к регулярным выражениям:

Определение 9 (Допустимые символы) Пусть r- регулярное выражение над множеством M. Тогда ? M(r) - это множество, содержащее все элементы из M, которые присутствуют в записи регулярного выражения.




Содержание  Назад  Вперед