5.4.7. Построение восходящих атрибутных преобразователей
Детерминированные атрибутные преобразователи могут работать не только на основе нисходящего, но и на основе восходящего метода. Особенность процедуры построения восходящих атрибутных преобразователей заключается в том, что перевод, реализуемый такими преобразователями должен быть задан в форме S-атрибутной грамматики, которая определяется следующим образом.
|
Определение.L-атрибутная грамматика в форме простого присваивания, у которой все атрибуты нетерминальных символов являются синтезируемыми атрибутами, называетсяS-атрибутной грамматикой. |
Необходимость использования только синтезируемых атрибутов вытекает из способа работы восходящего преобразователя, соответствующего построению дерева вывода в направлению от листьев к корню дерева, при котором передача наследуемых атрибутов оказывается невозможной. Свойства L-атрибутной грамматики гарантируют, что в правилах вычисления синтезируемых атрибутов нетерминала <X> не используются другие синтезируемые атрибуты этого символа, и что в правилах вычисления наследуемых атрибутов, находящихся в правых частях правил грамматики, используются только атрибуты символов, расположенных в правилах грамматики слева от символа с рассматриваемым атрибутом. В качестве примера приведем S-атрибутную грамматику, построеннуую по грамматике Г 3. 14, которая имеет вид:
Г5.7:
<E>%a <E>%b+T%c{СЛЕДУК}%d{СЛОЖИТЬ/x /y %z} !! x = b; y = c; (a, z) = d;<E>%g <T>%h !! g = h;<T>%k (<E>%l) !! k = l;<T>%n i/m !! n = m;
Эта грамматика для выражения строит последовательность атомов, атрибутами которых являются указатели на элементы памяти, хранящие значения операндов и результата.Значения указателей операндов передаются от терминалов iчерез атрибуты нетерминальных символов на выход. Указатели на элементы памяти, выделяемые для промежуточных результатов, формируются символом действия с функцией СЛЕДУК. Если задана постфиксная транслирующая грамматика в виде S-атрибутной грамматики, и если входная грамматика заданной транслирующей грамматики относится к подклассу грамматик, порождающих детерминированные языки, например, к подклассу LR(0) или SLR(1), то для нее можно построить детерминированный восходящий атрибутный преобразователь. Такой преобразователь строится путем расширения восходящего распознавателя цепочки входной грамматики. Расширение заключается в том, что каждому грамматическому вхождению в стеке выделяются дополнительные элементы памяти для хранения атрибутов. К операциям свертки добавляются действия, связанные с вычислением значений атрибутов, их записью в стек и удалением из стека, а к операциям переноса добавляются действия записи атрибутов в стек. Например, для грамматикиГ5.7операции Свертка(4) и Свертка(2) должны заключаться в замене символа, находящегося в вершине стека. При выполнении операции Свертка(3) необходимо прочитать 4 элемента из стека и сохранить значение третьего элемента, соответствующего атрибуту l, затем записать в стек символ <T> с атрибутом n, присвоить этому атрибуту значение l. Выполнение операции Свертка(1) можно описать следующим образом: 1) выполнить действие{СЛЕДУК}%dи присвоить значение атрибутаdатрибутуz, 2) прочитать из стека символ n, его атрибут, а затем присвоить значение этого атрибута атрибуту y, 3) удалить из стека один символ, 4) прочитать из стека символ и его атрибут, а затем присвоить этот атрибут атрибуту x, 5) записать в стек символ<E>с одним атрибутом и присвоить этому атрибуту значение атрибута с, 6) передать на выход атом{СЛОЖИТЬ/x /y %z}, атрибуты которого определены. Атрибутный преобразователь, построенный для грамматикиГ5.7, должен работать в соответствии с таблицами переходов и действий распознавателя (Табл. 3.4 и Табл. 3.5). Последователь ность шагов, выполняемых атрибутным преобразователем при трансля ции входной цепочки i5 + i7+- можно изобразить в следующем виде. 1. В исходном состоянии в стеке находится маркер дна, а на входе - заданная цепочка. Стек Вход Выход
h0 i/5 + i/7 |-- -
2. По таблицам 3.4 и 3.5 находим, что необходимо выполнить операцию переноса. В результате имеем: Стек Вход Выход
h0 5 i + i/7 |-- -
3. По таблицам определяем, что следует выполнить операцию Свертка(4). Получаем: . Стек Вход Выход
h0 5 T2 + i/7 |-- -
4. Следующей должна выполняться операция Свертка(2). Стек Вход Выход
h0 5 Ex + i/7 |-- -
5. После выполнения операции переноса имеем: Стек Вход Выход
h0 5 Ex + i/7 |-- -
6. Выполняя операцию переноса в стек символа i с атрибутом получаем: . Стек Вход Выход
h0 5 Ex + 7 i |-- -
7. Согласно таблицам очередной операцией должна быть Свертка(4), после выполнения которой имеем: Стек Вход Выход
h0 5 Ex + 7 T1 |-- -
8. По таблицам находим, что следующей должна выполняться операция Свертка(1), поэтому, полагая, что функция СЛЕДУК возвращает значение 22, имеем: . Стек Вход Выход
h0 22 Ex |-- {СЛОЖ/5/7/22}
9. Входной символ, находящийся в вершине стека в соответствии с таблицами работы определяет выполнение операции Допустить, которая говорит об успешном завершении работы преобразователя.
5.5. Резюме.
Атрибутные грамматики отличаются от транслирующих грамматик тем, что терминальные, нетерминальные и операционные символы могут иметь атрибуты, которые могут быть синтезируемыми или наследуемыми, и каждому правилу грамматики приписываются правила вычисления атрибутов.
Построение выводов с помощью правил АТ-грамматик совмещается с вычислением значений атрибутов. Такие вычисления для синтезируемых атрибутов не всегда оказывается возможным выполнить при подстановке правой части правила, поэтому при выводе приходится сохранять те выражения, которые нельзя вычислить до момента определения значений, входящих в них величин.
Построить преобразователь, реализующий перевод, определяемый АТ-грамматикой, оказывается возможным не для любой АТ-грамматики, а только такой, для которой выполняются требования L-атрибутных грамматик, и которая представлена в форме простого присваивания. Грамматика относится к классу L-атрибутных грамматик, если наследуемые атрибуты правых частей правил грамматики вычисляются по наследуемым атрибутам левой части или по атрибутам правой части, расположенным левее данного, и если синтезируемые атрибуты символов действия вычисляются по их наследуемым атрибутам.
АТ-грамматика находится в форме простого присваивания, если каждое правило вычисления атрибутов представляет собой оператор присваивания с идентификатором или константой в правой части. АТ-грамматику можно преобразовать к форме простого присваивания путем замены функций, используемых в правых частях правил вычисления значений атрибутов, операционными символами, и включения этих символов в правила грамматики.Нисходящий АП-преобразователь в процессе работы строит левый вывод входной цепочки в магазине, записывая в него атрибуты вместе с символами, образующими правила транслирующей грамматики. Если значения атрибутов при записи в магазин не определены, то вместо их значений записываются указатели на элементы магазина, в которых должны находиться эти значения или из которых нужно взять эти значения.Чтобы указатели не зависели от положения вершины магазина, необходимо использовать в качестве значения указателя смещение относительно рассматриваемого атрибута.Запись значений атрибутов и установка указателей совмещается с записью в магазин правой части правила. При этом все действия, связанные с построением фрагмента магазина, соответствующего правой части правила грамматики, могут быть определены заранее на этапе проектирования преобразователя и оформлены в виде инструкции, которая должна быть связана с командой преобразователя, выполняющей запись правой части правила в магазин.В каждом такте преобразователь читает символ, находящийся в вершине магазина, и в зависимости от вида символа выполняет действия, предписываемые правилами работы и командами преобразователя.Если задана LАТ- грамматика в форме простого пприсваивания, то построение преобразователя заключается в выделении из заданной грамматики соответствующей ей транслирующей грамматики, построении команд преобразователя для этой транслирующей грамматики, построении инструкций, описывающих выделение фрагментов магазина для правых частей правил LАТ-грамматики, и связывании инструкций с командами преобразователя. Для построения детерминированного нисходящего АТ-преобразователя необходимо, чтобы входная грамматика транслирующей грамматики, лежащей в основе заданной LАТ-грамматики, принадлежала классу LL(1) -грамматик.Восходящий АП-преобразователь выполняет перевод, задаваемый S-атрибутной грамматикой. Он выполняет переходы и действия, предписываемые таблицами перехода восходящего распознавателя. Таблицы распознавателя строятся по входной грамматике, которая получается из заданной S-атрибутной грамматики.Если входная грамматика принадлежит к классу LR(0) или SLR(1), то для заданной грамматики можно построить детерминированный АП-преобразователь. Такой преобразователь использует расширенные операции свертки и переноса, учитывающие необходимость работы с атрибутами.