ЯЗЫКИ И СИСТЕМЫ ПРОГРАММИРОВАНИЯ
УДК 681.3.06
МЕТОДЫ И СРЕДСТВА ТРАНСЛЯЦИИ ГРАФИЧЕСКИХ
ДИАГРАММ
© 2011 г. О.Г. Шаров, А.Н. Афанасьев Ульяновский государственный технический университет, 432027 г. Ульяновск, ул. Северный Венец, 32 E-mail: oleg@sharov.name Поступила в редакцию 21.10.2010 г.
Большинство синтаксически формальных графических языков не являются семантически формальными. Такие языки гибки за счет неполноты или неформальности их описания, и, как следствие, результирующие диаграммы можно интерпретировать неоднозначно. Кроме этого, гибкость языка может привести к возникновению семейства языков, т.е. множества языков, которые концептуально имеют общую базу, но различную интерпретацию, специфичную для предметной области их применения. Авторы предлагают еще один подход к семантической формализации графических языков и обобщению однородных графических языков.
1. СЕМАНТИКА ГРАФИЧЕСКИХ ЯЗЫКОВ
В работе [1] определены три типа формальности графических языков.
1. Формальные. Синтаксис и семантики таких языков формально определены.
2. Полуформальные. Синтаксис языка формален, а семантика может иметь разные интерпретации.
3. Неформальные. Синтаксис и семантика языка неформальны.
Там же представлено пространственное расположение графических языков в плоскостях формальности и специализированности (языки общего назначения и специализированные языки). Подавляющее большинство популярных графических языков, таких как UML, SDL, FDB, являются полуформальными. Нужны методы и инструменты их семантический формализации. Большинство исследователей предлагают придавать семантическую формальность языкам следующими методами.
1. Специализировать язык. Отказаться от некоторых возможностей языка, упростить
его, наделить новыми возможностями и т.п., что положительно повлияет на формализацию.
2. Определять семантику динамически. Динамическая семантика предполагает трансформацию диаграмм базового графического языка в некий целевой язык.
В методах предлагаются противоположные подходы, но они могут быть взаимодополняющими.
В первом случае это - сужение исходного определения языка, приведение его к состоянию, когда неоднозначность исчезает. Метод эффективен, когда необходимо реализовать узкоспециализированное, малобюджетное инструментальное средство для автоматизации процесса проектирования, программирования и т.п.
Во втором случае предлагается расшифровать эту неоднозначность и не изменять язык. Этот метод более перспективен, поскольку дает возможность на базе одного универсального инструментального средства реализовывать диаграммы различных графических языков. Метод развивает идеи библиотек примитивов. Однако в данном случае в библиотеках хра-
нятся не новые графические образы, а их интерпретация (отображение) в терминах целевого графического либо текстового языка. Причем может быть несколько интерпретаций для одного и того же графического образа, каждой из них назначается уникальное имя во избежание неоднозначного толкования и некорректного использования. В качестве целевого языка выбирают более формальный язык относительно базового.
Очевидно, что для любого из методов семантической формализации ставится цель - создание достаточных условий для получения семантического значения диаграммы графического языка. В свою очередь, конечный формат представления семантического значения и метод его получения определяются типом семантики.
Для графических языков выделяют следующие типы семантик.
• Денотационная семантика. Трансформация графической диаграммы в семантические домены (денотаты) есть процесс получения денотационной семантики. Денотаты рассматриваются как идеализированные математические объекты, моделирующие (представляющие) другие объекты. Для графических языков в качестве семантических доменов (денотатов) выбирают формальные языки: сети Петри [1], CSP (Communicating Sequential Processes) [2].
• Операционная семантика. Смысл графической диаграммы задается посредством описания процессов ее исполнения. Определение операционной семантики подразумевает получение из графической диаграммы отображения в терминах некоторой абстрактной вычислительной машины и правил выполнения этого отображения на ней. Отображением может являться исходный код на каком-либо языке программирования, набор математических формул, специализированная алгебра и т.п.
• Аксиоматическая семантика. Сосредотачивает внимание на выборе и исследовании постулатов (аксиом и правил вывода), которые обеспечивают универсум для рассуждения о программах.
• Алгебраическая семантика. Рассматривается как ветвь денотационной семантики, существенно привлекающая алгебраические понятия и методы.
Авторы рассматривают денотационную и операционную семантики и предлагают для их реализации метод трансляции графических диаграмм в более формальную (графическую или текстовую) форму.
2. МЕТОДЫ ТРАНСЛЯЦИИ ГРАФИЧЕСКИХ ДИАГРАММ
Метод базируется на БУТ-грамматике, транслирующей грамматике, позволяющей производить синтаксически-ориентированную трансляцию диаграмм графического языка в текстовые и графические формальные описания с целью последующего анализа семантической корректности диаграммы. Для повышения эффективности реализации инструментальных средств на базе БУТ-грамматики вводится два типа БУТ-грамматик.
1. БУТ^грамматика. Грамматика, для которой целевым является текстовое формальное описание (программы на языке программирования, текст на специализированном языке разметки и т.п.).
2. RУTg-грамматика. Грамматика, позволяющая формировать выходные цепочки в терминах графических языков.
БУТ-грамматика является развитием БУ-грамматики [4, 5]. В данном развитии продукции схемы грамматики расширены для хранения в них соответствия в терминах целевого формального описания, а внутренняя память содержит информацию, необходимую для процесса трансляции.
2.1. Определение ИУТЬ-грамматики.
БУТ^грамматикой языка Ь (О) называется упорядоченная семерка непустых множеств С = (У,и, Е, Е,М, Я, го), где
• V = [ие, е = 1, Ь} - алфавит операций над внутренней памятью базового языка;
МЕТОДЫ И СРЕДСТВА ТРАНСЛЯЦИИ ГРАФИЧЕСКИХ ДИАГРАММ
67
и = {ие, е = 1 , К} - алфавит операций над внутренней памятью, используемый целевым языком;
£ = {а^, £ = 1,Т} - терминальный алфавит графического языка, являющийся объединением множеств его графических объектов и связей (множество примитивов графического языка);
• £ = £ = 1 ,Т} - квазитерминальный алфавит, являющийся расширением терминального алфавита. Алфавит £ включает:
- квазитермы графических объектов,
- квазитермы графических объектов имеющих более одного входа,
- квазитермы связей-меток с определенными для них семантическими различиями,
- квазитерм, определяющий отсутствие связей-меток;
• М = ТТ и ТЫ - объединение алфавитов терминальных (ТТ) и нетерминальных (ТЫ) символов целевого языка;
• Я = {тг, г = 0,1} - схема грамматики О (множество имен комплексов продукций, причем каждый комплекс т состоит из подмножества Рц продукций
тг = {Р,-, 3 = и});
• то € Я - аксиома БУТ1-грамматики (имя начального комплекса продукций), Тк € Я -заключительный комплекс продукций.
Множества V, £, £, Я, то наследуются от БУ-грамматики и используются для определения синтаксический корректности анализируемой диаграммы.
Множества и, М необходимы для придания грамматике транслирующих функций. Именно они и создают новый формализм, расширяя БУ-грамматику.
Продукция Рц € тг имеет вид
р . ~ (71, ..., (71, ..., Тп\ х
Рг] • £ ' Тm{X},
где
• (71, ..., тп) - п-арное отношение, определяющее вид операции над внутренней памятью в зависимости от V € {0,1, 2, 3};
• - оператор модификации, определенным образом изменяющий вид операции над памятью базового (целевого) языка, причем ^ € {0,1, 2};
• тт € Я - имя комплекса продукции-преемника;
• х - отображение квазитерма в терминах целевого языка (набор символов т € М).
Методика построения БУ-грамматики [4, 5] для БУТ1-грамматики расширяется на фазе синтеза следующими этапами:
• определение отображения квазитерма в терминах целевого языка для каждой продукции, т.к. один и тот же квазитерм в зависимости от контекста может интерпретироваться разным набором символов целевого языка;
• определение операций над внутренней памятью для элементов целевого языка.
На этапе анализа грамматики устранение недетерминированности и неопределенности производится аналогично соответствующим операциям БУ-грамматики. А вот задача минимизации грамматики претерпевает некоторые изменения и для БУТ-грамматики осуществляется как циклическое применение двух типов минимизаций:
• минимизация количества состояний;
• минимизация отображений.
Этап минимизации количества состояний соответствует этапу минимизации БУ-грам-матики. Однако в данном случае эквивалентными состояниями считаются состояния, у которых, кроме одинаковых продолжений распознаваемой цепочки справа и операций над внутренней памятью, одинаковыми являются транслирующие операции над внутренней памятью и отображения в терминах целевого
языка. Сама процедура минимизации остается неизменной.
Минимизация отображений предполагает поиск и свертку эквивалентных цепочек символов терминального и нетерминального алфавитов целевого языка. Более развернуто эту процедуру можно описать как последовательность следующих действий:
1) выделение эквивалентных фрагментов (цепочек или подцепочек) отображений и назначение каждому классу эквивалентности нового нетерминального символа;
2) замена эквивалентных фрагментов соответствующими нетерминальными символами.
В качестве возможных эквивалентных фрагментов могут использоваться цепочки, не содержащие символов, для которых необходимо применять операции над внутренней памятью.
2.2. Специфика трансляции в текстовый целевой язык
Специфика трансляции в текстовый целевой язык состоит в том, что символы результирующей цепочки должны быть выстроены в определенной последовательности. Сложности преобразования появляются для случаев разнородности базового и целевого языков. Если не получается средствами грамматики определить требуемое соответствие, то для решения п
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.