Статья опубликована в №25 (сентябрь) 2015
Разделы: Информационные технологии
Размещена 11.09.2015. Последняя правка: 13.09.2015.
Просмотров - 2672

ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ ВИЗУАЛЬНОГО ПРЕДСТАВЛЕНИЯ СИНТАКСИЧЕСКИХ ДИАГРАММ

Шахов Максим Владимирович

Бюджетные и Финансовые Технологии

Младший специалист

Рязанов Юрий Дмитриевич, доцент, БГТУ им. В.Г. Шухова

УДК 519.685.3

Развитие информационных технологий приводит к необходимости создания новых трансляторов языков программирования. Для этого в настоящее время широко используются системы автоматизированного построения трансляторов (САПТ) [1 — 4]. Эффективность использования САПТ определяется языком описания спецификации транслятора. Как правило, спецификация транслятора в этих системах представляется в нотации РБНФ или ее модификациях. Одним из удобных способов задания спецификации транслятора является транслирующая синтаксическая диаграмма, которая практически не используется в САПТ. Здесь дается формальное определение транслирующей синтаксической диаграммы и описывается разработанное программное средство — редактор синтаксических диаграмм, которое может быть использовано в САПТ.

Транслирующую синтаксическую диаграмму будем задавать четверкой

D = (T, N, S, А, G), где T — конечное множество терминалов; N — конечное множество нетерминалов; S`in` N — начальный нетерминал; А — конечное множество действий, G = (V, E) — ориентированный граф, где V = V_TV_NV_АV_uV_входV_выход,где V_вход — множество точек входа, |V_вход| = |N|;

V_T — множество терминальных вершин;

V_u — конечное множество узлов;

V_выход — множество точек выхода, |V_выход| = |N|;

E = E₁E₂E₃E₄E₅E₆, где

E₁{(a, b) | a`in` V_вход, b`in` V_u}— множество входных дуг;

E₂{(a, b) |a`in` V_u, b`in` V_выход} — множество выходных дуг;

E₃{(a, b) |a`in` V_u, b`in` V_TV_N} — множество дуг, выходящих из узлов;

E₄ {(a, b) |a`in` V_TV_NV_A, b`in` V_u} — множество дуг, входящих в узлы;

E₅{(a, b) | a`in` V_NV_T, b`in` V_A}— множество дуг входящих в вершину действие;

E₆{(a, b) |a`in` V_u,b`in` V_u} — множество ε-дуг, соединяющих узлы.

Каждому нетерминалу соответствует связная компонента графа. Компонента именуется соответствующим нетерминалом, имеет только одну точку входа и одну точку выхода и конечное множество вершин других типов. Точки входа и выхода на диаграмме компоненты не изображаются. Нетерминальная вершина изображается прямоугольником, в который вписан терминальный символ. Узел изображается на диаграмме жирной точкой. В точку входа не входит ни одна дуга и выходит конечное множество дуг (входные дуги компоненты). Узлы, в которые входят входные дуги, называются начальными. Из точки выхода не выходит ни одна дуга и входит конечное множество дуг (выходные дуги компоненты). Узлы, из которых выходят выходные дуги, называются заключительными. Каждая дуга, за исключением входных и выходных дуг, может выходить из узла и входить в терминальную или нетерминальную вершину или другой узел, выходить из терминальной, нетерминальной или вершины действия и входить в узел, либо выходить из терминальной или нетерминальной вершины и входить в вершину действие. В каждую терминальную, нетерминальную вершину и в вершину действия входит только одна дуга и выходит только одна дуга. На количество дуг, входящих в узлы и выходящих из них, ограничений нет. На рисунке 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. Разработанный программный продукт будет более предпочтительным, так как он имеет функциональность (например, графическое представление диаграммы, построение транслятора, авто-преобразование диаграмм и др.), которая есть у аналогов, а также поддерживает ряд возможностей (например, устранение конфликтов перехода при построении транслятора), которых нет ни в одном другом аналоге.  

1. ANTLR // [Электронный ресурс]. Режим доступа: // URL: http://www.antlr.org/
2. ASF+SDF.// [Электронный ресурс]. Режим доступа: // URL: http://www.cwi.nl/projects/MetaEnv/
3. Bison // [Электронный ресурс]. Режим доступа: // URL: http://www.gnu.org/software/bison/
4. Coco/R // [Электронный ресурс]. Режим доступа: // URL: http://www.ssw.uni-linz.ac.at/Research/Projects/Coco/

Рецензии:

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 Борисевич Алексей Валерьевич Отзыв: В исправленном виде статью можно опубликовать. Извините, что ответил не сразу.

Оставить комментарий