Семантическая модель программы и ее реализация

4. Олейник П.П., Игумнов Е.А., Свечкарёв Е.А. Реализация модуля рецензирования в информационной системе проведения научных конференций // Объектные системы - 2011: материалы III Международной научно-практической конференции (Ростов-на-Дону, 10-12 мая 2011 г.) / Под общ. ред. П.П. Олейника. - Ростов-на-Дону, 2011. - С. 26-29.

УДК 004.4’232+004.4’41

СЕМАНТИЧЕСКАЯ МОДЕЛЬ ПРОГРАММЫ И ЕЕ РЕАЛИЗАЦИЯ1

Лаптев Валерий Викторович, к.т.н., доцент, Астраханский государственный технический университет, Россия, Астрахань, laptev@ilabsltd.com

Грачев Дмитрий Александрович, аспирант, Астраханский государственный технический университет, Россия, Астрахань, dagrachev@list.ru

В работе [1] описан учебный язык программирования и реализация его интерпретатора в рамках интегрированной среды [2,3] для обучения программированию. Интегрированная среда строится вокруг редактора кода, который не является обычным текстовым редактором, а оперирует конструкциями языка программирования и объектами программы. Для реализации подобного подхода авторами разработана семантическая модель программы. В статье описана формальная семантическая модель, внутреннее представление модели в системе и ее реализация на языке C#.

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

Для определения формальной семантической модели программы нужно определить формальную семантическую модель оператора. В общем виде формальная семантическая модель оператора представляет собой пару:

имя = < параметры, правила >

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

В качестве примеров рассмотрим несколько формальных моделей простых и блочных операторов учебного языка [1]. Простыми операторами являются оператор импорта, операторы определения констант и переменных, операторы ввода и вывода, оператор присваивания и операторы вызова подпрограммы. К блочным операторам относятся оператор определения модуля, операторы определения подпрограмм, оператор цикла, условный оператор и оператор определения типа. Сначала опишем семантику оператора неформально, а затем приведем формальную модель.

Оператор определения переменной включает тип переменной и ее имя. Если тип переменной является простым (целый, вещественный, символ, булевский), то разрешается инициализировать переменную начальным значением. Инициализатор - это выражение, тип значения которого должен совпадать с типом переменной. Имя переменной не должно совпадать с ранее объявленными именами. Тип переменной должен быть либо

1 Статья рекомендована к опубликованию в журнале "Информационные технологии"

92

определенным в языке, либо определенным в программе. Таким образом, формальную модель оператора объявления переменной можно представить следующим образом:

variable =

< param = < type, name, value >,

rules = < ~(name e Names), (type e Types), if ~(value=null) then

>

>

В этой модели определены следующие элементы:

• variable - ключевое слово оператора определения переменной в английской нотации;

• param - параметры формальной модели оператора;

• rules - правила и условия;

Параметрами являются:

• type - тип переменной;

• name - имя переменной;

• value - инициализирующее выражение переменной.

Модель включает два логических выражения:

• ~(name е Names) - это выражение истинно при отсутствии имени определяемой переменной в множестве Names объявленных имен;

• (type е Types) - это выражение истинно, если тип переменной присутствует в множестве Types встроенных или определенных типов программы;

В модели определено одно условие, при истинности которого проверяется истинность вложенных выражений и условий:

if ~(value=null) then

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

является истинным, если тип переменной является простым.

Блочные операторы отличаются тем, что включают тело - последовательность операторов учебного языка, которую обозначим как P:

P = mi m2 ..., mk,

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

Определим множества S, элементами которых являются модели операторов, которые разрешается задавать в теле того или иного блочного оператора:

• Sexe = { instant, variable, let, input, output, call }

• Sdcl = { instant, variable, type, procedure, function }

• Simp = { import }

Множество Sexe включает операторы, которые разрешается задавать в теле операторов определения процедур, функций, методов, в секции инициализации модуля, в теле оператора цикла и условного оператора. Операторы объявления константы и переменной включены в это множество, поскольку с помощью них во время выполнения определяются локальные в блоке переменные и константы. С помощью множество Sdcl определяет состав операторов объявления, которые разрешается задавать в секции определения модуля. И множество Simp

