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

?v=1

Здравствуйте, уважаемые читатели. В этой публикации речь пойдет о немного нестандартных применениях такого хорошо известного формализма как 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 с фильтром. Я не буду описывать правила, по которым обрабатывается фильтр-предикат, чтобы не усложнять изложение, скажу только, что этот фильтр четко описывает три набора данных, на которых он истинен:


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

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


	


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


	
		
	
	
		
	
	
		
	


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

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

A and B and C … and Z


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

A and B or C


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

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

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

   
      
         
      
      
         
   

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

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, пришлось ввести только функции.

Habrahabr.ru прочитано 5680 раз