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

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

  • <Var A=”1” B=”1” />
  • <Var A=”2” />
  • <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, пришлось ввести только функции.

    Оставить комментарий