Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

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

# 10, октябрь 2011
Файл статьи: Руденко_P.pdf (297.49Кб)
автор: Руденко Ю. М.

УДК 519.685.3

МГТУ им. Н.Э. Баумана

kirur@bk.ru

Построение транслятора, удобного для применения в вычислительных системах (ВС), особенно в неоднородных, является актуальнейшей задачей. ВС характеризуются наличием большого количества различных языков программирования, а также их диалектов и типов вычислительных модулей. Такой транслятор должен легко настраиваться под используемый язык программирования или тип используемого вычислительно модуля. Идея такого транслятора изложена в работах [1, 2, 3]. Эта задача может быть решена с помощью предлагаемой в этой работе WR – грамматики. при использовании параметрического транслятора. Правила вывода WR - грамматик могут быть представлены в виде обобщенных синтаксических диаграмм (ориентированных графов), у которых на дугах заданы условия их прохождения  (предикаты и действия над стеками и регистрами). На дугах WR - грамматик могут  встречаться также метапеременные, заданные, в свою очередь, графами, и синтермы - синтаксически эквивалентные классы терминальных символов. Использование предикатов и действий над стеками и регистрами дает возможность представления синтаксиса широкого класса языков. Средствами WR - грамматики - использованием регистровой памяти - могут быть описаны такие элементы семантики, как вычисление типов выражений и согласование типов операндов и операций и т.д. Предложенные WR- грамматики близки W -  грамматикам [3], имеющим в правилах вывода операции над стеками. Однако, для построения синтаксически управляемого транслятора более  простой и удобной оказалась регистровая память. Операции над памятью введены непосредственно в синтаксис и существенно используются на этапе распознавания в транслирующей системе.

В первом разделе рассмотрен частный случай WR - грамматик: WR0 - грамматика, в которой в отличие от WR -грамматики, рассмотренной во втором разделе, отсутствуют регистры и функции индикации синтермов.

 

1. WR0 - грамматики.

Пусть L - язык с алфавитом термов A={A1, ..., Ap},  и B - алфавитом синтермов B={B1,..., Bk}. Зададим функцию F={F1,...,Fk}, осуществляющую отображение F: Dp → Bp , Bp   B, Dp   A,  1 ≤ p ≤ k. Определим алфавит нетерминальных символов  V и вспомога­тельный алфавит R. V={V0 , V1 , ..., Vt }, R={R0, R1, ...,Rq}, такой что VR,  R0=V0 . При представлении WR -грамматики на графах Ri   имеют смысл имен вершин графов, R0  - начальной вершины (начальной аксиомы языка),  Rγ  - заключительные вершины,  γ  q.

Определим  P0  - совокупность правил вывода WR 0  -грамматики вида:

1)   Wbi,j,e  - единичное правило с предикатом - синтермом Ri   Rj, где Ri , R   R, Be   B, означающее переход и вершины Ri к  вершине  Rj  при наличии на ленте ввода L синтерма Be  , который при построении цепочки дописывается справа. Допускается правило вида Wi,j  с отсутствием синтерма, означающее безусловный переход из Rи Rj   без изменения ленты ввода L .

2)  Wvi,j,x  - единичное правило с предикатом - нетерминалом

Ri  Vx , Ri ,R R, V V, введем индикатор q стека S следующим образом: q=0 - стек не используется, q=1 - стек используется. Стек используется в WR- грамматике, если V содержит хотя бы один нетерминал, отличный от V0  . Через (S) обозначим содержимое S. Если грамматика  WR содержит правило вывода Wvi,j,x, то из вершины Ri осуществляется переход к вершине Vx с одновременной записью в стек S вершины - преемника Rj . Далее, при попадании в вершину Rg возможны два случая: (S)= Rj  или (S)=0. В первом случае происходит переход в вершину  Rj  и из стека S удаляется R; во втором случае вывод считается законченным, если содержимое ленты ввода (Λ) = 0 и предложение не принадлежит языку, если (Λ) ≠ 0.

