Файл проекта из среды UML моделирования представлял собой базу данных формата SQLite3, однако некоторую часть информации в этой БД среда хранила в виде сериализованных в BLOB поля объектов. Формат сериализации был текстовый, но не совместимый ни с одним из известных, такими как XML, YAML, совсем отдаленно напоминал JSON. Использовать существующие в природе парсеры было невозможно.
В простых случаях, когда вам не требуется весь объект целиком, а только пара скалярных полей конкретной инстанции, то конечно можно тупо добраться до нужного регулярками. В противном случае, есть универсальное решение проблемы, позволяющее быстро создавать собственные парсеры для подобных структур, десериализующие их в объекты Ruby.
Вот так примерно выглядят исходные сериализованные объекты.
Задача — получить это в виде комплексной структуры Ruby на базе Array и Hash.
data.txt
7ghoJdyGAqACCgeT:"User":Class { FromEndRelationships=( <vdHoJdyGAqACCgfe>, <9bToJdyGAqACCgfF> ); _masterViewId="7ghoJdyGAqACCgeS"; pmLastModified="1355667704781"; pmAuthor="author"; Child=( {UwZoJdyGAqACCgei:"name":Attribute { visibility=71; pmLastModified="1355667655234"; pmAuthor="author"; type=<_n2oJdyGAqACCgXh>; pmCreateDateTime="1355667628234"; _modelViews=NULL; _modelEditable=T; }}, {9lZoJdyGAqACCgel:"created":Attribute { visibility=71; type_string="date"; pmLastModified="1355667655234"; pmAuthor="author"; pmCreateDateTime="1355667630703"; _modelViews=NULL; _modelEditable=T; }}, {nLFoJdyGAqACCgeo:"active":Attribute { visibility=71; pmLastModified="1355667655234"; pmAuthor="author"; type=<_n2oJdyGAqACCgXY>; pmCreateDateTime="1355667639609"; _modelViews=NULL; _modelEditable=T; }} ); pmCreateDateTime="1355667607671"; _modelViews=( {4QhoJdyGAqACCgeU:"View":ModelView { container=<hguoJdyGAqACCgeL>; view="7ghoJdyGAqACCgeS"; }} ); _modelEditable=T; }
Если проанализировать исходный формат, то в нем можно выделить следующие элементы, которые четко определяют его грамматику:
- Объект. Он начинается со строки формата Id:"Name":Type, и далее в фигурных скобках содержит набор атрибутов.
- Атрибуты объекта. Указываются как ключ = значение, плюс точка с запятой.
- Значение атрибута. Может быть строкой, числом, ссылкой, другим объектом, или коллекцией любых из перечисленных значений.
- Значения указываются в определенной для каждого типа нотации. Строки заключается в кавычки. Объект заключается в фигурные скобки. Коллекция значений заключается в круглые скобки, через запятую.
Подобная грамматика является контекстно-свободной, ее легко можно описать при помощи формы Бэкуса — Наура. А для разбора использовать восходящий алгоритм сдвиг/свертка. Один из самых распространенных алгоритмов этой категории это LALR(1), он используется в таких известных «компиляторах компиляторов» как Yacc/GNU Bison. Существует и реализация для интересующей нас платформы Ruby — это Racc. Его мы и будем использовать для создания нашего парсера.
Восходящий алгоритм сдвиг/свертка
Для того, чтобы базово сориентироваться в Racc, и создать элементы нашего будущего парсера, достаточно в общем упрощенном виде представлять принцип работы алгоритма восходящего разбора сдвиг/свертка.
Предположим, у нас есть входной поток символов:
ВОДА + СПИРТ + СОК
Также у нас заданы правила грамматики:
ВОДКА это ВОДА + СПИРТ
КОКТЕЙЛЬ это ВОДКА + СОК
Входящий поток поделен на две части маркером: проанализированную левую, и непроанализированную правую. Маркер визуально представлен символом ‘|’. Алгоритм последовательно читает по одному символу из потока, это есть операция сдвига (Shift), которая передвигает маркер на одну позицию вправо. Следующим шагом алгоритм выполняет операцию свертки (Reduce) для левой от маркера части, в соответствии с правилами грамматики. И так до конца, пока не кончатся символы и все свертки не будут удовлетворены.
s: ВОДА | + СПИРТ + СОК
r: ВОДА | + СПИРТ + СОК
s: ВОДА + | СПИРТ + СОК
r: ВОДА + | СПИРТ + СОК
s: ВОДА + СПИРТ | + СОК
r: ВОДКА | + СОК
s: ВОДКА + | СОК
r: ВОДКА + | СОК
s: ВОДКА + СОК |
r: КОКТЕЙЛЬ |
Установка Racc
Среда выполнения для парсеров на базе Racc уже включена в Ruby. Начиная с версии 1.8.x любой парсер, созданный при помощи Racc, будет работать без дополнительных телодвижений. Однако для того, чтобы иметь возможность создавать собственные парсеры, необходимо установить пакет Racc, содержащий генератор парсеров. Это делается стандартно через gem:
# gem install racc
Создание парсера на Racc
Исходником для генератора парсеров Racc является файл (обычно с расширением .y), содержащий определение Ruby-класса парсера, и включающий дополнительные директивы Racc. В определении парсера должны присутствовать следующие элементы:
- Определения терминальных символов грамматики — токенов
- Определения правил грамматики и сверток
- Лексический анализатор
Токены
Итак, первое, что необходимо сделать, это в грамматике выделить так называемые терминальные символы — элементарные частицы, из которых составляются более сложные конструкции, и дать им имена. У нас получится примерно следующее:
- T_OBJECTID — идентификатор объекта
- T_IDENTIFIER — идентификатор атрибута
- T_STRING — текстовая строка
- T_NUMBER — число
- T_BOOLEAN — булево значение
- T_NULL — пустое значение
- T_REFERENCE — ссылка
- T_LBR, T_RBR, T_LPAR, T_RPAR, T_EQ, T_COMMA, T_SEMICOLON — знаки препинания: различные скобки, знак равно, запятая, точка с запятой
В определении класса парсера допустимые токены определяются, используя ключевое слово token.
Лексический анализатор
Следующим шагом следует создать лексический анализатор. В его функции входит сканирование входящего потока и выявление в нем токенов. Лексический анализатор должен трансформировать входящий поток в набор последовательных токенов. Racc, при выполнении операции сдвига, должен получить из входящего потока новый токен, преобразованный лексическим анализатором. Он это осуществляет посредством вызова у класса парсера метода next_token, который должен возвращать структуру, содержащую имя и значение токена:
[:TOKEN_NAME, 'Token value']
В качестве метки окончания потока служит значение:
[false, false]
Для создания лексического анализатора удобно использовать класс StringScanner. Иногда важно правильно выбирать порядок сканирования шаблонов, так как одни токены могут перекрывать другие. В данном примере лексический анализатор выполняет полную обработку всего входящего потока сразу при старте парсера, вызывая метод tokenize, и сохраняя получившиеся токены в массив, из которого каждый раз и получает следующий токен метод next_token.
Правила грамматики
Следующим шагом мы описываем правила грамматики. В Racc это выполняется при помощи директивы rule, следуя за которой задаются правила используя форму Бэкуса — Наура. Нетерминальные символы выражаются через терминальные и нетерминальные. Например, в следующем фрагменте задается нетерминал attribute — атрибут объекта, который в соответствии с нашей грамматикой представляет собой идентификатор, следующий за ним знак равенства, произвольное значение выраженное другим нетерминалом, и завершающая точка с запятой:
attribute: T_IDENTIFIER T_EQ value T_SEMICOLON { result = { val[0] => val[2] } };
В фигурных скобках после правила задается выражение Ruby, которое должно выполнять свертку заданной последовательности символов до объявленного нетерминала, в данном случае — attribute. Переменные val и result предопределены Racc. Массив val содержит значения свертываемой последовательности, в данном случае val[0] содержит значение T_IDENTIFIER, val[2] значение value. В переменную result размещается результирующее свернутое значение.
Для запуска парсера необходимо вызвать метод do_parse. Этот метод определен в классе Racc::Parser, от которого будет унаследован наш класс парсера.
Ниже представлен полный исходный текст определения парсера.
parser.y
class Parser token T_OBJECTID T_STRING T_REFERENCE T_IDENTIFIER T_NUMBER T_BOOLEAN T_NULL token T_LBR T_RBR T_LPAR T_RPAR T_EQ T_COMMA T_SEMICOLON start input rule input: object { @result = val[0] }; object: T_OBJECTID T_LBR attributes T_RBR { oid = val[0].split(':'); result = { :id => dequote(oid[0]), :name => convertNULL(dequote(oid[1])), :type => dequote(oid[2]) }.merge(val[2]) }; attributes: attribute { result = val[0] } | attributes attribute { result = val[0].merge(val[1]) } ; attribute: T_IDENTIFIER T_EQ value T_SEMICOLON { result = { val[0] => val[2] } }; values: value { result = [val[0]] } | values T_COMMA value { val[0] << val[2] } ; value: T_STRING { result = dequote(val[0]) } | T_REFERENCE { result = dequote(val[0]) } | T_NUMBER { result = val[0].to_i } | T_BOOLEAN { result = val[0] == 'T' } | T_NULL { result = nil } | T_LBR object T_RBR { result = val[1] } | T_LPAR values T_RPAR { result = val[1] } ; ---- header ---- require 'strscan' ---- inner ---- def tokenize(text) tokens = [] s = StringScanner.new(text) until s.eos? case when s.skip(/\s+/) next when s.scan(/\A[\w\.]+:\"*\w*\"*:\w+/) tokens << [:T_OBJECTID, s[0]] next when s.scan(/\A\{/) tokens << [:T_LBR, nil] next when s.scan(/\A\}/) tokens << [:T_RBR, nil] next when s.scan(/\A\(/) tokens << [:T_LPAR, nil] next when s.scan(/\A\)/) tokens << [:T_RPAR, nil] next when s.scan(/\A\=/) tokens << [:T_EQ, nil] next when s.scan(/\A\,/) tokens << [:T_COMMA, nil] next when s.scan(/\A\;/) tokens << [:T_SEMICOLON, nil] next when s.scan(/\w+/) if (s[0].match(/[0-9]+/)) tokens << [:T_NUMBER, s[0]] elsif (s[0].match(/\A[TF]{1}\Z/)) tokens << [:T_BOOLEAN, s[0]] elsif (s[0].match(/\ANULL\Z/)) tokens << [:T_NULL, nil] else tokens << [:T_IDENTIFIER, s[0]] end next when s.scan(/(["]).*?(?<!\\)\1/m) tokens << [:T_STRING, s[0]] next when s.scan(/\<.*?\>/) tokens << [:T_REFERENCE, s[0]] next else s.getch end tokens << [false, false] end return tokens end def parse(text) @tokens = tokenize(text) do_parse return @result end def next_token @tokens.shift end def dequote(text) text.gsub(/\A["<]|[">]\Z/, '').strip end def convertNULL(text) text.upcase == "NULL" ? nil : text end
Файл .y это еще не парсер. Парсер нужно сгенерировать, используя утилиту racc, и делать это необходимо каждый раз после изменения определения парсера в .y файле:
# racc parser.y -o parser.rb
Полученный файл с классом парсера можно подключать и использовать обычным образом:
main.rb
require 'pp' require './parser.rb' parser = Parser.new obj = parser.parse(File.read("data.txt")) puts obj.pretty_inspect
Таким будет результат работы парсера — комплексная структура Ruby:
output
{ :id => "7ghoJdyGAqACCgeT", :name => "User", :type => "Class", "FromEndRelationships" => ["vdHoJdyGAqACCgfe", "9bToJdyGAqACCgfF"], "_masterViewId" => "7ghoJdyGAqACCgeS", "pmLastModified" => "1355667704781", "pmAuthor" => "author", "Child" => [ { :id => "UwZoJdyGAqACCgei", :name => "name", :type => "Attribute", "visibility" => 71, "pmLastModified" => "1355667655234", "pmAuthor" => "author", "type" => "_n2oJdyGAqACCgXh", "pmCreateDateTime" => "1355667628234", "_modelViews" => nil, "_modelEditable" => true }, { :id => "9lZoJdyGAqACCgel", :name => "created", :type => "Attribute", "visibility" => 71, "type_string" => "date", "pmLastModified" => "1355667655234", "pmAuthor" => "author", "pmCreateDateTime" => "1355667630703", "_modelViews" => nil, "_modelEditable" => true }, { :id => "nLFoJdyGAqACCgeo", :name => "active", :type => "Attribute", "visibility" => 71, "pmLastModified" => "1355667655234", "pmAuthor" => "author", "type" => "_n2oJdyGAqACCgXY", "pmCreateDateTime" => "1355667639609", "_modelViews" => nil, "_modelEditable" => true } ], "pmCreateDateTime" => "1355667607671", "_modelViews" => [ { :id => "4QhoJdyGAqACCgeU", :name => "View", :type => "ModelView", "container" => "hguoJdyGAqACCgeL", "view" => "7ghoJdyGAqACCgeS" } ], "_modelEditable" => true }
ссылка на оригинал статьи http://habrahabr.ru/post/164091/
Добавить комментарий