Программные продукты и системы

Традиционно анализ, распараллеливание и преобразования программ выполняются над программами, представленными не на языках программирования высокого уровня, а посредством различных схем и моделей, которые являются удобным представлением для обработки исходных программ (например, схемы Мартынюка, Лаврова, представления программ в виде различных графов) и подробно описаны (см., напр.: В.В. Воеводин, Вл.В. Воевоедин “Параллельные вычисления” (2002); В.Н. Касьянов “Оптимизирующие преобразования программ”(1988)).

Внутренние представления в системах оптимизации и распараллеливания программ, как правило, реализуются в виде таких структур, как списки, деревья, графы. В некоторых системах (например, Polaris, SUIF/SUIF2, открытая распараллеливающая система (ОРС)) внутреннее представление программ реализовано в виде иерархии классов на объектно-ориентированном языке. Основное преимущество представления в таком виде – это простота проектирования, модифицируемость и расширяемость.

ОРС предполагает открытость к возможным изменениям в языке исходных текстов за счет дописывания или замены относительно небольших программ.

Многие системы для построения внутреннего представления программ, в том числе и ОРС, SUIF/SUIF2, используют внешние программы или библиотеки (ANTLR, Sage++, Bison, YACC, компиляторы Portland Group Inc.) с готовыми грамматиками языков, что ставит их в зависимость от сторонних разработчиков. При описании же собственных грамматик данные инструментальные средства, как правило, накладывают ограничения на их класс. Кроме того, приходится проводить определенную работу по интеграции представления программ, получаемых компиляторами переднего плана, основанными на таких инструментальных средствах, и собственными внутренними представлениями.

Таким образом, во многих системах возможности расширения на предмет добавления поддержки новых языков ограничены отсутствием собственного синтаксического анализатора (SUIF/SUIF2, Cetus) или ориентированностью их внутреннего представления программ на конкретный язык (Polaris, Parafrase).

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

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

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

В отделе интеллектуальных систем ИАПУ ДВО РАН (г. Владивосток) разрабатывается система преобразований программ (СПП), предназначенная для проведения исследований в области преобразований программ. Одним из требований, предъявляемых к данной системе, является поддержка расширяемого набора языков программирования исходных текстов программ, которые затем должны переводиться в единое промежуточное представление. Исходя из данного требования, в рамках решения проблемы обеспечения многоязыковости в системе преобразований программ, управляемой знаниями, была предложена концепция подсистемы генерации единого внутреннего представления программ. Предлагаемый подход позволяет преодолеть упомянутые выше недостатки и ограничения, присутствующие в существующих системах преобразования и распараллеливания программ.

Концепция подсистемы генерацииединого внутреннего представления в СПП

Рассмотрим архитектуру подсистемы генерации единого внутреннего представления в контексте СПП (рис.1). Подсистема состоит из следующих компонент: редактор проекций языков программирования высокого уровня на единое представление, генератор единого представления программ и инструментальное средство, осуществляющее анализ и синтез текстов (АИСТ), разработанное в отделе интеллектуальных систем ИАПУ ДВО РАН. Подсистема управления, также являющаяся частью СПП, связывает эти компоненты друг с другом, осуществляя передачу информации и управления между ними.

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

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

Инструментальное средство АИСТ используется для осуществления процедуры синтаксического анализа текстов программ и формирования представления этих программ в абстрактном синтаксисе.

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

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

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

Программа в абстрактном синтаксисе – это программа, представленная в терминах онтологии языка программирования, не содержащая элементов конкретного синтаксиса.

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

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

В задачи, решаемые данным средством, входят следующие компоненты:

· обход дерева абстрактного синтаксиса программы и выделение понятий языка программирования, в терминах которого представлена программа;

· поиск нужного соответствия: для каждого понятия языка программирования из описания проекции выбирается то соответствие, которое описывает набор (возможно, пустой) элементов языка единого представления, сопоставленный данному понятию;

