DOT → leex → yeek → {libgraph; ETS} → graph
Заголовок настоящей статьи расшифровывается просто — далее рассказывается о реализации транслятора описания графа на языке dot при помощи генераторов лексера и парсера leex и yeek в структуру графа с помощью пакета libgraph. Реализация выполнена на платформе языка Elixir, который занимает подобающее место на заставке.
Интересно, что заголовок статьи сам является графом технологической цепочки. Проиллюстрирую этот момент соответствующим рисунком:
Рис. 1. Технологическая цепочка алгоритма транслятора.
Побудительным моментом разработки траслятора DOT была проблема, обозначенная в книге [1]. Отправной точкой исследований послужил следующей рисунок:
Рис. 2. Потоки данных вызовов графового API обращения к сервису графов.
Справа видны пакеты Elixir, объединяемые в систему, описываемую в [1], для общей сквозной работы с графами. Видно, что пакет libgraph выпадает из общего ряда и числится как неактивный. Дадим сопутствующую цитату из этой книги:
«Верхний тип графов, использующий пакет libgraph, кодируется непосредственно в Elixir. Для этого типа (графов не существует соответствующей базы данных графов, поэтому мы не сможем создать для него сервис графов.»
«Если бы у нас был десериализатор, мы могли бы прочитать это обратно в структуру данных Elixir Graph. К сожалению, библиотека libgraph позволяет нам только сериализовать. Так что, по сути, мы можем публиковать графы, но не можем их потреблять. Есть желающие поупражняться в чтении?»
Под действием «публиковать» в цитате понимается конвертирование в файл в формате .dot.
Кстати, обозначенное аналогичное ограничение мы найдем и в других графовых движках: digraph, graphvix. Но у всех у них функция to_dot, или аналогичные, чем мы воспользуемся для тестирования результата.
Дело в том, что такой десериализатор был очень необходим мне для исследований в области графов. Поэтому я последовал рекомендации и взялся за реализацию десериализатора.
Получившийся пакет десериализатора выложен на GibHub под названием dlyleg — акроним, составленным из первых букв компонентов.
Компоненты, разработанной системы
Дадим описание, характеристики и ссылки на исходные строительные компоненты пакета.
DOT — распространенный язык описания графов. Граф, описанный на языке DOT, обычно представляет собой текстовый файл с расширением .dot или .gv. По личному опыту знаю, что язык DOT с программой отображения (рендеринга) Graphviz демонстрируют явно академический характер использования, но этот вывод пока нами не принимается в рассмотрение. Познакомится с основными свойствами языка DOT можно по руководству [2].
DOT является de–facto стандартным языком описания графа.
Leex— модуль Erlang генератора лексического анализатора, или лексера. Генератор лексера leex основан на регулярных выражениях во входном файле, в чем похож на lex или flex языка C.
Yeek— модуль Erlang генератора синтаксического анализатора, или парсера. Генератор парсеров yeek, похожий на yacc языка C. Принимает в качестве входных данных определение грамматики БНФ и создает код Erlang для парсера.
Генераторы leex и yeek входят в один пакет Erlang Parsetools.
Руководство по использованию Parsetools можно найти в Интернете по адресу [3].
По моему субъективному мнению предварительное знание C–шных lex и yacc полезно, но мало помогает в понимании технологии leex и yeek.
Почему? Во–первых, хорошо известны скудость документации и примеров leex и yeek.
Во–вторых, в Elixir технологические операции leex и yeek упрятаны в «черный ящик» инструмента сборки mix. Для применения leex и yeek желательно знание и Elixir, т.к. работа идет на стыке двух платформ. Если обнаруживаются ошибки в грамматических правилах, то ссылки даются не на сами правила, а на генерируемый код Erlang.
В–третьих, я испытал большие трудности в отладке генератора синтаксического анализатора. На выходе не императивный код, генерируется «бесcловесная» списковая структура, которая пропадает в случае неудачи. В результате для локализации проблемы я выработал отладочный приём: т.к. инструкции dot дискретны и независимы, я просто отключал подозрительные инструкции при помощи комментирования.
Ценную системную информацию о leex и yeek я получил в постах [5, 6]:
К сожалению, я так и не смог полностью решить проблему диагностики грамматического разбора, т.к. в моей реализации ошибки выявляются после синтаксического и грамматического разборов на этапе преобразования полученного списка в графовую структуру (см. далее «Выбор формы хранения структуры графа»), а к этому моменту контекстная информация уже потеряна.
libgraph — высокопроизводительная библиотека графовой структуры данных для проектов Elixir, разработанная Паулем Шенфельдерем в качестве альтернативы пакета digraph Erlang–а. Онлайн документация пакета libgraph находится по ссылке [4].
Таблица ETS — Erlang хранилище для быстрого извлечений данных. В таблице ETS хранятся кортежи, доступ к которым осуществляется по ключу. С кратким описанием ETS можно познакомиться в книге [8].
Грамматика языка DOT
Для десериализатора использован БНФ языка DOT, который взят из официального руководства по DOT на сайте graphviz [7]:
Из БНФ были удалены синтаксические категории, связанные с портом узлов, т.к. использование этого элемента в дальнейшей разработке не просматривается.
С другой стороны, БНФ была дополнена отсутствующей в формальной грамматике формой построения ребер от одного узла к сборке узлов в фигурных скобках. Эта возможность в официальной документации описывается вербально.
Лексер
Не стану приводить текст входной файл генератора лексера, т.к. все достаточно стандартно со времён легендарного lex.
При разработки правил лексера были приняты следующие соглашения:
В отличие от стандарта числовые идентификаторы не разрешаются.
Атрибуты представляют собой пары ключ–значение. Ключ задается атомом, значение — строкой.
Оставлены только однострочные комментарии, начинающиеся двумя слэшами »//».
Парсер
Правила генератора парсера yeek задаются на основании БНФ языка dot [2]. Для экономии места и времени читателя не привожу БНФ, но выскажу общее соображение, повлиявшее на алгоритм отображения структуры парсера на граф.
Во входном файле генератора парсера корневой элемент синтаксического анализатора назван branch, а не root, т.к. его результат подобен не синтаксическому дереву, а линейной последовательной ветви с «листьями и гроздьями атрибутов».
Выбор формы хранения структуры графа.
Без учета дешифровки подграфов результат работы leex и yecc оказался линейной цепочкой термов, соответствующих инструкциям dot, описывающих узлы и ребра строимого графа.
Вложенные термы в списке ветви, кодирующие цепочки типа
a → b → c
, фактически так же обрабатываются линейно с помощью хвостовой рекурсии.
Отдельным случаем кодирования был оператор «сборки» узлов:
{a; b; c} → {d; e; f}
, который разрешался с помощь декартового произведения двух списков. Обработка декартового произведения производится линейно.
Выявленная линейность адекватно ложится на последовательность вызовов функций пакета libgraph.
Необходимо было решить, как организовать доступ к внутренней структуре пакета Libgraph.Graph. Пожалуй, это была самая трудная архитектурная дилемма.
На выбор было два варианта:
1. структура graph сохраняется между вызовами функций при помощи передачи «эстафеты» посредством параметра и возврате измененной структуры из функции,
2. создание GenServer OTP с соответствующим API, содержащего структуру graph.
На нынешнем этапе был принят 1–ый вариант под влиянием решений в подобном пакете Graphvix [10].
Наверное, это оптимальный вариант для задач типа простого транслятора и на нем удобно строить конвейеры операторов. Например, вот как выглядит конвейера обработки первичного файла dot до стадии обратного преобразования во вторичный файл dot:
read |> lex |> pars |> covert |> toDot
В процессе разработки пришло понимание, что для более развитых архитектур более подходит GenServer OTP состояния. В будущем я намерен испробовать 2–ой вариант, который обещает дать распределение ветвей графа по отдельным вычислителям.
Таблица ETS
В ходе разработки встретилась один существенный недостаток движка libgraph — отсутствие возможности привязать к узлам, рёбрам и графам атрибуты свойств. Впору было отказаться от пакета libgraph в пользу пакета Erlang–а digraph, или graphvix. Между прочим digraph, или graphvix базирутся как минимум на 3 таблицах ETS.
С другой стороны разработчик libgraph Пол Шенфельдер в [9] утверждает, что он устранил ограничения модуля digraph на количество графов и достиг во многих своих тестах и большей производительности.
Взвесив эти аргументы, я решил оставить в разработке пакет libgraph, но использовать для хранения атрибутов графа, его узлов и рёбер одну таблицу ETS. Для подграфов вводятся дополнительные таблицы ETS.
Для исключения коллизий названий элементов была использована отдельная таблица ETS для регистрации имен обрабатываемых графов. Это оказалось удобно при последовательном прогоне отладочного скрипта.
По информации из известной книги Саши Юрича [8] эффективная работа штатного модуля Registry основана именно на таблице ETS. Поэтому выбор таблиц ETS оказался оптимальным.
В настоящей версии транслятора содержимое таблицы ETS на диске не сохраняется. Возможно это будет реализовано при помощи таблицы DETS, но пока вопрос остается открытым до принятия решения об обеспечении идентичности связанных таблиц и графов.
Применение макросов для формирования проверочных функций
Вернусь к вопросу диагностики грамматического разбора. При вызове функций построения графа на предпоследнем этапе проводится проверка соответствия названий атрибутов элементам графа стандартным именам.
Это механизм реализован с помощью макросов Elixir. Данные для генерируемых проверочных функций хранятся в трех файлах csv. Талица атрибутов узлов содержит 33 строки, рёбер — 54 и графа — 52.
Для обработки прочитанных строк применяется ленивый алгоритм на базе модуля Stream.
Проверочные функции испытывают только названия атрибутов на соответствие стандарту, но не их значений, по двум причинам:
1. проверка типов значений атрибутов требуют большой объем работы по реализации более 30 стандартов. Проверочные функции вытаскивают по имени атрибута список его типов, поэтому все готово, чтобы в дальнейшем эту работу выполнил специалист
2. атрибуты в библиотеке libgraph не загружаются и в текущей реализации транслятора не используются; это задел на будущее.
По сути атрибутика графа может служить основой для DSL языка прикладной области и каждый желающий может расширять список допустимых атрибутов элементов графа.
Поверочное конвертирование файла dot.
Для поверки транслятора можно загрузить в libgraph небольшой, но насыщенный граф из фирменного руководства Graphviz:
digraph G {
main → parse → execute;
main → init;
main → cleanup;
execute → {make_string; printf}
init → make_string;
main → printf;
execute → compare;
}
Т.к. библиотека libgraph умеет экспортировать построенный граф в файл в формате dot, то мы успешно сконвертировали его средствами Graphviz в рисунок в формате png.
Вот результат обратной конвертации:
Рис. 3. Обработанный пример графа из [2].
Результат совпадает с рисунком изначальным графа.
Итоги
Готовый транслятор выложен на GitHub: https://github.com/VAK-53/dlyleg
Для быстрого освоения транслятора в пакет встроен подпроект Example, который содержит технологические конвейеры разной степени сложности.
Конвертор физически разделяет граф на две составляющие:
· скелет графа,
· наложенный массив атрибутов элементов графа.
Вторая составляющая доступна разработчикам для насыщения графа прикладными атрибутами.
Реализованный конвертор открывает окно возможностей программирования графовых структур: описание, загрузка, анализ графов и наложение прикладных атрибутов.
Ещё очень надеюсь, что за мной последуют и другие специалисты.
Литература
1. Tony Hammond «Exploring Graphs with Elixir, Connect Data with Native Graph Libraries and Graph Databases»
2. https://graphviz.org/pdf/dotguide.pdf Drawing graphs with dot. Emden R. Gansner and Eleftherios Koutsofios and Stephen North January 5, 2015
3. https://www.erlang.org/docs/22/apps/parsetools/parsetools.pdf
4. https://hexdocs.pm/libgraph/api-reference.html
5. https://andrealeopardi.com/posts/tokenizing-and-parsing-in-elixir-using-leex-and-yecc/
6. https://arjanvandergaag.nl/blog/write-your-own-parser.html
7. https://www.graphviz.org/doc/info/lang.html
8. Саша Юрич, Elixir в действии, — М.: ДМК Пресс, 2020.
9. https://github.com/bitwalker/libgraph
10. https://blog.songsaboutsnow.com/elixir/graphviz/2018/06/26/graphvix-part1.html
Habrahabr.ru прочитано 13062 раза
