Enumerate: Высокие деревья преклонились над землёй

После некоторого перерыва в публикации записей, мы возвращаемся к изучению такой темы, как XML. Как и в предыдущих исследованиях, сегодня мы погрузимся в теорию, попытаемся рассмотреть способы обработки XML, алгоритмы работы парсера и варианты хранения данных в нём.

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

Загрузка исходных данных

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

Фабрика работы с исходными данными

Для того, чтобы мы не были зависимы от конкретного источника данных, нам следует создать слой абстракции над загрузкой данных. Именно он будет определять, какие именно данные следует получить и в соответствии с этим вызывать соответствующий обработчик. На практике подобное определение заключается, например, в эвристической обработке строки, в которой заключен путь к источнику данных. Вот примеры такой строки:

http://labs.web-zine.org/docs/oml/doc-xhtml1−strict.oml
/home/dinamyte/my.xml

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

<?xml version="1.0" encoding="utf-8" ?>

В этом случае обработчик источника данных привлекать не нужно, можно сразу передать XML парсеру. Строго говоря, даже при получении данных из файла или удалённого источника, мы всё равно сводим эти данные к обычной строке и передаём парсеру, который начинает усердно с ней работать.

Кодировка документа

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

Алгоритм парсинга

Перед обработкой данных, мы должны произвести ещё один подготовительный этап: выделить используемую документом кодировку. Данный этап нужен для того, чтобы правильно обрабатывать текстовые данные и данные об XML-элементах документа, ведь имена элементов и их содержимое может быть записано не только с помощью символов латинского алфавита: XML поддерживает Unicode, а, следовательно, и интернационализацию. При верном определении кодировки документа мы сможем добавить (или удалить) определённые шаги обработки документа. Например, если документ содержит лишь ASCII-символы, то нам не нужно применять функции для работы с интернационалым именованием.

Алгоритм определения кодировки заключается в следующем:

Определить кодировку документа по кодировке исходного файла или по одному из заголовков ответа от сервера (при получении исходных данных из удалённого источника);
Просмотреть атрибут encoding в декларации XML-документа и принять её как кодировку документа (даже несмотря на положительный результат предыдущей проверки, текущая имеет более высокий приоритет);
Если по каким-то причинам определить кодировку невозможно, это можно сделать эвристически, просканировав документ, либо логически, приняв utf-8 за кодировку документа.

Уже после этого этапа можно приступать к обработке документа.

Структуры парсинга

Парсинг любых данных подразумевает трансформацию исходных данных (зачастую текстовых) в структуры на применяемом для парсинга языке программирования. Мы будем составлять такие структуры с помощью хорошо комментированного Ruby.

В основе описания структур данных лежит принцип определения логической единицы в исследуемом нами явлении. В XML-парсинге такой единицей является элемент, который нам и следует описать. Он обладает следующим набором свойств:

Имя элемента;
Пространство (namespace) элемента;
Тип элемента (текстовый элемент, обычный элемент, и подобные);
Содержимое элемента (используется только для текстовых элементов);
Атрибуты элемента (массив атрибутов).

Помимо этого, мы должны определить набор свойств для связывания текущего элемента в дереве всех элементов. Это достигается путём добавления нижеуказанных свойств:

Родительский элемент (по умолчанию он не установлен, значит такой элемент является корневым элементом дерева);
Дочерние элементы (их массив, в том порядке, в каком они встречаются в исходных данных).

Теперь мы можем описать эту структуру с помощью Ruby, добавив при этом необходимые действия, которые мы можем выполнять с элементом.

#Объединяем классы (структуры данных) в отдельный модуль module XML #Отдельный XML-элемент (узел в дереве) class SimpleNode #Свойства только для чтения attr_reader :name, :type, :namespace #Свойства для чтения и записи извне класса attr_accessor :parent, :attributes, :child_nodes, :child_node_position, :node_data #Инициализация класса # name - имя элемента (RAW-имя, например, div или svg:transformation) # type - тип элемента (:element для обычного элемента и :text для текстового) def initialize name, type = :element #Пространство имён элемента (по умолчанию его нет) @namespace = nil #Определяем, есть ли пространство имён у данного элемента if name.include? ":" #Разделяем по двоеточию; слева — пространство имён, справа — имя name = name.split ":" #Устанавливаем имя и пространство имён @namespace = name[0] @name = name[1] else #Пространство не указано, устанавливаем имя элемента @name = name end #Тип элемента @type = type #Родительский элемент (по умолчанию его нет) @parent = nil #Ассоциативный массив атрибутов #Имеет вид: имя_атрибута = значение_атрибута @attributes = {} #Массив дочерних элементов @child_nodes = [] #Текстовое содержимое узла (только если его тип — text) @node_data = "" end #Набор простых операций с элементом #Добавление нового дочернего элемента (существующего) def append_node node #Текущий элемент — родительский для дочернего node.parent = self #Добавляем в массив всех дочерних @child_nodes << node end #Добавление нового атрибута def attribute_add name, value @attributes[name] = value end #Проверки тех или иных ситуаций #У элемента установлено пространство имён? def namespace_exists? @namespace != nil end #У элемента есть атрибуты? def attributes_exists? @attributes.length != 0 end #У элемента есть дочерние элементы? def child_nodes_exists? @child_nodes.length != 0 end #У элемента есть родительский элемент? def parent_exists? @parent != false end end end

Логическую единицу мы создали, теперь будем двигаться вверх по уровням абстракции. Выше элемента у нас набор элементов, то есть документ. Документ представляет собой дерево связанных между собой элементов. Каждый элемент может иметь несколько дочерних элементов. Каждый дочерний элемент может иметь родительский; если такого элемента нет, то данный элемент — корневой в дереве документа.

