Лекции по конструированию компиляторов - Глава 5. Элементы теории перевода

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

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

     - каждый символ, входящий в v1, ..., vm, либо принадлежит
П, либо  является Bk для Bu  называют   входным  правилом   вывода,  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) Sa, aSa
          S -> Sb, bSb
          S -> e, e

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

{(x$,y)|(x,y)u,v, где v X1 ... Xn

и будем  предполагать, что  G -  редуцированная КС-грамматика,
т.е.  в  ней  нет  нетерминальных  символов,  для  которых  не
существует полного  дерева вывода  ,  в  которое  входит  этот
нетерминал.
С каждым символом X X1  ... Xnp сопоставлено семантическое правило
a=fa(...).  Назовем   атрибут  a(Xi)  наследуемым,  если
одному из правил вывода p:X0 -> X1 ... Xi ... Xnp сопоставлено
семантическое правило  a=fa(...), i '
ГлобальныйАтрибут ::= ИмяАтрибута ''
Метка ::= Целое ':'
       |  Целое 'Е' ':'
       |  Целое 'А' ':'
Оператор ::= Условный
         |   ОператорПроцедуры
         |   ЦиклПоМножеству
         |   ПростойЦикл
         |   ЦиклСУсловиемОкончания

Описание атрибутной  грамматики состоит  из  раздела  описания
атрибутов  и   раздела  правил.   Раздел  описания   атрибутов
определяет состав  атрибутов для  каждого символа грамматики и
тип каждого  атрибута. Правила  состоят  из  синтаксической  и
семантической  части.   В  синтаксической  части  используется
расширенная  БНФ.   Семантическая  часть  правила  состоит  из
локальных объявлений  и  семантических  действий.  В  качестве
семантических    действий     допускаются    как    атрибутные
присваивания, так и составные операторы.
  Метка в  семантической части  правила привязывает выполнение
оператора к  обходу дерева  разбора сверху-вниз слева направо.
Конструкция "i  : оператор" означает, что оператор должен быть
выполнен сразу  после  обхода  i-й  компоненты  правой  части.
Конструкция "i  E :  оператор" означает,  что оператор  должен
быть выполнен,  только если  порождение i-й  компоненты правой
части пусто.  Конструкция  "i  A  :  оператор"  означает,  что
оператор должен быть выполнен после разбора каждого повторения
i-й  компоненты  правой  части  (имеется  в  виду  конструкция
повторения).
Каждое правило  может иметь  локальные определения  (типов и
переменных). В  формулах используются  как  атрибуты  символов
данного  правила   (локальные  атрибуты)   и  в   этом  случае
соответствующие символы  указываются номерами в правиле (0 для
символа левой части, 1 для символа правой части и т.д.), так и
атрибуты символов  предков  левой  части  правила  (глобальные
атрибуты). В  этом случае  соответствующий символ  указывается
именем  нетерминала.   Таким  образом,  на  дереве  образуются
области видимости  атрибутов: атрибут  символа  имеет  область
видимости, состоящую  из правила,  в которое  символ входит  в
правую часть,  плюс все  поддерево, корнем  которого  является
символ, за  исключением поддеревьев - потомков того же символа
в этом поддереве (рис. 5.4).

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

                         Рис. 5.4

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