Бюджетные и Финансовые Технологии
Младший специалист
Рязанов Юрий Дмитриевич, доцент, БГТУ им. В.Г. Шухова
УДК 519.685.3
Развитие информационных технологий приводит к необходимости создания новых трансляторов языков программирования. Для этого в настоящее время широко используются системы автоматизированного построения трансляторов (САПТ) [1 — 4]. Эффективность использования САПТ определяется языком описания спецификации транслятора. Как правило, спецификация транслятора в этих системах представляется в нотации РБНФ или ее модификациях. Одним из удобных способов задания спецификации транслятора является транслирующая синтаксическая диаграмма, которая практически не используется в САПТ. Здесь дается формальное определение транслирующей синтаксической диаграммы и описывается разработанное программное средство — редактор синтаксических диаграмм, которое может быть использовано в САПТ.
Транслирующую синтаксическую диаграмму будем задавать четверкой
D = (T, N, S, А, G), где T — конечное множество терминалов; N — конечное множество нетерминалов; S`in` N — начальный нетерминал; А — конечное множество действий, G = (V, E) — ориентированный граф, где V = VTVN
VА
Vu
Vвход
Vвыход,где Vвход — множество точек входа, |Vвход| = |N|;
VT — множество терминальных вершин;
Vu — конечное множество узлов;
Vвыход — множество точек выхода, |Vвыход| = |N|;
E = E1E2
E3
E4
E5
E6, где
E1{(a, b) | a`in` Vвход, b`in` Vu}— множество входных дуг;
E2{(a, b) |a`in` Vu, b`in` Vвыход} — множество выходных дуг;
E3{(a, b) |a`in` Vu, b`in` VTVN} — множество дуг, выходящих из узлов;
E4 {(a, b) |a`in` VTVN
VA, b`in` Vu} — множество дуг, входящих в узлы;
E5{(a, b) | a`in` VNVT, b`in` VA}— множество дуг входящих в вершину действие;
E6{(a, b) |a`in` Vu,b`in` Vu} — множество ε-дуг, соединяющих узлы.
Каждому нетерминалу соответствует связная компонента графа. Компонента именуется соответствующим нетерминалом, имеет только одну точку входа и одну точку выхода и конечное множество вершин других типов. Точки входа и выхода на диаграмме компоненты не изображаются. Нетерминальная вершина изображается прямоугольником, в который вписан терминальный символ. Узел изображается на диаграмме жирной точкой. В точку входа не входит ни одна дуга и выходит конечное множество дуг (входные дуги компоненты). Узлы, в которые входят входные дуги, называются начальными. Из точки выхода не выходит ни одна дуга и входит конечное множество дуг (выходные дуги компоненты). Узлы, из которых выходят выходные дуги, называются заключительными. Каждая дуга, за исключением входных и выходных дуг, может выходить из узла и входить в терминальную или нетерминальную вершину или другой узел, выходить из терминальной, нетерминальной или вершины действия и входить в узел, либо выходить из терминальной или нетерминальной вершины и входить в вершину действие. В каждую терминальную, нетерминальную вершину и в вершину действия входит только одна дуга и выходит только одна дуга. На количество дуг, входящих в узлы и выходящих из них, ограничений нет. На рисунке 1 приведен пример транслирующей синтаксической диаграммы.
Рисунок 1 — Пример транслирующей синтаксической диаграммы.
Программа «Редактор синтаксических диаграмм» позволяет строить синтаксические диаграммы, которые соответствуют приведенному выше описанию. Пример диаграммы, построенной в данной программе, представлен на рисунке 2. Программа обладает множеством функций и возможностей. Главное меню содержит следующие пункты:
1) Изменить список нетерминалов;
2) Изменить список терминалов;
3) Создать диаграмму нетерминала;
4) Сформировать выходной файл;
Рисунок 2 — Пример диаграммы, построенной в данной программе.
Интерфейс программы приведен на рисунке 3. Рабочая область программы разделена на три части — это панель инструментов, панель редактирования, панель параметров.
Рисунок 3 — Интерфейс программы.
После запуска программы для построения диаграммы необходимо задать список терминалов и нетерминалов. Затем выбрать пункт меню «Создать диаграмму нетерминала». Появится новая вкладка с окном редактирования.
В левой части рабочей области программы расположена панель инструментов, каждый из которых обозначен небольшой картинкой-пиктограммой. Соединительная прямая линия изображена прямой стрелкой, соединительная ломаная линия — ломаной стрелкой, терминал — прямоугольником, нетерминал — овалом, действие — ромбом, узел — точкой, функция удаления — корзиной. Назначение инструментов следующее:
1) Соединительная прямая линия. Позволяет соединить терминал и узел, нетерминал и узел, нетерминал и действие, терминал и действие. Для соединения двух объектов необходимо последовательно нажать на эти объекты левой кнопкой мыши.
2) Соединительная ломаная линия. Позволяет соединить те же объекты что и прямая линия, но имеет точки перелома, количество которых задает пользователь. Для соединения объектов ломанной линией необходимо последовательно нажать объект из которого выходит линия, затем точки перелома линии и объект, в который входит линия.
3) Терминал. Позволяет добавить на панель редактирования объект терминал и задать его название из списка терминалов.
4) Нетерминал. Позволяет добавить на панель редактирования объект нетерминал и задать его название из списка нетерминалов.
5) Действие. Позволяет добавить на панель редактирования объект действие (процедуру, которую следует выполнить при трансляции).
6) Узел. Позволяет добавить на панель редактирования объект узел и задать тип узла (начальный, промежуточный, допускающий). Узлы разных типов отличаются цветом. Начальный узел — синего цвета, промежуточный — черного, допускающий — красного.
7) Удаление объекта. Позволяет удалять любой объект, расположенный на панели редактирования. Для этого необходимо выбрать данный пункт, а затем выбрать объект, который необходимо удалить.
8) Включение/отключение сетки. Позволяет включить или отключить разлиновку панели редактирования. Эта возможность помогает в выравнивании объектов.
По центру расположена панель редактирования. Это и есть главное окно, в котором происходит построение синтаксической диаграммы. На эту панель перетаскиваются объекты из панели инструментов.
Справа находится панель инструментов, которая содержит три основных списка: список действий, список нетерминалов и список терминалов.
Кроме основных функций существуют еще и дополнительные, которые используются для редактирования уже созданной синтаксической диаграммы:
1) Перемещение объекта. Любой объект, расположенный на панели редактирования, можно перетаскивать, при этом все входящие и выходящие линии тоже перемещаются вместе с объектом.
2) Переименовать объект. Для переименования необходимо дважды кликнуть по объекту, после чего появится дополнительное окно, в котором пользователь вводит новое имя объекта и нажимает кнопку «Сохранить».
3) Изменить тип узла. После двойного клика по объекту появляется дополнительное окно, в котором можно выбрать новый тип узла и нажать кнопку «Сохранить». В этом случае узел меняет свой цвет.
Синтаксическая диаграмма каждого нетерминала располагается в отдельной вкладке.
Программа формирует выходной файл, который описывает структуру синтаксической диаграммы. Этот файл может быть использован в САПТ для необходимых преобразований синтаксической диаграммы и генерации транслятора.
Программное обеспечение «Редактор синтаксических диаграмм» реализовано на языке C# и представляет собой совокупность следующих модулей:
1) Node.cs — класс для узлов.
Свойства: point — координаты узла,
label — номер узла,
type — тип узла;
Методы: Node_Load() — добавление узла на панель редактирования,
Node_MouseDoubleClick() — событие при двойном клике по узлу,
Node_MouseMove() — перемещение узла,
2) Components.cs — класс терминалов и нетерминалов.
Свойства: point — координаты компонента,
type — тип (термин или нетерминал),
name — название компоненты;
Методы: Components _Load() — добавление компонента на панель
редактирования,
Components _MouseDoubleClick() — событие при двойном клике,
Components _MouseMove() — перемещение компонента;
3) Action.cs — класс действий.
Свойства: point — координаты действия,
Comp — компонент, после которого выполняется действие,
name — название действия;
Методы: Action _Load() — добавление действия на панель редактирования,
Action_MouseDoubleClick() — событие при двойном клике по действию,
Action _MouseMove() — перемещение действия,
4) Lines.cs — класс для линий.
Свойства: startPoint, endpoint — координаты начала и конца линии,
list — список переломных точек для ломаной линии,
startComp — компонент, из которого выходит линия,
endComp — компонент, в который входит линия.
MainModule.cs описывает логику работы программы, а также содержит реализацию ее интерфейса. В этом модуле описан класс формы mainForm, на которой размещены все основные компоненты для управления работой программы.
Таким образом, разработаны алгоритмы и программа для визуального представления синтаксических диаграмм, которая позволяет создавать, редактировать и представлять диаграммы в форме, удобной для дальнейшей обработки в САПТ.
Существуют следующие аналоги разработанного программного обеспечения: Railroad Diagram Generator, EBNF Visualizer, ANTLR. Разработанный программный продукт будет более предпочтительным, так как он имеет функциональность (например, графическое представление диаграммы, построение транслятора, авто-преобразование диаграмм и др.), которая есть у аналогов, а также поддерживает ряд возможностей (например, устранение конфликтов перехода при построении транслятора), которых нет ни в одном другом аналоге.
Рецензии:
12.09.2015, 7:34 Борисевич Алексей Валерьевич
Рецензия: Имея небольшой опыт разработки рекурсивных парсеров на основе Coco/R [4], лично мне предложенный подход представляется весьма продуктивным и интересным. Замечания:
1. Пожалуйста, проверьте отображение всех формул в статье (вместо операций над множиствами отображаются непонятные символы).
2. Существуют аналогичные решения, например, https://vll.java.net/. Наверное стоит упомянуть парочку и прокоментировать чем ваша разработка отличается от других.
3. Вы не думаете о развитии этой программы как open source? если так, то может стоит загрузить на github например и дать ссылку в статье?
В целом, после устранения замечаний 1 и 2, статью можно опубликовать.
22.09.2015, 14:23 Борисевич Алексей Валерьевич Отзыв: В исправленном виде статью можно опубликовать. Извините, что ответил не сразу. |