Практическое использование Racc — генератора LALR(1) парсера для Ruby

В рамках создания фреймворка для некоторой системы Enterprise класса, у меня стояла задача создания утилиты для автоматизированной генерации кода по UML модели. Ничего наиболее подходящего для быстрого и эффективного решения задачи, кроме как использование Ruby, и встроенного шаблонизатора ERB, под руку не подвернулось.

Файл проекта из среды 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
				next
		end
	end
	tokens << [false, false]
	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
}