93

определяет возможности конструирования последовательности операторов импорта. Тогда формальную модель оператора определения модуля можно задать таким образом:

module =

< param = < name, Pimp, Pdcl, Pexe > rules = < ~(name, ModuleNames),

>

>

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

Из моделей блочных операторов самой простой является модель оператора цикла:

while =

< param = < exp, P >

rules = < (type(exp)=boolean), (P e Sexe) >

>

Параметрами, очевидно, являются булевское выражение - условие цикла, и тело оператора. Более сложную модель имеет условный оператор, поскольку для условного оператора требуется определить еще модели вложенных ветвей else_if и else:

else if =

< param = < exp, P >

rules = < (type(exp)=boolean), (P e Sexe) >

>

else =

< param = < P >

rules = <(P e Sexe) >

>

Определим множество операторов, которые могут входить в тело условного:

Sif= Sexe U { else_if, else }

Тогда семантическая модель условного оператора определяется так:

if =

< param = < exp, P >

rules = < (type(exp)=boolean), (P e Sif), (last(P)=else) >

>

Третье семантическое правило устанавливает, что ветка else должна быть последней в теле.

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

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

94

Эту структуру строит редактор кода в соответствии с действиями программиста. При загрузке готового проекта строится такая же структура. Мы называем такое представление семантическим деревом программы.

Первоначально (в момент включения в проект первого модуля, в котором еще нет ни одного оператора) дерево состоит из одного специального пустого узла, который имеет внутренне имя NullOperator. Этот же узел представляет в дереве пустые строки, которые вставляются в программу для повышения читабельности. Обычно новый оператор вставляется в программу на месте некоторой пустой строки. В дереве эта операция представляет собой простую замену узла NullOperator на конкретный узел-оператор. Если вставляемый оператор является блочным, то на месте тела также вставляется NullOperator. Например, после вставки первого оператора модуль, дерево выглядит так, как показано на рис. 1 (показаны связи только вперед).

Рис. 1 - Семантическое дерево при вставке первого оператора модуль

Дочерняя вершина узла модуль - это тело секции определений, а дочерний узел вершины начало - это тело секции инициализации. Эти пустые узлы будут заменены на конкретные узлы-операторы при вставке. В качестве примера приведем простую программу, вычисляющую все факториалы от 1 до N.

#Вычисление факториалов#

модуль Факториал

подключить Математика;

закр процедура(входной целое х) Факт переменная-целое К; переменная-целое тФакт; присвоить тФакт := 1; присвоить К := 1; пока К <= х повторять вывести тФакт; вывести '\n'; присвоить К := К + 1; присвоить тФакт := тФакт * К; конец цикла; конец Факт;

начало

вызвать Факт(15);

конец Факториал.

#Конец модуля вычисления факториалов#

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

Решение о явном представлении программы в виде семантического дерева привело к важным последствиям при реализации интегрированной среды Semantic IDE [2,3]. Во-первых, регулярная структура семантического дерева делает алгоритм обхода [1] тривиальным. Во-вторых, ошибки выявляются в редакторе, поэтому на вход интерпретатора

95

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

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

И наконец, явное отделение внутреннего представления программы от внешнего позволило реализовать идею сменяемого синтаксиса во внешнем представлении [2,3]. Фундаментом реализации семантического дерева является паттерн Наблюдатель

96

[4]. Как известно, в этом паттерне устанавливаются отношения между субъектом и наблюдателем. Субъект хранит у себя список наблюдателей, которых оповещает при каких-либо изменениях в своем состоянии.

В рамках данной реализации субъект наблюдения реализуется абстрактным классом SemanticSubject, который является корнем обширной иерархии классов, часть которой показана на рис. 3. Символом <<A>> помечены абстрактные классы. В этой иерархии определены все классы-операторы, которые, как и операторы учебного языка, делятся на два вида: однострочные (простые) и многострочные (блочные). Помимо операторов в иерархию семантических объектов включены элементы операторов, которые сами имеют сложную структуру: выражения, список параметров процедур-функций-методов, не элементарные типы. Как правило, эти элементы операторов разрешено редактировать в составе оператора.

