Грамматика с памятью для создания трансляторов с параллельных языков вычислительных систем

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

электронное научно-техническое издание
НАУКА и ОБРАЗОВАНИЕ
Эя №& lt-Ш 77 — 30 569. Государственная регистрация № 421 100 025. 155Н 1994−0408_
Грамматика с памятью для создания трансляторов с параллельных языков вычислительных систем
77−30 569/235311
# 10, октябрь 2011 Руденко Ю. М.
УДК 519. 685. 3
МГТУ им. Н. Э. Баумана kirur@bk. ru
Построение транслятора, удобного для применения в вычислительных системах (ВС), особенно в неоднородных, является актуальнейшей задачей. ВС характеризуются наличием большого количества различных языков программирования, а также их диалектов и типов вычислительных модулей. Такой транслятор должен легко настраиваться под используемый язык программирования или тип используемого вычислительно модуля. Идея такого транслятора изложена в работах [1, 2, 3]. Эта задача может быть решена с помощью предлагаемой в этой работе WR — грамматики. при использовании параметрического транслятора. Правила вывода WR — грамматик могут быть представлены в виде обобщенных синтаксических диаграмм (ориентированных графов), у которых на дугах заданы условия их прохождения (предикаты и действия над стеками и регистрами). На дугах WR — грамматик могут встречаться также метапере-менные, заданные, в свою очередь, графами, и синтермы — синтаксически эквивалентные классы терминальных символов. Использование предикатов и действий над стеками и регистрами дает возможность представления синтаксиса широкого класса языков. Средствами WR — грамматики — использованием регистровой памяти — могут быть описаны такие элементы семантики, как вычисление типов выражений и согласование типов операндов и операций и т. д. Предложенные WR- грамматики близки W — грамматикам [3], имеющим в правилах вывода операции над стеками. Однако, для построения синтаксически управляемого транслятора более простой и удобной оказалась регистровая память. Операции над памятью введены непосредственно в синтаксис и существенно используются на этапе распознавания в транслирующей системе.
В первом разделе рассмотрен частный случай WR — грамматик: WRo — грамматика, в которой в отличие от WR -грамматики, рассмотренной во втором разделе, отсутствуют регистры и функции индикации синтермов.
1. WRo_- грамматики.
Пусть L — язык с алфавитом термов Л=(Л1, …, Ар}, и В — алфавитом синтермов Б={Б1,…, Вк}. Зададим функцию F={F1,…, Fk}, осуществляющую отображение Fp: Бр ^ Вр, Бр е Б, Бр е А, 1 & lt- р & lt- к. Определим алфавит нетерминальных символов V и вспомогательный алфавит R. V={V0, У1, …, У }, R={R0, R1, … ^Я^}, такой что V е R, R0=V0. При представлении WR -грамматики на графах Ri имеют смысл имен вершин графов, Я — начальной вершины (начальной аксиомы языка), Ry — заключительные вершины, у е Ф
Определим П0 — совокупность правил вывода WR 0 -грамматики вида:
1) Wb i, j, e — единичное правило с предикатом — синтермом Ri Я) где Ri, Я) е R, Бе е В, означающее переход и вершины Ri к вершине Я) при наличии на ленте ввода Л синтерма Ве, который при построении цепочки дописывается справа. Допускается правило вида Wi, j с отсутствием синтерма, означающее безусловный переход из Ri и Я) без изменения ленты ввода Л.
2) Wv у, х — единичное правило с предикатом — нетерминалом
Я --Ух, Ri е Я, Ух е V, введем индикатор q стека S следующим образом: q=0 — стек не используется, q=1 — стек используется. Стек используется в WR0 -грамматике, если V содержит хотя бы один нетерминал, отличный от V0. Через обозначим содержимое S. Если грамматика WR0 содержит правило вывода Wv i, j, x, то из вершины Ri осуществляется переход к вершине V с одновременной записью в стек S вершины — преемника Я). Далее, при попадании в вершину возможны два случая: (Б)= Я) или (S)=0. В первом случае происходит переход в вершину Я) и из стека S удаляется Я) — во втором случае вывод считается законченным, если содержимое ленты ввода (Л) = 0 и предложение не принадлежит языку, если (Л) Ф 0.
3) WБ матричное правило с предикатами — синтермами^^Ъ,…, 1ч), М =
е
(М1,…, Мч), W i, J, M = W уш, Мт, где каждое правило W i, J, M — это объединение
т=1
единичных правил предикатов синтермов, для дуг исходящих из ьой вершины с заданным набором синтермов ВМ1, БМ2, БМт.
4) Wvi, J, л — матричное правило с предикатами — нетерминалами,
е
J = (J1, …, JQ), Л = (Л1з…, Л), Wvi, J, л =, объединение правил пре-
& quot- 1, 1 т, Л т
дикатов — нетерминалов, аналогично п. 3. В
, 1, к, т,
В
В
5) Ж.. — матричное правило общего вида, 1,1, к, л
/, 1, к, т, Л =(и '-, Л", тт
) и (и 1, 1 т, Л т
^ т=1 т=1 т=1
которое для каждой дуги, исходящем из ьи вершины, содержит правила с предикатами — синтермами и предикатами — нетерминалами.
Определение 2. WRo — грамматикой назовем грамматику вида WRo (А, В, F, V, R, Пo, Яо, я).
Требование 1. Будем считать, что грамматика WRo удовлетворяет условию: из любой вершины у е V, используя правила перехода П0, можно попасть за конечное число переходов в заключительную вершину из у.
Дадим определение W — грамматик. Пусть S — словарь синтермов. и = у^, 1 е Г — вспомогательный словарь, Г={1,…, к}.р — множество имен конечных множеств
(возможно пустых) подмножеств правил вида г -Ж (г'-) & gt- R или г -Ж (11,-, 1п) & gt- R, где
через -Ж (г'-) & gt- обозначено многоместное отношение, означающее, что синтерм слева контактирует с синтермом левой части любого правила, имя которого указано справа. Точка справа соответствует заключительному выводу, г е S, R е р, р = { 0,
Ri}, i е Г1, 0 — номер пустого множества правил, Г1 = {1,…, к1}, ij е и1 р, ] =
1,…, п. Число п аргументов определяется числом стеков, используемых при интерпретации правил грамматики. При этом I = 0 задает многоместное отношение нулевого типа, которое определяет, что синтерм г может конкатенировать с синтермом из левых частей множества р с именем R. Многоместное отношение первого типа (I = 1) означает, что синтерм г может конкатенировать с синтермом из левых частей R с одновременной записью в стеки 11 ,…, 1п непустых слов. Многоместное отношение второго типа (1=2) означает, что синтерм г может конкатенировать с синтермом из левых частей R только при условии, что все вершины стеков 11 ,…, 1п совпадают со словами у1
,…, Уп.
Пусть I е T — терм, где Т — множество термов, d — параметр, 5 е Z, Z — множество индексов правил. Определим функции Ф (^, 5), которая задает соответствие термов и синтермов.
Теорема 1. Пусть W (T, S, Ъ, и, Ф, М, М0) — грамматика с многоместным отношением нулевого типа. Тогда WRo (А, В, F, V, R, П0, И, о) ~ W (A, B, Ъ, и, Г, М, М), если У={У0 }, Ъ = {1}, и1 = {0}, с некоторыми М, М0.
Доказательство. Условие q=0 и V={Vo} означает многоместным отношением нулевого типа. Тогда очевидно, что в П0 содержатся только правила вида WB у, т. Условие ^1= {0} означает отсутствие стеков в грамматике W. Условие Z={1} означает, что функция Ф (5) не зависит от 5 и может быть выбрана равной F. Через Я-, i=0,1,…, d обозначим все правила WB у, т е П0. Будем считать, что М0. определяет
й
множество правил Я0, а X = Я-. Из определения WR0, W и М = {0, X}, если R =
г=1
{Я 0, …, Яа}, следует, что множества заключительных вершин двух грамматик совпадают, поэтому, L (WR0)= L (W). Теорема доказана.
Теорема 2. Пусть W (A, B, Ъ, и1, Г, М, М^ - грамматика с многоместными отношениями первого и второго типа. Тогда WR0 (А, В, F, V, R, П0, И0, 1) ~ W (A, B, Ъ, и1, Г, М, М0), если Ъ={1}, и1 = S — имя стека в грамматике WR0, с некоторыми М, М0.
Доказательство. Условие Z={1} означает, что Ф (^ 5) не зависит от 5 и может быть выбрана равной F. Все правила, не содержащие нетерминала, порождают совпадающие заключительные вершины аналогично теореме 1. Условие q=1 в WR0 — грамматике означает наличие в П 0 правил вывода вида Wv у, х и требует использования стека S. Заменим правило Wv у, х е П0 для каждого i W 1 — выводом Ri:
В1 -(Д/) & gt- Ух. Для всех заключительных вершин Ry е R грамматики WR0 добавим
— выводы Ry: В1 -(д*) & gt-, к=0,…, d, согласно требованию 1 обеспечивается
возврат к вершинам Ry — Яу: В1 -(0) & gt- Яу, где В1 — синтерм со значением пусто. При таких выборах W1, W2 выводов L (WR0)=L (W). Теорема доказана.
2. WR — грамматики общего вида
WR — грамматики отличаются от WR0 — грамматик, и в силу теорем 1, 2 от W -грамматики использованием регистровой памяти в предикатах и действиях. При этом, проход по дуге правила вывода, имеющей предикат, осуществляется, если этот предикат принимает значение & quot-истина"-. Если дуга содержит действия над регистрами, то при проходе по ней эти действия выполняются. Определим С={С1,…, Сч} - алфавит имен регистров. Введем операции & lt-ор>- е { =, & lt-, & gt-, & lt-, & gt- }, где & lt- ор & gt- описывает, например, операции отношения между величинами, а ^о& gt- - логические операции
дизъюнкции и конъюнкции. Зададим множество целых чисел у=(у1,…, уч }. Поставим в соответствие каждому С] е С число V е V. Это соответствие будем обозначать (С]) = V], т. е. применительно к процессору — значение, записанное в счетчике С], есть V.
Пусть I ?, ш, у- - целые положительные числа е V, т = 1,…/. Через h — обозначим линейную комбинацию значений вида: h — = ± I Viд ± … ± I ц Vi, m.
Введем предикат: ph — = И — & lt- ор & gt-, где i — номер предиката, определяющий набор чисел (г },, набор { vi, m }, и вид h — и более сложный предикат: рх -= рИ 1& lt-ёо>-. & lt-ёо>-рЬ ч, i = 1,…^, где j — номер предиката, определяющий набор номеров i = i (j), предикатов ph i и их число q =q (i). Определим синтерм В] как класс эквивален-ных терминальных символов, а у е А, I =1,., ц, р= ц) Введем целочисленную функцию х (индикатор синтерма В]), равную порядковому номеру терминала в синтерме В] Каждому индикатору х поставим в соответствие имя регистра С] е С, со значением x. Таким образом, функции х могут входить в предикаты р^ и рх-. Назовем действием над регистрами операцию di, j засылки линейной комбинации Ь в регистр С], т. е. di, j: ^ С], где ^ обозначает операцию засылки. С помощью операции засылки, таким образом, можно изменить значение регистра, т. е. в результате выполнения этой операции (С]) =. Дополним правила вывода По правилами вида:
1. рИк — единичное правило вида Я: Р^, И] с предикатом phk (пере-
ход из вершины Ri в вершину Rj, если р^ принимает значение & quot-истина"-).
2. рхк — единичное правило вида Ri: рХк & gt- И] с предикатом рхк.
3. Матричные правила, представляющие собой всевозможные объединения правил из По и правил Wi, jphk, '-^^рИы, выходящих из одной вершины Ri.
4. Ко всем перечисленным правилам можно добавить выполнения действия dm, n при переходе по какой-либо дуге данного правила. Рассмотрим, например, правило WBi, j, l. Добавление dm, n позволяет получить правило WBi, j, l ёт, п вида:
В. >- И], означающее переход из вершины Ri в вершину Я] при наличии на ленте Л
синтерма Вг и одновременном выполнении действия dm, n. Полученную совокупность правил обозначим П.
Определение 3. WR — грамматикой назовем грамматику вида WR (A, B, F, V, C, R, П, Ro, q).
3. Использование WR — грамматик для построения синтаксически управляемого
транслятора.
Зададим языки Li д=1,…, п с алфавитами терминальных символов Л{. Введем параметры^- номер языка, N — признак атрибута, отвечающий за согласование типов операндов и операций, выражений, выбор типа процессора, и т. п. Пусть задан алфа-
п
вит синтермов В такой, что В]=Б^, К) е В, ]=1,., к, А= У Аг.
г=1
Будем считать, что матрица -функция Б{Гу } осуществляет отображение 2А1 *. *2Ап и {у =^о (К), гденомер языка, j- номер синтерма В], знак * означает прямое произведение. Обозначим Р=В1*… *Вп. Пусть ф, Ке С алфавиту регистров, 1 ^ ф, К ^ К. Значение регистра ф считается фиксированным, регистр К может использоваться в вычислениях, как указано в разделе 2.
Определение 4. Параметризованной то^ - грамматикой с параметрами назовем грамматику вида то^ (А, в, Г, У, СЗ, ПЗо^), где ф, КеС и 1 ^ ф, NК.
Пусть для языков L1,…, Ln заданы их WR (t) — грамматики. Тогда нетрудно показать, что существует такая грамматика то^, что
п
WR (t) (А, Б1, , VI, С, Я, П, Яс, 1 ,%) с тоЯ (А, в, Б, V, C, R, П, Ro, q) с У
1=1
WR (t) (А1, Б1, Б, V, С, , П, Яс, 1), где qtе {0,1}, q= тах qt по 1, 1& lt- К п.
п
В частности можно взять в = У Б t, Б: 2А1 *. *2Ап ^ В так, что
1=1
Б={Б1 ,…, Б п }, Б !: 2Аг & gt- Б, С с у Сг, V с У Vl ,
1=1 1=1
пп
п с i) П, я с у Я.
1=1 1=1
Однако, реально, за счет параметризации и наложения близких синтаксических структур общее число правил параметризированной грамматики то^ удается существенно сократить для достаточно близких языков. При этом существенно используются дополнительные по сравнению с W — грамматикой типы памяти, предикаты и индикаторы WR — грамматик. В качестве примера использования грамматик то^ можно привести построение синтаксиса предложений в стандарте Ореп_МР для языков ФОРТРАН, СИ, приведенные в работе [4] для процессоров первого и второго типов N={1,2}.
Для иллюстрации использования предлагаемого метода параметризации на рис. 1 представлен ориентированный граф с нагруженными дугами для зависящей от пара-
метра t={1,2,3} подключение системы Open_MP), которое зависит от символьных констант для языков СИ (=1), ФОРТРАН 0=2) и НОРМА (t=3) и различных типов процессоров N={1,2}.
Принятые обозначения:
#pragma omp — символьная константа, определяющая, что далее идут инструкции Open_Mp для языка СИ.
!$omp — символьная константа, определяющая, что далее идут инструкции Open_Mp для языка ФОРТРАН.
При прохождении первой дуги исключается язык НОРМА 0=3). Далее, по значению t=1 и значению символьной константы '-#pragma omp'- для первого типа процессора могут быть сформированы инструкции по выполнению параллельных операций. Аналогично, по значению t=2 и значению символьной константы '-!$omp'- для второго типа процессора могут быть выполнены необходимые действия по подготовке параллельных вычислений
Таким образом, предлагаемый способ параметризации грамматик позволяет создавать объединенные трансляторы, которые затем можно адаптировать под требуемые языки и типы процессоров. Достаточно удобным предлагаемый метод может оказаться для создания транслятора, учитывающего диалекты языка. Особенно широкое применение параметрические трансляторы могут найти в вычислительных системах, объединяющих неоднородные вычислительные сети.
ЛИТЕРАТУРА
1. Руденко Ю. М. Требования к языкам программирования на современном этапе. -
УСиМ, N 6,1991 г., с. 74−79.
2. Параметрический транслятор для неоднородной вычислительной системы. Тезисы
докладов на Международной научно-технической конференции, посвященной 30-летию со дня основания Университета, «Гражданская авиация на рубеже веков». Министерство транспорта РФ, государственная служба гражданской авиации, Московский Государственный технический университет гражданской авиации. 30−31 мая 2001 г., с. 247−248
3. Баша В. В., Руденко Ю. М. Использование параметрического под- хода при решении
проблем мобильности транслирующих систем. -УСиМ, 1988, № 5, с. 46−51.
4. Антонов А. С. Введение в параллельные вычисления. Методическое пособие. — М. :
Изд-во МГУ, 2002. — 72с.: ил.

ПоказатьСвернуть
Заполнить форму текущей работой