Способ описания ограничений
Чтобы как-то учитывать требования при построении дерева, необходимо организовать движение информации по дереву. Иными словами, при построении очередной вершины мы должны знать, в каком контексте находится эта вершина и какие ограничения должны быть наложены на поля вершины в соответствии с этим контекстом.
В каждый момент построения дерева мы имеем какую-то конфигурацию вершин и атрибутов. Для конкретной вершины в этом недостроенном дереве мы можем определить её состояние - это то, что окружает вершину в данный момент. Фактически, это вся построенная часть дерева, но с точки зрения данной вершины. Рассмотрим понятие состояния на примере. На рис. 7 показано дерево с тремя вершинами типа Def (определение переменной). Чем отличается состояние, например, второй вершины от состояния первой? Состояния этих вершин различны, так как положения их в дереве различны. Из состояния (положения) первого определения видно, что в нём не могут быть использованы ссылки на переменные, так как до этой инструкции нет определённых переменных, а во втором определении можно использовать ссылку на переменную, поскольку к этому моменту уже есть определённая переменная v1.
При построении дерева обычно не требуется полностью знать состояние вершины. Нужны некоторые аспекты построенной части дерева, которые могут влиять на построение полей данной вершины. Эти аспекты будем называть аспектами состояния вершины. В приведённом выше примере для построения новой инструкции определения переменной нам нужен только один аспект состояния - список уже определённых переменных. Заметим, что при построении очередного элемента дерева все аспекты состояний вершин, для которых существенен этот элемент, должны измениться.
Итак, множество значений поля вершины может зависеть от:
- значений других полей этой вершины;
- некоторых аспектов состояния вершины.
Введём понятие элементарного ограничения. Это ограничение накладывается на поле вершины. Чтобы его определить, нужно задать:
- тип вершины t;
- поле f вершины типа t, на которое накладывается ограничение;
- поля вершины f1, f2, …, fk, от которых зависит множество допустимых значений поля f;
- аспекты состояния вершины S1, S2, … , Sn, от которых зависит множество допустимых значений поля f;
- способ вычисления множества допустимых значений поля f;
- функцию проверки значения поля f на соответствие определяемому ограничению;
- функцию ограничения количества используемых значений поля f.
Итак, в каждой вершине строящегося дерева определены:
- аспекты состояния этой вершины, существенные для её построения;
- ограничения на поля вершины.
Систему аспектов состояния вершины и ограничений на её поля будем называть контекстом данной вершины. Контексты детей вершины зависят от контекста вершины. Контекст ребёнка, который зависит от какого-то поля, должен вычисляться с учётом построенного значения этого поля.