3) WBi,j,m матричное правило с предикатами - синтермами,J=(J1,..., Jq),  M = (M1,..., Mq), WBi,J,M =  WBi,Jm, Mm , где каждое правило WBi,J,M  - это объединение единичных правил предикатов синтермов, для дуг исходящих из i-ой вершины с заданным набором синтермов BM1,  BM2, BMm  .

4) Wvi,J,L - матричное правило с предикатами - нетерминалами,

J = (  J1, ... , JQ ),   , Wvi,J,L, объединение правил предикатов - нетерминалов, аналогично п. 3.

5)  - матричное правило общего вида, 

= ()()  ,

которое для каждой дуги, исходящей из i-й вершины, содержит правила с предикатами - синтермами и предикатами - нетерминалами.

Определение 2. WR0 - грамматикой назовем грамматику вида WR0 (A,B, F,V,R,П0 , R0 , q).

Требование 1. Будем считать, что грамматика WR0 удовлетворяет

условию: из любой вершины vj v, используя правила перехода П0 ,можно попасть за конечное число переходов в заключительную вершину  из γ .

Дадим определение W - грамматик. Пусть S  - словарь синтермов.  u = {o0, ni}, i  G - вспомогательный словарь, Г={1,..., k}. - множество имен конечных множеств (возможно пустых)  подмножеств правил вида rR или rR, где через  обозначено многоместное отношение, означающее, что синтерм слева контактирует с синтермом левой части любого правила, имя которого указано справа. Точка справа соответствует заключительному выводу, r S, R   ,  = {, Ri}, i  Г1 ,  - номер пустого множества правил, Г1 = {1,..., к1}, ij   u1  , j = 1,...,n. Число n аргументов определяется числом стеков, используемых при интерпретации правил грамматики. При этом I = 0 задает многоместное отношение нулевого типа, которое определяет, что синтерм r может конкатенировать с синтермом из левых частей множества  с именем R.  Многоместное отношение первого типа (I = 1) означает , что синтерм r может конкатенировать с синтермом из левых частей R с одновременной записью в стеки l1 ,..., ln непустых слов. Многоместное отношение второго типа (I=2) означает, что синтерм r может конкатенировать с синтермом из левых частей R только при условии, что все вершины стеков l1 ,...,  ln   совпадают со словами n1 ,..., nn .

Пусть t  T  - терм, где Т - множество термов, d - параметр, δ  Z, Z - множество индексов правил. Определим функции Ф(t, δ), которая задает соответствие термов и синтермов.

Теорема 1.  Пусть W(T,S, Z, υ, Ф, M , M0 ) – грамматика  с многоместным отношением нулевого типа. Тогда WR0 (A, B, F, V, R, П0, R0 , o) ~ W(A,B, Z, υ1 , F, M , M), если V={V0 } , Z = {1}, υ1 = {0} , с некоторыми M , M0.

Доказательство. Условие q=0  и V={V0} означает многоместным отношением нулевого типа. Тогда очевидно, что в П0  содержатся только правила вида WBi,j,m  .Условие υ1= {0} означает отсутствие стеков в грамматике W.Условие Z={1} означает, что  функция  Ф(t, δ) не зависит от δ и может быть выбрана равной F. Через Ri, i=0,1,...,d обозначим все правила WBi,j,m П0 . Будем считать, что M0.  определяет множество правил  R0 , а X = Ri . Из определения WR0 , W  и M = {0, X}, если R = {R 0 , ..., Rd} ,следует, что множества заключительных вершин двух грамматик совпадают, поэтому, L(WR0 )= L(W). Теорема доказана.

Теорема 2.  Пусть W(A,B, Z, υ1 , F, M , M0) - грамматика с многоместными отношениями первого и второго типа. Тогда WR0 (A, B, F, V, R, П0, R0 , 1) ~ W(A,B, Z, υ1 , F, M , M0 ), если Z={1}, υ1 = {S}, S - имя стека в грамматике WR0 , с некоторыми M , M0.