Семантическое дерево, элементами которого являются объекты-операторы, реализуется отдельным классом SemanticTree. В абстрактном классе SemanticOperator (см. на рис. 3 класс Оператор) определены все необходимые поля-ссылки.

Множество классов-наблюдателей, составляющих иерархию классов-блоков с базовым абстрактным классом Block, реализуют интерфейс ISemanticObserver. Все эти классы так или иначе связаны с отображением семантического дерева в окне редактора. Сам редактор, реализуемый классам Editor, тоже является наблюдателем. Паттерн Наблюдатель используется еще в некоторых случаях, в частности, для наблюдения за курсором.

Рис. 3 - Иерархия классов субъекта наблюдения

Помимо паттерна Наблюдатель в реализации широко применяется паттерн Команда [4] (Command). В Semantic IDE определен классический базовый абстрактный класс Command с методами Execute() и Undo(). Посредством паттерна Компоновщик (Composite) реализован классический класс MacroCommand, определяющий составную команду. Такой подход позволил определить наборы базовых команд для различных объектов модели, а уже из них компоновать более сложные составные команды. Например, базовые команды определены для выражения, списка параметров, модуля, семантического дерева, слова и т.п. В системе реализован класс CommandHistory для хранения истории выполненных команд.

97

Команды IDE составляют отдельную иерархию с базовым абстрактным классом IDECommand, но тоже скомпонованы по «тематическим» группам. Например, все команды для работы с проектом собраны в одну группу. Для хранения команд IDE реализован классический стек команд с методами Undo() и Redo().

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

Литература

1. Грачёв А.Д., Лаптев В.В. Разработка учебного языка программирования и интерпретатора для обучающей среды // Объектные системы-2012: материалы VI Международной научнопрактической конференции (Ростов-на-Дону, 10-12 мая 2012г.) / Под общ. ред. П.П. Олейника. - Ростов-на-Дону: ШИ ЮРГТУ (НПИ), 2012. - 110 с., с. 92-101.

2. Грачёв А.Д., Лаптев В.В. Интегрированная среда для обучения программированию //

Объектные системы - 2013: Материалы VII Международной научно-практической

конференции (Ростов-на-Дону, 10-12 мая 2013 г.) / Под общ. ред. П.П. Олейника. - Ростов-на-Дону: ШИ (ф) ЮРГТУ (НПИ), 2013. - 118 c., с.17-24

3. Грачёв А.Д., Лаптев В.В. Семантическая интегрированная среда для обучения программированию // Педагогическая информатика. - 2013, №2. - с. 71-81.

4. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. - Спб.: Питер, 2001. - 368 с.

98

Шахтинский институт (филиал) федерального государственного бюджетного образовательного учреждения высшего профессионального образования "Южно-Российский государственный политехнический университет (НПИ) имени М.И. Платова"

Донской государственный технический университет Институт сферы обслуживания и предпринимательства (филиал) ДГТУ в г.Шахты

IX Международная научно-практическая конференция

Подробную информацию о конференции можно найти на официальном сайте www.objectsystems.ru

ОБЪЕКТНЫЕ СИСТЕМЫ - 2015

pumiiru

Информационные партнёры конференции:

Сообщество системных аналитиков

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

Ежемесячный теоретический и прикладной научно-технический журнал

Теоретический и прикладной научнотехнический журнал "Информационные технологии"

с ежемесячным приложением

АВТОМАТИЗАЦИЯ

Ежемесячный научно-технический и производственный журнал "Автоматизация в промышленности"

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ

Журнал "Информационные технологии и вычислительные

системы"

10-12 мая 2015 г , Россия, Ростов-на-Дону

Статьи сборников конференции индексируются в РИНЦ http://elibrary.ru/title about.asp?id=48777

Конференция посвящена принципам проектирования, реализации и сопровождения объектных систем и включает в себя обсуждение широкого круга проблем. В организации и работе конференции принимают участие как известные учёные, так и крупные специалисты в области разработки корпоративных информационных систем, представители ВУЗов и коммерческих организаций России, ближнего и дальнего зарубежья (Греции, Польши, Испании). Конференция является заочной. По окончании работы конференции публикуется

99