Автор: В.А.Серебряков

Глава 5. Элементы теории перевода

5.1. Преобразователи с магазинной памятью

Преобразователем с магазинной памятью (МП-преобразователем) называется восьмерка P=(Q,T,Г,П,Ф,q0,Z0,F), где Q - множество состояний, T - конечный входной алфавит, Г - конечный алфавит магазинных символов, П - конечный выходной алфавит, Ф - отображение множества Qx(T U {e})xГ в множество конечных подмножеств множества QxГ*xП*, q0<-Q - начальное состояние, Z0<-Г - начальный символ магазина, F<-Q - множество заключительных состояний.

Определим конфигурацию преобразователя P как четверку (q,x,u,y), где q<-Q - состояние, x<-T* - цепочка на входной ленте, u<-Г* - содержимое магазина, y<-П* - цепочка на выходной ленте, выданная вплоть до настоящего момента. Если Ф(q,a,Z) содержит (r,u,z), то будем писать (q,ax,Zw,y)|- (r,x,uw,yz) для любых x<-A*, w<-Г* и y<-П*. Рефлексивное и транзитивное замыкание отношения |- будем обозначать |-*. Цепочку y назовем выходом для x, если (q0,x,Z0,e)|- *(q,e,u,y) для некоторых q<-F и u<-Г*. Переводом (или преобразованием), определяемым МП-преобразователем P (обозначается t(P)), назовем множество {(x,y)|(q0,x,Z0,e)|- *(q,e,u,y) для некоторых q<-F и u<-Г*}. Будем говорить, что МП-преобразователь P=(Q,T,Г,П,Ф,q0,Z0,F) детерминированный (ДМП-преобразователь), если выполняются следующие условия:

1) для всех q<-Q, a<-T U {e} и Z<-Г множество Ф(q,a,Z) содержит не более одного элемента,

2) если Ф(q,e,Z)#{}, то Ф(q,a,Z)={} для всех a<-T.

Пример 5.1. Перевод арифметического выражения в ПОЛИЗ.

