А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 87
Текст из файла (страница 87)
Таким образом, при свертке г в М Ал находится непосредственно под ннм, откуда и может быть считано. Значение ЛХ.а, находящееся в стеке слева вместе с ЛХ, в действительности представляет собой В.г' и находится ниже, сразу за тем местом, где позже будет выполнена свертка в В. П Пример 5.26. Давайте превратим СУТ на рис. 5.28 в СУТ, которая может использоваться при ЬК-синтаксическом анализе переделанной грамматики. Введем маркер М перед С и маркер Ж перед Яп так что лежащая в основе СУТ грамматика принимает вид  — чййе (М С) Ж 51 М вЂ” ~ е 437 5.5.
Реализация !.-атрибутных СУО Перед тем как рассмотреть действия, связанные с маркерами М и Х, сформули- руем "гипотезу индукции" о том, где хранятся атрибуты. 1. Ниже всего тела иЫ!е-продукции — т.е. ниже ткЫ!е в стеке — находится наследуемый атрибут Ялехл Мы можем не знать, какой нетерминал или состояние синтаксического анализатора связано с этой записью в стеке, но мы можем быть уверены, что в фиксированной позиции этой записи имеется поле, хранящее клех! до того, как мы начнем распознавать, что же именно порождено этим Я.
2. Наследуемые атрибуты Слгие и С~а!хе находятся в стеке в записи, расположенной непосредственно под записью для С. Поскольку предполагается, что грамматика принадлежит классу !.1., наличие тгЫ!е во входном потоке гарантирует, что может быть распознана единственная продукция, а именно — иЫ!е-продукция, так что можно гарантировать, что М будет находиться в стеке непосредственно под С, а запись М будет содержать наследуемые атрибуты С.
3. Аналогично наследуемый атрибут Яз.лех! должен находиться в стеке непосредственно под Яы так что можно разместить этот атрибут в записи для М. 4. Синтезируемый атрибут С.соа!е будет находиться в записи для С. Как всегда, когда в качестве значения атрибута выступает длинная строка, на практике в записи хранится указатель на (объект, представляющий) строку, в то время как сама строка располагается вне стека. 5. Аналогично синтезируемый атрибут Я1 лехг находится в записи для Яи Проследим теперь за процессом синтаксического анализа конструкции вЫ!е.
Предположим, что запись, в которой хранится Ялехб находится на вершине стека, а очередной входной символ — терминал и й11е. Перенесем этот терминал в стек. Теперь определенно известно, что распознаваемая продукция представляет собой вЫ!е-продукцию, так что ).й-синтаксический анализатор может перенести ( и определить, что следующим шагом должна быть свертка г в М. Состояние стека в этот момент показано на рис. 5.36. На этом рисунке приведены также действия, связанные со сверткой в М. Здесь создаются значения Л! и Л2, которые хранятся в полях М-записи. В этой же записи располагаются поля для С.о.ие и С~а!хе. Эти атрибуты должны находиться во втором и третьем полях записи для согласованности с другими записями стека, которые могут находиться ниже С в других контекстах и также предоставлять эти атрибуты С.
Действие завершается присваиванием значений атрибугам Слгие и С.1а)зе, одному — только что сгенерированного значения Х 2, а другому — значения из записи, располагающейся ниже в стеке, в которой, как мы знаем, может быть найдено значение Ялехп 438 Глава 5. Синтаксически управляемая трансляция Вершина стека ? ~ ттваеД ~( Кол, выполняющийся при свертке в в М кнехт с( =ненрк Д2 =лен(); С.тате = с2; суада = пасв(тор — 31.пехт; Рнс. 5.36.
Стек ЬВ.-синтаксического анализа после свертки в в М Мы предполагаем, что все очередные символы входного потока корректно сворачиваются в С. Следовательно, синтезированный атрибут С.сок(е размещается в записи для С. Это изменение в стеке показано на рис. 5.37; на нем показаны также несколько записей, которые позже оказываются в стеке над записью С. Вершина стека [иы(в )'~ ( 1' н с ~>~,в д, С сот(е о оаех! Янсоне кнехт Рнс. 5.37. Стек непосредственно перед сверткой тела шййе-продукцнн в Я Продолжая распознавание конструкции твЬ11е, синтаксический анализатор должен обнаружить во входном потоке символ ), который он поместит в стек в соответствующую запись.
В этот момент синтаксический анализатор, в силу принадлежности грамматики к классу ЬЕ знающий, что он работает с конструкцией твЫ1е, выполнит свертку е в 7тт. Единственные данные, связанные с Ж, — это наследуемый атрибут Б,.пехп Заметим, что этот атрибут должен находиться в записи для Х, потому что она находится непосредственно под записью для Яп Выполняемый при свертке код вычисляет значение 5ппех( следующим образом: Ят щех( = х(асяс '1(ор — 3] .х 1: Это действие обращается к третьей записи под т"тт (которая находится в момент выполнения кода на вершине стека) и получает значение А1. Затем синтаксический анализатор выполняет свертку некоторого префикса остающегося входного потока в нетерминал Я (который мы везде указываем с индексом, как Я(, чтобы отличать его от нетерминала о в заголовке продукции).
Вычисленное при этом значение Я(.соде находится в записи стека для Яп Этот шаг приводит нас в состояние, показанное на рис. 5.37. 439 5.6. Резюме к главе 5 В этот момент синтаксический анализатор выполняет свертку всей части стека от и'Ь11е до 51 в Я. Вот код, который выполняется при этой свертке: !етрСоде =!аЬе! (! з1асфор — 41.Л! !) з(асфар — 31.соде (( 1аЬе! )! е1ас)фор — 4~ Л 2 (( з1ас)фор1 сог1е; 1ор = 1ор — 5; зГасфор1 соае = 1етрСоае; Иначе говоря, мы собираем значение Я.сос1е в переменной гетрСоде.
Это обычный код, состоящий из меток Ы и Л2, кода С и кода Яп Затем выполняется снятие со стека, так что Я оказывается в стеке на том месте, где находился терминал и Ьйе. Код Я размещается в поле соде указанной записи, где он может рассматриваться как синтезируемый атрибут Я.сос~е. Заметим, что в процессе рассмотрения нашего примера мы нигде не показывали работу с !.К-состояниями, которые также должны находиться в стеке в поле, в которое мы вносим грамматические символы. 5.5.5 Упражнения к разделу 5.5 Упражнение 5.5.1.
Реализуйте каждое из ваших СУО из упражнения 5.4.4 в виде синтаксического анализатора, работающего методом рекурсивного спуска, как это было сделано в разделе 5.5.1. Упражнение 5.5.2. Реализуйте каясдое из ваших СУО из упражнения 5.4.4 в виде синтаксического анализатора, работающего методом рекурсивного спуска, как это было сделано в разделе 5.5.2. Упражнение 5.5.3. Реализуйте каждое из ваших СУО из упражнения 5.4.4 при помощи ББ-синтаксического анализатора, как это было сделано в разделе 5.5.3, с генерацией кода "на лету". Упражнение 5.5.4.
Реализуйте каждое из ваших СУО из упражнения 5.4.4 при помощи ББ-синтаксического анализатора, как это было сделано в разделе 5.5.3, но в этом случае код (или указатель на код) хранится в стеке. Упражнение 5.5.5. Реализуйте каждое из ваших СУО из упражнения 5.4.4 при помощи 1.й-синтаксического анализатора, как это было сделано в разделе 5.5.4. Упражнение 5.5.6.
Реализуйте ваше СУО из упражнения 5.2.4 так, как это было сделано в разделе 5.5.1. Будет ли чем-то отличаться реализация в стиле раздела 5.5.2? 5.6 Резюме к главе 5 + Наследуемые и сиитезируемые атрибуты. Синтаксически управляемые определения могут использовать два типа атрибутов. Синтезируемые атрибуты в узле дерева разбора вычисляются с использованием атрибутов 440 Глава 5. Синтаксически управляемая трансляция в дочерних узлах. Наследуемый атрибут в узле вычисляется с использованием атрибутов в родительском узле и/или в узлах-братьях. + Графы зависимостей. Для данного дерева разбора и СУО мы проводим дуги между экземплярами атрибутов, связанными с каждым узлом дерева разбора, для указания того, что атрибут, на который указывает стрелка дуги, вычисляется с использованием значения атрибута, из которого выходит данная дуга. + Циклические определения.
В проблематичных СУО можно найти деревья разбора, для которых не существует порядка, в котором можно вычислить все атрибуты всех узлов. Такие деревья разбора содержат циклы в связанных с ними графах зависимостей. Выяснение, имеет ли СУО такие циклические графы зависимостей, — очень сложная задача. + Я-атрибутные определения. В б-атрибутном СУО все атрибуты синтезируемые. + Т:атрнбутные определении.
В Е-атрибутном СУО атрибуты могут быть наследуемыми или синтезируемыми. Однако наследуемые атрибуты в узле дерева разбора могут зависеть только от наследуемых атрибутов в родительском узле и от любых атрибутов в братских узлах, находящихся слева от рассмаз риваемого. + Синпшксические деревья. Каждый узел синтаксического дерева представляет конструкцию; дочерние узлы представляют значащие компоненты конструкции.
+ Реализация 3-атрибутных СУО. Б-атрибутное СУО может быть реализовано при помощи СУТ, в которой все действия находятся в конце продукций (постфиксная СУТ). Действия вычисляют синтезируемые атрибуты заголовков продукций с использованием синтезируемых атрибутов символов их тел. Если лежащая в основе грамматика принадлежит классу ьК, то такая СУТ может быть реализована в стеке ьй-синтаксического анализатора.
+ Устранение левой рекурсии из СУТ. Если СУТ содержит только побочные действия (без вычисления атрибутов), то применим стандартный алгоритм устранения левой рекурсии из грамматики, при использовании которого действия рассматриваются так, как если бы это были терминалы. При вычислении атрибутов устранение левой рекурсии возможно, если СУТ является постфнксной. 441 5.7. Список литературы к главе 5 + Реализация й-атрибутного СУО в процессе синтаксического анализа методом рекурсивного спуска. Если имеется Е-атрибутное определение на основе грамматики, к которой применим нисходящий синтаксический анализ, то для реализации трансляции можно построить синтаксический анализатор, работающий методом рекурсивного спуска без возврата. Наследуемые атрибуты становятся аргументами функций для их нетерминалов, а синтезируемые атрибуты этими функциями возвращаются.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
