Структурно-предикативная система построения внутреннего представления программ, ориентированного на оптимизацию и распараллеливание

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Введение

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

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

Существует большое количество моделей для представления программ, как чисто теоретических, так и широко применяемых на практике:

· постфиксная нотация;

· трехадресный код;

· синтаксическое дерево;

· другие граф-модели.

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

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

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

В 1980 году Ф. Перейрой и Д. Уорреном были описаны грамматики DCG (Definite Clause Grammars), относящиеся к классу логических грамматик. Сейчас эти грамматики неизменно включаются во все развитые системы программирования на языке Пролог. Эти грамматики в отличие от атрибутных грамматик, не требуют задания строгого порядка выполнения семантических правил. Однако построение семантической структуры программы с помощью DCG, как и в атрибутных грамматиках, нужно описывать в процедурном виде (на языке Пролог).

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

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

Для достижения поставленной цели решаются следующие задачи:

1. Создание программной реализации СП-грамматик, представления структурного графа и алгоритма унификации вершин структурного графа и термов.

2. Применение СП-грамматик для определения и построения внутреннего представления программ, написанных на процедурных языках, в виде структурного графа.

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

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

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

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

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

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

Апробация результатов работы. Основные результаты диссертационной работы докладывались и обсуждались на Всероссийской научной конференции “Научный сервис в сети Интернет: технологии параллельного программирования”, г. Новороссийск, 2006 г., на научно-методической конференции “Современные информационные технологии в образовании: Южный федеральный округ”, г. Ростов-на-Дону, 2006г., на научных семинарах кафедр ИВЭ и АДМ мехмата РГУ, на научно-исследовательском семинаре ЮГИНФО РГУ, 2006 г.

Публикации. По результатам выполненных исследований опубликовано 6 печатных работ, в том числе 2 в соавторстве. Из них 3 статьи в российском рецензируемом журнале, 1 статья в сборнике трудов аспирантов РГУ и 2 в тезисах докладов всероссийской и региональной конференций.

1. Обзор современного состояния исследований в области оптимизации и распараллеливания программ

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

Первый раздел данной главы, посвящен подходам к распараллеливанию программ. Рассматриваются 3 основных подхода: «ручное», автоматическое и полуавтоматическое распараллеливание.

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

Во втором разделе первой главы приводится обзор различных технологий параллельного программирования. Рассматриваются расширения традиционных языков Фортран и Си, такие как HPF (High Performance Fortran), Fortran-DVM, C-DVM, mpC, а также коммуникационные библиотеки и интерфейсы параллельного программирования MPI, OpenMP, PVM. Рассмотренные технологии позволяют использовать для написания программ традиционные последовательные языки, однако не избавляют программиста от необходимости перестроения алгоритмов для их эффективного выполнения на параллельных машинах.

Далее рассматривается альтернативный подход, связанный с использованием специализированных параллельных библиотек, таких как Aztec, ScaLAPACK, ATLAS, PARPACK, которые избавляют программистов от рутинной работы по написанию подпрограмм для решения стандартных задач численных методов и позволяют сконцентрироваться на предметной области.

При обзоре средств автоматического распараллеливания программ упоминаются такие системы, как PIPS, cемейство препроцессоров-векторизаторов KAP, VAST/Parallel. Данные системы в значительной степени могут облегчить и ускорить разработку параллельных программ, однако получить с их помощью эффективно работающие параллельные программы не всегда удается.

