XML - статьи

/A>Описание алгоритма


Для анализируемого исходного выражения считаем, что для него требуется количество предков, равное 0, и анализируем подвыражения, из которого оно состоит, в соответствии с грамматикой языка XPath.

  1. Для пути доступа (location path) будем рассматривать входящие в его состав шаги доступа в обратном порядке.
  2. LocationPath ::= Step1 / Step2 /.../ Stepn-1 / Stepn

Для последнего шага будем требовать, чтобы он сохранил в контексте такое количество предков, которое требуется от всего пути доступа. Для предпоследнего шага будем требовать сохранения такого количества предков, которое потребовал для себя последний шаг доступа. И так далее, пока мы не дойдем до первого шага доступа, и количество предков, которое он для себя потребует, будет тем количеством, которое требуется при вычислении всего пути доступа. Данные рассуждения можно компактно записать в виде суперпозиционной формулы:

LocationPath(ancestors_number) = Step1( Step2 ( ... ( Stepn-1 ( Stepn(ancestors_number) ) ) ... ) )   .

Написанная формула в формальном виде отражает то наблюдение, что каждый шаг доступа должен сохранять в контексте определенное количество предков, руководствуясь теми шагами доступа, которые являются следующими после него в пути доступа.

  1. В шаге доступа (location step) нас будут интересовать его спецификатор оси и предикаты. Тест узла (node test), входящий в состав шага доступа, нас интересовать не будет, поскольку для его вычисления не требуются знания о предках контекстного узла.
  2. Step ::=AxisSpecifier NodeTest Predicate1...Predicatem

Реализация спецификатора оси при своей работе должна сохранить в контексте столько предков контекстного узла, сколько их требуется для данного шага доступа. Для предикатов не требуется сохранять каких-либо предков, поскольку задачей предикатов является лишь фильтрация контекстного узла, т.е. фактически ответ вида «да-нет» на вопрос, включается ли контекстный узел в результат шага доступа. Шаг доступа должен требовать, чтобы ему предоставили в контексте такое число предков, которое потребуется для вычисления спецификатора оси, с учетом также максимума по числу предков, которые потребуются для применения предикатов к результату выполнения оси. В виде формулы это может быть записано следующим образом: Step(ancestors_number) = AxisSpecifier( max( ancestors_number: max(Predicatei(0)) )). i=1,m


  • Спецификатор оси (axis specifier) – эта то правило грамматики XPath, которому уделяется основная роль в рассматриваемом алгоритме. Именно реализация каждой конкретной оси отвечает за то, чтобы выбрать в соответствии с семантикой оси узлы документа (возможно, пользуясь предками контекстного узла, сохраненными в контексте), а также непосредственно отвечает за то, чтобы сохранить в своем результирующем контексте такое количество предков, которое потребуется для дальнейшего вычисления всего выражения языка XPath. Основные принципы реализации осей с учетом сохраненных предков контекстного узла будут рассмотрены в разделе , а сейчас мы определим количество предков, которое необходимо сохранять для корректной работы каждой оси: .




    1. Предикат (predicate) содержит в себе выражение языка XPath общего вида. Для выражения (expr), представляющего собой арифметическую или булевскую операцию или операцию сравнения, для его корректного вычисления в контексте будет требоваться такое количество предков контекстного узла, сколько их по максимуму требуется для каждого из подвыражений данной операции. Если от выражения одного из перечисленных типов требуется сохранять в его результирующем контексте отличное от нуля количество предков, то это свидетельствует о наличии семантической ошибки в анализируемом исходном выражении XPath, потому что в нем происходит применение оси к аргументу, не являющемуся узлом, что некорректно согласно Спецификации XPath [].

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

      UnionExpr ::= PathExpr1 | ... | PathExprk   ; UnionExpr(ancestors_number)=max PathExpri(ancestors_number)). i=1,k

    2. Выражение пути (path expression) по своей структуре схоже с правилом для пути доступа




    3. PathExpr ::= FilterExpr / Step1 / Step2 /.../ Stepn ;


    поэтому на него накладываются условия, аналогичные условиям, накладываемым на путь доступа:

    PathExpr(ancestors_number) = FilterExpr ( Step1( Step2

    ( ... ( Stepn(ancestors_number) ) ... ) ) ).

    Аналогичная взаимосвязь прослеживается между выражением фильтрации (filter expression) и рассмотренным ранее шагом доступа.

    FilterExpr ::= PrimaryExpr Predicate1 ... Predicatep ;

    FilterExpr(ancestors_number)= PrimaryExpr; max(ancestors_number);(Predicatei(0)) )) ). i=1,p

    Базовое выражение (primary expression), являющееся одной из констант, сохранения предков в контексте не требует, т.к. константа сама создает новый контекст. Неправомерным будет также требовать от константы сохранять отличное от нуля количество предков в ее результирующем контексте, потому что подобная ситуация сигнализирует о том, что в исходном анализируемом выражении присутствует применение оси к константе (не являющейся узлом), что является семантической ошибкой выражения.

    Для базового выражения, представляющего собой вызов одной из функций из Библиотеки базовых функций XPath [], для большинства из этих функций не требуется сохранения предков ни для ее аргументов, ни для возвращаемого результата. Исключение составляют лишь функция lang, требующая сохранения всех предков для своего аргумента, и функция id, возвращающая набор узлов, поскольку к нему на последующих шагах доступа могут применяться обратные оси XPath.


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