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

Ссылки сюда (1) →

Короткая ссылка: 20241004G

Докладчик

Даниил Исакевич

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

Уделено внимание организации программы и программирования, возникающим ситуациям и приёмам.

Презентация

Thesis

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• https://gitflic.ru/project/strusov/refal-machine
• https://gitflic.ru/project/dvisa/drakoder
• https://gitflic.ru/project/dvisa/metahim