Парсинг документа

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

Метод конечных автоматов

После удаления комментариев мы остаёмся один на один со структурной раскладкой документа. Мы должны приступать к его обработке. Какие шаги нам следует предпринять и как следует обрабатывать XML? Существует множество способов работы с XML. Некоторые заключаются в построении кеша и преобразовании XML в другой тип данных, чтобы потом применить другой парсер. Другие создают дерево элементов, как мы и условились сделать с самого начала, используя при этом метод конечных автоматов.

Весь процесс парсинга в последнем случае состоит из нескольких этапов: точки входа, различных постоянных состояний и точки выхода. При этом нам понадобится один временный элемент, который будет указывать на текущий элемент во всём дереве и одна переменная, указывающая на текущее состояние парсинга.

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

Состояния могут быть следующими:

Открывающий тег (окончание открывающего тега) — создаётся новый элемент и заполняется имеющимися данными. Текущий элемент устанавливается в новый;
Закрывающий тег (его окончание) — текущий элемент устанавливается в родительский элемент текущего, так как нам следует подняться вверх по иерархии элементов (текущий элемент закончился);
Текстовое содержимое — создаётся новый элемент с отличным от обычного типа и заполняется текстовым содержимым. Представлять текстовые элементы лучше именно в виде отдельных элементов, так как нам необходимо хранить точную структуру документа;
Начало секции CDATA — отключается XML-парсер до окончания секции (в соответствии со спецификацией XML, где указано, что мы не можем обрабатывать теги внутри CDATA;
Окончание секции CDATA — включается XML-парсер и продолжается дальнейшая обработка документа. Секция CDATA может быть присоединена к дереву в качестве обычного текстового элемента, либо в качестве элемента отдельного типа.

Когда тегов больше нет, мы попадаем в точку выхода, достигая таким образом окончания документа.

#Нам необходим класс простого элемента require "library/xml/parser/node" #Группируем созданные классы module XML class Document #Свойства для чтения attr_reader :tree #Инициализация документа #В качетсве параметра передаётся тип создаваемых элементов #Данный шаг предпринят для обеспечения гибкости класса документа def initialize node_type = XML::SimpleNode #Сохраняем тип элемента @node_type = node_type #Создаём корень нашего дерева (тип — root) @tree = @node_type.new "root", :root end #По умолчанию мы считаем, что документ содержит кодировку utf-8 #Обработка данных из строки def parse_string string #Удаляем комментарии string.gsub!(//m, "") #При использовании CDATA в документе, мы должны обеспечить её целостность if string.include? "<![CDATA[" #Удаляем < и > из секций CDATA string.scan(/(<!\[CDATA\[(.*?)\]\]>)/um).each do |token| token[1].gsub!("<", "<") token[1].gsub!(">", "&rt;") string.gsub!(token[0], "<![CDATA[" + token[1] + "]]>") end end #Заключаем содержимое каждого элемента в PCDATA #Этот шаг предпринят для получения текстового содержимого элемпента string.gsub!(/>(?!<)/m, "><![PCDATA[") string.gsub!(/(?!>)</m, "]]><") #Создаём указатель на результирующий массив result = @tree #All-in-one pattern: сканируем все возможные вхождения (кроме XMLDecl) string.scan(/\<([a-zA-Z0-9:\-]+)\s*([^>]+>|>)|<\/([a-zA-Z0-9:\-]+)>|<!\[(?:P|)CDATA\[(.*?)\]\]>/um).each do |token| #Переходим к методу конечных автоматов if token[0] != nil and token[1] != nil #Открывающий тег #Создаём экземпляр нового элемента и устанавливаем его имя new_tag = @node_type.new token[0], :element #Есть ли атрибуты у данного элемента? if token[1] != ">" #Если есть, добавляем их к элементу token[1].scan(/(([A-Za-z:\-_]+)=(?:\"|')([^"]+?)(?:\"|'))/).each do |attr| new_tag.attribute_add attr[1], attr[2] end end #Добавляем созданный элемент к дереву всех элементов result.append_node new_tag #Новый элемент становится текущим #Если элемент не содержит других элементов, то операция не производится result = new_tag if token[1][token[1].length - 2].chr != "/" elsif token[2] != nil #Закрывающий тег #Устанавливаем текущий элемент в родительский текущего #Условие: существование родительского элемента result = result.parent if result.parent_exists? elsif token[3] != nil and token[3].strip != "" #(P)CDATA — текстовое содержимое #Создаём текстовый элемент (его имя может быть пустым) new_tag = @node_type.new "", :text #Добавляем текстовые данные #result.node_data = token[3].gsub("<", "<").gsub(">", ">") new_tag.node_data = token[3] #Добавляем к текущему элементу result.append_node new_tag end end end end end

Теперь мы можем создавать XML-документы и иметь доступ к их древовидной структуре, обращаясь к соответствующему свойству объекта документа. Примечательно, что применение данного способа позволяет обрабатывать не только полностью валидные документы, но даже и отдельные их части, поэтому такой парсер называется потоковым (Stream XML parser).

Итоги

Мы написали небольшой XML-парсер. Его можно оптимизировать и дальше, но в учебных целях подойдёт и столь компактная его версия. После реализации XML-парсера, мы можем со спокойной душой отправляться в плавание по просторам XML-трансформации и разного рода модификациям исходного дерева XML. Мы не станем останавливаться на текущем шаге и посвятим ещё парочку выпусков данной теме. А пока вы можете посмотреть на одну из моих рабочих версий XML-парсера.