/A>Описание алгоритма
Для анализируемого исходного выражения считаем, что для него требуется количество предков, равное 0, и анализируем подвыражения, из которого оно состоит, в соответствии с грамматикой языка XPath.
- Для пути доступа (location path) будем рассматривать входящие в его состав шаги доступа в обратном порядке.
LocationPath ::= Step1 / Step2 /.../ Stepn-1 / Stepn
Для последнего шага будем требовать, чтобы он сохранил в контексте такое количество предков, которое требуется от всего пути доступа. Для предпоследнего шага будем требовать сохранения такого количества предков, которое потребовал для себя последний шаг доступа. И так далее, пока мы не дойдем до первого шага доступа, и количество предков, которое он для себя потребует, будет тем количеством, которое требуется при вычислении всего пути доступа. Данные рассуждения можно компактно записать в виде суперпозиционной формулы:
LocationPath(ancestors_number) = Step1( Step2 ( ... ( Stepn-1 ( Stepn(ancestors_number) ) ) ... ) ) .
Написанная формула в формальном виде отражает то наблюдение, что каждый шаг доступа должен сохранять в контексте определенное количество предков, руководствуясь теми шагами доступа, которые являются следующими после него в пути доступа.
- В шаге доступа (location step) нас будут интересовать его спецификатор оси и предикаты. Тест узла (node test), входящий в состав шага доступа, нас интересовать не будет, поскольку для его вычисления не требуются знания о предках контекстного узла.
Step ::=AxisSpecifier NodeTest Predicate1...Predicatem
Реализация спецификатора оси при своей работе должна сохранить в контексте столько предков контекстного узла, сколько их требуется для данного шага доступа. Для предикатов не требуется сохранять каких-либо предков, поскольку задачей предикатов является лишь фильтрация контекстного узла, т.е. фактически ответ вида «да-нет» на вопрос, включается ли контекстный узел в результат шага доступа. Шаг доступа должен требовать, чтобы ему предоставили в контексте такое число предков, которое потребуется для вычисления спецификатора оси, с учетом также максимума по числу предков, которые потребуются для применения предикатов к результату выполнения оси. В виде формулы это может быть записано следующим образом: Step(ancestors_number) = AxisSpecifier( max( ancestors_number: max(Predicatei(0)) )). i=1,m
- Выражение пути (path expression) по своей структуре схоже с правилом для пути доступа
Предикат (predicate) содержит в себе выражение языка XPath общего вида. Для выражения (expr), представляющего собой арифметическую или булевскую операцию или операцию сравнения, для его корректного вычисления в контексте будет требоваться такое количество предков контекстного узла, сколько их по максимуму требуется для каждого из подвыражений данной операции. Если от выражения одного из перечисленных типов требуется сохранять в его результирующем контексте отличное от нуля количество предков, то это свидетельствует о наличии семантической ошибки в анализируемом исходном выражении XPath, потому что в нем происходит применение оси к аргументу, не являющемуся узлом, что некорректно согласно Спецификации XPath [].
Выражение объединения (union expression) требует от каждого из своего аргументов сохранить в контексте такое количество предков, которое потребовали от него самого. Выражению объединения должно быть предоставлено в контексте такое количество предков, которое по максимуму потребовалось для вычисления его аргументов:
UnionExpr ::= PathExpr1 | ... | PathExprk ; UnionExpr(ancestors_number)=max PathExpri(ancestors_number)). i=1,k
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.