Опыт использования Рефала-5 для преобразования текстов на формальных языках (Даниил Исакевич, OSSDEVCONF-2024) — различия между версиями

Текущая версия на 19:39, 23 октября 2024

Докладчик: Даниил Исакевич

Показаны примеры использования Рефала-М для преобразования текстов на формальных языках: автоматического построения ДРАКОНовских диаграмм (редактор drakon) из псевдокода и наборов формул предложенного автором языка в виде схем-графов (пакет graphviz).
Уделено внимание организации программы и программирования, возникающим ситуациям и приёмам.

Видео

Презентация

Thesis

Введение

Рефал — язык, созданный для написания программ, пишущих программы. Его наличие поощряет создание языков под своё понимание и нужные классы задач. Часто перевод с одного формального языка высокого уровня на другой более низкого уровня осуществим достаточно быстро.

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

Среди востребованных задач такого рода — построение содержательной графики.

Укрощение drakon'а

Автоматизация формирования ДРАКОНовских диаграмм понадобилась из-за того, что для редактора drakon диаграмма — лишь куча графических элементов; он не имеет представления об их связях, и при редактировании диаграмма «расползается».

А результат (штук пятнадцать красивых картинок) понадобился если не послезавтра, то хотя бы на следующей неделе. Поэтому было решено прекратить тесное общение с drakonом, скормив ему готовые диаграммы.

Файл имя.drn, в котором drakon хранит диаграммы, является базой данных SQLite и может быть создан последовательностью SQL-запросов; собственно диаграммы и графические элементы создаются INSERT-ами в соответствующие таблицы.

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

текст ::= строка переводстроки текст | конецфайла
строка ::= описаниешага `//' комментарии | описаниешага
комментарии ::= комментарий `//' комментарии | комментарий
описаниешага ::= заголовок `{' | `}' | описаниедействия
заголовок ::= условие `?' | перем `=' нач `:' кон |
              названиеблокакода

Псевдокод на этом языке переводится в SQL-запросы Рефал-программой^[1] за три основных этапа (каждый этап — несколько более мелких шагов):

Ввод текста, распознавание и преобразование его структуры
Размещение блоков на диаграммах
Дорисовка соединительных линий и вывод SQL-запросов

Для размещения графических элементов потребовалось вычислять их размеры и координаты. Координаты зависят от вложенности блоков кода и удобнее вычисляются, если программа представлена как лес. Координаты на диаграмме вычисляются в порядке следования по программе как плоскому списку.

От набора формул к схеме

Другая задача — перевод набора формул ЯСП (описан в отдельном докладе) в команды языка dot пакета graphviz. Перевод выполняется Рефал-программой^[2].

Основные его этапы:

Ввод и разбор формул и построение леса, перевод выражений в префиксную форму
Выделение представляющих интерес общих подвыражений
Представление леса как списка узлов (корни и листья именованы) и дуг
Склейка одноимённых узлов
Нумерация узлов, формирование команд выходного языка.

Замечания о программировании

Последовательность преобразований реализована функцией

ЦепьПреобразований {
    .вхарг (.прочие (?функция .допарг)) =
        <Mu ?функция .допарг
            <ЦепьПреобразований .вхарг (.прочие)»;
    .вхарг () = .вхарг;
}

— используя которую удобно наращивать цепочку вызовов; порядок вызовов слева направо, поэтому код сохраняет читаемость.

Особое внимание уделяется построению плана преобразований, одни из которых изменяют структуру данных в целом, а другие обрабатывают локальные ситуации (обычные или особые). Документирование такой программы — отдельная задача.

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

При расчётах размеров и координат терм нагружается подтермами, и было бы удобно искать значения по «ключу» — что требует реализовать функцию поиска. Сейчас такой функции нет, и программист следит за расположением подтермов сам.

Примечания и ссылки

↑ Исакевич Д. Преобразователь псевдокода в диаграммы ДРАКОН. https://gitflic.ru/project/dvisa/drakoder
↑ Исакевич Д. Преобразователь формул ЯСП в схемы GraphViz. https://gitflic.ru/project/dvisa/metahim

[Drakoder-1] Исакевич Д. Преобразователь псевдокода в диаграммы ДРАКОН. https://gitflic.ru/project/dvisa/drakoder

[Metahim-2] Исакевич Д. Преобразователь формул ЯСП в схемы GraphViz. https://gitflic.ru/project/dvisa/metahim

[1]

[2]