Хабрахабр

Конструирующий XPath? Алгоритмический XPath? Ничего, кроме XPath

Здравствуйте, уважаемые читатели. В этой публикации речь пойдет о немного нестандартных применениях такого хорошо известного формализма как XPath. Все знают, что он очень удобен для извлечения информации из XML- или HTML- или еще каких-нибудь *ML-документов (как простых текстовых, так и каких-нибудь виртуальных, которые являются верхним слоем представления какой-либо сложной информации), то есть для того, чтобы задавать этим документам какие-либо вопросы. Однако известно, что чем лучше сформулирован вопрос, тем большую часть ответа он уже содержит. Поэтому напрашивается простая мысль – а нельзя ли использовать записанные на XPath выражения как утверждающие, то есть достраивающие документ таким образом, чтобы это XPath-выражение было истинным? Думаю можно, и это первое, о чем здесь пойдет речь. И второе – если уж мы научимся путем прямого применения XPath создавать новые элементы в документе, то нельзя ли превратить XPath в простой алгоритмический язык программирования? В самом деле, обращаться к данным умеет, создавать данные умеет. Несложно представить, как на нем описать последовательность операторов и оператор ветвления, остается подумать о циклах в нем и о функциях. Это интересно, ну хотя бы, теоретически. И об этом тоже пойдет речь.
Итак, обычный XPath описывает последовательность шагов продвижения по дереву документа, причем на каждый шаг может быть наложен фильтр-условие (предикат, записываемый в квадратных скобках). В результате получаем какое-то конечное множество узлов или число или строку или логическое значение. Нас интересует, прежде всего, случай множества узлов. Обычный XPath выдает узлы, которые уже существуют в документе. Рассмотрим гипотетический конструирующий XPath, который будет не только возвращать уже имеющиеся узлы, но еще и достраивать новые узлы таким образом, чтобы они полностью соответствовали запросу.

А потом будем проверять, какие из этих вариантов уже существуют и достраивать несуществующие. Идея очень проста – на очередном шаге XPath-запроса будем анализировать фильтр-предикат и составлять варианты данных, которые под этот фильтр подпадают.

Например, вот запрос:

/OBJS/Var[@A=1 and @B=1 or @A=2 or @A=3]/X

Если рассматривать его как конструирующий, то прежде всего проверим, существует ли корневой элемент , и, если нет – создадим. Далее идет шаг Var с фильтром. Я не буду описывать правила, по которым обрабатывается фильтр-предикат, чтобы не усложнять изложение, скажу только, что этот фильтр четко описывает три набора данных, на которых он истинен:

  1. <Var A=”1” B=”1” />
  2. <Var A=”2” />
  3. <Var A=”3” />

Значит, нам надо сделать так, чтобы в элементе были дочерние элементы с такими данными. И, наконец, далее идет шаг X без условия – это означает, что необходимо, чтобы в каждом элементе Var был дочерний элемент .

В результате применения такого конструирующего XPath, например, к документу
Итак, все просто.

<OBJS> <Var A=”2” />
</OBJS>

получим выходной документ:

<OBJS> <Var A=”2”> <X/> </Var> <Var A=”1” B=”1”> <X/> </Var> <Var A=”3”> <X/> </Var>
</OBJS>

И при этом мы обошлись исключительно средствами XPath, без XSL или еще чего-либо в этом роде.
Итак, мы научили XPath создавать данные. Теперь поучим его (немного) их алгоритмически обрабатывать.

Оно вычисляется строго слева направо, это и есть то, что нужно. Последовательность операторов можно описать обычным логическим AND-выражением. Если оно должно быть выполнено полностью, то надо просто позаботиться, чтобы все его элементы возвращали истинное выражение.

A and B and C … and Z

Условный оператор вида if(A) then B else С, разумеется (и здесь я ничего нового не скажу), можно описать логическим выражением

A and B or C

Все немного сложнее с циклом. Просто так его вводить не очень хотелось, поэтому я решил просто ввести понятие XPath-функции, которая может быть рекурсивной. И тогда можно любой цикл представить цепочкой рекурсивных вызовов с проверкой условия окончания.

Не требуется даже переменных – их заменяют элементы текущего документа. В-принципе, это почти все (в минимальном варианте). Требуются только именованные аргументы функций.

Допустим, у нас есть документ, содержащих два списка чисел, описанных сериями вложенных элементов <list>:
Приведу пример.

<a> <b> <list data="1"><list data="2"></list></list> </b> <c> <list data="3"><list data="4"></list></list></c> </a>

Для этого необходимо ввести три XPath-функции:
Пусть надо сцепить списки из элемента <b> и элемента <c> и поместить результат прямо в <a>.

concat_list($#, $##): add_list(#/self::*) and add_list(##/self::*) add_list($#): count(list) = 0 and copy_list(#/self::*) or list[add_list(#/self::*)] or true() copy_list($#): count(#/list) = 0 or create(list[@data = #/list/@data]) and (list[copy_list(#/list)] or true())

и добавить к ним вызывающий XPath:

concat_list(/a/b,/a/c)

Я надеюсь, что вам, уважаемые читатели, будет немного интересно разобраться в таком «коде». Единственное, что я обязательно упомяну – create(XPATH) – это системная функция, которая исполняет свой аргумент XPATH в конструирующем режиме.

Понимая это, я ввел полноценные переменные, которые, собственно, в XPath уже есть – они начинаются со знака «$», но я добавил возможность присваивания им значения новой функцией set. А теперь о том, что все это, конечно, интересно, но программировать так, без переменных, все- таки довольно сложно. Пожалуйста, вот пример функции depth_list с двумя аргументами – ссылкой на начальный элемент, содержащий вложенный список из элементов (как в примере выше), и выходной переменной, в которую помещается длина списка:

depth_list($#, &$OUT1): set($OUT1,0) and (#/list[set($OUT1,1) and depth_list(#/list,$OUT0) and set($OUT1,max($OUT0+1,$OUT1))]) or true()

Иными словами, если есть текстовое описание некоторой задачи (для определенности — на русском языке), для решения которой надо сгенерировать программу, то это описание распознается и превращается в упорядоченный набор элементов постановки задачи (объектов с параметрами). В появившийся в результате микроязык, который я прозвал XPath Defender, я добавил еще некоторые необходимые функции и воспользовался им в своей системе распознавания и порождения программ PGEN++ для выполнения такой важной задачи, как автоматическое достраивание модели программы, представленной в виде XML-документа. Распознанные элементы помещаются в XML-документ и к ним применяются правила, записанные как в виде простых ограничивающих или порождающих XPath-утверждений, так и в виде фрагментов на XPath Defender (это один из вариантов рабочего процесса). Это первичная постановка, которая еще не содержит плана решения задачи. И уже потом по полученной модели система строит решающую программу. Эти правила проверяют и дополняют XML-документ-модель элементами плана решения. Эта схема успешно опробована на простых задачах математической обработки векторных данных.

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть