Тестирование софта - статьи


         

Предварительные сведения и понятия


В начале введём понятие атрибутированного дерева.

Как известно, дерево - это граф, в котором нет циклов. Мы будем рассматривать ориентированные деревья, то есть деревья, у которых имеется выделенная вершина - корень, и все ребра ориентированы от более близких к корню вершин к более дальним.

Пусть A - некоторая вершина ориентированного дерева. Если она не является корнем, то существует единственная вершина B, из которой в A идет ребро. Вершину B мы будем называть родителем вершины A, а вершину A, соответственно, ребёнком вершины B. В отличие от родителя, детей у вершины может быть много.

Деревья, которые мы рассматриваем, являются атрибутированными, то есть с каждой вершиной могут быть связаны её атрибуты - объекты произвольного типа.

Мы будем рассматривать гетерогенные деревья, то есть деревья, у которых каждая вершина имеет определённый тип. Тип регламентирует, какие дети и атрибуты и какого типа могут быть у вершины данного типа. При этом все дети и атрибуты именуются. Кроме того, в определении типа может содержаться указание на то, что детей (или атрибутов) данного типа может быть несколько (то есть они образуют список), а также на то, что какой-то ребёнок или атрибут является необязательным, то есть может отсутствовать у вершины данного типа.

Пример. Рассмотрим следующее определение типа вершины: вершины типа A должны содержать одного ребёнка типа B с именем child, необязательный атрибут name типа "строка", список list детей типа С. Примеры вершин типа A приведены на .

Заметим, что на рис. нет атрибута name - это возможно, так как в определении типа этот атрибут заявлен необязательным, в то же время список list присутствует всегда, хотя может и не содержать элементов.

Итак, в определении типа вершины должны быть описаны:

  • Атрибуты вершины: их имена и типы, а также то, являются ли они обязательными.
  • Списки атрибутов: их имена и типы элементов этих списков.
  • Дети вершины: их имена и типы, а также то, являются ли они обязательными.
  • Списки детей: их имена и типы элементов этих списков.

Детей, атрибуты и списки вершины мы будем называть полями этой вершины.

Пусть имеется конечное множество T типов вершин, замкнутое относительно использования типов (то есть все типы вершин, на которые есть ссылки в определениях типов из этого множества, определены). Далее мы будем рассматривать множество D деревьев, типы вершин которых принадлежат множеству T.

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