ПОЛИЗ - Польская инверсная запись или, что то же, постфиксная запись арифметических выражений. Трансляция может определяться следующим ДМП:

 Q={q0,+,*,),$};
 T={буквы,+,*,(,),$}, здесь $ - концевой маркер;
 Г={Z0,(,+,*};
 П={буквы,+,*};

Функция переходов определяется таблицей на рис. 5.1.

+------------------------------------------------+
| Г  |  Q  |   T   ||     Г*     |   Q  |  П     |
|----+-----+-------||------------+------+------- |
| Z0 | q0  | буква ||     z      |  q0  | буква  |
| Z0 | q0  |   (   ||     z(     |  q0  |        |
| Z0 | q0  | проч  ||     z      | проч |        |
|----+-----+-------||------------+------+------- |
|(   |  )  |       ||     e      |  q0  |        |
|+,* |  )  |       ||     e      |  )   | +,*    |
|----+-----+-------||------------+------+------- |
| +  |  *  |       ||     +*     |  q0  |        |
| *  |  +  |       ||     *+     |  q0  |        |
|проч| +,* |       || проч {+,*} |  q0  |        |
|----+-----+-------||------------+------+--------|
|+,* |  $  |       ||      e     |  $   | +,*    |
| Z0 |  $  |       ||      e     |      |        |
+------------------++----------------------------+
                  Рис. 5.1

                             76
+--------------------------------+
| Стек |Состояние|  Вход   |Выход|
|------+---------+---------+-----|
|Z0    |    q0   | a*(b+c)$|  a  |
|Z0    |    q0   |  *(b+c)$|     |
|Z0    |    *    |   (b+c)$|     |
|Z0*   |    q0   |   (b+c)$|     |
|Z0*(  |    q0   |    b+c)$|     |
|Z0*(  |    q0   |     +c)$|  b  |
|Z0*(  |    +    |      c)$|     |
|Z0*(+ |    q0   |      c)$|  c  |
|Z0*(+ |    q0   |       )$|     |
|Z0*(+ |    )    |        $|  +  |
|Z0*(  |    )    |        $|     |
|Z0*   |    q0   |        $|     |
|Z0*   |    $    |         |  *  |
|Z0    |    $    |         |     |
+--------------------------------+
                Рис. 5.2

Последовательность состояний автомата и магазина на строке a*(b+c) изображены в таблице рис. 5.2.

5.2. Синтаксически управляемый перевод

Схемой синтаксически управляемого перевода (или трансляции, сокращенно: СУ-схемой) называется пятерка Tr=(N,T,П,R,S), где

  N - конечное множество нетерминальных символов;
  T - конечный входной алфавит;
  П - конечный выходной алфавит;
  R -  конечное множество  правил перевода  вида A->u,  A1=v1,

A2=v2, ... , Am=vm, удовлетворяющих следующим условиям:

- каждый символ, входящий в v1, ..., vm, либо принадлежит П, либо является Bk для B<-N и B входит в v (здесь k - номер вхождения B в v),

- если u имеет более одного вхождения символа B, то каждый символ Bk во всех v соотнесен (верхним индексом) с конкретным вхождением B;

S - начальный символ, выделенный нетерминал из N.

A->u называют входным правилом вывода, Ai - переводом нетерминала A и Ai=vi - элементом перевода, связанным с этим правилом перевода. Если через P обозначить множество входных правил вывода всех правил перевода, то G=(N,T,P,S) будет входной грамматикой для Tr. Если в СУ-схеме Tr нет двух правил перевода с одинаковым входным правилом вывода, то ее называют семантически однозначной. Выход СУ-схемы определим снизу вверх. С каждой внутренней вершиной n дерева разбора (во входной грамматике), помеченной A, свяжем одну цепочку для каждого Ai. Эта цепочка называется значением (или переводом) символа Ai в вершине n. Каждое значение вычисляется подстановкой значений символов перевода данного элемента перевода Ai=vi, определенных в прямых потомках вершины n. Переводом t(Tr), определяемым СУ-схемой Tr, назовем множество {(x,y)|x имеет дерево разбора во входной грамматике для Tr и y - значение выделенного символа перевода S в корне этого дерева}. Если Tr=(N,T,П,R,S) - СУ-схема, то т(Tr) называется синтаксически управляемым переводом (СУ-переводом).

Пример 5.2. Рассмотрим формальное дифференцирование выражений, включающих константы 0 и 1, переменную x и функции sin, cos, + и *. Такие выражения порождает грамматика

                E -> E+T | T
                T -> T*F | F
                F -> (E) | sin(E) | cos(E) | x | 0 | 1

Свяжем с каждым из E, T и F два перевода, обозначенных индексом 1 и 2. Индекс 1 указывает на то, что выражение не дифференцировано, 2 - что выражение продифференцировано. Формальная производная - это E2. Законы дифференцирования таковы:

 d(f(x)+g(x))=df(x)+dg(x)                       dx=1
 d(f(x)*g(x))=f(x)*dg(x)+g(x)*df(x)             d0=0
 dsin(f(x))=cos(f(x))*df(x)                     d1=0
 dcos(f(x))=-sin(f(x))df(x)

Эти законы реализуются СУ-схемой:

 E -> E+T    E1=E1+T1             F -> cos(E) F1=cos(E1)
             E2=E2+T2                         F2=-sin(E1)*(E2)
 E -> T      E1=T1                F -> x      F1=x
             E2=T2                            F2=1
 T -> T*F    T1=T1*F1             F -> 0      F1=0
             T2=T1*F2+T2*F1                   F2=0
 F -> ( E )  F1=(E1)              F -> 1      F1=1
             F2=(E2)                          F2=0
 F -> sin(E) F1=sin(E1)
             F2=cos(E1)*(E2)

Дерево вывода для sin(cos(x))+x приведено на рис. 5.3.

Теорема 5.1. Если число вхождений каждого нетерминала в слове v не превосходит 1, то t(Tr) является КС-языком. Обратное не всегда верно [5].

Пример 5.2. T=({S,A},{a},{a,b},{S->A,AbAbA;A->a,a;A->aA,aA}. Здесь входной язык {an|n>=1}, выходной {anbanban}. Выходной язык не КС.

Теорема 5.2. Для каждого магазинного преобразователя существует эквивалентная СУ-схема [5].

Обратное, вообще говоря, не верно.

Определение. Семантически однозначная СУ-схема Tr=(N,T,П,R,S) называется простой, если для каждого правила A->u,v из R соответствующие друг другу вхождения нетерминалов встречаются в u и v в одном и том же порядке.

                               E  E1=sin(cos(x))+x
                              / \ E2=cos(cos(x))
           E1=sin(cos(x))    / + \  *(-sin(x)*(1))+1
           E2=cos(cos(x))   E     T
             *(-sin(x)*(1)) |     | T2=1
                            |     | T1=x
           T1=sin(cos(x))   |     |
           T2=cos(cos(x))   T     F F1=x
             *(-sin(x)*(1)) |     | F2=1
                            |     |
           F1=sin(cos(x))   |     |
           F2=cos(cos(x))   F     x
             *(-sin(x)*(1)) |
                            |
                      sin ( E ) E1=cos(x)
                            |   E2=-sin(x)*(1)
                            |
                            T   T1=cos(x)
                            |   T2=-sin(x)*(1)
                            |
                            F   F1=cos(x)
                            |   F2=-sin(x)*(1)
                            |
                      cos ( E ) E1=x  E2=1
                            |
                            T   T1=x  T2=1
                            |
                            F   F1=x  F2=1
                            |
                            x

                          Рис. 5.3

Перевод, определяемый простой СУ-схемой, называется простым синтаксически управляемым переводом (простым СУ-переводом).

Теорема 5.3. Пусть Tr=(N,T,П,R,S) - простая СУ-схема. Существует такой МП-преобразователь P, что t(P)=t(Tr) [5].

Таким образом, класс трансляций, определяемых магазинными преобразователями, совпадает с классом простых СУ-переводов.

Теорема 5.4. Пусть Tr=(N,T,П,R,S) - семантически однозначная простая СУ-схема, входной грамматикой которой служит LL(k)- грамматика. Тогда перевод {x$,y)|(x,y)<-t(Tr)} можно осуществить детерминированным МП-преобразователем [5]. Существуют семантически однозначные простые СУ-схемы, имеющие в качестве входных грамматик LR(k) грамматики и не реализуемые ни на каком ДМП-преобразователе.

Пример 5.3. Рассмотрим простую СУ-схему T с правилами

          S -> Sa, aSa
          S -> Sb, bSb
          S -> e, e

Входная грамматика является LR(1) грамматикой, но не существует ДМП-преобразователя, определяющего перевод

{(x$,y)|(x,y)<-t(Tr)} [5].

Определение. Назовем СУ-схему Tr=(N,T,П,R,S) постфиксной, если каждое правило из R имеет вид A->u,v, где v<-N*П*. Иными словами, каждый элемент перевода представляет собой цепочку из нетерминалов, за которыми следует цепочка выходных символов.

Теорема 5.5. Пусть Tr=(N,T,П,R,S) - семантически однозначная простая постфиксная СУ-схема, входной грамматикой которой служит LR(k)-грамматика. Тогда перевод {(x$,y)|(x,y)<-t(Tr)} можно осуществить детерминированным МП-преобразователем [5].

5.3. Атрибутные грамматики

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

5.3.1. Определение атрибутных грамматик

Пусть G - КС-грамматика: G=(T,N,P,Z), где T, N, P, Z, - соответственно, множество терминальных символов, нетерминальных символов, множество правил вывода и аксиома грамматики. Правила вывода КС-грамматики будем записывать в виде

p: X0 -> X1 ... Xn

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

С каждым символом X <- N U T свяжем множество A(X) атрибутов символа X.Некоторые из множеств A(x) могут быть пусты. Запись a(X) означает, что a <- A(X). С каждым правилом вывода p <- P свяжем множество F семантических правил, имеющих следующую форму:

a0 = fpa0(a1, ... , aj),

где ik <- [0,np] - номер символа правила p, а ak - атрибут символа Xik , т.е. ak <- A(Xik). В таком случае будем говорить , что a0 "зависит" от a1,...,aj или что a0 "вычисляется по" a1,...,aj. В частном случае j может быть равно нулю, тогда будем говорить, что атрибут a0 "получает в качестве значения константу". КС-грамматику, каждому символу которой сопоставлено множество атрибутов, а каждому правилу вывода - множество семантических правил, будем называть атрибутной грамматикой (AG).

Назовем атрибут a(X0) синтезируемым, если одному из правил вывода p: X0 ->X1 ... Xnp сопоставлено семантическое правило a<0>=fa<0>(...). Назовем атрибут a(Xi) наследуемым, если одному из правил вывода p:X0 -> X1 ... Xi ... Xnp сопоставлено семантическое правило a=fa(...), i <- [1,np]. Множество синтезируемых атрибутов символа X обозначим через S(X), наследуемых атрибутов - через I(X). Будем считать, что значение атрибутов терминальных символов - константы, т.е. их значения определены, но для них нет семантических правил, определеяющих их значения.

5.3.2. Атрибутированное дерево разбора

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

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

5.3.3. Язык описания атрибутных грамматик

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

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

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

При записи синтаксиса мы будем использовать расширенную БНФ. Элемент правой части синтаксического правила, заключенный в скобки [ ], может отсутствовать. Элемент правой части синтаксического правила, заключенный в скобки ( ), означает возможность повторения один или более раз. Элемент правой части синтаксического правила, заключенный в скобки [()], означает возможность повторения ноль или более раз. В скобках [] или [()] может указываться разделитель конструкций. Ниже дан синтаксис языка описания атрибутных грамматик.

Атрибутная грамматика ::= 'ALPHABET'
          ( ОписаниеНетерминала ) ( Правило )
ОписаниеНетерминала ::= ИмяНетерминала
                   '::' [( ОписаниеАтрибутов / ';')] '.'
ОписаниеАтрибутов ::= ( ИмяАтрибута / ',') ':' Тип
Правило ::= 'RULE' Синтаксис 'SEMANTICS' Семантика '.'
Синтаксис ::= ИмяНетерминала '::=' ПраваяЧасть
ПраваяЧасть ::= [( ЭлементовПравойЧасти )]
ЭлементПравойЧасти ::= ИмяНетерминала
         | Терминал
         | '(' Нетерминал [ '/' Терминал ] ')'
         | '[' Нетерминал ']'
         | '[(' Нетерминал [ '/' Терминал ] ')]'
Семантика ::= [( ЛокальноеОбъявление ])
              [( СемантическоеДействие ])
СемантическоеДействие ::= Присваивание
           | [ Метка ] Оператор
Присваивание ::= Переменная ':=' Выражение

Переменная ::= ЛокальнаяПеременная
           |   Атрибут
Атрибут ::= ЛокальныйАтрибут
        |   ГлобальныйАтрибут
ЛокальныйАтрибут ::= ИмяАтрибута '<' Номер '>'
ГлобальныйАтрибут ::= ИмяАтрибута '<' Нетерминал '>'
Метка ::= Целое ':'
       |  Целое 'Е' ':'
       |  Целое 'А' ':'
Оператор ::= Условный
         |   ОператорПроцедуры
         |   ЦиклПоМножеству
         |   ПростойЦикл
         |   ЦиклСУсловиемОкончания

Метка в семантической части правила привязывает выполнение оператора к обходу дерева разбора сверху-вниз слева направо. Конструкция "i : оператор" означает, что оператор должен быть выполнен сразу после обхода i-й компоненты правой части. Конструкция "i E : оператор" означает, что оператор должен быть выполнен, только если порождение i-й компоненты правой части пусто. Конструкция "i A : оператор" означает, что оператор должен быть выполнен после разбора каждого повторения i-й компоненты правой части (имеется в виду конструкция повторения).

Каждое правило может иметь локальные определения (типов и переменных). В формулах используются как атрибуты символов данного правила (локальные атрибуты) и в этом случае соответствующие символы указываются номерами в правиле (0 для символа левой части, 1 для символа правой части и т.д.), так и атрибуты символов предков левой части правила (глобальные атрибуты). В этом случае соответствующий символ указывается именем нетерминала. Таким образом, на дереве образуются области видимости атрибутов: атрибут символа имеет область видимости, состоящую из правила, в которое символ входит в правую часть, плюс все поддерево, корнем которого является символ, за исключением поддеревьев - потомков того же символа в этом поддереве (рис. 5.4).

                             |
                            ...
                          .  N  .
                         .  / \  .
                        .  /   \  .
                       .  /\   /\  .
                      .  / /\ /\ \  .
                     .  /  -- --  \  .
                    ...N...........N...
                      /\           /\
                      --           --

                         Рис. 5.4

Значение терминального символа доступно через атрибут VAL соответствующего типа.