XML - статьи

/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.
  • Из определения следует, что при количестве предков равном +? в контексте должны сохраняться все предки контекстного узла до корневого узла включительно.

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

    В качестве единицы подвыражения XPath мы возьмем грамматическое правило языка XPath. Большинство грамматических правил может включать в своем определении другие правила, например, путь доступа (location path) включает в себя несколько шагов доступа (location step). Можно говорить о том, что предлагаемый алгоритм рассматривает выражение языка XPath в виде абстрактного синтаксического дерева: вершинами этого дерева служат грамматические правила языка XPath, а дугами – отношение включения между правилами. Если рассматривать выражение XPath в виде подобного абстрактного синтаксического дерева, то идея алгоритма заключается в обходе данного дерева и в приписывании каждой его вершине такого количества предков, которое необходимо для вычисления соответствующего подвыражения XPath.


  • аргументом функции является количество предков, которое требуется от данной вершины;


  • возвращаемым результатом функции является количество предков, которое данная вершина требует для себя (и которое естественным образом зависит от аргумента функции в соответствии с определением 3).


  • Необходимо заметить, что поскольку тип аргумента и возвращаемого результата функции совпадают, правомерно рассматривать суперпозиционную комбинацию функций рассмотренной сигнатуры, что семантически будет соответствовать отношению включения грамматических правил языка 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

      &#8800 ?   ;

      max(+?, C) = +?   .


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