Доказательство. Условие Z={1} означает , что Ф(t, δ)  не зависит от δ и может быть выбрана равной F. Все правила, не содержащие нетерминала, порождают совпадающие заключительные вершины аналогично теореме 1. Условие q=1  в WR0 - грамматике означает наличие в П 0  правил вывода вида Wvi,j,x   и требует использования стека S. Заменим правило Wvi,j,x   П0   для каждого i W 1 - выводом Ri : B1Vx . Для всех заключительных вершин Rγ  R грамматики WR0 добавим W2 - выводы Rg: B1 Rk , k=0,..., d  , согласно требованию 1 обеспечивается возврат к вершинам Rγ ; Rγ:B1 Rγ, где B1 - синтерм со значением пусто. При таких выборах W1 , W2  выводов L(WR0)=L(W). Теорема доказана.

 

2. WR - грамматики общего вида

WR - грамматики отличаются от WR0 - грамматик, и в силу теорем 1, 2 от W - грамматики использованием регистровой памяти в предикатах и действиях. При этом, проход по дуге правила вывода , имеющей предикат, осуществляется, если этот предикат принимает значение “истина”. Если дуга содержит действия над регистрами, то при проходе по ней эти действия выполняются. Определим C={C1,..., Cq} - алфавит имен регистров. Введем операции <ορ>  { =, ≠,  ≤ ,  ≥, <, > } , где < ορ > описывает, например, операции отношения между величинами, а <dο> - логические операции дизъюнкции и конъюнкции. Зададим множество целых чисел  v={v1,...,vq  }.Поставим в  соответствие каждому Сj  C число vjv. Это соответствие будем обозначать  (Сj ) = vj ,
т.е. применительно к процессору – значение, записанное в счетчике Сj , есть vj.

Пусть i i,m  , γi – целые положительные числа ,vi,mv,  m = 1,…,f .Через h i  обозначим линейную комбинацию значений вида : h i = ± ι i,1 vi,1±±  ι i,f vi,m .

Введем предикат: ph i = h i < ορ > gi , где i – номер предиката, определяющий набор чисел {ι i,m }, γi , набор { vi,m } , γi и вид h i и  более сложный предикат: px J= ph 1<dο> …<dο>ph q ,    i = 1,…,q , где j – номер предиката, определяющий набор номеров i = i(j) , предикатов ph и их число q =q(j) .Определим синтерм Bj как класс эквиваленных терминальных символов α i,j  A, i =1,..,μ ,μ= μ(j). Введем целочисленную функцию χj (индикатор синтерма Bj) , равную порядковому номеру терминала в синтерме Bj .Каждому индикатору χj  поставим в соответствие имя регистра Cj  C , со значением χj. Таким образом, функции χj  могут входить в предикаты phi и pxi . Назовем действием над регистрами операцию di,j засылки линейной комбинации hi в регистр C, т.е. di,j : hi  Cj , где   обозначает операцию засылки. С помощью операции засылки, таким образом, можно изменить значение регистра , т.е. в результате выполнения этой операции (Cj) = hi . Дополним правила вывода По правилами вида:       

1.                   Wi,j phk – единичное правило вида Ri :  Rj  с предикатом phk (переход из вершины Ri в вершину Rj , если phi принимает значение “истина”) .

2.                       Wi,j pxk – единичное правило вида Ri :  Rj  с предикатом pxk .

3.                       Матричные правила, представляющие собой всевозможные объединения правил из По и правил Wi,jphk , Wi,j1phk1 , выходящих из одной вершины Ri .

4.                       Ко всем перечисленным правилам можно добавить выполнения действия dm,n при переходе по какой-либо дуге данного правила . Рассмотрим, например, правило WBi,j,i . Добавление dm,n позволяет получить правило WBi,j,i dm,n  вида Ri :      Rj , означающее переход из вершины Ri в вершину Rj при наличии на ленте  Λ синтерма Bi и одновременном выполнении действия dm,n . Полученную совокупность правил обозначим П.

Определение 3. WR – грамматикой назовем грамматику вида WR(A,B,F,V,C,R,П,RO,q) .

 

3. Использование WR – грамматик для построения синтаксически управляемого транслятора.

