Автоматный метод определения проблемно-ориентированных языков (часть 1) Текст научной статьи по специальности «Компьютерные и информационные науки»

Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Новиков Ф. A., Тихонова У. Н.

Описывается новый метод определения синтаксиса и семантики проблемно-ориентированных языков с помощью диаграмм классов и диаграмм автоматов.

Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Новиков Ф. A., Тихонова У. Н.

An automata based method for domain specific languages definition (Part 1)

A new method for domain specific language definition is proposed. The method allows to define both syntax and semantics with class and state machine diagrams.

Текст научной работы на тему «Автоматный метод определения проблемно-ориентированных языков (часть 1)»

АВТОМАТНЫЙ МЕТОД ОПРЕДЕЛЕНИЯ ПРОБЛЕМНО-ОРИЕНТИРОВАННЫХ ЯЗЫКОВ (Часть 1)

канд. физ.-мат. наук, заведующий лабораторией астрономического программирования Институт прикладной астрономии РАН У. Н. Тихонова, аспирант

Санкт-Петербургский государственный политехнический университет

Описывается новый метод определения синтаксиса и семантики проблемно-ориентированных языков с помощью диаграмм классов и диаграмм автоматов.

Ключевые слова — проблемно-ориентированный язык, абстрактный синтаксис, метамодель, автоматное программирование.

Создание прикладного программного обеспечения — это сложный процесс. Наиболее критичной его частью является непосредственно программирование приложения, так как на этом этапе осуществляется мысленное отображение понятий прикладной предметной области в используемый язык программирования, что требует знания как языка предметной области, так и языка программирования. Прикладное программирование может быть упрощено с помощью проблемно-ориентированных языков (языки предметной области, domain-specific languages — DSL), которые позволяют формулировать решение целевой задачи в терминах предметной области этой задачи, а не в терминах вычислительной машины. Такой подход облегчает разработку программ и повышает их качество.

Парадигма прикладного программирования, основанная на использовании проблемно-ориентированных языков, известна уже давно [1]. Основным препятствием для ее широкого применения является сложность создания новых проблемно-ориентированных языков и всего сопутствующего им программного обеспечения. Одной из технологий, разработанных в последнее время с целью устранить этот недостаток, является языковый инструментарий Meta Programming System (MPS) [2]. В его основе лежит постулат о том, что программа на проблемно-ориентированном языке — это любое точно определенное решение

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

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

Первым методом определения языков программирования, в котором последовательно проведено разделение абстрактного и конкретного синтаксисов, является Венский метод [3]. Именно в Венском методе показано, что при определении семантики языка необходимо и достаточно опираться на абстрактный синтаксис языка. Кроме того, в Венском методе предложен оригинальный подход к определению семантики языка, основанный на интерпретирующих автоматах.

Традиционным способом описания синтаксиса языка являются формальные грамматики. Правила формальной грамматики некоторого

языка могут быть сведены к автомату, распознающему этот язык [4]. Этот подход позволяет определить конкретный синтаксис, в том числе и нетекстовый, с помощью системы автоматов [5].

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

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

Назначение и область применения метода

Чтобы достичь практических преимуществ решения прикладных задач с помощью проблемно-ориентированных языков, необходимо облегчить создание новых языков, модификацию уже существующих, поддержку и развитие диалектов. В предлагаемом методе эта возможность достигается за счет полного формального определения языка, исчерпывающим образом определяющего интерпретацию как вычислительной машиной (исполнителем языка), так и человеком (пользователем языка), что также немаловажно для распространения и использования нового языка.

Автоматный метод определения проблемноориентированных языков позволяет задать язык в виде трех составляющих: метамодели языка (включающей абстрактный синтаксис), конкретного синтаксиса (или набора конкретных синтаксисов) и операционной семантики. При этом мы используем в качестве средства описания всех трех составляющих стандартный унифицированный язык моделирования UML [6]: абстрактный синтаксис и метамодель языка описываются с помощью диаграммы классов, конкретный синтаксис и семантика — с помощью специализированных диаграмм автомата. Новые языки можно определять, используя уже разработанные модели. Таким образом, предлагаемый метод поощряет повторное использование моделей.

Мы разделяем взгляды С. Дмитриева [2] и М. Фаулера [1] на понятие программы: программой является абстрактная структура, а для ее редактирования, хранения и выполнения могут использоваться различные представления — в виде

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

Охарактеризуем более точно область применения метода. Мы рассматриваем язык, в том числе проблемно-ориентированный, с самой общей точки зрения — как знаковую систему для передачи информации. Знаки могут иметь различное представление: буквы некоторого алфавита, или графические фигуры на диаграмме, или элементы управления (кнопки) на форме графического интерфейса, или звуковые сигналы, или что угодно. Более того, мы считаем, что один знак может иметь несколько различных представлений, и даже в рамках одного языка. Множество знаков предполагается конечным и заранее заданным так, что знаки однозначно различимы в любом представлении. Таким образом, в автоматном методе предполагается зафиксированным конечный алфавит имен абстрактных знаков.

