УДК 519.685.3

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

kirur@bk.ru

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

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

1. WR₀ - грамматики.

Пусть L - язык с алфавитом термов A={A₁, ..., A_p},  и B - алфавитом синтермов B={B₁,..., B_k}. Зададим функцию F={F₁,...,F_k}, осуществляющую отображение F_p  : D_p → B_p , B_p   B, D_p   A,  1 ≤ p ≤ k. Определим алфавит нетерминальных символов  V и вспомога­тельный алфавит R. V={V₀ , V₁ , ..., V_t }, R={R₀, R₁, ...,R_q}, такой что VR,  R₀=V₀ . При представлении WR -грамматики на графах R_i   имеют смысл имен вершин графов, R₀  - начальной вершины (начальной аксиомы языка),  R_γ  - заключительные вершины,  γ  q.

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

1)   W^b_i,j,e  - единичное правило с предикатом - синтермом R_i   R_j, где R_i , R_j     R, B_e   B, означающее переход и вершины R_i к  вершине  R_j  при наличии на ленте ввода L синтерма B_e  , который при построении цепочки дописывается справа. Допускается правило вида W_i,j  с отсутствием синтерма, означающее безусловный переход из R_i  и R_j   без изменения ленты ввода L .

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

R_i  V_x , R_i ,R_j   R, V_x   V, введем индикатор q стека S следующим образом: q=0 - стек не используется, q=1 - стек используется. Стек используется в WR₀  - грамматике, если V содержит хотя бы один нетерминал, отличный от V₀  . Через (S) обозначим содержимое S. Если грамматика  WR₀   содержит правило вывода W^v_i,j,x, то из вершины R_i осуществляется переход к вершине V_x с одновременной записью в стек S вершины - преемника R_j . Далее, при попадании в вершину R_g возможны два случая: (S)= R_j  или (S)=0. В первом случае происходит переход в вершину  R_j  и из стека S удаляется R_j  ; во втором случае вывод считается законченным, если содержимое ленты ввода (Λ) = 0 и предложение не принадлежит языку, если (Λ) ≠ 0.

3) W^B_i,j,m матричное правило с предикатами - синтермами,J=(J₁,..., J_q),  M = (M₁,..., M_q), W^B_i,J,M =  W^B_i,Jm, _Mm , где каждое правило W^B_i,J,M  - это объединение единичных правил предикатов синтермов, для дуг исходящих из i-ой вершины с заданным набором синтермов B_M1,  B_M2, B_Mm  .

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

J = (  J₁, ... , J_Q ),   , W^v_i,J,L =  , объединение правил предикатов - нетерминалов, аналогично п. 3.

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

= ()()  ,

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

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

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

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

Дадим определение W - грамматик. Пусть S  - словарь синтермов.  u = {o₀, n_i}, i  G - вспомогательный словарь, Г={1,..., k}. - множество имен конечных множеств (возможно пустых)  подмножеств правил вида rR или rR, где через  обозначено многоместное отношение, означающее, что синтерм слева контактирует с синтермом левой части любого правила, имя которого указано справа. Точка справа соответствует заключительному выводу, r S, R   ,  = {, R_i}, i  Г₁ ,  - номер пустого множества правил, Г₁ = {1,..., к₁}, i_j   u₁  , j = 1,...,n. Число n аргументов определяется числом стеков, используемых при интерпретации правил грамматики. При этом I = 0 задает многоместное отношение нулевого типа, которое определяет, что синтерм r может конкатенировать с синтермом из левых частей множества  с именем R.  Многоместное отношение первого типа (I = 1) означает , что синтерм r может конкатенировать с синтермом из левых частей R с одновременной записью в стеки l₁ ,..., l_n непустых слов. Многоместное отношение второго типа (I=2) означает, что синтерм r может конкатенировать с синтермом из левых частей R только при условии, что все вершины стеков l₁ ,...,  l_n   совпадают со словами n₁ ,..., n_n .

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

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