Зададим языки Li ,i=1,…,n  с алфавитами терминальных символов Ai  . Введем параметры:t- номер языка, N – признак атрибута, отвечающий за согласование типов операндов и операций, выражений, выбор типа процессора,  и т.п. Пусть задан алфавит синтермов B такой, что     Bj=Bj(t,N) B,  j=1,…,k , A= .

Будем считать, что матрица –функция F{fi,j}  осуществляет отображение  2A1 *…*2An  и  ft,j =fi,j (N)  , где  t-номер языка, j- номер синтерма Bj , знак * означает прямое произведение. Обозначим       β=B1*…*Bn . Пусть  ,C  алфавиту регистров, t ,N    . Значение регистра  считается фиксированным, регистр  может использоваться в вычислениях, как указано в разделе 2.

Определение 4. Параметризованной   - грамматикой с параметрами   t,N, назовем грамматику вида  (А, β ,F , V,C,R,П,RO,q) , где  ,C и   t , N .

Пусть для языков L1,…,Ln заданы их WR(t) – грамматики. Тогда нетрудно показать, что существует такая грамматика   , что

WR(t) (At , Bt , Ft , Vt , Ct , Rt, Пt, Ro, t,qt)   ( А, β ,F , V,C,R,П,RO,q)   WR(t) (At , Bt , Ft , Vt , Ct , Rt, Пt, Ro, t,qt) , где qt{0,1} , q= maxqt по t , 1≤ t≤ n .

В частности можно взять    β  =  Bt  ,   F :2A1 *…*2An     B так, что  F={F1 ,...,Fn },  Ft : 2Ai  B, C Cι  , V  Vι  ,

П  Пι , R  Rι .

Однако, реально, за счет параметризации и наложения близких синтаксических структур общее число правил параметризированной грамматики  удается существенно сократить для достаточно близких языков. При этом существенно используются дополнительные по сравнению с W – грамматикой типы памяти, предикаты и индикаторы WR – грамматик. В качестве примера использования грамматик  можно привести построение синтаксиса предложений в стандарте Open_MP для языков ФОРТРАН, СИ, приведенные в работе [4] для процессоров первого и второго типов N={1,2}.

Для иллюстрации использования предлагаемого метода параметризации на рис. 1 представлен ориентированный граф с нагруженными дугами для зависящей от параметра  t={1,2,3}  подключение системы Open_MP), которое зависит от символьных констант для языков СИ (t=1), ФОРТРАН (t=2) и НОРМА (t=3) и различных типов процессоров N={1,2}.

Принятые обозначения:

#pragmaomp - символьная константа, определяющая, что далее идут инструкции Open_Mp для языка СИ.

!$omp - символьная константа, определяющая, что далее идут инструкции Open_Mp для языка ФОРТРАН.

 

Рис. 1.

 

При прохождении первой дуги исключается язык НОРМА (t=3). Далее, по значению t=1 и значению символьной константы ‘#pragmaomp’ для первого типа процессора  могут быть сформированы инструкции по выполнению параллельных операций. Аналогично, по значению t=2 и значению символьной константы ‘!$omp’ для второго типа процессора  могут быть выполнены необходимые действия по подготовке параллельных вычислений

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

ЛИТЕРАТУРА

1.                   Руденко Ю.М. Требования к  языкам программирования на современном этапе. -УСиМ, N 6,1991г., с.74-79.

2. Параметрический транслятор для неоднородной вычислительной    системы. Тезисы докладов на Международной научно-технической  конференции, посвященной 30-летию со дня основания Университета, «Гражданская авиация на рубеже веков». Министерство транспорта РФ, государственная служба гражданской авиации, Московский Государственный технический университет гражданской авиации. 30-31 мая 2001 г., с.247-248

3. Баша В.В., Руденко Ю.М. Использование параметрического под-  хода при решении проблем мобильности транслирующих систем. –УСиМ, 1988, №5, с.46-51.

4.   Антонов А.С. Введение в параллельные вычисления. Методическое пособие. – М.: Изд-во МГУ, 2002. – 72с.: ил.

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2019 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)