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

11 ноября 2008 года, 13:12

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теперь мы можем описать эту структуру с помощью 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-теги: открывающие, закрывающие и то, что между ними.

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

  1. Открывающий тег (окончание открывающего тега) — создаётся новый элемент и заполняется имеющимися данными. Текущий элемент устанавливается в новый;
  2. Закрывающий тег (его окончание) — текущий элемент устанавливается в родительский элемент текущего, так как нам следует подняться вверх по иерархии элементов (текущий элемент закончился);
  3. Текстовое содержимое — создаётся новый элемент с отличным от обычного типа и заполняется текстовым содержимым. Представлять текстовые элементы лучше именно в виде отдельных элементов, так как нам необходимо хранить точную структуру документа;
  4. Начало секции CDATA  — отключается XML-парсер до окончания секции (в соответствии со спецификацией XML, где указано, что мы не можем обрабатывать теги внутри CDATA;
  5. Окончание секции 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-парсера.

Мнения (12)

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

  • Miscђka

    13 ноября 2008 г.13:30

    а есть просто картинки без букаф?

  • Дин автор

    13 ноября 2008 г.13:49

    Пока нет, нужно раскрывать тему, которую обещал раскрывать.

  • Sannis

    14 ноября 2008 г.00:20

    За картинки отдельный респект :) Только на них буквы сильно меньше, чем размер текста, а при увеличении мазаться начинают картинки.

  • Дин автор

    14 ноября 2008 г.00:40

    @Sannis, советую пройти тогда по первой ссылке в записи и там слева нажать «Zoom», будет удобнее, уверяю. ;-)

  • Sannis

    14 ноября 2008 г.02:12

    @Дин, я думал это саморисованные картинки :) Так что вручную подбирать зум, конечно же, не нужно было для принтскрина, это я перегнул.

    Всем-всем: переходите по ссылке, там лучше и удобнее :)

  • Mischka

    14 ноября 2008 г.11:02

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

    Кстати, давай прикрутим такую же флешку тебе сюда, если уж она так нужна? Только можно сделать ее по-человечески.

  • Дин автор

    14 ноября 2008 г.12:47

    Да я могу и просто ссылки давать, какая разница?

    Она кстати и сделана максимально по-человечески. Всё для людей.

  • Mischka

    14 ноября 2008 г.13:26

    Если б она была для людей, я смог бы вернуться с нее назад на эту страницу. Ан нет!

  • Дин автор

    14 ноября 2008 г.13:28

    Не все люди убирают 88% кнопок Opera, да и не все пользуются ею. ;-)

  • Mischka

    14 ноября 2008 г.16:20

    это не значит, что полноэеранный флеш человечен :)

    Кстати, лучше такую же байду замутить на жабаскрипте, раз уж на то пошло.

  • Snowcore

    22 ноября 2008 г.18:39

    Хорошо потрудился!

    Нужно будет и мне на php подобное реализовать, а то Ruby еще не освоил :(

  • Дин автор

    22 ноября 2008 г.18:55

    @Snowcore, алгоритм один, реализация, я думаю, дело не самое сложное, справитесь. ;-)

Я тоже знаю!

Для обращения к человеку используйте символ @, после которого следует имя того, к кому обращаетесь (пробелы заменяются на знак подчёркивания). Если вам интересно, можете подписаться на комментарии по RSS или по эл. почте. Ведите себя достойно, вы же не роботы, правда?

Вы можете использовать следующие XHTML-элементы в разметке комментария: strong, em, span[class=crossline], a[href=uri], code[type=язык], blockquote, ul и ol. В качестве языка кода может быть указан, например, javascript или css.