В заключение второй части первой главы приводится обзор средств создания и проектирования параллельных программ. Рассматриваются отечественные проекты Открытая распараллеливающая система (ОРС), системы V_Ray, ПРОГРЕСС, ТРАНСФОРМ, а также зарубежные системы Parafrase, Polaris, SUIF/SUIF2, PTOOL и другие. Хотя большинство из рассмотренных систем являются исследовательскими, в них используются более сложные методы исследования и преобразования программ, чем те, которые традиционно включаются в компиляторы или системы автоматического распараллеливания. Основной недостаток большинства из рассмотренных систем - это ограниченные возможности расширения. Во-первых, многие системы для построения внутреннего представления программ используют внешние программы или библиотеки (ANTLR, Sage++, Bison, YACC, компиляторы Portland Group Inc.) с готовыми грамматиками языков, что ставит их в зависимость от сторонних разработчиков. Во-вторых, внутреннее представление программ во многих системах ориентировано на конкретный язык, что может вызывать большие трудности при добавлении новых языков. В-третьих, отсутствует поддержка динамически подключаемых библиотек (модулей), вследствие чего для внесения изменений или добавления новых возможностей требуется перекомпиляция всей системы.

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

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

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

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

Определение: Структурным графом называется конечный ориентированный упорядоченный граф, удовлетворяющий следующим условиям:

1. Каждая вершина графа помечена либо объектом первичного сорта (ОПС), либо конструктором, либо переменной; сорт метки считается сортом вершины; две вершины не могут помечаться одной переменной.

2. Дуги графа соответствуют аргументам конструкторов, т.е. выходят только из вершин, помеченных n-местным конструктором, где n ? 0; если тип конструктора f: s1,…,sn > s, то из вершины f выходит n дуг и i_ая дуга входит в вершину vi сорта si (вершины v1,…,vn не обязательно различны). В этом случае вершину f можно обозначать f (v1,…,vn).

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

Таблица 1. Алгоритм унификации вершин структурного графа и термов

	Вершина графа	Подтерм	Результат
1.	f(v1,…,vn)	f(t1,…,tn)	Переход к последовательной унификации вершин v1 и термов t1, и т.д. При этом найденные на каждом шаге подстановки применяются ко всему терму.
2.	Объект первичного сорта или 0-местный конструктор	Тот же объект или конструктор	Унификация вершины успешно завершена
3.	Вершина	Та же вершина
4.	Вершина v сорта s, не являющаяся переменной	Переменная X сорта s	Все вхождения X заменяются на v; в графе вершины X и v отождествляются. При отождествлении вершин в графе они отождествляются и в терме.
5.	Переменная X сорта s	Вершина v того же сорта
6.	Переменная X сорта s	Переменная Y сорта s	Отождествление (переименование) всех вхождений этих переменных. В графе это может привести к отождествлению вершин X и Y.
7.	Переменная X сорта s	Терм T сорта s, не являющийся вершиной или переменной (X может входить в T)	Вершины дерева терма T и графа, помеченные ранее переменной X, отождествляются с корнем дерева терма T. Отождествляются и другие вершины полученного графа, помеченные одной переменной. Остальные вершины дерева, не являвшиеся вершинами графа, становятся новыми вершинами графа.
8.	В остальных случаях унификация невозможна.

Унификация вершин структурного графа и термов (обозначается бинарным оператором =@=) используется в правилах СП-грамматики для построения семантической структуры программы и навигации по ней.

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

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

Пример 1. В таблице 2 приводится описание атрибутной грамматики для построения семантической структуры арифметических выражений, содержащих операции `+' и `-'. В семантических правилах грамматики для создания узлов дерева используются функции mknode, mkleaf.

Таблица 2. Атрибутная грамматика для построения семантической структуры выражений