Доказательство. Условие q=0  и V={V₀} означает многоместным отношением нулевого типа. Тогда очевидно, что в П₀  содержатся только правила вида W^B_i,j,m  .Условие υ₁₌ {0} означает отсутствие стеков в грамматике W.Условие Z={1} означает, что  функция  Ф(t, δ) не зависит от δ и может быть выбрана равной F. Через R_i, i=0,1,...,d обозначим все правила W^B_i,j,m П₀ . Будем считать, что M_0.  определяет множество правил  R₀ , а X = R_i . Из определения WR₀ , W  и M = {0, X}, если R = {R ₀ , ..., R_d} ,следует, что множества заключительных вершин двух грамматик совпадают, поэтому, L(WR₀ )= L(W). Теорема доказана.

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

Доказательство. Условие Z={1} означает , что Ф(t, δ)  не зависит от δ и может быть выбрана равной F. Все правила, не содержащие нетерминала, порождают совпадающие заключительные вершины аналогично теореме 1. Условие q=1  в WR₀ - грамматике означает наличие в П ₀  правил вывода вида W^v_i,j,x   и требует использования стека S. Заменим правило W^v_i,j,x   П₀   для каждого i W ₁ - выводом R_i : B1V_x . Для всех заключительных вершин Rγ  R грамматики WR₀ добавим W₂ - выводы Rg: B₁ R_k , k=0,..., d  , согласно требованию 1 обеспечивается возврат к вершинам Rγ ; Rγ:B₁ Rγ, где B₁ - синтерм со значением пусто. При таких выборах W₁ , W₂  выводов L(WR₀)=L(W). Теорема доказана.

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

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

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

Введем предикат: ph _i = h _i < ορ > g_i , где i – номер предиката, определяющий набор чисел {ι _i,m }, γ_i , набор { v_i,m } , γ_i и вид h _i и  более сложный предикат: px _J= ph ₁<dο> …<dο>ph _q ,    i = 1,…,q , где j – номер предиката, определяющий набор номеров i = i(j) , предикатов ph _i  и их число q =q(j) .Определим синтерм B_j как класс эквиваленных терминальных символов α _i,j  A, i =1,..,μ ,μ= μ(j). Введем целочисленную функцию χ_j (индикатор синтерма B_j) , равную порядковому номеру терминала в синтерме B_{j .}Каждому индикатору χ_j  поставим в соответствие имя регистра C_j  C , со значением χ_j. Таким образом, функции χ_j  могут входить в предикаты ph_i и px_i . Назовем действием над регистрами операцию d_i,j засылки линейной комбинации h_i в регистр C_j  , т.е. d_i,j : h_i  C_j , где   обозначает операцию засылки. С помощью операции засылки, таким образом, можно изменить значение регистра , т.е. в результате выполнения этой операции (C_j) = h_i . Дополним правила вывода П_о правилами вида:       

1.                   W_i,j ph_k – единичное правило вида R_i :  R_j  с предикатом ph_k (переход из вершины R_i в вершину R_j , если ph_i принимает значение “истина”) .

2.                       W_i,j px_k – единичное правило вида R_i :  R_j  с предикатом px_k .

3.                       Матричные правила, представляющие собой всевозможные объединения правил из П_о и правил W_i,jph_k , W_i,j1ph_k1 , выходящих из одной вершины R_{i .}

4.                       Ко всем перечисленным правилам можно добавить выполнения действия d_m,n при переходе по какой-либо дуге данного правила . Рассмотрим, например, правило W^B_i,j,i . Добавление d_m,n позволяет получить правило W^B_i,j,i d_m,n  вида R_i :      R_j , означающее переход из вершины R_i в вершину R_j при наличии на ленте  Λ синтерма B_i и одновременном выполнении действия d_m,n . Полученную совокупность правил обозначим П.

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

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

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

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

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

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

WR_(t) (A_t , B_t , F_t , V_t , C_t , R_t, П_t, R_{o, t},q_t)   ( А, β ,F , V,C,R,П,R_O,q)   WR_(t) (A_t , B_t , F_t , V_t , C_t , R_t, П_t, R_{o, t},q_t) , где q_t{0,1} , q= maxq_t по t , 1≤ t≤ n .

В частности можно взять    β  =  B_t  ,   F :2^A1 *…*2^An     B так, что  F={F₁ ,...,F_n },  F_t : 2^Ai  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с.: ил.