/A>Количество предков для контекстного узла
Предки контекстного узла, которых мы будем сохранять в контексте, будут определяться с помощью целого неотрицательного числа, которое назовем количеством предков.
Определение 1 Количество предков – это целое неотрицательное число или +?:
ancestors_number = 0, 1, 2, ..., +? .
В соответствии со значением этого числа, в контексте вычисляемого выражения языка XPath будут дополнительно храниться узлы {node1, node2, ..., noden}, где
- node1 – родительский узел для контекстного узла;
- nodek+1 – родительский узел для узла nodek, k=1, n - 1;
- либо n<ancestors_number и noden – корневой узел дерева XML-документа, либо n=ancestors_number.
- аргументом функции является количество предков, которое требуется от данной вершины;
- возвращаемым результатом функции является количество предков, которое данная вершина требует для себя (и которое естественным образом зависит от аргумента функции в соответствии с определением 3).
- входной контекстный узел, который стал родителем для результирующего контекстного узла;
- если во входном контексте были сохранены узлы-предки контекстного узла, то они также могут быть сохранены в результирующем контексте, соответственно как прародитель, прапрародитель и т.д.
Из определения следует, что при количестве предков равном +? в контексте должны сохраняться все предки контекстного узла до корневого узла включительно.
В предлагаемом алгоритме мы будем определять количество предков, которое требуется для вычисления данного подвыражения XPath (в его взаимоотношении с другими подвыражениями анализируемого выражения). В соответствии с данным выше определением, количество предков будет однозначно задавать тех предков контекстного узла, которых необходимо сохранить в контексте для корректного вычисления данного подвыражения
В качестве единицы подвыражения XPath мы возьмем грамматическое правило языка XPath. Большинство грамматических правил может включать в своем определении другие правила, например, путь доступа (location path) включает в себя несколько шагов доступа (location step). Можно говорить о том, что предлагаемый алгоритм рассматривает выражение языка XPath в виде абстрактного синтаксического дерева: вершинами этого дерева служат грамматические правила языка XPath, а дугами – отношение включения между правилами. Если рассматривать выражение XPath в виде подобного абстрактного синтаксического дерева, то идея алгоритма заключается в обходе данного дерева и в приписывании каждой его вершине такого количества предков, которое необходимо для вычисления соответствующего подвыражения XPath.
Необходимо заметить, что поскольку тип аргумента и возвращаемого результата функции совпадают, правомерно рассматривать суперпозиционную комбинацию функций рассмотренной сигнатуры, что семантически будет соответствовать отношению включения грамматических правил языка XPath друг в друга.
Пример 2 Пусть в некоторой вершине абстрактного синтаксического дерева выражения языка XPath стоит спецификатор оси
child, и от данной вершины требуется сохранение 2 предков (т.е. родителя и прародителя контекстного узла). Поскольку ось
child выбирает дочерние узлы для контекстного узла, то контекстный узел является родителем для узлов, которые будут получены в результате применения оси
child к контекстному узлу. Ввиду данного наблюдения, реализация оси
child может по требованию сохранить в контексте результата:
Легко видеть, что реализация оси
child, имея на входе контекст, содержащий лишь контекстный узел (и не хранящий никаких его узлов-предков), в качестве результата возвращает контекст, в котором по требованию может быть сохранен родитель результирующего контекстного узла. Если же требуется сохранить большее количество предков, то тогда вершина абстрактного синтаксического дерева, в которой стоит спецификатор оси
child, должна потребовать для себя количество предков, на 1 меньшее, чем то количество предков, которые потребовали от нее. В принятых выше обозначениях, это может быть кратко записано в виде: Child(ancestors_number) = ancestors_number - 1 ,
а для нашего примера: Child(2) = 1.
В терминах введенных выше определений, построение алгоритма вычисления выражений XPath на основе сохраняемых в контексте предков контекстного узла заключается в определении каждой функции, соответствующей каждому из правил грамматики XPath. Поскольку грамматические правила включают в себя спецификатор оси (axis specifier), рассуждения попутно будут включать в себя определение необходимого количества предков для вычисления каждой обратной оси языка XPath.
В том случае, когда количество предков принимает значение +?, для него будут применяться стандартные математические соглашения о работе с бесконечностями:
+? - C = +?, C
≠ ? ;
max(+?, C) = +? .