· интерпретация описания соответствия и, как результат интерпретации, если набор элементов не пуст, синтез описанной в этом соответствии конструкции языка единого представления.

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

Модель онтологии проекций языковпрограммирования на единое представление

В разрабатываемом подходе предлагается формально задавать проекции языков высокого уровня на единое представление программ. Под проекцией будем понимать отображение следующего вида: P: C→E, где C={concepts} – множество понятий языка программирования; E={elements} – множество элементов языка единого представления.

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

При описании использованы следующие обозначения языка спецификаций, который приведен в работе А.П. Ершова, В.В. Грушецкого «Метод описания алгоритмических языков, ориентированный на реализацию» (1977): объед – объединение; [а] – а не обязательно (может отсутствовать); = – определение понятия; : – раскрытие позиции, * – возможно неопределенный атрибут; сер – серийная компонента.

Язык описания проекций = (сер язык программирования : Описание проекции)

Описание: Язык описания проекций задает правила описания проекции заданного языка программирования на единое представление программ.

Описание проекции = (сер соответствие : Описание соответствия)

Описание: Описание проекции определяет множество соответствий понятий заданного языка программирования конструкциям языка единого представления программ.

Описание соответствия = (понятие языка программирования : СТРОК, конструкция языка единого представления : элементы языка единого представления)

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

Семантика: Для заданного понятия языка программирования интерпретировать описание структуры конструкции языка единого представления, представленное в данном соответствии.

Элементы языка единого представления = ([фрагменты : Набор фрагментов], [дуги управления: Набор дуг управления], [атрибуты : Набор атрибутов])

Описание: Конструкция языка единого представления состоит из наборов фрагментов, дуг управления и атрибутов, возможно, пустых.

Семантика: Создать конструкцию языка единого представления заданной структуры.

Набор фрагментов = (сер фрагмент : Фрагмент)

Фрагмент = объед (Выражение, Присваивание, Ввод, Вывод, …)

Описание: Набор фрагментов представляет собой множество имен классов фрагментов (они представлены компонентой Фрагмент), специфицированных в языке единого представления.

Семантика: Последовательно создать фрагменты, множество имен которых определяет компонента Набор фрагментов.

Набор дуг управления = (сер дуга управления : Дуга управления)

Описание: Набор дуг управления представляет собой множество дуг управления.

Дуга управления =

(

имя дуги : объед (Если, То, Иначе, Выражение_справа, Выражение_слева, …),

фрагмент-начало дуги : объед (Программный_блок, Условный_оператор, Цикл_с_шагом, Присваивание, …),

фрагмент-конец дуги : объед (Выражение, Цикл_с_предусловием, Ввод, Вывод, …)

)

Описание: Дуга управления представляет собой направленную дугу, которая характеризуется своим именем и соединяет два фрагмента. Началом дуги является фрагмент, определяемый селектором “фрагмент-начало дуги”, концом дуги – фрагмент, определяемый селектором “фрагмент-конец дуги”.

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

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

На рисунке 2 приведен пример описания соответствия между понятием языка программирования Паскаль “Оператор присваивания” и конструкцией языка единого представления. Данное описание выполнено в соответствии с представленной выше моделью онтологии.

В работе изложена концепция подсистемы генерации единого внутреннего представления программ на основе описаний проекций языков программирования высокого уровня на единое представление. Приведен фрагмент модели онтологии проекций языков программирования высокого уровня на единое представление и на примере продемонстрировано, каким образом на основе модели онтологии представляется фрагмент описания отдельной проекции. На основе предложенной концепции разработан прототип подсистемы генерации единого внутреннего представления программ в рамках системы преобразований программ в специализированном банке знаний о преобразованиях программ. Прототип реализован в среде программирования Java в среде разработки IntelliJ Idea с использованием ресурсов многоцелевого банка знаний (http://www.iacp.dvo.ru/es/ mpkbank).