24 August 2019

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

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

Конструирующий XPath


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

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

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

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

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

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

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

Итак, все просто. В результате применения такого конструирующего 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


Итак, мы научили 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>

Пусть надо сцепить списки из элемента <b> и элемента <c> и поместить результат прямо в <a>. Для этого необходимо ввести три 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, пришлось ввести только функции.
Tags:XMLXPathязык программированияпорождение программ
Hubs: Programming XML
+19
5.3k 41
Comments 19
Popular right now
Top of the last 24 hours