Зафиксировав природу знаков, необходимо определить, каковы рассматриваемые знаковые системы, т. е. как можно комбинировать абстрактные знаки или, другими словами, какие абстрактные структуры допустимы в определяемых языках. Классический подход, ориентированный на формальные языки, представленные текстами, или на естественные языки, представленные живой речью, фактически рассматривает один тип структур — конечные последовательности знаков (линейно упорядоченные мультимножества). Это, разумеется, самый распространенный тип структур, более того, конечные структуры любой другой природы можно представить (закодировать) последовательностями. Однако такое «вытягивание» нелинейной структуры в линейное представление может быть не вполне удобным в некоторых случаях, навязывая искусственный линейный порядок, которого в абстрактной структуре на самом деле нет, и маскируя нелинейную структуру в линейном коде. В автоматном методе мы допускаем не только линейные структуры, но и ориентированные деревья, и (более общий случай) ориентированные графы с одним источником. Таким образом, предлагаемый метод имеет весьма широкую область применения.

Автоматный метод состоит из четырех шагов:

1) определение абстрактного синтаксиса как иерархической композиции конструкций языка;

2) определение метамодели как абстрактного синтаксиса, дополненного системой неиерархических отношений между конструкциями языка;

3) определение конкретного синтаксиса как распознавателя, конструирующего абстрактную программу по ее представлению;

4) определение операционной семантики как интерпретатора абстрактных программ.

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

Определение абстрактного синтаксиса диаграммой классов

В предлагаемом автоматном методе определения языков в центр ставится описание абстрактной структуры предложений языка, которое обычно называют абстрактным синтаксисом языка. При использовании классического метода определения языков с помощью порождающих формальных грамматик абстрактный синтаксис обычно не описывается отдельно, но извлекается из правил вывода формальной грамматики. А именно, структурные единицы обозначаются нетерминальными символами и определяются правилами вывода. В результате применения правил вывода происходит последовательное уточнение, разворачивание определения начальной структурной единицы языка — его аксиомы. Различные последовательности таких уточнений порождают различные предложения (строго говоря, деревья вывода). Предложение на языке является частным случаем применения синтаксических правил языка, а значит экземпляром структуры, определяемой правилами абстрактного синтаксиса. При этом экземпляр структуры содержит только абстрактные знаки, тогда как в предложении на языке присутствуют еще и терминальные символы, используемые для обозначения структуры (скобки, запятые и т. д.). Очевидно, что в абстрактном синтаксисе, описывающем структуру предложений языка, эти терминальные символы не определяются. Они входят в определение конкретного синтаксиса языка [3].

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

скими отношениями метамодели, рассматриваемыми далее.

В предлагаемом автоматном методе для описания абстрактного синтаксиса правила порождения не используются. Мы описываем структуру языка явным образом, а именно абстрактный синтаксис языка определяем с помощью диаграмм классов (А, В и С на рис. 1 обозначают некоторые конструкции, в частности абстрактные знаки).

• Абстрактные знаки языка и их комбинации — конструкции языка — описываются в виде классов. При использовании порождающих формальных грамматик им соответствуют терминалы и нетерминалы.

• Определение конструкции языка через ее составляющие производится с помощью отношения композиции. При этом мы понимаем под композицией классов отношение типа «часть-целое» с наложенным на него ограничением альтернативной декомпозиции: в каждом экземпляре отношения композиции экземпляр конструкции А включается либо в экземпляр конструкции В, либо в экземпляр конструкции С, но не в оба вместе (см. рис. 1, слева). На языке порождающих формальных грамматик альтернативная декомпозиция соответствует паре правил В ::= А и С ::= А, где в каждом конкретном случае порождение может пойти только по одному пути.

• Обязательные составляющие некоторой конструкции, включенные в нее по отношению композиции, при реализации в совокупности образуют одно целое. Такую композицию мы называем конъюнктивной: в конструкцию А включаются и конструкция В, и конструкция С (см. рис. 1, в центре). На языке порождающих формальных грамматик конъюнктивной композиции соответствует правило А ::= ВС. Заметим, что конъюнктивная композиция в нашем варианте задания абстрактного синтаксиса, в отличие от задания правилами грамматики, не предписывает упорядоченности составных частей.

• Альтернативное определение конструкции языка может осуществляться с помощью дизъюнктивной композиции: в конструкцию А включается конструкция В или конструкция С, но не обе вместе (см. рис. 1, справа). На языке порождающих формальных грамматик это соответствует правилу А ::= В | С.

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

■ Рис. 1. Правила композиции

ствовать, по крайней мере, одно вхождение дизъюнктивной композиции, позволяющее завершить рекурсию [соответствующий пример см. ниже, (рис. 7)]. Нетрудно показать, что введенные правила позволяют описывать языки, реализациями (экземплярами) абстрактного синтаксиса которых являются корневые деревья.

Кроме перечисленных выше элементов диаграммы классов UML, мы используем свойства отношения композиции: кратность, роль и ограничения полюса [6]. Эти выразительные средства диаграммы классов имеют аналоги в известных методах определения абстрактного синтаксиса языка. Роль полюса отношения композиции соответствует селектору [3, 7]. С помощью кратности полюса можно определять необязательные элементы отношений (например, с помощью кратности вида 0..1) и так называемые серийные компоненты [7]. Ограничения позволяют наложить некоторые контекстные условия.

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