Правила грамматики (продукции)	Семантические правила
E > E1 + T	E.nptr := mknode(`+', E1.nptr, T.nptr)
E > E1 - T	E.nptr := mknode(`-', E1.nptr, T.nptr)
E > T	E.nptr := T.nptr
T > ( E )	T.nptr := E.nptr
T > id	T.nptr := mkleaf(id, id.entry)
T > num	T.nptr := mkleaf(num, num.val)

В результате синтаксического анализа по данной грамматике арифметического выражения a - 4 + c будет построена семантическая структура этого выражения (рис. 1).

Рис. 1. Семантическая структура выражения a - 4 + c

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

1: expr(E) --> term(E1),terms(E1,E).

2: term(Id) --> [id(Id)].

3: term(N) --> [num(N)].

4: term(E) --> "(",expr(E),")".

5: terms(E1,E) --> "+",term(E2),terms(plus(E1,E2),E).

6: terms(E1,E) --> "-",term(E2),terms(minus(E1,E2),E).

7: terms(E,E) --> "".

В таблице 3 описывается пошаговый анализ по СП-грамматике и построение семантической структуры выражения a - 4 + c.

Таблица 3. Пошаговое построение семантической структуры выражения

№	Вызов правила	Действия и результат
1	1: expr(E)
2	2: term(E1)	%Действия: E1 =@= a %Результат: %E1 = R0
3	6: terms(R0,E)	%Действия: E1 =@= R0 %Результат: %E1 = R0
4	3: term(E2)	%Действия: E2 =@= 4 %Результат: %E2 = R1
5	5: terms(minus(R0,R1),E)	%Действия: E1 =@= minus(R0,R1) %Результат: %E1 = R2
6	2: term(E2)	%Действия: E2 =@= c %Результат: %E2 = R3
7	7: terms(plus(R2,R3),E)	%Действия: E1 =@= plus(R2,R3), E =@= E1 %Результат: %E1 = R4 %E = R4

Второй раздел данной главы посвящен программной реализации СП-грамматик, состоящей из трех этапов:

1. выбор представления структурного графа;

2. реализация алгоритма унификации вершин структурного графа и термов;

3. разработка способа преобразования правил СП-грамматики в правила Пролога.

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

Таблица 4. Представление структурного графа

Вершина, помеченная	представлена записью в БД, в которой хранится
переменной	переменная
объектом первичного сорта	константа (атом, число, строка)
конструктором f(v1, v2, …, vn)	структура f(R1, R2, …, Rn) (Ri - ссылки)
конструктором [v1, v2, …, vn]	список [R1, R2, …, Rn] (Ri - ссылки)

Для представления вершин структурного графа будем использовать следующее обозначение:

R > V (R - ссылка, V - метка вершины)

или

R0 > R1 > ... > Rk > V (Ri - ссылки) в тех случаях, когда происходит отождествление вершин.

Пример 2. В таблице 5 описывается представление структурного графа, изображенного на рисунке 2.

Рис. 2. Структурный граф

Таблица 5. Представление структурного графа

Представление	Тип
R0 > f(R1, R2)	конструктор
R1 > [R3, R4]	конструктор
R2 > A	переменная
R3 > v	ОПС
R4 > 5	ОПС

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

На рисунке 3 изображена ситуация, когда унифицируется несколько вершин структурного графа (A и B - вершины переменные, V - вершина любого типа).

В результате унификации вершин:

A =@= B

B =@= V

структурный граф (рис. 3, а) должен быть перестроен, как показано на рисунке 3, b.

Рис. 3. Унификация нескольких вершин структурного графа

Для этого потребуется отыскать в графе все родительские вершины f1, f2, …, f6 по отношению к вершинам A и B, и заменить в них ссылки, так чтобы они ссылались на вершину V. При большом количестве вершин в графе поиск родительских вершин может занять много времени. Для ускорения поиска можно было бы для каждой вершины хранить обратные ссылки на родительские вершины. Однако такой подход требует использования дополнительной памяти.

Предлагается следующее решение этой проблемы.

Обозначим через Ri > Vi - вершину-переменную, а через Rj > Vj - вершину любого типа. Для отождествления этих двух вершин запишем в запись по ссылке Ri ссылку Rj. В результате отождествления из двух вершин получится одна, представленная в виде Ri > Rj > Vj. Чтобы получить метку такой вершины, представленной цепочкой ссылок, используется рекурсия.

Решение описанной выше ситуации изображено на рисунке 4.

Рис. 4. Перестроенный структурный граф после отождествления его вершин

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

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

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

Для преобразования СП-правил в правила Пролога необходимо:

1. Заменить в заголовке правила параметры Yi, помеченные унарным оператором , новыми переменными Xi.

2. Добавить в заголовок правила параметры R0 и Rz, где R0 - ссылка на начало входной цепочки лексем, Rz - ссылка на начало оставшейся части цепочки лексем после разбора (аналогичный приём используется при преобразовании правил грамматики DCG в правила Пролога).

3. В начало правой части правила для каждого помеченного параметра Yi вставить предикат унификации Xi =@= Yi вершины X и терма Y.

4. Заменить последовательности терминальных и нетерминальных символов, а также семантических процедур в соответствии с таблицей 6:

Таблица 6. Преобразование правил СП-грамматики в правила Пролога

Правило СП-грамматики	Правило Пролога
N(…,Y1,…,Y2,…,Ym,…) -->	N(…,X1,…,X2,…,Xm,…,R0,Rz) :-
	X1 =@= Y1, … Xm =@= Ym,
[E1|L1], N1(…),	cmp([E1|L1],R0,R1), N1(…,R1,R2),
…	…
Ni, [Ej|Lj], Ni+1(…),	Ni(…,Rf,Rf+1), cmp([Ej|Lj],Rf+1,Rf+2) Ni+1(…,Rf+2,Rf+3),
…	…
{Tr},	Tr,
…	…
Nk(…).	Nk(…,Rz-1,Rz).

Здесь предикат cmp(L, Ri, Rj) считывает лексемы из входного потока, начиная с лексемы Ri, и сравнивает их со списком терминальных символов L. Если сравнение проходит успешно, то предикат возвращает Rj - ссылку на следующую лексему для анализа.

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

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

Для возможности дальнейшего расширения внутреннего представления введен обобщенный конструктор для представления операторов программы:

stmnt(Label, Parent, Block, Prev, Next, Name, Args)

Аргументы:

Label - метка безусловного перехода на данный оператор.

Parent - оператор-родитель, т.е. оператор, под непосредственным

управлением которого находится данный.

Block - блок операторов, в котором находится данный оператор.

Prev, Next - предыдущий и следующий операторы в блоке (по месту

расположения в тексте программы).

Name - идентификатор оператора.

Args - список аргументов.

Пример 3. На рисунке 5 изображен структурный граф для фрагмента программы:

Id = Expr1;

L: if (Expr2)

Stmnt1;

else

Stmnt2;



Рис. 5. Структурный граф фрагмента программы

Для построения внутреннего представления программ и работы с ним используется процедура унификации вершин структурного графа и термов. Например, создать представление оператора присваивания n = n + (k - 1) можно следующим образом:

NewSt =@= stmnt(L,P,B,S1,S2,let,[n,plus(n,minus(k,1))])

В результате унификации будет построено дерево терма (рис. 6) stmnt(…), а в переменную NewSt будет записана ссылка на корень этого дерева - вершину-конструктор stmnt.

Рис. 6. Дерево терма

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

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

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

В алгоритме построения графа зависимостей по данным учитывается 4 вида зависимостей - истинная, антизависимость, выходная и входная. Для определения наличия и вида зависимости используются известные тесты: НОД и неравенства Банержи. Вершинами графа зависимостей по данным являются операторы программы. Дуга графа может содержать информацию о переменной, виде зависимости и носителях (уровнях) зависимости.

Вершинами в графе вызовов процедур являются программные единицы (главная программа, процедуры и функции), описанные в тексте программы.

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

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

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

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

Система позволяет:

1. Строить промежуточное представление программ, написанных на Си, Паскале и Фортране (используются ограниченные подмножества этих языков).

2. Для анализа программы строить управляющий граф, граф зависимостей по данным и граф вызовов.

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

4. Получить из внутреннего представления текст программы на Си.

Система состоит из следующих компонентов:

· ядро;

· дополнительные модули;

· интерфейс.

Ядро системы написано на языке Пролог в системе логического программирования Arity/Prolog32 и включает в себя:

· средства для работы со структурным графом;

· конвертер правил СП-грамматики в правила Пролога;

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

· вспомогательные предикаты.

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

· лексический анализатор;

· СП-грамматика исходного языка;

· средства анализа внутреннего представления;

· преобразования;

· средства визуализации внутреннего представления;

· генератор исходного кода;

· вспомогательные утилиты.

Интерфейс системы (рис. 7) реализован на Visual C++ в виде многооконного редактора, в котором можно создавать и редактировать тексты пользовательских программ и модулей системы (в том числе и СП-грамматик). Помимо текстов программ в главном окне могут отображаться:

· подключенные модули системы;

· внутреннее представление программы;

· отладочная информация.

Рис. 7. Интерфейс структурно-предикативной системы

предикативный компилятор алгоритм

Данная система является экспериментальной и, конечно, уступает по количеству преобразований, средствам анализа и визуализации таким системам, как SUIF/SUIF2, Polaris, ОРС, PIPS, V-Ray, которые разрабатываются уже на протяжении нескольких лет целыми группами разработчиков. Однако у этой системы есть ряд возможностей, которые могут оказаться полезными как для обычных пользователей, так и для разработчиков компиляторов.

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

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

В-третьих, управление модулями во время работы с системой происходит динамически. То есть пользователь может подключать, отключать или изменять дополнительные модули, не компилируя их и не выходя из системы. Это может быть полезным, например, при написании и отладке преобразований. В системе SUIF/SUIF2 имеется аналогичная возможность динамического подключения модулей, однако, модули должны быть откомпилированы.

В-четвертых, при работе с большими программами, анализ которых может занимать много времени, у пользователя есть возможность сохранения построенного внутреннего представления программы в файл. Таким образом, пользователь может продолжить свою работу с момента сохранения или открыть файл с внутренним представлением программы в интерпретаторе Arity/Prolog32 для пошаговой отладки модулей системы, например, средств анализа и преобразований. Из рассмотренных систем такой возможностью обладает только система SUIF/SUIF2.

Литература

Разработана программная реализация СП-грамматик, включающая в себя способ представления структурного графа, реализацию алгоритма унификации вершин структурного графа и термов, интерпретацию правил СП-грамматики.

Разработаны СП-грамматики для подмножеств языков Си, Паскаль и Фортран, ориентированные на построение внутреннего представления программ в виде структурного графа.

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

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

Литература

Крицкий С. П., Тапкинов Б. Ю. Реализация оптимизирующих преобразований программ с помощью структурных предикативных грамматик // Приложение к журналу «Известия вузов. Северо-Кавказский регион. Естественные науки», 2006, № 1, С. 3_13.

Крицкий С. П., Тапкинов Б. Ю. Система построения оптимизирующих и распараллеливающих компиляторов // Приложение к журналу «Известия вузов. Северо-Кавказский регион. Естественные науки», 2006, № 9, С. 24-28.

Тапкинов Б. Ю. Преобразование правил структурной предикативной грамматики в правила DC-грамматики // Труды аспирантов и соискателей Ростовского государственного университета, Ростов-на-Дону, 2005, т. XI, С. 28_30.

Тапкинов Б. Ю. Внутреннее представление программы в Системе построения оптимизирующих и распараллеливающих компиляторов // Труды Всероссийской научной конференции «Научный сервис в сети Интернет: технологии параллельного программирования», Новороссийск, 18_23 сентября 2006, С. 88-91.

Тапкинов Б. Ю. Обучающие аспекты системы построения оптимизирующих и распараллеливающих компиляторов // Тезисы научно-методической конференции "Современные информационные технологии в образовании: Южный федеральный округ", Ростов-на-Дону, 20-21 апреля 2006, С. 240-242.

Тапкинов Б. Ю. Представление структурного графа и реализация алгоритма унификации его вершин и термов // Приложение к журналу «Известия вузов. Северо-Кавказский регион. Естественные науки», 2006, № 1, С. 30-36.

Размещено на Allbest.ru

...